基于甩挂运输组织的车辆路径优化

李维　成耀荣　吴百珂

摘 要：传统大型制造业内部运输成本较高。文章针对运输任务对车辆具有独占性的特点及甩挂运输的组织特性，分析得到总运输费用的大小取决于车辆的空车运行费用。在此基础上，将原有的甩挂运输任务问题转换为经典的TSP问题。建立了相应的数学模型，并设计了改进的自适应遗传。

关键词：甩挂运输；车辆路径；遗传算法

中图分类号：U116.2 文献标识码：A

Abstract： The cost of internal transport in traditional large manufacturing is very high. In this paper， according to the characteristics of the transport task for the exclusive vehicle and the organization characteristics of trailer pick-up transport， the total transportation cost is determined by the empty running cost of vehicles. On this basis， transform the original task of trailer pick-up transport into a classic TSP problem. The corresponding mathematical model is established and an improved adaptive genetic algorithm is designed.

Key words： trailer pick-up transport； vehicle routing； genetic algorithm

在制造业生产过程中，根据生产流程和工艺需要将分布在厂区不同地理位置上的原材料、再制品与半成品、产成品以及回收物料通过厂内车辆及时运送到各车间保证生产的正常进行。因此，在生产车间既需要将该车间生产完成的物料运送到下一工序车间，同时也需要将本车间生产所需要的原材料及时送达。因为甩挂运输的特殊性，牵引车从某个车间挂上挂车出发后，甩挂车辆进行组合运行的目的地必然是此挂车所在货物所对应的卸货点。在任务开始的最初时刻，所有牵引车辆都位于中心车场，挂车已经分配在各客户点。大型生产企业场内甩挂运输组织问题，实际上是属于车辆调度（VSP）范畴。因为各环节搭接的时间有限，所以甩挂模式通常是大型制造业场内运输的主要模式。国内外学者在车辆调度（Vehicle Scheduling Problem， VSP）方面取得了较多的理论和实际成果[1-3]。在国外TTRP（Truck and Trail Routing Problem）定义为甩挂运输问题。这类问题涉及到运输与生产计划的协调、挂车和牵引车在运输任务的组织、车辆的行驶路径规划与行驶时间的安排问题。此类问题的优化目标：在满足运输要求下，如何有效组织牵引车和挂车的使用，使得总运输成本最小[4]。

1 问题描述

节点Ni为装货点，以i为索引卸货地点为Nn+i。车库点为0。這样就区分了任务点、装卸货点以及其他的点。N

=0，1，…，n，…，2n为所有运输节点的集合，p =1，2，…，n为装货点集合，D =n+1，n+2，…，2n为卸货点集合。值得注意的是，不同的点可能带有相同的物理位置，也就是说有的点可能是虚拟的点。带时间窗的车辆路径问题在每个任务点有硬时间窗e ，l ，最早到达时间e ，最晚到达时间l 。c 、t 为对应两点间的车辆行驶费用、时间。q 为客户i要求从节点Ni运到节点Nn+i的运输量，中间过程不允许服务别的客户。对于不能一次完成运输的任务，将视为不同的客户服务请求。d 为任意两点间距离。基于甩挂运输的特性，本文不考虑装卸货时间。

2 概念和假设

（1）挂车装载能力相同且最大值为Q ；

（2）牵引车只能牵引一辆挂车；

（3）有足够多的牵引车和挂车可用；

（4）牵引车从车场出发完成一系列任务后最终返回车场；

（5）行驶的费用和时间与距离成正比。

2.1 策略和模型

根据甩挂运输的组织模式特性，当牵引车在某点挂上挂车后，那么牵引车和挂车运行的下一个点必然是该挂车的目的点。因此，总运费的大小将取决于车辆的空车运行费用。对甩挂运输模型进行一定的变型，将节点Ni和其运输目的点Nn+i组合起来看成一个甩挂运输任务点N i。如图1各组合点间以运输任务的形式构建任务模型。转化后的问题就是典型的TSP问题[5]。

在一个有向图G =N ，D 中，N =0，1 ，2 ，…，n ，节点0表示甩挂运输车辆所在车场，其他节点为转化后的运输任务节点，D 为连接任意两个任务间的距离。转化后的N i状态参数变为e ，l ， e =e ； l =l ； t =t ；a 车辆k到达i 点的服务时间；

c =c 车辆在转化后的点停留时间w =t ； d =d 。综上所述可将甩挂运输模型描述为一个经典的TSP模型，并便于求解。

决策变量：x = ；y =

minf= c x +λ y （1）

y =1 ？坌i ∈N ＼0 （2）

x = x =y ？坌i ∈N ， ？坌k （3）

ET ≤a +w t ≤LT ？坌i ， j ∈N ， k∈K （4）

x = x =1 k∈K （5）

x ≤S-1， ？坌S？哿N ＼0， S≥2， ？坌k （6）

x ， y =0或1， ？坌i ，j ，k （7）

目标函数（1）总运输费用最小；约束条件（2）、（3）表示每个客户点有且只能被访问一次；约束条件（4）牵引车服务客户j的时间要满足j点的时间窗要求；约束条件（5）每辆牵引车从车场出发完成一系列任务后回到车场；约束条件（6）防止客户间的子回路。

3 算法设计

因为将装货点i和其卸货点i+n整合成一个任务点来建立模型，所以需要对原来运输网络中节点距离做一些改变，变成甩挂任务距离矩阵[6-8]。

3.1 任务距离矩阵生成算法

输入 原始甩挂运输网络状态参数。

输出 改造后运输任务网络G =N ，D 。

开始

确定每个运输任务的装货点和卸货点，编制成运输任务属性表；将运输任务编号，创建一个空矩阵M。

开始1

对每个运输任务，计算该任务的卸货点到其他所有运输任务装货点的距离，按编号将结果记录到矩阵M相应的行中。

返回1

输出任务距离矩阵M。

结束

获取甩挂运输任务距离矩阵后，选用遗传算法求解运输任务的最佳完成顺序。遗传算法是借助生物进化过程中自然选择和自然遗传机制的随机搜索算法，对解决复杂和非线性优化问题比传统搜索算法有更强的适应能力。

3.2 运输任务最佳完成顺序生成算法

输入 任务距离矩阵M，遗传算法控制因子MAXGEN、NIND、GGAP、P 、P 等，其他计算系数如：车辆行驶成本、车辆核载等。

输出 运输任务完成路径。

开始

确定编码方案，

生成初始种群。

当迭代次数gen

开始1

当种群m

开始2

计算种群适应度值，

选择操作，

交叉操作，

变异操作，

进化逆转操作。

返回2

算法终止判断。

返回1

绘制迭代示意图、目标函数变化图以及路径图。

结束

3.3 算法关键参数设计

选择操作

选择操作是从原群体以一定的概率将优良个体选择出来，组成新的种群繁殖得到下一代个体。个体的适应度值越高，被选择的概率越大。选择算子是计算适应度比例的选择策略，选择算子：

p = （8）

其中：F 为个体i的适应度值，N为种群个体数目。

（1）交叉操作

交叉操作从种群中随机选择两个个体，通过两个染色体的交换组合，把父代的优良特性遗传给子代，从而产生新的优秀个体。由于个体采用实物编码，所以交叉操作采用实数交叉法，第k个染色体a 和第l个染色体a 在j位的交叉变换为：

a =a 1-b+a b （9）

a =a 1-b+a b （10）

其中：b是0，1区间的随机数。

（2）变异操作

变异操作主要是为了维持种群的多样性。进行变异操作，首先从种群中随机选取一个个体，选择该个体基因中的一点进行变异以产生更优秀的个体。第i个个体的第j个基因a 进行变异的操作：

a = （11）

其中：a 是基因a 的上界，a 是基因a 的下界，fg=r 1-g/G ，r 是一个随机数，g是当前的迭代次数，G 是最大进化次数，r为0，1区间的随机数。

（3）进化逆转操作

在选择、交叉、变异之后，进行多次单方向的逆转操作来改善遗传算法的局部搜索能力，在逆转操作后，只有适应度值提高的才接受该逆转，否则逆转无效。例如在1，10随机产生两个数4和7，在一条染色体确定两个位置，将其位置调换。

9 5 1 | 7 3 8 | 6 10 4 2

逆转操作之后成为：

9 5 1 | 8 3 7 | 6 10 4 2

（4）判断终止条件

因为遗传算法是随机搜索算法的特性，很难找到一个明确的终止条件。一般的解决办法要么是设置固定的进化迭代次数

G （一般G ∈100，1 000），或者当前的优化解在连续进化若干代也没有变化作为算法的终止条件，本文选用设置固定的迭代次数作为算法的终止条件。

4 结 论

（1）运输任务对车辆具有独占性，分析得出总运输费用的大小将取决于车辆的空车运行费用。

（2）提出新的策略，将原有的甩挂运输任务模型变为经典的TSP问题；并建立带时间窗的TSP模型。

（3）本文设计了改进的遗传算法进行相应的优化求解；能够较为快速地计算出较优的牵引车行驶路径。

参考文献：

[1] 刘云忠，宣慧玉. 车辆路径问题的模型及算法研究综述[J]. 管理工程学报，2005，19（1）：124-130.

[2] Anderson E， Phillips C， Sicker D， et al. A simple and effective evolutionary algorithm for the vehicle routing problem[J]. Computers & Operations Research， 2004，31（12）：1985-2002.

[3] Salhi S， Nagy G. Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries[J]. European Journal of Operational Research， 2005，162（1）：126-141.

[4] Cheng Y R， Liang B， Zhou M H. Optimization for vehicle scheduling in iron and steel works based on semi-trailer swap transport[J]. Journal of Central South University， 2010，17（4）：873-879.

[5] 孙国华. 带时间窗的开放式满载车辆路径问题建模及其求解算法[J]. 系统工程理论与实践，2012，32（8）：1801-1807.

[6] 李建祥，唐立新. 钢铁供应链生产计划与调度研究综述[J]. 控制工程，2010，17（1）：123-126.

[7] Tang L， Zhao J， Liu J. Modeling and solution of the joint quay crane and truck scheduling problem[J]. European Journal of Operational Research， 2014（236）：978-990.

[8] 辛曼玉. 網络型甩挂运输模式下的车辆调度问题研究[J]. 物流技术，2014，33（1）：254-258.