考虑空重箱转换的港口集装箱甩挂运输问题研究

徐世达, 何雯晴, 靳志宏

(大连海事大学 交通运输工程学院,辽宁 大连 116026)

0 引言

集装箱作为一种高效流通的标准化运运载单元，被广泛应用在现代物流运输系统中。近年来，国内港口集装箱吞吐量呈现出逐年上升的良好态势[1]。港口内陆集装箱运输(Inland Container Transport, ICT)主要研究港口、内陆堆场和客户间的集装箱卡车运输调度问题。内陆集疏运环节的集卡运输在为客户提供门到门服务的同时面临高昂的单位运输成本，因此为了在激烈竞争的市场环境中处于有利地位，企业管理者需要在提升货运周转率的同时有效降低运输成本[2]。

随着运输装备的发展，车辆动力部分和载重部分可进行分离的甩挂运输车辆被广泛应用在港口集装箱运输实践中。Xue等[3]将此类问题定义为局部集装箱托运问题(Local Container Drayage Problem, LCDP)，并通过对比分析表明，采用甩挂运输模式能够有效降低任务等待时间和服务成本。

集装箱的重挂任务属于起止点(Origin-Destination, OD)确定性的运输需求，其运输路线固定且不可拆分的特点决定了相关研究主要集中在降低重挂任务之间牵引车空驶的衔接成本部分。马华伟等[4,5]分别采用了模拟退火算法和禁忌搜索算法对多车单挂情形的甩挂运输问题进行了研究。Song等[6]将空重箱任务相互独立的甩挂运输问题转化为一类基于DAOV图的带有时间窗约束的非对称车辆路径问题，并设计分支定价算法求解。杨珍花等[7]将上一决策期的重挂车辆转化为本决策期的空挂车辆资源，提出空挂OD不确定的空重挂车联合调度问题并采用两阶段算法求解。

受到港口堆场堆存能力以及空箱保有量等条件的限制，往往要求单个决策周期内所有运出的重集装箱必须以空集装箱的形式返还给堆场，这种空重箱状态转换的特点使得集装箱在单个决策期内同时具有空箱和重箱两种属性与运输任务。张建同等[8]基于上述研究提出了基于交换箱(Swap Body)的甩箱运输模式，决策变量中除访问顺序外还设置了集卡到达时间和集卡离开时间，设计了考虑访问序列限制的蚁群算法，但所提出的路径切割方法只适用于空、重箱任务同属一辆集卡服务的问题。Xue等[9]采用牵引车和挂车可分离的甩挂运输模式对空重箱转化问题进行了研究，建立了混合整数规划模型并采用改进的最大最小蚁群算法进行求解。

谷首更等[10]建立了整数规划模型进行求解，但对于各个运输任务都设定了时间窗并作为参数输入，当问题规模扩大时，任务间冲突的时间窗可能导致无法搜索可行解。

通过上述分析可知，现有的研究在处理港口集装箱甩挂运输的空重箱转化问题时，大多以牵引车访问顺序、到达时间和离开时间为决策变量建立混合整数规划模型进行求解，主要通过优化节点访问时间的方法来解决空重箱转化所产生的运输任务访问顺序约束。然而，当问题规模逐渐扩大时，混合整数规划问题的求解时间呈现爆炸性的指数增长。因此，本文针对此类问题提出了基于前置任务访问约束的方法，以牵引车任务序列访问顺序和安排任务数量为决策变量建立了整数规划模型，根据所建立数学模型的特点设计了基于集群选择的改进蚁群算法进行问题求解，并通过数值试验证明所提出模型和算法的有效性。

1 问题描述与相关定义

考虑空重箱转换的港口集装箱甩挂运输问题与传统的集卡运输模式以及其他甩挂运输模式相比，最主要的特点在于充分利用甩挂运输减少车辆等待时间的特点，以达到单周期内空重集装箱的状态转换以及回收的目的。为进一步阐述本文研究问题的特点，在问题描述之前首先给出如下定义：

(1)定义1:运输需求

客户节点所提出的集装箱运输需求，而不是传统甩挂运输中提出重挂运输任务。运输需求可以细分为送货人到港口重箱堆场的进港客户需求和港口重箱堆场的出港需求。每个客户节点可以具有多项不同类型的运输需求。

(2)定义2:集装箱任务

客户的每项运输需求都可以拆分为两项相互关联的集装箱任务。其中进港客户需求可拆分为送空箱任务(DE)和取重箱任务(PF)，出港客户需求可拆分为送重箱任务(DF)和取空箱任务(PE)，上述各类集装箱任务对应的牵引车运输操作如表1所示。

表1 集装箱任务的牵引车运输操作

通过表1中牵引车的运输操作可知，送箱类任务(DE, DF)的终点均为客户节点，由于装卸条件的限制通常采用甩箱又甩挂的操作模式；而取箱类任务(PF, PE)的终点为集装箱堆场，则可通过集装箱作业设备实现甩箱不甩挂操作模式。

(3)定义3：衔接任务

表示两项集装箱任务之间牵引车所需要完成的衔接任务。不同任务之间牵引车的衔接运输操作如表2所示：

(4)定义4：前置任务

结合甩挂运输的操作特点，当送箱任务完成后牵引车可独立离开并进行其他运输任务，当货物装卸完成后由其他牵引车完成取箱任务。由于装卸任务时间的限制，取箱任务的最早开始时间应为送箱任务交付时间与该集装箱拆箱任务时间的总和。综上，我们定义每项任务需求所拆分的送箱任务为取箱任务的前置任务。

结合上述定义，港口集装箱甩挂运输问题可以描述如下：在某一港口的区域范围内具有挂车中心、重箱堆场和空箱堆场三项基础设施。在该港口的内陆腹地中具有一定数量的客户节点，针对客户节点的进港需求和出港需求，牵引车需要在满足前置任务约束的情况下完成每项运输需求的空重箱运输任务，且两项运输任务可以由不同的牵引车进行服务。由于客户节点往往不具有大型集装箱吊装作业设备，因此在客户节点采用同时甩下半挂车和集装箱的“甩箱又甩挂模式”，在港口的空重箱堆场采用只甩下集装箱的“甩箱不甩挂模式”。如表2所示，牵引车在完成两项集装箱任务的衔接任务过程中，可能由于当前牵引车状态限制导致需要前往挂车中心完成“单独牵引车”或“牵引车+半挂车”的状态转换。

表2 衔接任务的牵引车运输操作

本问题主要解决的是所有集装箱任务在满足前置任务约束的前提下，在当前决策期内均被完成, 并最小化牵引车调用数量和衔接任务行驶距离。

3 带有前置任务访问约束的整数规划模型

3.1 模型假设

假设1牵引车只能同时拖挂一辆半挂车，车辆状态又可细分为：“牵引车+半挂车”、“牵引车+半挂车+空箱”和“牵引车+半挂车+重箱”三类。

假设2假设牵引车在不同车辆状态时速度相同，且保持恒定速度运输。

假设3不考虑集装箱、挂车、牵引车之间的设备尺寸匹配问题。

假设4挂车与空集装箱调用数量无限制。

3.2 参数设置

C:运输节点集合，C={0,1,2,…,P}，其中0表示挂车中心，1表示重箱堆场，2表示空箱堆场，3,4,…,M表示客户节点。

K:牵引车数量。

k:牵引车编号,k∈{1,2,…,K}。

R:集装箱任务集合，R=DE∪PF∪DF∪PE，其中DE表示送空箱任务集合，PF表示取重箱任务集合，DF表示送重箱任务集合，PE表示取空箱任务集合。

g(i)表示任务i的前置任务。 (i∈PE,g(i)∈DE;i∈PE,g(i)∈DF)。

CF:牵引车固定调用成本。

Cd:牵引车的单位时间运输成本。

τi:集装箱任务的执行时间，以送空箱任务(DE)为例，执行时间=提取空箱时间+运往客时间+空箱和挂车甩挂时间(i∈R)。

tij:集装箱任务i和集装箱任务j之间衔接任务所需服务时间。以送重箱任务(DF)和送空箱任务(DE)之间的衔接任务为例，衔接时间=从DF的客户点前往挂车中心时间+提取挂车时间+从挂车中心前往空箱堆场时间(i,j∈R)。

T:每辆牵引车的最长工作时间。

3.3 决策变量与衍生变量

(1)决策变量:

(1)

Nk:牵引车k所安排的运输任务数量。

Nk∈{0,1,…,|R|}

(2)

(2)衍生变量：

(3)

Ti:集装箱任务i的完成时间。

(4)

3.4 带有前置任务访问约束的整数规划模型

(1)目标函数:

(5)

模型的目标函数由两部分构成，第一部分表示牵引车调用成本，主要受牵引车调用数量影响；第二部分表示牵引车运输成本。由于集装箱任务的OD具有确定性，当所有任务都被服务时这些重挂运输任务的成本为固定值，因此第二部分的牵引车运输成本仅计算集装箱任务之间衔接任务的运输成本。模型的优化目标在于降低牵引车调用数量和衔接任务的运输距离进而使总运输成本最低。

(2)约束条件

(6)

(7)

(8)

(9)

(10)

Tg(i)≤Ti-τi,∀i∈PF,g(i)∈DE

(11)

Tg(j)≤Tj-τj,∀j∈PF,g(j)∈DE

(12)

(13)

Nk∈{0,1,2,…,|R|},∀k∈K

(14)

其中式(6)表示所有集装箱任务均被安排到不同的牵引车中；式(7)表示每个集装箱任务只安排给一辆牵引车在一次运输任务中完成；式(8)表示客户节点处任务流量守恒约束；式(9)表示每辆牵引车必须从挂车中心出发并最终返回，且调用牵引车总数量不能超过挂车中心的最大车辆数；式(10)表示牵引车工作时间限制，完成所有集装箱任务和衔接任务时间的总和不能超过牵引车最长工作时间；式(11)和式(12)表示前置任务约束，即第二阶段任务的开始时间必须大于其前置任务的完成时间；式(13)和式(14)表示变量取值约束。

4 基于集群选择的改进蚁群算法

蚁群算法(Ant Colony Optimization, ACO)最早由Dorigo等人提出，该算法的概率选择操作能够始终保证算法在可行解空间内进行迭代寻优，因此被广泛应用在车辆路径问题(Vehicle Routing Problem, VRP)及其拓展问题中[11～14]。

对于本文所研究的考虑空重箱转化的港口集装箱甩挂运输问题，每个客户点的运输需求被拆分为空箱任务和重箱任务两部分，需要对每个客户点在满足前置约束的前提下进行两次访问。同时集合甩挂运输的特点，两次运输服务可以由不同的牵引车完成。这就需要算法在解的生成过程中能够准确的表述出前置任务的完成情况，而现有蚁群算法无法有效的处理这种多路径之间相互影响的情况，因此本文提出了基于集群选择的蚁群算法(ACO with Cluster Select, CSACO)，主要对蚁群算法的编码方式和概率选择操作进行了改进。

4.1 任务时间矩阵与变维数矩阵编码

任务时间矩阵的初始阶段形式如图1所示，该矩阵是一个N×2维矩阵，第一行表示集装箱任务编号，第二行表示对应任务的最早可开始时间。为方便表述，本文将奇数列任务设为偶数列任务的前置任务。在初始阶段，奇数列任务作为前置任务可开始时间均为0，偶数列任务由于前置任务没有完成，可开始时间设为一个充分大的正数M。

图1 任务时间矩阵初始形式

当前置任务1完成后，任务时间矩阵更新形式如图2所示。任务1被牵引车选择后可开始时间立刻更新为另一个充分大的正数MM，防止单个任务被多辆牵引车选择。同时，对应的二阶段任务可开始时间更新为任务1的完成时间T1，计算方法见式(4)。

图2 任务时间矩阵更新后形式

算法的解的编码结构如图3所示，该编码由一个K×max(Nk)维矩阵构成，其中max(Nk)表示所有牵引车安排任务的最大值。由于矩阵的维数随着决策变量的变化而变化，因此称之为变维数矩阵编码。编码中元素表示集装箱任务编号，每一行包含元素个数为该辆牵引车k所安排的运输任务数量Nk。当Nk=0时，即编号为k的牵引车未被调用，该行的所有元素编码为0。

4.2 基于集群选择的概率选择操作

由于每个客户可能具有多项运输需求，即多项进港、出港的集装箱运输任务，因此在牵引车在进行路径选择时除了需要考虑任务之间衔接时间之外，还受客户点剩余任务数量的影响。客户点可以视作具有多项集装箱运输任务的任务集群，因此本文设计了基于集群选择的概率选择操作模式。首先，本文设计了节点剩余任务矩阵和车辆状态矩阵，如图3和图4所示：

节点剩余任务矩阵由一个P×4维矩阵构成，行表示客户点编号i，对应列的元素表示该客户节点不同类型运输任务的剩余量Taski。设cj表示任务j所对应的客户节点，则Taski=|{j|cj=i}|。在初始阶段，PF和PE作为二阶段任务数量为0。随着牵引车运输路线的安排，DE和DF类型任务完成后，会在PF和PE类型列中更新剩余任务数量。

图3 节点剩余任务矩阵

车辆状态矩阵由一个k维数组构成，表示各辆牵引车完成最后一个集装箱运输任务后的车辆状态。矩阵内元素由0-1元素构成。其中0表示“单独牵引车”状态，元素1表示“牵引车+半挂车”状态。

结合上述的节点剩余任务矩阵和车辆状态矩阵，牵引车路径第n次决策的基于集群选择的概率选择操作可以描述如下：

Step1对于当前牵引车k运输路径的最后一个集装箱任务节点i,计算该任务对应客户节点c(i)到剩余任务矩阵中有需求的客户节点的行驶时间。

Step2根据任务时间矩阵，判断各个有需求客户节点所包含集装箱任务是否可行。若任务可行，则将该任务放在可行集合J(n)中。

任务可行性根据任务可开始时间和添加该任务后是否超过牵引车最长工作时间进行判断。

由于一个客户节点可能存在多项进港、出港任务，因此一个客户点可能会在可行集合中添加多项任务。

Step3遍历结束后生成可行集合J(n)。若J(n)=Ø，则对应以下两种情况：1)所有集装箱任务均被完成；2)当前牵引车剩余可服务时间不足以完成任何一项运输任务。此时把挂车中心0加入到路径中，此辆牵引车路径搜索结束。若J(n)≠0，进行节点选择操作。

Step4计算集装箱任务节点i到可行集合J(n)中所有集装箱任务的转移概率，如式(15)所示:

(15)

(16)

(17)

式(15)表示第n次决策时，牵引车k的下一集装箱任务为j的转移概率。主要受轨迹强度τ(i,j)、能见度η(i,j)和倾向任务数ω(i,j)影响。

轨迹强度τ(i,j)受蚁群信息素浓度影响，更新函数为τn+1(i,j)=ρτn(i,j)+Δτ(i,j)。

式(16)表示能见度系数，由任务所在集群的客户节点间距离表示，其中d[g(i),g(j)]表示集装箱任务i所在客户节点g(i)和集装箱任务j所在客户节点g(j)之间的运输距离。

式(17)表示倾向任务数，即任务j所在客户节点在牵引车当前车辆状态更倾向选择服务的任务数量。其中φ(k)=0表示车辆状态为“单独牵引车”，为了避免返回挂车中心切换车辆状态，倾向任务为PE和PF类型集装箱任务。PE(j)和PF(j)分别表示任务j所在节点剩余取空箱任务数和取重箱任务数；φ(k)=1表示车辆状态为“牵引车+半挂车，倾向任务类型为DE和DF。DF(j)和DF(j)分别表示任务j所在节点剩余送空箱任务数和送重箱任务数。

Step6根据集装箱任务的选择情况对任务时间矩阵、节点剩余任务矩阵、车辆状态矩阵等相关任务信息进行更新。

5 仿真实验与结果分析

为了进一步证明本文基于前置任务访问约束所建立的整数规划模型的有效性，在此与文献10[10]中任务时间作为参数的整数规划模型和文献9[9]中任务时间作为决策变量的混合整数规划模型在最优解、求解时间等方面进行对比分析。同时，将本文所提出的基于集群选择的蚁群算法与其他优化算法进行求解效率和稳定性方面的对比分析。

5.1 算例1:整数规划模型与混合整数规划模型对比分析

本部分的算例采用CPLEX商用求解软件(version 12.9)在英特尔酷睿i5处理器(2.5GHz)、4.0GB内存、64位Windows 10操作系统的个人计算机上运行，对三个数学模型在不同客户点数量、不同算例规模的算例中采用相同的运算环境进行求解分析，对比结果如表3所示。表中任务时间作为参数的数学模型是以牵引车各阶段任务的访问情况作为决策变量，任务时间作为决策变量的数学模型则是采用任务之间衔接情况和任务开始时间作为决策变量，建立一个混合整数规划模型求解。

在小规模算例中，三个数学模型均能够在可接受的时间内求得问题的最优解。随着问题规模的扩大，由于不同客户需求的时间窗冲突的可能性增加，只能够通过牵引车绕行或增加牵引车数量的方式满足所有客户需求。在精确解求解时间方面，在本文提出的基于前置访问约束整数规划模型中，虽然前置访问约束使得模型中的约束条件数量大于上述模型，但由于除任务数量变量Nk之外其他决策变量均为0-1变量，没有明显的增加模型的求解时间。通过对求解时间的对比分析，本文提出的模型在不同算例中平均节约28%的运算时间。

因此，本文所提出的基于前置任务约束的整数规划模型能够对此类问题进行准确的表达，同时在精确解的求解时间方面优于现有的混合整数规划模型。

表3 整数规划模型与混合整数规划模型求解对比分析

5.2 算例2:算法性能分析

为了进一步分析本文所提出的基于集群选择的改进蚁群算法(CSACO)的求解效率和有效性，在相同规模的数值算例中，分别与CPLEX和遗传算法(GA)的求解结果进行对比分析，如表4所示。由于CPLEX在求解大规模算例时难以在可接受时间范围内获得问题的最优解，因此对于30规模以上的数值算例，表中CPLEX的最优解为5小时内算法搜索的最优解下界。

通过对表4中的数据对比分析可知，在小规模算例中遗传算法与本文所提出的CSACO算法均能够搜索到问题的最优解，并且算法运行时间明显低于商用求解器CPLEX的计算耗时。随着问题规模的扩大，GA算法虽然在运行时间方面优于CSACO算法，但对最优解的搜索能力较弱，同时算法稳定性较差。这是由于CSACO算法利用了蚁群算法的特点，通过概率选择操作生成的解的方式能够保证算法始终在可行解空间内进行迭代寻优。同时，本文通过添加任务时间矩阵、剩余任务矩阵以及转移概率中的牵引车倾向任务数w(k,j)的方式，避免大量不可行解计算的同时加速了算法的迭代。

表4 算法性能分析

因此，基于集群算法操作的改进蚁群算法(CSACO)可以在较快的时间中以良好的稳定性求得此类问题的最优解。

6 结论

本文针对港口集装箱甩挂运输问题开展了相关研究，结合甩挂运输的特点在不同运输节点处分别采用甩箱不甩挂和甩箱又甩挂的操作模式。同时，通过甩挂运输实现了单个决策周期内集装箱空重状态的转化以及回收问题，提出带有前置任务访问约束的整数规划模型。通过构造牵引车最大任务数量以及衔接任务内容两个决策变量，避免了数学模型中出现非整数决策变量，进而提升了精确解的搜索时间和求解规模。同时，结合问题的特点设计了基于集群选择的改进蚁群算法，通过引入节点剩余任务矩阵的方式提收敛性以及搜索速度。数值试验结果表明，本文所提出的蚁群算法能够在较短的时间内以良好的稳定性获得更好的最优解。

针对文中所提到的取空箱任务(PE)，本文的研究采用的运输策略是统一运回空箱堆场进行调度，而在实际作业中，由重箱转化的空箱亦可作为一种资源在客户点之间流动。考虑客户点间空箱流动的空重箱联合调运问题将在后续研究中展开，由于前置任务约束的特点，第一阶段任务完成时间的不确定导致第二阶段任务的开始时间和起始点不能在决策期开始前确定，因此可归结为一类OD流完全不确定的空箱调运问题。需要对数学模型和算法进行进一步的优化。