多场站城际干线甩挂牵引车调度问题及求解＊

李红启 吕 潭

（北京航空航天大学交通科学与工程学院 北京 100191）

迄今学术界在甩挂运输汽车列车调度问题方面的研究成果主要体现为3类：（1）针对卡车与全挂车组合而成汽车列车调度的TTRP问题，研究成果以文献［1－3］等为代表；（2）针对城市垃圾运输过程的牵引车加挂半挂车组合而成汽车列车调度的RRVRP问题，研究成果以文献［4－6］等为代表；（3）针对厂内（局部）运输过程的牵引车加挂半挂车组合而成汽车列车调度问题，研究成果以文献［7－8］等为代表；以及针对城际干线运输过程的牵引车加挂半挂车组合而成汽车列车调度的TSRP问题［9］.本文定位于多场站的、城际干线运输背景下的牵引车调度这一问题，建立一类公路牵引车调度问题数学模型，设计基于遗传算法的求解算法，并辅以算例分析.

1 问题特点与数学模型

多场站的城际干线甩挂运输牵引车调度问题（multi－depot intercity line－haul tractor routing problem，MD－ILTRP）有以下基本特征：（1）“多对多”的运输需求.多个专业化场站（记数量为m）可保有大量牵引车，是牵引车运行路线的始发终到点.每个专业化场站可辐射服务若干个客户点，客户点的运输需求以载货半挂车为单位，任意2个客户点之间都可以有任意数量的运输需求.记所有客户点数量为n；（2）限定运距和开放路线.路线是开放的，且路线的运距在一个合理的范围内，允许牵引车在同一运行路线中多次进出不同的专业化场站和特定客户点.牵引车运行形式只有两种，牵引车独自行驶，牵引车拖挂载货半挂车行驶；（3）车型匹配和常量设定.牵引车和半挂车车型满足匹配性要求.设定牵引车独自行驶和拖挂载货半挂车行驶的平均速度为常量，设定牵引车独自行驶或拖挂载货半挂车行驶的百公里油耗量为常量，设定载货半挂车的额定载重量和货物实载率为常量；（4）效率型目标函数.MD－ILTRP问题的求解目标是“t·km CO2排放量”，旨在明确甩挂运输车辆调度模式的效率和节能减排效果.依据联合国政府间气候变化专门委员会提供的CO2排放量计算方法，每燃烧1L柴油排放2 730g CO2.

设定以下变量：rij为节点i到j的运输需求，为牵引车独自在节点i与j间行驶的油耗量，表示牵引车拖带载货半挂车在节点i与j间行驶的油耗量，tij为车辆在节点i与j间的行驶时间，H为所需牵引车总数，D1和D2分别为某条牵引车运行路线的运距的下限和上限.

MD－ILTRP数学模型如下.

式中：（1）为运输需求满足约束；（2）和（3）要求牵引车路线的始发终到点为场站.在多场站条件下，允许牵引车路线的始发终到点可以不是同一场站；（4）为牵引车进出场站的度平衡约束；（5）为牵引车进出客户点的度平衡约束；（6）为客户点的度平衡约束；（7）为牵引车路线的运距约束；（8）明确所需牵引车总数，「·⏋和⎿·」分别表示向上和向下取整.

2 求解算法设计

2.1 染色体编码和结构设置

MD－ILTRP问题的求解结果为由专业化场站和客户点组成的点的序列，可将一组可行解排列在一起组成一个染色体基因序列.当有m个专业化场站（1，2，…，m）以及n个客户点时，为避免将不同路线组合在一起时无法以专业化场站作为不同路线区分节点的问题，在构造染色体时添加一个虚拟节点0.染色体的形式为“0—（场站1或2或…或m）—客户点i—…—客户点j—（场站1或2或…或m）—0—（场站1或2或…或m）—客户点k—…—客户点l—（场站1或2或…或m）—0”.

2.2 初始种群

考虑到MD－ILTRP中运输需求分布于路段上的特点，本文以概率选择方式生成染色体.

1）随机选择某一专业化场站a（节点1或2或…或m）作为牵引车路线的第一个点.

2）选择不同于a的一个点b，判断a与b之间是否有运输需求.当a与b之间有运输需求时，若b为专业化场站，则以概率p1选择b；若b为客户点，以概率p2选择b；当a与b之间无运输需求时，以概率p3选择b.搜索所有可用的节点b，若都未成功选取，则随机生成b.

3）计算路线a—b—d（d为场站）的运距，当增加点c（搜索所有不同于b的点）使a—b—c—d的运距超出约束时，确定a—b—d作为一条路线；否则，以第2步的方法继续增加路线中的点.

4）搜索需求矩阵，判断是否存在非零项.若存在非零项，则通过以上三步产生新路线；若不存在非零项，则路线生成过程结束，将各条路线组合在一起并在首尾以0加以区分.

2.3 适应度函数

本文选取以下形式的适应度函数.

式中：M为足够大的正数；κ为整数；p为惩罚数.

2.4 遗传操作

2）“先破坏后重组”操作 采用“先破坏后重组”的方法进行交叉操作，具体如下：（1）搜索染色体上作为路线分隔的所有“0”点，随机选择其中的两个并将染色体从这两个点处断裂；（2）将破坏操作产生的染色体段作为新染色体的开始段，根据染色体段中的路线情况对需求矩阵进行处理，运用概率选择生成的方法产生染色体的后半段.

3）变异操作 设定一个较小的变异概率Pm；针对种群中每个染色体的任意非0且非路线两段的基因位的数值进行操作.随机生成一个［0，1］区间的浮点数p，当p＜Pm时，随机生成一个不等于该基因位原来数值且不同于前后基因位数值的点序号，代替该基因位的数值.

2.5 主要参数设置及终止条件

参照本文针对若干算例的试算经验，设定染色体的长度为运输需求总数的5～10倍，种群的大小设定为运输需求总数的2～4倍.变异操作中的Pm值设定为0.05左右.

“先破坏后重组”操作是整个算法中的关键部分，其发生概率Pd的设置至关重要.在遗传进化前期，个体的适应度一般较低，Pd取较大值可扩大搜索范围；而在进化后期，较大的Pd很可能破坏已产生的优良个体.本文采用自适应式的破坏重组概率.

式中：Pdmax与Pdmin分别为最大和最小破坏重组概率；t为当前进化代数；T为设定最大进化代数.本文以进化代数达到设定最大进化代数作为算法的终止条件.

3 算例设计及其求解

参照文献［9］提供的单场站小规模随机算例，对其中数个算例采用随机方式选取某个节点作为另一个场站，从而将这些算例改变为双场站随机算例.借助CPLEX12.4求解 MD－ILTRP问题数学模型获得算例的精确解，借助GA算法寻求算例的满意解，并同时与文献［9］提供的精确解进行对比，计算结果见表1.

表1 小规模随机算例求解结果一览

随机算例求解结果显示：（1）本文求解 MDILTRP的GA算法能够获得满意解，满意解与相应精确解之间的误差大多保持在10%以内；（2）相比于单场站情形，尽管新增设场站会导致基础设施建设投入的增加，但增加场站数量有助于降低牵引车使用量，也有助于提高运输效率（表1第3和5列对比，即第9列）；（3）算例中场站位置布局是随机的，一些特殊的场站选址明显影响着计算结果.如算例 RAND7－1，RAND7－2和 RAND8－2的计算效果不佳，而这些算例中场站多位于研究区域的边界.

4 结束语

本文针对多场站情景下的城际干线甩挂运输过程所用的公路牵引车的优化调度问题（MD－IL－TRP问题）开展研究.该问题的基本特征包括：货运需求为“多对多”式、以载货半挂车为计量单位，路线是开放的、且运距在一个合理的范围内，优化目标为货运吨公里碳排放量最小化.算例求解结果显示，本文所设计的模型与基于遗传算法的求解流程是可行和有效的；此外，多场站体系有助于减少甩挂运输车辆使用量和提高货运效率.后续研究工作可从多个角度展开，如：增加时间窗等约束而形成新的模型，寻求求解效率和效果更好的混合启发式算法，等等.

［1］CHAO I M.A tabu search method for the truck and trailer routing problem［J］.Computers ＆ Operations Research，2002，29（1）：33－51.

［2］LIN S W，YU V F，CHOU S Y.Solving the truck and trailer routing problem based on a simulated annealing heuristic［J］.Computers ＆ Operations Research，2009，36（5）：1683－1692.

［3］VILLEGAS J G，PRINS C，PRODHON C，et al.A matheuristic for the truck and trailer routing problem［J］.European Journal of Operational Research，2013，230（2）：231－244.

［4］BODIN L，MINGOZZI A，BALDACCI R，et al.The rollon－rolloff vehicle routing problem ［J］.Transportation Science，2000，34（3）：271－288.

［5］DERIGS U，PULLMANN M，VOGEL U.A short note on applying a simple LS／LNS－based metaheuristic to the rollon－rolloff vehicle routing problem ［J］.Computers ＆ Operations Research，2013，40（3）：867－872.

［6］WY J，KIM B I.A hybrid metaheuristic approach for the rollon－rolloff vehicle routing problem ［J］.Computers ＆ Operations Research，2013，40（8）：1947－1952.

［7］梁 波.大型钢铁企业厂内车辆循环甩挂运输模式研究［D］.长沙：中南大学，2009.

［8］裴育希.大型钢铁企业甩挂运输实证研究［D］.太原：山西大学，2012.

［9］LI H Q，LI Y，ZHAO Q，et al.The tractor and semitrailer routing considering carbon dioxide emissions［J］.Mathematical Problems in Engineering，2013（S1）：1－12.