基于码头集卡共享的运输任务分配优化模型

曾庆成 于婷

摘要：为提高港口集疏运效率，减少集卡空驶，提出一种基于集卡共享的任务分配方法。以最大化承运人的总利润为目标，引入补偿机制激励承运人合作，考虑进出口任务的截止时间、承运人车队大小，建立基于码头集卡共享的任务分配模型。通过优化进出口任务分配，减少集卡空驶，并设计启发式算法求解模型。分析不同情景下承运人的利润变化，并通过算例分析验证算法的有效性。结果表明：基于集卡共享的任务分配模型能够有效地对任务分配过程进行优化和控制，进而提高集卡作业效率。

关键词：
集装箱码头; 集疏运系统; 遗传算法; 集卡共享; 任务分配

中图分类号：
U169.71    文献标志码：
A

Abstract：
In order to improve the efficiency of port collecting and distributing system and decrease the unloaded distance of trucks， a task allocation method based on truck sharing is proposed. With the objective of maximizing carriers total profit， a compensation mechanism is introduced to motivate carriers to cooperate together. Considering the deadline of import and export tasks and the size of carriers fleet， a task allocation model based on truck sharing is developed. The unloaded distance of trucks is decreased by optimizing the allocation of import and export tasks. A heuristic algorithm is designed to solve the model. The carriers profit change under different conditions is analyzed， and the validity of the algorithm is verified by example analysis. Results indicate that the task allocation model based on truck sharing can effectively control and optimize the process of task allocation， and then improve the operation efficiency of trucks.

Key words：
container terminal; collecting and distributing system; genetic algorithm; truck sharing; task allocation

我国港口集装箱有80%以上通过公路集疏运，由外集卡完成进港-出港的拖运作业。大量的拖运作业导致高峰时段码头拥堵，这不仅会严重影响集疏运效率，降低码头运营效率，而且会加剧港区污染。此外，由于进出口运输任务不平衡，大量的集卡都是单程运输，所以集卡运输成本高，集疏运效率低。

国内外学者针对集卡调度和任务分配问题开展了大量研究。集卡的路径优化方面：曹庆奎等[1]探讨了成本对路径选择的影响，并建立了面向作业面的集卡路径成本优化模型;李广儒等[2]分析了整个码头水平作业的动态调度方案，提出一种求解集卡动态调度路径的自适应蚁群算法，进而提高集卡利用率;ZHANG等[3]研究了多个仓库和码头的集卡路径规划问题，并考虑入站满箱、入站空箱、出站满箱、出站空箱等4种集装箱运输方式以及港口的时间窗，获得了作业时间最短的集卡运输路径;STERZIK等[4]同时考虑了车辆路径和空箱使用率，并设计禁忌搜索算法得出车辆行驶时间最短的运输路径;CORDEAU等[5]在研究集卡路径优化时综合考虑了集卡的运行时间和等待时间，并通过仿真来模拟不同时刻集卡的运输路径，设计局部搜索算法进行求解;杨静蕾[6]建立了基于总行驶距离最短的集装箱码头路径规划模型，获得集卡的最优路径。集卡任务分配方面：LAI等[7]将进出口任务结合起来，假设集装箱和集卡不是分开服务的，并设计了Clarke-and-Wright算法，最大限度地降低集卡的运营成本;周林等[8]以运输成本最小为目标，分别考虑物流成本和延迟成本，建立多任务优化模型，设计了基于优先权的遗传算法;赵金楼等[9]综合研究燃料成本和作业时间对集卡运输的影响，构建基于集卡作业时间最短、燃料成本最低的任务分配模型，并用算例验证了模型的有效性;曾庆成等[10]从码头整体作业效率角度出發，建立集卡动态调度模型，并设计了Q学习算法对每辆集卡的装卸任务进行分配;NOSSACK等[11]对承运人的运输任务安排以及空箱调度进行分析，建立了集卡任务分配模型;YU等[12]研究了基于越库作业的集卡任务分配问题，以最小化作业时间为目标，求得集卡的最优任务分配方案和作业位置。为提高集卡利用率，承运人联盟与集卡联合调度得到越来越多的关注：KRAJEWSKA等[13]运用合作博弈理论研究横向合作所产生的节约成本的分配，并以最大化总节约成本为研究目标，提出一种用于多个承运人之间协作的规划方法;LI等[14]提出部分信息共享机制，解决两个承运人协作过程中的任务选择和交换问题，以最大化承运人的总利润为目标构建了两阶段混合整数规划模型;VERDONCK等[15]提出了共享配送仓库机制，该问题可以归类为选址问题，为确保合作的可持续性，需要将协作成本公平地分配给不同的参与者，通过合作博弈来分析共享仓库的好处以及不同的成本分配方式可能带来的影响;STERZIK等[16]的研究表明，在承运人之间共享空箱能够极大地节约成本，推动两家公司继续合作的机制至关重要;ZENER等[17]提出在一个物流网络下的托运人形成一个联盟，将所有货运需求整合优化分配给承运人可以大大降低运输成本，并通过合作博弈论验证了该方案的可行性;CABALLINI等[18]以节约的运输成本最多为目标，探讨了在多承运人联盟的情况下，运输任务的整合与分配，并通过启发式算法证明任务的整合与再分配能够减少集卡的空驶。

本文在已有研究基础上提出一种基于外集卡共享的任务分配方法，以最大化承运人的总利润为目标，引入补偿机制激励承运人合作，同时考虑进出口任务的截止时间和承运人车队大小，建立任务分配模型，将进口任务与出口任务进行最优组合后分配给承运人，进而提高集卡利用率，降低运输成本。

1 問题描述与建模

1.1 基于集卡共享的任务分配问题

集装箱码头集卡拖运问题可以归结为“星型”网络问题，如图1所示。图1中：中心节点1代表港口，对于进口任务节点1为起点，对于出口任务节点1则为终点;其他节点代表物流中心;实线代表进口，虚线代表出口。

传统的进出口运输过程如图2a所示。进口过程：承运人R1的集卡在港口1提一个满箱→运载满箱至物流中心2并交付→空驶返回港口1。出口过程：承运人R2的集卡在港口1提一个空箱→运载空箱至物流中心3并装货→运载满箱至港口1并交付。这种进出口策略不仅造成了大量的空驶和较高的成本，同时也加重了交通拥堵和环境问题。

共享经济背景下的进出口运输过程如图2b所示：集卡在港口1提一个满箱→运载满箱至物流中心2并交付→继续行驶至物流中心3，提一个满箱→运载满箱至港口1并交付。

与传统的进出口运输过程相比，外集卡共享运输不仅减少了集卡的空载行驶距离，而且改变了很多码头集卡单程运输的作业状态，有利于提高集卡的作业效率，进而提高集疏运效率。为此，本文构建基于集卡共享的运输任务分配优化模型，通过将进口任务与出口任务进行最优组合，减少集卡空驶，提高码头作业效率。

1.2 模型构建

构建模型的假设条件如下：（1）港口有多个承运人在此承运货物，每个承运人有一定数量同质的集卡和一些进出口运输任务，每个任务的运输距离已知;（2）所有承运人的运输任务可以共享;（3）每个承运人有统一的管理成本;（4）所有的集装箱尺寸均为20 TEU;（5）每个运输任务有一个起点、一个终点和一个截止时间;（6）每个托运人的需求均能得到满足，且有时间窗限制;（7）只有进口与出口任务可以进行组合。

模型参数定义如下：NI为进口任务的集合，ni∈NI;NE为出口任务集合，ne∈NE;N为所有进口与出口任务集合，N=NI∪NE，n∈N;R为承运人集合，r∈R;dn（n∈N）为任务n起点与终点之间的距离，km;tne为服务任务ne所需的时间，tne=dne/v+βne，其中v为集卡的行驶速度，km/h，βne为在节点拆箱和装箱的时间;δni为与任务ni相关的补偿费用;δne为与任务ne相关的补偿费用;bne为任务ne的开始时间;fni为任务ni的完成时间;hne为任务ne的截止期限;tnine为服务任务对（ni，ne）所需的总时间;fnine为任务对（ni，ne）的结束时间;[Pone，Po′ne]为任务ne在开始节点的时间窗;[Pdne，Pd′ne]为任务ne在结束节点的时间窗;εnine为把任务ni与ne组合起来时，需要行驶的距离;Cdnine为延迟成本，如果任务ne在截止期限后结束则计算延迟成本，Cdnine=cd（fnine-hne），其中cd为单位延迟成本;Nr为承运人r所拥有的任务的集合;cr为承运人r执行任务的单位成本，元/km;znr，若任务n由承运人r执行，则znr=1，否则znr=0;Sr0为承运人r独立执行其任务所获得的利润;Sr为承运人r的最终利润;Vr为承运人r可用的集卡的数量;g为承运人执行一次任务的单位收入;M为一个很大的数。

步骤6 交换变异算子。首先从1、2、3三个数中随机选择一个，1代表第一行进行变异，以此类推;接着随机产生两个变异点的位置，将对应位置的任务序列进行交换，即可生成新的染色体。

步骤7 修复算子。通过交叉和变异操作会产生很多不可行解，对不可行解的修复对提高算法的运行效率十分重要，因此构造修复步骤如下：①将初始化种群过程中生成的优质解存储到一个元胞数组G{i}中;②对交叉变异后的每个个体进行约束检验;③当检测出不可行解时，首先按照初始化种群的步骤重新生成个体，进行再检测，并设置此迭代的最大次数为3，当运行3次后依旧是不可行解时，用存储的优质解G{i}代替不可行解，进而保证种群规模不变。

步骤8 终止准则。当进化代数达到设定的最大迭代次数时，计算结束，得到最优分配方案，否则执行步骤3。

3 模拟计算与结果分析

3.1 基于集卡共享的任务分配问题

港口A有3家承运人负责30个运输任务。假设3家承运人均服务于由1个港口节点和8个物流节点构成的相同区域。表1设置了10种不同的情景，每个情景之间均存在差异。表1中：I/E表示进/出口任务数;集卡的平均行驶速度为50 km/h。

3.2 算法有效性验证

为选择合适的遗传参数，先进行多次实验，在保证解的精确性和算法运行时间最短的情况下，设定种群规模为100，最大迭代次数为200，交叉概率为0.8，变异概率为0.1。

为验证本文设计的改进的遗传算法的有效性，小规模算例采用Cplex进行求解，大规模算例采用启发式算法求解，每个算例运行5次，取平均值。表2和3分别展现了不同规模算例的求解结果。

由表2可以发现，当进出口任务数达到30个时，Cplex已经无法在短时间内求出精确解，而本文设计的遗传算法能够在很大程度上提高计算效率，并且可以在较短时间内求得高质量的解，平均Gap值只有3.31%。表3展示了本文提出的算法在求解大规模算例时的计算时间和目标函数值。由表3可以发现，程序的计算时间差别不大，即使任务数达到100个，本文提出的算法仍然可以在较短时间内求出结果，计算时间只有15.72 s。由此可见，本文设计的求解算法是有效的。

3.3 Digkstra算法初始化种群有效性分析

化种群的程序收敛速度对比  当承运人数量为3，进出口任务数为30时，计算目标函数值，验证Digkstra算法初始化种群的有效性，实验结果见图5。从图5可知：采用随机组合法生成初始种群时，适应度函数值在收敛过程中有些波动，且最优解不稳定，计算时间长达38.26 s;使用Digkstra算法的收敛速度较快，迭代次数少，适应度函数值变化范围小，且能够保持在最优解中，计算时间7.45 s，算法有效。

3.4 承运人利润对比分析

图6给出了不同情景下承运人最终利润和初始利润的对比情况，其中实线柱代表最终利润，虚线柱代表初始利润。由图6可知，承运人1所获得的利润最高，一方面是因为承运人1拥有的初始任务数最多，共享后获得的补偿多，另一方面是因为承运人1拥有较低的单位成本。对于整个联盟而言，最终利润高于初始利润，也证明共享集卡有利。

3.5 δ值分析

承运人利润的影响  为进一步分析补偿值δ对承运人利润的影响，假设每个承运人的经营成本相同，δ取值范围200～500。图7显示了δ值变化对承运人最终利润的影响。当δ>450时，至少有一个承运人的最终利润低于其初始利润，出现这种情况就表明共享集卡对该承运人是不利的，从而应该终止合作，因此δ的取值對于整个联盟至关重要。

对于一个承运人而言，在执行一次组合的任务后，所获得的收益为2gdni+dne-crdni+dne+εnine-Cdnine。如果这两个任务均是与其他承运人共享的，那么该承运人就要给任务对（ni，ne）的承运人一定的补偿，且收益2gdni+dne-crdni+dne+εnine-Cdnine一定大于或等于补偿值δni+δne。因此，各承运人可以通过上述关系得出补偿值δ大概的取值范围，并与其他承运人协商出一个恰当的值，进而保证合作的可持续性。4 结 论

本文针对拖车运输作业环节，提出一种基于外集卡共享的任务分配方法。以最大化承运人的总利润为目标，引入补偿机制激励承运人合作，同时考虑进出口任务的截止时间、承运人车队大小，建立了基于集卡共享的运输任务分配优化模型，通过将进口任务与出口任务进行最优组合，减少集卡空驶。设计了改进的遗传算法求解模型，并用实际数据对不同情景下承运人的利润进行对比分析。实验结果表明，在共享背景下每个承运人的最终利润都不低于其初始利润，表明此合作机制有效。本文构建的基于集卡共享的运输任务分配优化模型不仅能够为合作承运人带来经济优势，还可以减少拥堵和环境污染，提高集卡的作业效率。

本文没有考虑工作量均衡以及卡车司机最长的工作时间等因素，进一步研究可以考虑此类约束，进一步完善集卡调度优化模型，设计更精确的算法，使其更接近集卡运输的实际情况，具有更强的实用性。

参考文献：

[1] 曹庆奎， 赵斐. 基于遗传蚁群算法的港口集卡路径优化[J]. 系统工程理论与实践， 2013， 33（7）：
1820-1828. DOI：
10.3969/j.issn.1000-6788.2013.07.023.

[2] 李广儒， 杨大奔， 任大伟. 集卡动态调度路径优化算法[J]. 交通运输工程学报， 2012， 12（3）：
86-91.

[3] ZHANG Ruiyou， YUN Won Young， KOPFER H. Heuristic-based truck scheduling for inland container transportation[J]. OR Spectrum， 2010， 32：
787-808. DOI：
10.1007/s00291-010-0193-4.

[4] STERZIK S， KOPFER H. A tabu search heuristic for the inland container transportation problem[J]. Computers & Operations Research， 2013， 40（4）：
953-962. DOI：
10.1016/j.cor. 2012.11.015.

[5] CORDEAU J F， LEGATO P， MAZZA R M， et al. Simulation-based optimization for housekeeping in a container trans-shipment terminal[J]. Computers & Operations Research， 2015， 53：
81-95. DOI：
10.1016/j.cor.2014.08.001.

[6] 杨静蕾. 集装箱码头物流路径优化研究[J]. 水运工程， 2006（1）：
32-35. DOI：
10.3969/j.issn.1002-4972.2006.01.008.

[7] LAI M， CRAINIC T G， FRANCESCO M D， et al. An heuristic search for the routing of heterogeneous trucks with single and double container loads[J]. Transportation Research Part E， 2013， 56：
108-118. DOI：
10.1016/j.tre.2013.06.001.

[8] 周林， 王旭， 林云， 等. 面向空间分布式小批量物流供需的多任务集成调度[J]. 计算机集成制造系统， 2016， 22（3）：
822-832. DOI：
10.13196/j.cims.2016.03.027.

[9] 赵金楼， 黄金虎， 刘馨， 等. 考虑燃料成本的集装箱码头集卡路径优化[J]. 哈尔滨工程大学学报， 2017， 38（12）：
1985-1990. DOI：
10.11990/jheu.201709060.

[10] 曾庆成， 杨忠振. 集装箱码头集卡调度模型与Q学习算法[J]. 哈尔滨工程大学学报， 2008， 29（1）：
1-4. DOI：
10.3969/j.issn.1006-7043.2008.01.001.

[11] NOSSACK J， PESCH E. A truck scheduling problem arising in intermodal container transportation[J]. European Journal of Operational Research， 2013， 230：
666-680. DOI：
10.1016/j.ejor.2013.04.042.

[12] YU W， EGBELU P J. Scheduling of inbound and outbound trucks in cross docking systems with temporary storage[J]. European Journal of Operational Research， 2008， 184（1）：
377-396. DOI：
10.1016/j.ejor.2006.10.047.

[13] KRAJEWSKA M A， KOPFER H， LAPORTE G， et al. Horizontal cooperation among freight carriers：
request allocation and profit sharing[J]. Journal of the Operational Research Society， 2008， 59（11）：
1483-1491. DOI：
10.1057/palgrave.jors.2602489.

[14] LI Junsong， RONG Gang， FENG Yiping. Request selection and exchange approach for carrier collaboration based on auction of a single request[J]. Transportation Research Part E， 2015， 84：
23-39. DOI：
10.1016/j.tre.2015.09.010.

[15] VERDONCK L， BEULLENS P， CARIS A， et al. Analysis of collaborative savings and cost allocation techniques for the cooperative carrier facility location problem[J]. Journal of the Operational Research Society， 2016， 67（6）：
853-871. DOI：
10.1057/jors.2015.106.

[16] STERZIK S， KOPFER H， YUN W Y. Reducing hinterland transportation costs through container sharing[J]. Flexible Services and Manufacturing Journal， 2015， 27：
382-402. DOI：
10.1007/s10696-012-9167-y.

[17] ZENER O ， ERGUN . Allocating costs in a collaborative transportation procurement network[J]. Transportation Science， 2008， 42（2）：
146-165. DOI：
10.1287/trsc.1070.0219.

[18] CABALLINI C， SACONNE S， SAEEDNIA M. Planning truck carriers operations in a cooperative environment[J]. IFAC Proceedings Volumes， 2014， 47（3）：
5121-5126.

[19] 劉志宏， 胡永明， 施工. 特征统计算法及其在NP组合优化问题上的应用[J]. 科技导报， 2006， 24（11）：
28-30. DOI：
10.3321/j.issn：1000-7857.2006.11.009.

[20] 侯运炳， 夏兴， 闫旭. 基于矿井地理网络模型的最短路径改进算法[J]. 煤炭科学技术， 2011， 39（2）：
103-105. DOI：
10.13199/j.cst.2011.02.108.houyb.030.

（编辑 贾裙平）