单车场无时间窗甩挂运输车辆调度的启发式算法

张振华，贾淑娟，顾九春

（1.鲁东大学 交通学院，山东 烟台 264025；2.鲁东大学 土木工程学院，山东 烟台 264025）

1 引言

甩挂运输是指牵引车按照预定的运行计划，在货物装卸作业点甩下所拖的挂车，换上其他与牵引车准牵引总质量相匹配的挂车继续运行的运输组织方式[1]。甩挂集中体现了道路货运业组织化、规模化、网络化、信息化和标准化发展水平，是一种集约、高效的运输组织模式。它以有利于促进多式联运、减少牵引车数量、提高车辆利用率，从而降低能源消耗、保护环境等优点，在物流园区、港区、大型厂区等局部物流网络作业环境以及重要干线节点之间得到广泛应用，有利于促进生产与物流的协调，是建设资源节约型、环境友好型道路运输市场的有效途径。

甩挂运输的显著特点是货物装卸过程与运输过程的分离，因而可以提高牵引车的利用效率。一辆牵引车可以服务多台挂车，挂车既可以作为运输工具，也可以作为货物暂存的工具，货物装卸时间段内牵引车可以脱离去转接其他集散任务，这种牵引车与挂车的动态组合使得甩挂运输较传统的车辆调度有不同的特点。国外对卡车拖带挂车（Truck and Trailer，汽车列车）的甩挂运输车辆调度（Truck and Trailer Routing Problem，简称TTRP）研究文献较多，并提出了多种算法[2-4]，但对拖车或者牵引车拖带挂车（Tractor and Trailer）的研究工作相对有限。在所查的文献中，Juyoung Wy[5]研究了垃圾处理中心、车场和客户点之间的单挂车甩挂问题，以牵引车数量最少和牵引车空驶时间最短为目标，提出了一种混合启发式算法；Roberto Baldacci[6]将多车场、多处理中心问题作为一个图来研究，并提出一种精确算法；Juyoung Wy和A.M.Benjamin[7-8]则研究多车场的时间窗问题，提出了一种大型搜索算法；Ulrich Derigs[9]参考欧洲对工作时间的严格限制，对大型机场货物中心与其他货物中心的陆路转运甩挂问题进行了比较详细的研究。

近年来国内学者对甩挂运输也做了许多卓有成效的工作，如高洪涛、李红启[10]详细讨论了甩挂运输市场的需求分析、资源配置组织以及在山东省的应用实践；李晴[11]从车辆购置与运营固定成本效益、车辆运用效益、装卸转运与包装成本效益、运输站场成本效益、人力成本效益及其他效益六个方面，参照相关经济学理论，量化计算了甩挂运输的经济效益。但真正研究甩挂运输车辆调度的文献却十分有限，胡志华[12]研究了港口集装箱循环甩挂问题，引入虚拟任务建立了集散任务的时间优先关系网络，并在总作业时间最小化的目标下，建立了混合整数规划模型并用两阶段方法求解；温旖旎[13]将甩挂运输的车辆调度问题划分为空返和非空返两类，并为两类车辆调度问题分别建立数学模型。在两类数学模型的基础上，对已有的车辆调度求解算法进行了改进，引入贪婪算法，分别为两类模型设计了相应求解算法；范宁宁[14]针对烟台至大连滚装航线货物集疏港的现实情况，对牵引车调度问题进行了条件假设和变量设定，建立了数学模型，并用Matlab编程语言对模型进行求解；梁波[15]根据大型钢铁企业厂内存在运输车辆装卸停歇时间长、车辆利用率低、在途车辆多但运输效率低的特点，建立了厂内循环甩挂调度模型，设计了求解模型的禁忌搜索算法，并建立了绩效评价指标体系。

传统车辆调度大多以车辆或者牵引车行驶距离最短为优化目标，本文则考虑单车场甩挂运输的特点，依据牵引车空驶、牵带空挂车和牵带重挂车行驶的成本不同，定义了牵引车运行成本的概念，将其作为判别调度方案优劣的指标。研究了不同类型客户点的任务特点及部分牵引任务起点或终点不确定的单车场无时间窗车辆甩挂问题，提出了一种启发式算法进行求解，从而有别于现有文献的工作，为甩挂运输车辆调度问题提供了一种新的求解途径。

2 问题提出

国外对一拖一挂甩挂运输车辆调度方面的研究工作主要包括两个方面：大型垃圾处理运输调度问题及大型航空公司货物转运的车辆调度问题。其中第一个问题可描述为：在有大量垃圾产生的地点（如建筑工地作为客户点）放置挂车，装满后由牵引车运往垃圾处理中心，牵引车一次只能运一辆挂车，这样随着客户点位置分布、车场位置及垃圾处理中心位置及数量、有无时间窗等参数的变化，就衍生出了一系列车辆调度问题；第二个问题出于德国的大型机场货物中心与其他货物中心的陆路转运甩挂问题。

汽车列车甩挂在中国当前还难以推广，而一拖一挂甩挂则有更为现实的意义。单车场车辆甩挂调度是指这样的问题：甩挂码头的车场或者甩挂干线两端节点车场既是牵引车的存放场，也是空、重挂车的集疏场所，牵引车的任务是从车场把空、重挂车运往客户点，或者把空、重挂车从客户点运往车场，或者将空挂车从某一客户点运往另一客户点。这样并非全部任务的起点和终点都为固定，即若某客户需求一辆空挂车，则该辆空挂车既可以从车场运入，也可以从其他有多余空挂车的客户点运入；同样，若某客户点有空挂车需要运出，则既可以运往车场也可以运往其他有需要的客户点。

设牵引车为同一类型，即牵引车可以与任何挂车匹配。牵引任务可以分为四种类型：

（1）车场重车运出任务。即下船后（或者外部运入）的载货挂车暂存于车场，需要运往目的客户，任务特点是有确定的起点和终点。

（2）客户点重车运出需求。客户点有一满载挂车需要运往车场以备装船或者暂存，其特点也是有确定的起点和终点。如果该客户点没有其他运入任务，则牵引车需要空驶到该客户点执行任务。

（3）客户点空车运入需求。客户点需要一辆空挂车装货，该挂车来源可以是其他客户点卸货后的挂车，也可以来自车场，所以该类型任务的特点是起点不确定。

（4）客户点空车运出需求。客户卸车后不再需要空挂车，需要运出，可以运往其他客户需求点，也可以运往车场，所以该类型任务的特点是终点不确定。

其他类型如客户点运入一辆重挂车并有一辆重挂车运出（重入重出）、运入一辆重挂车并有一辆空挂车运出（重入空出）、需求一辆空挂车并有一辆重挂车运出（空入重出）等可以视为该客户有两项任务。

定义1 任务链Li：指牵引车ci一个班次执行的任务序列，如L4=l3-l5-l12-l7-l14表示牵引车c4在一个班次内执行的各任务次序，其中虚拟任务包含于各任务中。

定义2 虚拟任务：牵引车为执行某一任务必须空驶一段距离，称为虚拟任务。

定义3 运行成本：由于牵引车空驶、带空挂车行驶和带重挂车行驶所产生的油耗及车辆磨损不同，因此在车辆平均行驶时间的基础上乘以一个区别不同行驶类型的系数即为运行成本，作为调运方案优劣的判别指标。牵引车i一个任务链的运行成本用Ci表示。

定义4 链内交叉：交换任务链Li内两任务的执行顺序，如l3-l5-l12-l7-l14→l3-l7-l12-l5-l14。链内交叉可能引起Ci变化，若减小，则交叉有效，更新相应的Li和Ci。

定义5 链间交叉：两条链各取一项任务交叉，如：

检验两条链运行成本之和的变化量，若减小，则交叉有效，更新相应两条链的Li和Ci。

3 算法设计

设牵引车和挂车均为甩挂公司所有，若某客户点有空挂车运出，则可以运往任何需要的客户点或车场；若某客户点需要空挂车，则可将任何节点包括车场的空闲挂车运入；所有的运输任务在开始时都已经确定；班次开始时所有牵引车和多余空挂车均存放于车场，班次结束时牵引车需要回到车场。

3.1 参数设定

B：行驶时间矩阵，即参考各节点（含车场）间的距离矩阵，忽略空、重车行驶速度差别及甩挂和上挂时间，换算为相应的平均行驶时间矩阵，元素为buv；

m：牵引车数量，牵引车i用ci表示；

lj'=1,2,3,4：表示任务的类型，任务类型1、2的起点和终点为已知，任务类型3的终点已知起点待定，任务类型4的起点已知，终点待定；

si：牵引车i的位置参数，位于车场或客户点位置，是一个动态变量；

Si：牵引车i一个班次经过的所有节点顺序序列，起点和终点都是车场；

ti：牵引车i的总运行时间，应有ti≤Tmax，即一个班次牵引车的总运行时间应该不大于某一预先设定的值；

3.2 初始调运方案

初始调运方案即安排初始任务链，其做法是一次取一辆牵引车，从所有任务中选出起点距牵引车当前位置最近的任务加入该牵引车的任务链。其中任务类型3的起点应包含所有任务类型4和车场。若牵引任务是空挂车，则其目的地为任务类型3的终点或车场中最近者。任务链的约束是牵引车必须在班次结束时间回到车场，因此当任务链不能再加入新任务时，取下一辆牵引车开始新的任务链，见算法1。

算法1：初始方案

｛lj''=0 (j=1,2,...,n)/给所有任务状态变量附初值0/

ti=0,Li=ϕ,Si=1,si=1(i=1,2,···,m)/给所有牵引车附初值空集/

for i=1,2,···,m/牵引车中循环/

If lj''=1(j=1,2,···,n)终止运算，输出 Li,Si，ti,Ci(i=1,2,···,m')/如果所有的任务已经执行，则终止运算，输出结果，其中m'为任务链数量/

否则在lj''=0的任务中循环直到没有任务可以加入Li

将任务lj给牵引车ci执行，更新任务的状态变量以及牵引车位置、位置序列和总运行时间/｝

在初始方案中，牵引车的下一任务始终按就近选择，这在一定程度上保证了初始方案的可接受性，但却不能保证所有牵引车的总行驶成本是否有进一步降低的可能。由于牵引车空驶以及牵带空挂车和重挂车行驶的运行成本不同，因此必须对初始方案进行优化，目标为保证所有牵引车总运行成本尽量低。

3.3 链内优化

链内优化即为链内交叉。随机交换任务链中两项任务的执行顺序，检验牵引车运行成本的变化，如果使运行成本降低，则交换有效，更新任务链。

算法2：链内交叉

｛设任务链Li中有qi个任务，最大迭代次数g1

产生随机数e∈[1,qi]，f∈[1,qi]

假设交换任务链中第e个和第f个任务，计算Ci和ti

交换有效，更新 Li,Si，Ci，

输出 Li,Si，Ci(i=1,2···m')｝

3.4 全局优化

全局优化包括三方面内容：其一是任务链合并，检验是否可减少任务链或牵引车数量，其二是空车调运优化，即随机交换任务类型3的起点或者任务类型4的终点；其三是链间交叉，随机交换任意选取的两条链上的两项任务，检验两条任务链运行成本的变化，见算法3。

算法3：全局优化

｛/牵引车数量优化/

调用算法2，链内优化；

对每一条任务链中每一项任务，试探性插入其他任务链逐个位置，若插入后该任务链运行时间不超过Tmax，则插入有效；

更新所有任务链，更新后任务链重新编号，设数量m''；

调用算法3，对新任务链进行链内优化；

以下为迭代算法，设最大迭代次数g2

/空车调运交叉/

S3为任务类型3的终点集合，S4为任务类型3的起点及车场集合

S3中随机选出 e3'，S4中随机选出 s4'，配对e3'与 s4'，若配对所涉及的两条任务链运行时间均不超过Tmax且运行成本之和减小，则交换有效，更新相应两条链的L和S。

/链间交叉/

产生随机数z1∈[1,m'']，z2∈[1,m'']

假设交换任务链Lz1中第项和Lz2中第项

4 仿真算例

设有9个客户点（编号2-10）和车场（编号1）共计10个节点，16项任务，10辆牵引车，，Tmax=480 min，g1=100，g2=500，节点间平均行驶时间（min）矩阵及计算过程见表1-表5。

表2 各项任务的类型和起点终点

表3 空车调运初始方案

表4 任务链初始方案

表5 最终调运方案

从计算过程和结果看出，由于考虑了就近原则，初始方案运行成本比较满意。经过算法优化后，牵引车数量减少1辆，任务链变化较大且运行成本降低较明显，从而验证了算法的有效性和可行性。

5 结束语

单车场甩挂运输的主要特点是重车运输只能在车场与客户点之间进行，而空挂车则可以就近方便配置，同时车场既作为车辆的存放场所，也是每个班次的交接班场所，牵引车一个班次的开始和结束均在车场。文中将任务类型分为四种，是为了突出这种运输类型的特点。虽然仿真算例中按就近原则给出的初始方案可行性较高，且经过优化计算后的调度方案效果进一步提高，但初始方案和优化算法中仍有进一步改进的余地。

现有文献对甩挂运输车辆调度方案优劣的判别标准是牵引车行驶路线最短，且所有牵引任务的起点和终点均固定。本文考虑到牵引车在不同载重状态下包括油耗、磨损在内的成本显然不同，因此定义了牵引车运行成本作为评判调度方案的准则。另外，空挂车需求任务的起点和多余空挂车运出任务的终点都未必是车场，使得这种车辆调度计算的复杂性增加。

[1]孙辉泰,贺亦军.甩挂运输是我国发展绿色货运的必然选择[J].物流科技,2012,(1):107-108.

[2]Gerdessen J C.Vchicle Routing Problem with Trailers[J].European Journal of Operational Research,1996,93(1):135-147.

[3]Scheuerer S.A Tabu Search Heuristic for the Truck and Trailer Routing Problem[J].Computers and Operations Research,2006,33(4):894-909.

[4]Lin S W,Yu V F,Chou S Y.Solving the Truck and Trailer Routing Problem Based on a Simulated Annealing Heuristic[J].Computers and Operations Research,2009,36(5):1683-1692.

[5]Juyoung Wy,Byung-InKim.A hybrid Metaheuristic Approach for the Rollon rolloff Vehicle Routing Problem[J].Computers and Operations Research,2013,40:1947-1952.

[6]Roberto Baldacci,Lawrence Bodin,Aristide Mingozzi.The Multiple Disposal Facilities and Multiple Inventory Locations Rollon-rolloff Vehicle Routing Problem[J].Computers and Operations Research,2006,33:2667-2702.

[7]Juyoung Wy,Byung-In Kim,Seongbae Kim.The Rollon-rolloff Waste Collection Vehicle Routing Problem with Time Windows[J].European Journal of Operational Research,2013,224:466-476.

[8]A M Benjamin,J E Beasley.Metaheuristics for the Waste Collection Vehicle Routing Problem with Time Windows,Driver Rest Period and Multiple Disposal Facilities[J].Computers and Operations Research,2010,37:2270-2280.

[9]Ulrich Derigs,René Kurowsky,Ulrich Vogel.Solving a Real-worldVehicle Routing Problem with Multiple Use of Tractors and Trailers and EU-regulations for Drivers Arising in Air Cargo Road Feeder Services[J].European Journal of Operational Research,2011,213:309-319.

[10]高洪涛,李红启.道路甩挂运输组织技术及其应用实践[M].北京:中国物资出版社,2012.

[11]李晴.甩挂运输经济效益的定量计算[J].物流工程与管理,2011,33(8):19-22.

[12]胡志华,曹杨,王云霞.集装箱集散的空重箱循环甩挂调度方法[J].武汉理工大学学报,2012,34(10):68-73.

[13]温旖旎.甩挂运输的运作模式设计及其车辆调度问题研究[D].广州:华南理工大学,2012.

[14]范宁宁.烟大滚装甩挂运输牵引车调度优化研究[D].大连:大连海事大学,2012.

[15]梁波.大型钢铁企业厂内车辆循环甩挂运输模式研究[D].长沙:中南大学,2009.