甩箱模式下考虑多箱型任务组合的集卡调度优化

靳志宏，黄颖，张佳艺，徐世达

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

0 引言

在港口集装箱集散过程中，公路运输因其便捷快速且能提供门到门服务的优势，在堆场与客户间的集疏运作业中发挥重要作用。但这种运输作业距离较短、运输频率高，以及有大量往返的短途运输，不仅会加剧港区内拥堵现象，还会产生高额运输成本。因此，在不断发展港口集装箱运输业的同时，运输成本和运输资源调用的问题也引起关注。

在运输集装箱时，根据车辆是否在客户点等待集装箱装卸作业，将运输模式分为传统模式、甩挂模式及甩箱模式。在甩挂模式下，牵引车到达客户点后甩下集装箱与挂车，可继续执行其他任务，以提高车辆运输效率，降低运输成本[1]。HE 等[2]在研究港口堆场与内陆客户间的牵引车调度问题时，考虑集装箱的空重箱转化过程，并加入牵引车作业过程中的碳排放成本，以达到提高运输效率并减少环境污染的效果。彭勇等[3]针对交换箱的甩挂运输牵引车调度优化问题进行了研究。靳志宏等[4]对比了滚装甩挂新船型的运输模式与传统船型运输模式，建立滚装甩挂码头牵引车调度模型。

与甩挂模式类似，甩箱模式下集装箱通过独立支架可脱离集卡底盘独立放置在客户装卸区，更方便快速。XUE 等[5]研究甩箱模式下的集卡调度问题，证明甩箱模式能有效减少15.26%的成本，并且随着装卸时间增加，优势更加明显。SONG 等[6]的研究中，集装箱在卸载完成后产生的空箱需要送回堆场，建立混合整数规划模型并利用分支定价精确算法进行求解。张建同等[7]研究了类似情况下，基于甩箱模式的港口集卡路径优化问题，通过数值实验发现，在客户与堆场间位置较为集中时，集卡的使用数量和集卡总作业时间明显减少。

在多样化的货运市场中，集装箱尺寸繁多，并以20 ft和40 ft为主。集卡通过特殊底盘装置一次能携带两个20 ft 的集装箱或者一个40ft 的集装箱。在单个周期内，进口集装箱在卸载完成后需要以空箱的形式运回堆场，而出口集装箱需要提供空箱装载货物。对于这种空重状态转化特点，将空箱与重箱任务进行组合，能够有效缓解由于进出口贸易不对称所产生的空箱资源紧缺现象。在此背景下，ZHANG 等[8]和FUNKE 等[9]同时考虑不同箱型空箱和重箱任务的组合运输，限制运输过程中集卡携带的集装箱数量，在甩箱模式下，分别以集卡的总行驶时间和距离最小化为目标，建立调度优化模型。MAHBOOBEH等[10]为研究等待模式和分离模式下车队规模不同和集装箱尺寸不同情况下的集装箱运输问题，提出了一个广义模型，并利用现实案例进行求解。

从上述分析中可以发现，现有研究将20 ft 和40 ft 的集装箱运输任务在集卡单次运输行程中进行组合时，未考虑到空重箱的转化过程和任务访问顺序，因为在设计集装箱的空重转化过程时，单次运输途中集卡的状态变化与任务的匹配过程变得难以解决。因此，本文充分结合空重箱状态转化和多箱型任务组合的特点，研究甩箱模式下的集卡调度优化问题。

1 问题描述

在港口与内陆客户组成的运输网络中，运输公司为具有不同箱型的进出口集装箱运输需求的客户点提供服务。在单周期内，所有的进出口集装箱任务具有送和取两阶段的任务特性，因此，客户的20 ft和40 ft集装箱运输需求可进一步细分，如表1所示。

表1 集装箱运输任务Table 1 Container transportation tasks

在行驶过程中，集卡在到达客户点后，进行甩箱作业，之后集装箱在客户处完成空重转化过程。为了减少由于往返堆场而产生的不必要行驶，收货人处卸载完毕的空箱可以直接送往托运人客户处。所有集装箱任务的执行操作只包含在客户点进行的甩箱和提箱过程。而在堆场以及客户之间的运输过程包含在两个集装箱任务之间的衔接任务中，衔接任务的确定需要结合集卡状态与任务需求。集装箱任务作业流程如图1所示。

图1 集装箱任务作业流程Fig.1 Container task transportation process

1 个简单的有向运输网络图G=(N,A)，其中，N={1,2,3} 为任务集合，A为衔接任务集合。当20 ft 取重箱任务1 和2 与40 ft 取重箱任务3 组合时，由于集卡执行完任务1和2后处于满载状态，因此，衔接任务(2，3)的内容为返回堆场交付当前车上集装箱，随后，前往任务3 客户处。集卡当前状态决定集卡当前任务与下个任务的衔接任务行驶距离以及衔接时间。简单的多箱型集疏运任务如图2所示。

图2 多箱型集疏运任务运输示意Fig.2 Example of multi-size container collection and distribution tasks

甩箱模式下，考虑多箱型任务组合与重空转化的集卡调度问题属于非对称旅行商问题。由于对进出口任务进行拆分，所以，每个提箱任务都有与之对应的前置送箱任务。提箱任务需要在其前置任务已经执行，并且对应的集装箱已经装卸完成之后才能开始执行，当集卡提前到达时将会产生等待时间。在行驶过程中，集卡状态的动态变化增大了问题的求解复杂性。因此，本文将在保证单周期内所有集装箱任务都被完成的情况下，考虑任务的前置任务约束以及集卡状态与不同箱型任务需求的匹配程度，以集卡启用成本、行驶以及等待过程中的成本最小化为目标建立数学模型，在考虑到集装箱的空重转化过程时，拆分港口不同箱型进出口集装箱任务，并引入前置任务约束。最后，根据模型特点设计基于不可行弧过滤策略的蚁群算法求解问题。

2 数学模型

2.1 模型假设

(1)集卡停放于车场，并在初次执行任务时由车场出发，执行完所有任务后返回车场；

(2)堆场堆存足够数量的空箱；

(3)所有客户点具备甩箱装备；

(4)集卡1 次最多能携带2 个20 ft 的集装箱或者1个40 ft的集装箱。

2.2 符号设置

(1)参数设置

K——集卡集合，K={1,…,k,…,|K|}，k∈K；

N——所有任务集合，N={0,1,…,i,…,j,…,|N|}，其中，{0}为集卡出发以及返回的虚拟任务，N1=N{0}，i,j∈N；

N1——除去虚拟任务的任务集合，N1=，其中为N1中取空箱的任务子集合，且为取20 ft空箱任务集合，为取40 ft取空箱任务集合，类似地，N1(DF)、N1(DE)、N1(PF)分别为送重箱、送空箱、取重箱的任务子集合；

S——任务集合N的子集，S⊆N；

m——集卡在港口提和交20 ft 集装箱时间，2m为集卡在港口提和交40 ft集装箱时间；

n——集卡在客户点提和交20 ft集装箱时间，2n为集卡在客户点提和交40 ft集装箱时间；

T——集卡的最大工作时间；

c1——集卡单位启用成本；

c2——集卡单位行驶成本；

c3——集卡单位等待成本；

M——充分大的正整数；

ξi——任务i中集装箱箱型，ξi={1,2}，其中，20 ft 集装箱任务对应ξi=1，40 ft 集装箱任务对应ξi=2；

ti——任务i的执行时间；

tij——任务i到任务j的行驶时间，，其中，dij为任务i、j的衔接距离，v为集卡行驶速度，∀i,j∈N1，∀k∈K；

ωi——任务i的前置任务；

pi——任务i的集装箱装卸时间。

(2)状态变量

αik——集卡执行任务i的离港剩余箱位数量，αik={0,1,2}；

βik——集卡执行任务i的当前使用箱位数量，βik={0,1,2}；

——集卡执行任务i时集卡携带20 ft空箱数量，{0,1,2}；

——集卡执行任务i时集卡携带40 ft空箱数量，{0,1}；δijk——与集卡当前状态以及任务j的需求相关，δijk={0,1}。

(3)决策变量

xijk——当集卡k连续执行任务i和j时，xijk=1，否则xijk=0；

yik——当集卡k执行任务i时，yik=1，否则yik=0；

zi——任务i的开始时间。

2.3 数学模型

(1)目标函数

目标函数由3 部分组成，第1 部分表示集卡的使用成本，与集卡的启用数量相关；第2 部分是集卡的行驶成本，包括任务衔接时的行驶成本和当任务与集卡状态不匹配时前往堆场交付所有当前车上任务时的行驶成本；第3部分是集卡提前到达任务起点时集装箱装卸未完成所产生的等待成本。模型的目的是使3部分成本总和最小化。

(2)约束条件

式(2)限制所有任务只能由一辆车提供服务。式(3)限制启用集卡数不能超过最大集卡数。式(4)表示若集卡被启用，必须执行起始任务。式(5)表示集卡不存在从一个任务出发又返回到同一个任务的情况。式(6)和式(7)限制任务被执行时一定有1辆集卡对任务进行访问并且离开。式(8)表示任务只能被集卡访问一次。式(9)是任务节点流量守恒约束。式(10)为回路消除约束。式(11)限制第一个任务的开始时间不能早于到达时间。式(12)限制集卡执行最后一个任务必须有足够的时间返回虚拟任务节点。式(13)为两个任务之间的衔接时间约束。式(14)为前置任务约束。式(15)限制任务开始时间范围。式(16)为相关决策变量取值约束。

本文研究问题中，由于集卡状态随所执行任务不断变化，需详细说明集卡执行任务过程中剩余箱位和空箱资源变化情况，集卡的初始箱位和相关参数的取值范围为

集卡每执行完1次提箱和送箱任务后，车上剩余箱位数和所携带空箱个数都会发生相应变化，从而影响δijk的取值。对于∀i∈N，∀k∈K，若j∈N1(PF)⋃N1(PE)，δijk的取值仅与当前箱位βik有关，且仅在βik≥ξj时，δijk=0。而当j∈N1(DE)时，首先，需要考虑车上所带空箱资源情况，以为例，若0，且αik≤ξj或者βik≤ξj时，δijk=1；其余情况下，δijk=0。对于∀k∈K，∀i∈N，集卡行驶过程中的箱位数变化情况为

车上携带空箱资源的变化情况为

由于本文所建立的集卡调度模型中，前置任务约束和集卡箱位的限制导致问题难以用Cplex求解器直接进行求解，因此，仅利用小规模算例对模型进行简单验证。选取任务规模以及比例为8(4-4)的算例，其中，0为出发以及返回的虚拟任务，{1，2，3，4，5，6，7，8}为任务集合，奇数任务为偶数任务的前置任务，利用Cplex 求解调度结果如图3所示。使用集卡数量为1，显示集卡调度方案为0→1→5→3→2→7→4→6→8→0，目标函数最优解为205.08，验证模型有效。

图3 求解结果Fig.3 Solve results

3 基于不可行弧过滤策略的蚁群算法

蚁群算法作为一种概率性算法对求解车辆调度问题(VRP)具有一定的优越性。然而，在较为复杂问题的求解过程中，容易出现死循环、收敛过早或者出现局部最优解的情况。在本文研究的考虑箱型组合和重空箱转化的集卡调度优化问题中，进出口任务拆分的空箱和重箱任务可以分配给不同的集卡，在此种情况下，同时考虑集卡调度和前置任务限制时，难以用传统的蚁群算法求出可行的解决方案。因此，本文设计了基于不可行弧过滤策略的蚁群算法求解问题，关键设计如下。

(1)解的编码形式

本文的解编码由1个m0×n0的变维矩阵构成，其维数随着集卡任务安排的变化而不断变化。在解编码中，m0为集卡的使用数量，n0为1辆集卡执行的最大任务数，编码中每行元素代表集卡k所执行的任务。解的编码如图4所示。

图4 解的编码Fig.4 Solution code

(2)不可行弧过滤策略

在利用蚁群算法解决集卡调度问题时，蚁群需要遍历当前所有潜在运输弧。潜在运输弧由所有可用集卡的当前已执行任务与未被访问的任务组成。在本文所研究的问题中，集卡的调度问题还需要考虑前置任务、集卡剩余箱位数及集卡最大行驶时间限制，导致潜在运输弧中存在部分明显无法满足这些限制的不可行弧。不可行弧的存在将会大大增加算法的计算复杂性和计算时间，因此，针对本文所研究问题的特点，提出一种不可行弧过滤策略，过滤准则如下：

①任务j的前置任务ωj已经被服务；

②集卡k的离港箱位满足任务j所需条件；

③加入任务j后，集卡k有足够的时间返回出发点。

同时满足上述3种条件时，潜在弧被判定为可行弧。图5给出了1组任务集合和当前任务执行情况。设定每个奇数任务为后一偶数任务的前置任务。从集卡1，2，3的末尾任务0，4，0为当前集卡任务起始节点，与未访问的任务进行衔接组成潜在弧。在未访问的任务中，仅有任务2的前置任务被访问，而集卡2 在执行完任务2 后没有足够的时间返回堆场，且当前的离港剩余容量不满足任务5所需箱位要求。不可行弧过滤策略的具体操作如图6所示。

图5 任务编码以及当前任务执行情况Fig.5 Task code and task execution

图6 不可行弧过滤Fig.6 Infeasible arc filtering strategy

(3)状态转移

在蚁群算法中，蚂蚁需要根据当前被访问节点到所有可能的下个访问节点的转移概率来选择下个任务访问节点。在过滤不可行弧之后，需要计算每条可行弧的转移概率，任务节点i到可行任务节点j的转移概率为

式中：i、j属于可行弧集；pij为蚂蚁从任务i转移到任务j的概率；ηij=1/ΔZ为能见度系数，ΔZ由集卡启用、行驶以及等待的总成本表示；τij为可行弧(i,j)上的信息素浓度；a为信息启发式因子；b为期望启发式因子。

同时，为了提高蚁群算法的搜索性能，防止陷入局部最优解，使用以下3个不同的选择策略提高算法性能。

① 精英策略，选择转移概率pij最大的弧(i,j)。

②随机策略，从可行弧中随机选择弧(i,j)。

③轮盘赌策略，每个弧的被选择概率对应于其转移概率pij。

(4)信息素更新

在蚁群算法寻优过程中，多条路径上的信息素浓度不相上下时会干扰蚂蚁的选择，影响算法的性能。最大最小蚂蚁系统(Max-Min Ant System，MMAS)能够有效避免传统蚁群算法的收敛速度和陷入局部最优的情况。MMAS 更新策略中，首先，通过加强全局最优和当前最优路径的信息素浓度，有效改善算法收敛速度；其次，对每条路径的信息素浓度设定变化的最大值和最小值，避免存在信息素浓度过高或过低而产生的局部最优解；最后，通过将信息素浓度设置成最大值，减缓路径信息素浓度的挥发。具体步骤如下：

Step 1 选择一个解。

Step 2 从解的编码中随机选取元素不都为0 的一行，按顺序提取所有非零任务序号，例如，7→1→8。

Step 3 确定集卡执行任务的子序列，例如，0→7，7→1，1→8，8→0。

Step 4 如果该蚂蚁的目标值优于当前最优解，则采用MMAS策略更新子序列的信息素(信息素更新量为Q/ΔZ。其中，ΔZ为目标函数数值，Q为信息素更新值)；否则，更新每个蚂蚁的整个子序列信息素。

Step 5 重复Step 2～Step 4，直到Step 1 中的所有集卡任务子序列信息素浓度更新。

基于上述主要环节，基于不可行弧过滤策略的蚁群算法流程如图7所示，其中，Niter为迭代次数，Aant为蚂蚁编号。

图7 基于不可行弧过滤策略的蚁群算法流程Fig.7 Flow chart of ant colony algorithm based on infeasible arc filtering strategy

4 数值试验与结果分析

4.1 算例生成和参数设置

本文基于Solomon 标准数据集随机生成任务规模数不同的算例。在算例生成过程中，对所有箱型的进出口集装箱任务进行拆分，并设定奇数任务为偶数任务的前置任务。将所有进出口任务随机分配给抽取的客户点，保证每个客户点都有任务。每个生成的任务包含有任务起点、任务终点、任务类型、前置任务、装卸时间及任务占用箱位等信息。具体算例设置如表2所示。数值实验的相关参数如表3所示。

表2 算例设置Table 2 Example settings

表3 参数设置Table 3 Parameter settings

在利用基于不可行弧过滤策略的蚁群算法求解问题时，分别将每种规模的算例独立运行10次，并记录目标函数的最小值与均值。实验过程中，当达到预设的最大迭代次数时，算法停止迭代，输出当前最优解。为了选取合适的迭代次数进行后续的实验，对前10个算例分别进行多次实验，并记录相应的最优解迭代次数，最优解的迭代次数统计情况如图8所示。

图8 最优解的迭代次数分布Fig.8 Iteration times of optimal solution

在10 个算例中，得到最优解的迭代次数在0～50、51～100 及101～200 之间的占比分别为6%，10%，21%，且集中在前期的小规模算例中，在算例规模逐步增大时，部分实验产生最优解的迭代次数增加。在所有的算例中，迭代次数在500以内的占比76%，而迭代次数在501～1000 内的占比24%。迭代次数的增加可能会使得一部分大规模算例寻得更优解，同时，也会大幅增加算法的求解时间，影响算法性能。因此，为了更好地进行后续实验，并凸显算法性能，设定算法最大迭代次数为500。

4.2 甩箱模式和传统模式实验结果对比分析

为验证甩箱模式运用在多箱型集装箱运输过程中的优越性，利用本文的算法分别求解甩箱模式和传统模式下的多箱型集装箱运输作业总成本。两种模式下的求解结果和运行时间如表4所示。甩箱模式与传统模式的总成本的结果以及甩箱模式下多次求解的最优值与均值结果如图9所示，其中，GAP1 为甩箱模式与传统模式的最优值差值，GAP1=100%×(最优值2-最优值1)/最优值2；GAP2 为甩箱模式下最优值与均值的差值，GAP2=100%×(均值-最优值1)/均值。

结合表4和图9可以发现，传统模式下，由于进出口集装箱任务拆分后的两个任务必须前后完成，减少了算法求解的复杂性，因此，在任务规模增加时，甩箱模式下的求解时间大于传统模式的求解时间。采用甩箱模式进行多箱型集装箱运输作业的集卡运输总成本远远低于传统模式下的集卡运输总成本。相比较传统模式，甩箱模式由于大幅降低了集卡在客户等待装卸的时间，总成本平均减少45.10%。甩箱模式通过减少集卡等待装卸的时间，能够大幅提高集卡的利用率，并减少等待所产生的高额等待成本。

表4 两种模式的求解结果和求解时间Table 4 Results and solving time of two modes

图9 结果比较Fig.9 Result comparison

从表4的结果进一步发现，任务规模相同，两种箱型的任务比例不同时，其对应的目标函数值存在一定差异。为研究两种箱型的任务比例对目标函数的影响，选取任务规模为32的算例，改变20 ft与40 ft集装箱任务的比例，任务比例不同的情况下算法求解的结果如图10所示。

由图10可知，随着20 ft 集装箱任务比例的增加，集卡执行任务的总成本也存在不同程度的降低。由于在多箱型集装箱运输过程中，集卡1次最多可携带1 个40 ft 的集装箱或者2 个20 ft 的集装箱，1 个集装箱对应1 个任务，因此，当20 ft 集装箱任务增多时，集卡车上1 次所携带的任务加倍，提高了集卡的利用效率，也减少了部分重复往返堆场与客户之间的行程。因此，在港口多箱型集装箱集疏运过程中，20 ft 集装箱任务占总任务比例越多，一车多箱的优势更能发挥，为企业节约更多运输成本。

图10 不同任务比例下的求解结果Fig.10 Solution results under different proportions of tasks

4.3 算法性能分析

通过图9中Gap2值的变化可知，算法多次求解最优值与均值的差距随着任务规模的增大而不断增大，其差距均值为5.21%，最大值为15.81%，证明算法在不同规模下的求解稳定性较优。算法在不同规模任务下的收敛速度如图11所示。

图11 不同规模下的收敛图Fig.11 Convergence graph at different scales

在不同任务规模下，算法均能够在较小的时间内获得较优解，证明算法具有稳定性和快速收敛性。在较大规模算例中，由于前置任务约束和不可行弧过滤策略导致问题求解难度增加，导致计算时间的增长。在任务规模大于100后，计算时间超过10 min，但仍能得到较为良好的结果。本文所提出的基于不可行弧过滤策略的蚁群算法利用不可行弧过滤策略将不可行弧提前剔除，通过概率选择操作保证算法在可行解空间中持续迭代寻优，减少了大量不可行解的计算，提升了算法的性能。因此，在求解多箱型集装箱运输问题时，本文所提出的算法能够较为稳定且快速的求解问题最优解。

5 结论

本文通过甩箱模式实现单周期内的多箱型集装箱空重转化和协调运输过程，建立集卡调度优化模型，并设计基于不可行弧过滤策略的蚁群算法求解问题。利用Solomon数据集进行算例试验，验证算法具有较好的稳定收敛性能。在任务规模数相同时，相较于传统模式，甩箱模式下的集卡总成本平均减少45.10%，且随着规模越大，两种模式下的总成本差距越大。另外，20 ft集装箱任务占比增加能够更好地提升集卡的利用率。将甩箱模式与一车多箱运输模式进行结合，能充分发挥两者的优势，在减少集卡空驶和降低集卡运输成本的同时，提高港口集疏运的效率。