基于遗传算法的甩挂运输路径优化研究

张涵悦 刘 松 岳海亮

（1．重庆交通大学交通运输学院，重庆 400074；2．山地城市交通系统与安全重点实验室，重庆 400074）

随着物流业的发展，配送车辆的路径优化问题也越来越重要，如何在满足客户需求的情况下实现高效节能的配送成为现代物流业一个重要的问题。其中，公路运输在配送过程中使用卡车加挂车形成的甩挂车进行配送任务，能在同等运输条件下，提高运输效能。车辆示意图如图1所示，车队是由两种不同车型组成，卡车（带有1节车厢）和甩挂车（带有2节可卸车厢），网络还包含一类特殊的点，称之为甩挂点。在甩挂点，车辆可以停放、装卸以及改变装载顺序。甩挂运输是指特定的卡车加上挂车，按照预定好的方案在甩挂点甩下或挂上指定的挂车，继续配送的一种运输组织方式，能在同等条件下，最大限度地利用牵引力，加速车辆周转率，提高运输效能，是一种节能减排、降低运输成本的先进道路运输组织方式。

图1 卡车与甩挂车车型示意图

甩挂运输作为一种新型高效的运输方式，国内外学者已有一定的进展。边展[1]等研究了带时间窗的甩挂运输路径优化问题，建立了驾驶时间为目标函数构建模型。李红启[2]等以货运吨公里碳排放量为目标函数，构建了混合整数规划模型，实现了良好的节能减排效果。杨珍花[3]等建立了混合模式下的多车型交叉甩挂调度模型并设计了混合模拟退火算法来求解模型，结果体现了良好的节约成本作用。

1 模型的建立

1.1 问题描述

SB-VRP是在VRP基础上加入甩挂车的概念，解决的是确定一个满足客户需求的允许甩挂的车辆路线规划，目的是求得最优的配送路径以实现最少的配送费用。小型SB-VRP的大致配送流程如图2所示。

图2 小型SB-VRP实例

图2 中，灵活点表示既允许卡车配送也允许甩挂车配送的客户点；限制点表示只允许卡车配送不允许甩挂车配送的客户点；已选甩挂点表示经算法运行被用于进行甩挂操作的中转点。本文研究的SB-VRP可归纳为：利用卡车和甩挂车，在车辆最大装载能力内，对配送范围内的客户点进行配送任务，以满足各个客户点的需求量。

1.2 模型建立

在对SB-MVRP建模的开始要先进行如下假设：

（1）每辆车都要从物流配送中心出发，完成配送任务后回到配送中心；

（2）允许甩挂运输的路径在配送过程中只允许一次甩挂操作；

（3）限制点客户只允许卡车进行配送，灵活点客户允许卡车和甩挂车进行配送；

（4）每条配送路线上各客户点的需求量之和不可以超过所派汽车最大允许容量。

基于以上假设，建立SB-MVRP优化模型，相关数学符号定义如下：

N=O∪S∪L∪R表示物流网络中所有节点集合。O表示配送中心；S表示甩挂点（甩挂车进行甩挂操作的中转点）集合，s表示甩挂点标号；L表示灵活点（同时允许卡车和甩挂车进行配送任务的客户点）集合，l表示灵活点标号；R表示限制点（只允许卡车进行配送任务的客户点）集合，r表示限制点标号；i、j表示配送网络中所有节点编号。t表示卡车标号，nt表示卡车启动数量；k表示甩挂车标号，nk表示甩挂车启动数量；ct、ck分别表示卡车和甩挂车的启动费用；bt、bk分别表示卡车和甩挂车的单位里程所耗费用；f表示司机费用。aijt、aijk分别表示卡车和甩挂车从i→j行驶里程；h表示司机一天最大允许工作时间。

决策变量定义如下：

有上述定义可建立数学模型如下：

表示车辆行驶过程中所耗的费用之和；(nt+nk)f表示所需司机的费用之和；(ntct+nkck)表示车辆的启动成本之和。具体数学表达如下：

式（2）表示所有车辆从配送中心出发回到配送中心；式（3）表示允许甩挂运输的路径在配送过程中只允许一次甩挂操作；式（4）表示限制点客户只允许卡车进行一次配送；式（5）表示灵活点客户允许卡车或者甩挂车进行一次配送；式（6）表示只允许卡车进行配送的路径的容量约束；式（7）表示既允许卡车也允许甩挂车进行配送的路径容量约束；式（8）表示只允许甩挂车进行配送的路径的容量约束。

2 算法设计及有效性分析

2.1 算法设计

（1）编码解码。采用小数编码的方式，按照小数由小至大的顺序解释成整数编码，相等小数按前后位置解释成整数。每条整数编码可以解释成一条配送路径。

（2）遗传操作。采用轮盘赌进行个体选择。采用单点交叉。随机选择交叉位，将两个个体交叉位后基因互换形成新个体。采用单点变异。随机选择个体某基因位，随机产生一小数替换该基因位基因，实现个体变异。

（3）种群管理策略。在算法中，采用单种群管理策略，满足给定种群规模m进行选择、交叉、变异操作，并采用基因保留策略，更新最优解。

2.2 算法有效性分析

本文选取Solomon中R101的所有点的坐标并得到节点间距离，再选取所有点的Demand，作为客户点需求量。如图1所示配送中心以及待配送客户点，如何在满足所有客户需求量以及满足各路段道路条件的同时，在规定时间内花费最少费用完成所有配送并回到配送中心。假设配送网络中卡车的最大装载能力为200，甩挂车最大装载能力为400；车辆平均行驶速度为60 km/h；卡车固定启动成本为1，单位行驶成本为1；甩挂车固定启动成本为2，单位行驶成本为1.5；甩挂点启动成本为5；司机日工作时长为12 h，日工资为10。

为验证本文设计的遗传算法的有效性，取种群规模100，令交叉概率分别为0.9，变异概率0.1。最大迭代次数Maxgen=200，通过MATLAB软件编程计算，并在一台CPU为IntelCore(I7)，内存为8.0 GB的计算机上进行运算。图3为最优解随遗传算法迭代次数的变化图。由图3可知，算法可以在有限迭代次数下达到收敛状态。当迭代次数达到1700代左右，达到最优解收敛状态。

图3 遗传算法迭代图

3 结语

本文提出了一种允许甩挂的车辆路径问题，针对该问题，以配送最低成本为目标，在满足客户点的需求量的前提下，建立了配送路径总成本模型，并针对该模型设计了遗传算法进行求解。通过2 000次的迭代发现，算法可在有限迭代次数内达到收敛状态。