集装箱甩挂运输车辆调度优化模型的三阶段启发式算法

杨光敏　曹馨湖 杨珍花 靳志宏

摘要：

为完善解决轴辐式网络下的集装箱甩挂运输调度问题，针对轴辐式甩挂运输网络中的不同任务类型，考虑挂车中心数量、位置及任务时间窗，构建甩挂运输车辆调度优化数学模型；设计基于任务紧迫度函数、惩罚函数和距离函数的三阶段启发式算法，分别调度紧急任务、普通任务和超期任务.通过对经典算例求解，分别针对牵引车、挂车、挂车中心和紧急任务等数量的变化等进行敏感性分析，显示不同因素变化对整体调度方案的影响.该方法可为甩挂运输企业调度决策者提供相关的决策支持.

关键词：

甩挂运输； 轴辐式网络； 挂车中心； 时间窗； 启发式算法

中图分类号： U169.71；U492.22

文献标志码： A

0 引 言

轴辐式网络是道路运输的常见形式，胡志华等[1]对该物流网络进行过枢纽重配置优化研究.甩挂运输集汽车列车运输与装卸甩挂作业技术于一体，是一种集约、高效的运输组织模式.常见的甩挂模式有：一线两点，两端甩挂；循环甩挂；一线多点，沿途甩挂；多线一点，轮流拖带[2].

现有文献中有关带有挂车的车辆路径问题（Vehicle Routing Problem， VRP）的研究主要分为两类.一类问题可以被描述为：一辆货车配备一辆或者若干辆可以与之接挂或分离的挂车组成汽车列车.针对这类问题展开的研究主要有：SEMET等[3]首次讨论了“公路列车”（拖带一辆或多辆挂车的货车）的VRP；GERDESSEN[4]提出了VRPT（Vehicle Routing Problem with Trailers）的两种现实情境；CHAO[5]将带有挂车的VRP定义为TTRP（Truck and Trailer Routing Problem），并首次为该问题建立数学模型而不是描述性模型；SCHEUERER[6]、LIN等[79]和VILLEGAS等[1011]分别设计启发式算法、模拟退火算法和超启发式算法求解TTRP；DERIGS等[12]对TTRP的变形问题进行研究；胡志华[13]为该问题建立子回路分割模型.

另一类问题则是对目前国内所推广的“甩挂运输”的研究.该类问题与前述问题的区别在于：（1）甩挂运输问题中牵引车仅提供动力部分，没有装货的空间，而前述问题中的货车车头既是动力引擎又提供装货空间；（2）与前述问题拖挂分离的目的不同，甩挂运输中拖挂分离的目的是为了提高牵引车的利用率.虽然两类问题都存在其现实意义与研究价值，但是本文的研究内容主要集中在对第二类问题即甩挂运输问题的研究.

在甩挂运输相关文献中，HALL等[14]运用基于预测路径生产率的控制规则判断在循环甩挂中何时释放牵引车.SMILOWITZ[15]运用嵌入列生成的分支定界法对带有柔性任务的多资源路径规划问题进行求解.FRANCIS等[16]对SMILOWITZ[15]的模型及算法进行了改进，得到了更好的解.ZHANG等[17]对同一问题[1516]进行动态调度研究，运用两阶段算法对问题进行求解，目标是使运输成本最小.TAN等[18]在LEE等[19]模型的基础上加入挂车约束，首次建立了甩挂运输问题的数学模型，运用混合多目标进化算法得到问题的帕累托最优解.胡志华等[20]研究集装箱集散环境下空重箱循环甩挂的调度问题，建立混合整数规划模型，运用两阶段优化方法求解该问题.继而，胡志华[21]将该方法应用于集装箱码头间互拖的集卡甩挂运输调度问题.LI等[22]研究单车场牵引车与半挂车路径问题（tractor and semitrailer routing problem），运用启发式算法得到牵引车数量和每辆牵引车的路径，但文章缺乏对该问题的数学建模.袁野等[23]对单一客户点甩挂运输的建模进行了分析.

分析文献可以看出，现有文献集中在对循环甩挂和多线一点、轮流拖带这两种甩挂模式的研究上.在问题描述方面，对多线一点、轮流拖带的轴辐式网络结构缺乏明确的定义.在建模方面，对甩挂运输问题的数学建模，尤其是针对不同甩挂运输模式的特色建模，还处于研究初期，需要进一步完善.在算法方面，除文献[1517]运用分支定界法对问题进行求解外，其余文献主要集中在启发式算法上.本文基于已有的研究成果，运用启发式算法求解轴辐式网络下的集装箱甩挂运输调度问题，对该种模式的问题提取和模型建立进行深入研究.

本文对轴辐式网络下的集装箱整箱运输牵引车调度问题进行研究，研究贡献集中在：（1）对轴辐式集装箱甩挂运输的网络进行明确的定义及阐述；（2）提出三阶段启发式算法迅速给出调度方案，保证甩挂企业实际应用的时效性；（3）对牵引车数量，挂车中心数量、位置，挂车数量、分布，以及紧急任务数量等重要参数进行敏感性分析，为甩挂企业经营人进行合理的资源配置提供参考.

1 问题描述

如图1所示，椭圆中的轴辐式网络由中央集散中心（或港口）与分布在周围的客户点、挂车中心（TrailerCenter，TC）和连接各点的弧构成.牵引车的路径闭合，即从集散中心出发，最终回到集散中心.

出口集装箱甩挂运输操作流程为：牵引车从集散中心出发，先到TC挂一辆空挂车，再回到集散中

心的堆场取空箱运至客户点处，并将载有空箱的挂车甩下，然后从客户点返回集散中心或者驶向下一任务的开始节点.甩下的空挂车停留在客户点处进行装箱作业.待客户点处装箱完毕后，牵引车将从客户点将重挂取回至集散中心，重箱与挂车分离，落至堆场等待干线运输.需要说明的是，为客户点送空挂的牵引车和取重挂的牵引车可以不是同一辆.进口集装箱甩挂运输操作流程则与之相反.

根据集装箱流向和客户的需求，将牵引车的任务类型分为4种：取空箱、送空箱、取重箱、送重箱.4种任务类型两两组合可以形成16种任务子序列，当某个任务子序列为两个送箱任务相连时，牵引车需要在两任务中间访问TC取空挂车；当相连任务为取箱任务时，牵引车需要访问TC还空挂车.本文根据调度的不同阶段，将任务分为紧急任务、普通任务和超期任务.紧急任务被定义为：在本规划期的牵引车路径规划完成后，企业接到的新任务或任何需要优先于其他任务完成的任务.普通任务被定义为：本规划期内不需要被优先完成的任务.超期任务被定义为：已经接受客户申请，但因公司资源条件限制，无法在本规划期内完成的任务.加入对紧急任务的处理是本文的创新点之一.

为了日常调度的实用性和时效性，启发式算法在解决VRP中被大量应用.本文采用三阶段启发式算法对问题进行求解，三阶段算法分别调度紧急任务、普通任务以及超期任务.在80个客户点、100项任务、不同资源配置下的50项实验中，该算法均能在5 s之内给出调度方案，极大地满足企业在实际调度工作中对时效性的需求.

2 数学模型

在文献[18]和[23]的基础上进行扩展，建立如下数学模型.

2.1 模型假设

一辆牵引车仅能挂一辆挂车；牵引车与挂车在各任务节点的挂/甩挂车时间已知且不变；所有挂车均载有40英尺的集装箱.

2.2 参数和变量

2.2.1 参数

G=V，D为运输网络；V=0，1，…，i，…，I为节点集合，其中节点0表示集散中心，其他节点表示客户点及TC；D为节点之间弧的集合，Dij为两节点i与j之间的路网距离；Ck为牵引车k的每千米油耗；K为牵引车总数；M为任务总数；Ma为紧急任务数；Mb为普通任务数；ma为紧急任务序号；mb为普通任务序号；

T为牵引车在规划期内能够完成的任务数上限；Tma，2为所有紧急任务的结束时间；Tmb，1为第一个普通任务的开始时间；Thpm为牵引车从紧前任务h终点到挂车中心p，再到紧后任务m起点的行驶时间；Thm为牵引车从紧前任务h终点到紧后任务m起点的行驶时间；Tm为牵引车从任务m起点到终点的行驶时间；Hm，1为任务m在起点的操作时间；Hm，2为任务m在终点的操作时间；Tk，1为牵引车k开始工作的时间；Tk，2为牵引车k结束工作的时间；TEm为任务m的最早开始执行时间；TLm为任务m的最晚开始执行时间；NSK为送空箱任务集合；NSZ为送重箱任务集合；NQK为取空箱任务集合；NQZ为取重箱任务集合.

2.2.2 决策变量

2.3 数学模型

式（1）为优化目标，即方案总成本最小；式（2）表示每个任务仅被执行一次；式（3）保证所有牵引车的任务分配有序；式（4）表示所有普通任务要在紧急任务之后被完成；式（5）～（8）表示每项任务的时间序列，其中式（5）是同一牵引车执行前后两项任务的时间递推；式（9）表示每辆牵引车的工作时间均在规划期内；式（10）保证满足任务的时间窗要求；式（11）和（12）保证每辆牵引车的路线是闭合的；式（13）～（15）表示对TC的访问约束，式（13）中当牵引车执行第一项任务时，只有涉及送挂车时才会产生访问TC取挂车的情况，执行其他任务时前后两项任务均需送挂车才会产生访问TC取挂车的情况.

3 三阶段启发式算法

设计启发式算法进行求解.根据任务的待执行紧迫程度，将其分为紧急任务、普通任务和超期任务等3种，而任务性质的划分则依赖于决策函数（紧迫度函数、惩罚函数和距离函数）.

任务的紧迫度越高，紧迫度函数值越大；任务执行方案对其时间窗违反程度越高，惩罚函数值越大；距离函数则是执行该任务所需行驶的总距离.

3.1 三阶段启发式算法总体流程

算法总体思路为优先分配紧急任务，然后分配普通任务，最后推迟或外包超期任务，具体见图2.

3.2 三阶段启发式算法具体步骤

3.2.1 分配紧急任务

紧急任务的紧迫度函数值相同，因此当同时出现多个紧急任务时，分别计算各任务的惩罚函数值后再进行分配.具体流程见图3.

3.2.2 分配普通任务

紧急任务分配结束后，以任务的紧迫程度和子序列的惩罚函数值为标准进行普通任务的分配，具体流程见图4.

3.2.3 外包或推迟超期任务

当存在超出规划期的任务时，将这些超期任务推迟至下一规划期或外包，具体见图5.

4 算例实验

通过改进文献[18]中的算例，本文分别从牵引车数量、TC数量、挂车数量和紧急任务数量这4个方面验证算法的有效性，并分析各因素对整体调度方案的影响.

轴辐式网络由一个集散中心、若干个TC以及80个客户点组成.TC和客户点的位置随机分布在100×100的网格上，集散中心位于网格中心.任意两点之间采用欧氏距离.另外，本文的规划期为早8：00到晚8：00（1天内）.牵引车行驶速度为60 km/h，单位挂/甩挂车时间为30 min.违反时间窗的惩罚因数a=b=1.

4.1 牵引车数量

本例共有11项实验，牵引车数量从15辆逐一变化至25辆，任务数量均为100个，TC有5个，均匀分布在网络中.每个TC的可用挂车均为6辆.

由图6可以看出，牵引车的数量能够直接影响任务的完成情况.当牵引车数量上升至19辆时，未完成的任务数下降至0，说明该系统内牵引车最低保有数量为19辆.牵引车从15辆逐渐增多，迟到惩罚成本降幅超过提前惩罚成本的涨幅；当牵引车数量超过20辆并继续增多时，提前惩罚成本大幅上升，并且覆盖了迟到惩罚成本的减少，造成总惩罚成本曲线呈“U”型.

4.2 TC数量

为研究TC的地理分布对调度方案总成本的影响，设置TC数量不同的算例，共8项实验，TC数量有1，3和5个等3种情况.TC分布方式有：TC1～TC5均匀分布，仅设TC1，仅设TC2，仅设TC3，仅设TC4，仅设TC5，设置TC1，TC3和TC5，设置TC1，TC2和TC4等8种.挂车在TC均匀分布，总数均为30辆.

由图7可以看出，TC的数量和分布方式会直接影响任务的完成情况和系统整体调度方案.总体而言，TC数量越多，分布越均匀，牵引车行驶的总里程及方案的总惩罚成本越小.当仅设置单一TC，且TC分布在1，3，4，5等4个位置时，出现了未完成任务.而当TC位于2位置时，总里程和总惩罚成本较其他算例更优，证明TC的选址也会影响经营成本.

图7 TC数量不同时的算例运算结果

4.3 挂车数量

该算例包括5组25项实验，TC数量均为1个，分布方式分别为TC1，TC2，TC3，TC4和TC5.每项实验任务数量均为100个，牵引车数量为20辆，每组实验TC的挂车数量（NT）从23辆逐渐增至27辆.

由表1可见，在各TC的挂车数量增加的过程中，当挂车数量为23辆和24辆时以及第3组和第5组中当挂车数量为25辆时，因挂车数量难以满足需要未能给出规划结果.挂车数量不仅影响经营成本，还会直接影响经营质量：挂车数量过少无法完成既定的任务，而过多又会增加公司经济负担和管理成本.

4.4 紧急任务数量

设置紧急任务数量不同的6项实验，任务数均为100个，牵引车数量均为20辆，TC可用挂车数均为30辆，5个TC均匀分配挂车，紧急任务的数量从0逐渐增长到5个.

由图8可以看出，初期随着紧急任务数量的增加，提前惩罚成本和迟到惩罚成本均逐渐下降，优先处理紧急任务可以使整体方案违反时间窗的程度降低；当紧急任务数量上升至5个时，迟到惩罚成本仍保持下降趋势，但提前惩罚成本增加，导致总惩罚成本上升幅度较大.这说明紧急任务的数量较多时，为尽快完成任务，对时间窗上限的违反程度较高.

图8 紧急任务数量不同时的算例运算结果

5 结束语

本文建立了轴辐式网络中甩挂运输车辆调度问题的模型，提出了基于启发式规则的三阶段调度算法.基于牵引车数量不同、挂车中心数量不同、可用挂车数量有限和紧急任务数量不同等4个类型的算例实验，提出了配置牵引车和挂车数量以及优化挂车中心地理位置的具体方法，并阐述了紧急任务数量对调度计划的影响.全面剖析了甩挂运输系统调度时各因素的影响，为营运者提供一定的决策借鉴.

未来的研究将考虑甩挂运输新模式下的调度优化问题，例如牵引车对开、相遇后司机折返等.

参考文献：

[1]胡志华， 洪雯婷， 胡青蜜. 轴辐式物流网络扩张的枢纽重配置优化[J]. 上海海事大学学报， 2015， 36（1）： 1924.

[2]高洪涛， 李红启. 道路甩挂运输组织理论与实践[M]. 北京： 人民交通出版社， 2010： 1819.

[3]SEMET F， TAILLARD E. Solving reallife vehicle routing problems efficiently using tabu search[J]. Annals of Operations Research， 1993， 41（4）： 469488.

[4]GERDESSEN J C. Vehicle routing problem with trailers[J]. European Journal of Operational Research， 1996， 93（1）： 135147.

[5]CHAO I M. A tabu search method for the truck and trailer routing problem[J]. Computers & Operations Research， 2002， 29（1）： 2251.

[6]SCHEUERER S. A tabu search heuristic for the truck and trailer routing problem[J]. Computers & Operations Research， 2006， 33（4）： 894909.

[7]LIN S W. Solving the truck and trailer routing problem based on a simulated annealing heuristic[J]. Computers & Operations Research， 2009， 36（5）： 16831692.

[8]LIN S W， YU V F， CHOU S Y. A note on the truck and trailer routing problem[J]. Expert Systems with Applications， 2010， 37（1）： 899903.

[9]LIN S W， YU V F， LU C C. A simulated annealing heuristic for the truck and trailer routing problem with time windows[J]. Expert Systems with Applications， 2011， 38（12）： 1524415252.

[10]VILLEGAS J G， PRINS C， PRODHON C. GRASP/VND and multistart evolutionary local search for the single truck and trailer routing problem with satellite depots[J]. Engineering Applications of Artificial Intelligence， 2010， 23（5）： 780794.

[11]VILLEGAS J G， PRINS C， PRODHON C. A GRASP with evolutionary path relinking for the truck and trailer routing problem[J]. Computers & Operations Research， 2011， 38（9）： 13191334.

[12]DERIGS U， PULLMANN M， VOGEL U. Truck and trailer routing problems， heuristics and computational experience[J]. Computers & Operations Research， 2013， 40（2）： 536546.

[13]胡志华. 基于混合进化算法的甩挂配送问题[J]. 公路交通科技， 2013， 30（5）： 147152.

[14]HALL R W， SABNANI V C. Control of vehicle dispatching on a cyclic route serving trucking terminals[J]. Transportation Research Part A： Policy and Practice， 2002， 36（3）： 257276.

[15]SMILOWITZ K. Multiresource routing with flexible tasks： an application in drayage operations[J]. IIE Transaction， 2006， 38（7）： 555568.

[16]FRANCIS P， ZHANG G， SMILOWITZ K. Improved modeling and solution methods for the multiresource routing problem[J]. European Journal of Operational Research， 2007， 180（3）： 10451059.

[17]ZHANG G， SMILOWITZ K， ERERA A. Dynamic planning for urban drayage operations[J]. Transportation Research Part E： Logistics and Transportation Review， 2011， 47（5）： 764777.

[18]TAN K C， CHEW Y H， LEE L H. A hybrid multiobjective evolutionary algorithm for solving truck and trailer vehicle routing problems[J]. European Journal of Operational Research， 2006， 172（3）： 855885.

[19]LEE L H， TAN K C， OU K. Vehicle capacity planning system： a case study on vehicle routing problem with time windows[J]. IEEE Transactions on Systems Man and Cybernetics Part A Systems and Humans， 2003， 33（2）： 169178.

[20]胡志华， 曹杨， 王云霞. 集装箱集散的空重箱循环甩挂调度方法[J]. 武汉理工大学学报， 2012， 34（10）： 6873.

[21]胡志华. 集装箱码头间互拖的集卡甩挂运输调度问题[J]. 重庆交通大学学报（自然科学版）， 2013， 32（2）： 313317.

[22]LI Hongqi， LU Yue， ZHANG Jun， et al. Solving the tractor and semitrailer routing problem based on a heuristic approach[J]. Mathematical Problems in Engineering， 2012. DOI：10.1155/2012/182584.

[23]袁野， 徐家旺， 方云龙. 集装箱甩挂运输模型与应用[J]. 沈阳航空航天大学学报， 2014， 31（1）： 9296.

（编辑 贾裙平）