基于改良C⁃W节约算法的甩挂运输车辆调度模型…………………

张 笛 钟 明 陈 龙等

张 笛1 钟 明2 陈 龙1 梁 军1 葛慧敏1 谈建祥3

1.江苏大学汽车工程研究院，镇江， 212000 2.江苏省镇江市公安局交通警察支队交通指挥控制中心，镇江， 212000

3.镇江兴港国际物流有限公司，镇江， 212000

摘要：为研究甩挂运输车辆调度模型，以带有时间窗的车辆配送模型为基础，构建了包括油耗成本、过路费成本、装卸停歇时间成本和延时惩罚成本在内的总成本最小目标函数，建立了基于不同载重油耗方程的甩挂运输车辆调度模型。在算法上，构建了改良型的C-W节约算法，并用该算法找出了一个9客户案例的最优物流配送路径。

关键词：甩挂运输车辆；油耗模型；车辆路径规划；节约算法

中图分类号： F54

DOI：10.3969/j.issn.1004⁃132X.2018.19.013 开放科学(资源服务)标识码(OSID)：

A Vehicle Scheduling Model for Trailer Pick-up Transport Based on

Modified C-W Saving Algorithm

ZHANG Di ZHONG Ming2 CHEN Long1 LIANG Jun1 GE Huimin1 TAN Jianxiang3

1

1.Automotive Engineering Institute of Jiangsu University，Zhenjiang，Jiangsu，212000

2.Traffic Police Detachment Traffic Command and Control Center of Zhenjiang Public Security Bureau

of Zhenjiang City，Jiangsu Province，Zhenjiang，Jiangsu，212000

3.Zhenjiang Xingang International Logistics Co.，Ltd.，Zhenjiang，Jiangsu，212000

Abstract： In order to study the model of trailer pick ⁃ up transport vehicle scheduling，the minimum objective function of fuel costs，toll costs，loading and unloading costs and delay penalty costs was built， based on the vehicle delivery mode which with time windows. Based on the different load ⁃ bearing fuel consumption equations，the model of trailer pick⁃up transport vehicle scheduling was constructed. An im⁃ proved C -W（Clarke ⁃ Wright）saving algorithm was established，and the algorithm was used to find the optimal logistics delivery path of a 9⁃customers case successfully.

Key words： trailer pick ⁃ up transport transport transport vehicle；fuel consumption model；vehicle routing problem；saving algorithm

0 引言甩挂运输集汽车列车运输与装卸甩挂作业技术于一体，是一种集约、高效的运输组织模式，是道路货运业组织化、规模化、网络化、信息化和标准化发展水平的集中体现，在提高运输效率、降低运输成本、促进节能减排等方面具有非常显著的

收稿日期： 2018－01－02

优势 。甩挂运输车辆调度问题一直是领域内的

［］ 1

研究热点。

为了解决车辆调度中装货和卸货时挂车运输交换问题，王莹 提出了一种基于半挂车运输节点

［］ 2

之间装卸调度算法模型； CHENG等 建立了甩挂

［］ 3分离模式下的集装箱车辆调度数学模型；朱晓兰等 提出了针对装配企业采购物流的 C-W

［］ 4

（ Clarke-Wright）节约算法，并在线路规划中插入

车辆载重量和容积的双重约束条件；马建华等 采

［］ 5

用C-W节约算法求解了线路规划可能存在的交叉路径、增加运输里程等情况，并对连接点选择问题进行了优化；潘立军等 提出了三类带时间窗约

［］ 6

束的车辆调度模型。

本文结合甩挂运输物流的特性，增加了车辆载重和时间窗的约束条件，建立了基于不同载重油耗模型的甩挂运输物流配送模型以及改良的CW节约算法，并以镇江兴港国际物流有限公司为例，验证了改良C-W节约算法的实用性。

1 问题描述

某车辆调度中心拥有装载量为Q （ k= 1，2，⋯， m）的汽车列车，在不同的客户点有若干辆半挂车的运输任务，已知客户点i的货运量为qi（ i= 1， 2，⋯ ，且n）， qi ≥ 0， Qk ≥ 0， k ∈ K, i ∈ C, K为所有牵引车的集合， C为所有客户的集合。求满足货运要求的费用最少的车辆行驶路线。

相关参数假设如下： Eij为运输车从客户i到客户 j的运输成本； t ij为牵引车从客户i到客户j的行车时间； t si为牵引车在客户i处的停留时间； T0K为牵引车K的出发时间； TBK为牵引车K的要求返回时间； TEi为客户i允许的最早开始时间； TLi为客户i允许的最迟结束时间； Pk ( t 0i )为惩罚函数，用来表示车辆到达客户i 的时间迟于客户i的最迟结束时间对应的惩罚成本； t0 i为车辆从调度中心或车场到达客户点i的时间。

另外，变量xijk 和y ik的值为0或1。若牵引车K为客户i服务，则y ik 为1，否则为0，即y ik = { 0, 1 }， y ik表示牵引车分配方案可用布尔矩阵表示；若牵引车 k经由客户i到客户j，则 xijk 为1，否则为0，即xijk = { 0, 1 }， xijk表示牵引车路线安排。

为使成本最小以及考虑配送的实际情况，模型同时满足以下约束条件 ： ①甩挂运输中牵引车

［］ 7甩挂的是半挂车，而不是零担货物； ②装卸时间只与挂车的数量有关，且在运输网络中的甩挂是没有时间延迟的； ③甩挂运输的效率只与汽车列车

Σ总的行驶时间和半挂车的装卸停歇时间有关，与

i半挂车的数量及货物的体积、质量无关； ④所有牵

Σ引车路线均起始并终止于调度中心，一辆车可以

i服务多个客户点； ⑤每个客户点都有一个非负的货物需求量； ⑥满载时，需要运输的挂车数量等于一辆汽车列车允许装载的最大半挂车数量的整数倍，完成所有任务要多辆运输车辆；非满载时，需要运输的挂车数量少于一辆汽车列车允许装载的

半挂车数量，完成任务只需要一辆运输车辆。

2 成本模型建立

运输过程中的汽车油耗成本是运输成本的一个重要组成部分，燃油的消耗量受到车辆状况、行车速度、行驶里程、车辆载重、驾驶习惯、道路状况，油品质量以及天气状况等多种因素的影响，本文探讨的油耗成本模型只考虑行驶里程和车辆载重（挂车的数量），在计算满载和非满载等情况下认为风阻力不变（行车速度不变），汽车的机械传动损失不变，路面情况不变，路面的摩擦损失与压力成正比，油耗和牵引车加挂车的质量之和成正比。这里给出不同载重和不同行驶距离下的车辆油耗模型：

Efij = min xijk Dij f [ A (+ m0 a ij m1) + B ] （ 1）

, j, k

式中， Efij为运输车从客户i到客户j的油耗成本； Dij为客户点i和客户点j之间的地理距离，百公里；为每升燃油的价f格，元； A为油耗和载重的正相关系数； B为常数； m0为牵引车的质量， t； m1为挂车的质量， t； a ij为需要从客户点i运输到客户点j的挂车数量，辆。

过路费成本是指车辆通过高速公路需要的过路费，主要和车辆行驶的距离有关，此成本模型为

Erij = min xijk Dij H （ Σ 2）

, j, k i 式中， Erij为运输车从客户i到客户j的过路费成本； H为车辆每行驶百公里的过路费用。

装卸停歇时间成本是指牵引车在客户处装卸挂车所产生的时间成本，这一成本只和装卸挂车的数量相关，此成本模型为 Esij = minΣ aij D （ 3） i , j

式中， Esij为运输车从客户i到客户j的装卸停歇时间成本； D为一辆挂车装载或者卸载所需要的时间成本。

配送延迟成本Epi指车辆没在规定的时间内到达客户处所需要支付的罚金。此成本模型为

∀ i、j ∈ C, ∀∈ k K

TEi ≤+ T0K Σxijk + Σyik ≤ （ 10）

t ij t si TLi

∀∈ kK j= 1, 2, …, i, i + 1

其中，式（ 5）为目标函数；式（ 6）表示一条线路上客户需求总量不超过车辆的最大载重量；式（ 7）、式（ 8）表示每个客户点只能由一辆车服务，且这些客户点是在一条服务路线上；式（ 9）表示每辆牵引车的行车路线总耗时不超过预先确定的数值，即每辆牵引车需要在规定时间内返回配送中心；式（ 10）表示对某个客户点，牵引车到达时间限制在某一时间段内。

3 算法求解

C-W节约算法是由Clarke 和 Wright 于 1964年首次提出的，起初是为解决旅行商问题，因此它不考虑各种约束条件，故无法直接用来求解车辆路径问题（ vehicle road problem，VRP），但可以通过加入检验车辆载重约束和时间窗约束来完善CW节约算法，使之能够求解单类型车辆路径问题 。

［］ 8在初始路径0- i- 0中， Ef0i是汽车从调度中心或者车场去往客户点i过程中产生的油耗成本， Efi0是车辆由客户点i返回调度中心过程中所产生的油耗成本，虽然来回过程的运输距离是一样的，但由于载重量不同，所以Ef0i 和 Efi0不相等。过路费成本只和运输距离成正相关关系。装卸停歇时间成本由于每次装卸的时间是固定的，因此只和每个客户点需要装卸的半挂车数量相关。配送延迟成本需要结合具体情况分析。用改良节约算法解决该问题的步骤如下： （ 1）首先计算客户i和客户j之间线路的费用节约值s ( i, j )，形成集合N ，并按照从大到小对s ( i, j )进行排序， s ( i, j )分为油耗费用节约值s f ( i, j )和过路费用节约值s r ( i, j ) ，即s ( i, j )= s f ( i, j )+ s r ( i, j ),而s f ( i, j )= Efoi + Efi0 + Ef0j + Efj0 - E - Efij - E （ 11）

′ ′ f0i fj0其中， Ef0j为在初始路径0- j- 0中汽车从调度中心或者车场去往客户点j过程中产生的油耗成本； Efj0是车辆由客户点j回调度中心过程中所产生的油耗成本。在调度后的路径0- i-j- 0中， E 为汽车

′ f0i从调度中心到客户点i过程中所产生的油耗成本； Efij为从客户点i到客户点j的油耗成本； E 为客户

′ fj0

点 j回到调度中心的过程中产生的油耗成本。但由于车辆从j点返回配送中心时，车辆都处于空载状态，所以Efj0 = E fj0 ，因此：

′ s f ( i, j )= Efoi + Efi0 + Ef0j - E - Efij （ 12）

′ f0i

再将油耗成本模型公式代入式（ 12），得sf ( i, j )= fD0i (- B Aa0i m1 ) + f (- D0j Dij ) [ A (+ m0

a 0j m1 + B )] （ 13）式中， D0i、D0j分别为调度中心和客户点i、的地理距离； j a 0i和a 0j分别为调度中心运输到客户点i和j的挂车数量。过路费用节约值

s r ( i, j )= Eroi + Erj0 - Erij （ 14）式中， Eroi、Erj0分别为车辆路径0- i和j- 0的过路费成本。将过路费成本模型公式代入式（ 14），得

s r ( i, j )= C (+- D0i Dj0 Dij ) （ 15）

式中， Dj0为车辆从客户点j到调度中心的距离。

综上可得s f ( i, j )= fD0i (- B Aa0i m1 ) + f (- D0i Dij ) [ A ( m0 +

a 0j m1 + B )] + H ( D0i +- Dj0 Dij ) （ 16） （ 2）若N为空，则终止叠代，否则考察N中的第一项s ( i, j )是否满足下列条件之一： ①点i和j均不在已构成的线路上； ②点 i 和 j在已构成的线路上，但不与车辆调度中心相连； ③点i和j位于已构成的不同线路上，且均不与车辆调度中心相连，一个是起点，一个是终点。如满足此条件则转步骤（ 3），否则转步骤（ 6）。

（ 3）考察点i和 j连接后的线路上总货运量n n

q i y ik ，若 q i y ik ≤ Qk ，则转步骤（ 4），否则转步Σ =1 =1 i

骤（ 6）。

（ 4）计算连接点i和j所在的线路后，车辆到达j点的时间比原路线上车辆到达j点的时间的变化量为： Δt j = t 0i + t si + t ij - t 0j。t 0i为车辆从调度中心或者车场到达客户点i的时间， t 0j为车辆从调度中心或者车场到达客户点j的时间。①若Δt j= 0，则转步骤（ 5）；②若Δt j < 0，则计算Δj-，当Δt j ≤ Δj时，转步骤（ 5），否则转步骤（ 6）；③若Δt j > 0，则计算 Δj+ ，当 Δt j ≤ Δj+时，转步骤（ 5），否则转步骤（ 6）。 其中， Δj-为线路上j点后面的各个客户处均不需要等待的到达j点时间的最大允许提前量； Δj+为线路上j点后面的各个客户不违反时间约束的到达j点时间的最大允许推迟量。

（ 5）连接点i和点j，计算牵引车到达各个客户点时的新时间。

（令6） N =- N s ( i, j )，转步骤（ 2）。以上是针对单个车辆调度中心的车辆优化调度问题的求解，多调度中心的车辆调度问题可以转化为单个调度中心问题来处理，首先确定每个调度中心需完成的任务，然后再求解多个调度中心的车辆调度问题。

4 应用研究

如图1所示，地点A是镇江兴港国际物流有限公司的配送中心，地点1~9是主要装卸点。根据调查，得到各装卸点之间的距离以及各个装卸点与配送中心之间的距离，见图1。 A.镇江 1.南京 2.扬州 3.常州 4.无锡 5.苏州 6.泰州

7.南通 8.宣城 9.芜湖

图1 配送中心与装卸点之间的分布示意图（km） Fig.1 Distribution center and the distance between the

loading and unloading point diagram（ km）据英国交通部对车辆油耗与载重间关系的研究数据可知 ，车辆的油耗与载重间存在较强的线

［］ 9性正相关特性，可以简化为线性关系：

F = 0.556M + 16.7 M =+ m0 a ij m1

式中， F为每百公里油耗成本； M为整车质量。

一般情况下，牵引车会使用0号柴油，价格为6.36 元/L，定义牵引车的质量为10 t，每辆挂车的质量为15 t ，车辆的过路费为160 元/百公里，每辆半挂车平均装卸停歇时间为0.6 h ，时间成本40元/h，牵引车的时间惩罚系数为0.6，每辆牵引车最多可拖带4辆挂车，牵引车的平均速度为80 km/h，所允许最长的运输总时间为6h。

车辆调度开始前，各个装卸点需运输的挂车数量如表1所示。

表1 各个装卸点需运输的挂车数量

Tab.1 The number of trailers to be transported at

each loading and unloading point

运用上文的甩挂运输调度算法对这次车辆调度进行优化。进行初步调度需要牵引车的数量如表2所示，调度后各个装卸点剩余挂车数量如表3所示，费用节约值如表4所示。

根据改良的节约算法对所需牵引车进行调度的行驶路线如图2所示。

线路1（A-7-6-A）的费用节约值为602.3元，时间为4.025 h；线路2（A-3-4-5-A）的费用节约值为528.7元，时间为3.475 h；线路3（A-1-2-A）的费用节约值为255.3 元，时间为 2.075 h ；线路4（A -8-9-A）的费用节约值为 77 元，时间为3.425 h；各条路线的费用节约总值为1 463.3 元。使用改良节约算法进行车辆调度运输总成本减少了1 463.3元，降低了25.01%。

算例证明本文所创建的节约算法可以降低甩挂运输的运输成本，并且有效地解决了运输过程中的车辆调度问题。

5 结论

本文基于不同载重下的油耗模型以甩挂运输车辆最优运输路径为研究对象建立了一种改良型C-W节约算法，构建了基于油耗模型的甩挂运输物流配送优化路径模型，模型以包括油耗成本、过路费成本、装卸停歇时间成本以及延时惩罚成本在内的总成本最小为目标函数，以车辆载重和时间窗作为约束。在算法上，构建了改良型的C-W节约算法，并用该算法找出了一个9客户算例的最优路径。最后通过在算例中比较调度前后的运输成本，证明了节约算法可以降低甩挂运输的运输成本，从而得出建立基于不同载重油耗模型的甩挂运输物流配送路径优化模型的必要性。

参考文献：

［ 1 ］ 孙焰.现代物流管理技术［ M. ］ 上海：同济大学出版社， 2004.

SUN Yan. Modern Logistics Management Technol⁃ ogy ［］ M .Shanghai：Tongji University Press，2004.

［ 2 ］ 王莹.拖挂分离模式集装箱运输车辆调度研究［ D. ］武汉：武汉理工大学， 2010.

WANG Ying. Study on Vehicle Routing Problems with Trucker and Semitrailer Separated ［］ D Wuhan： Wuhan University of Technology，2010.

［］ 3 CHENG Yaorong，LIANG Bo，YU Wen. Semi ⁃ trailer Swap Transport Applied in Large⁃scale Man⁃ ufacturing Enterprises ［］ C //2009 Second Interna⁃ tional Conference on Intelligent Computation Tech⁃ nology and Automation. Washington DC，2009，4：

426⁃429.

［ 4 ］ 朱晓兰，赵一飞. C-W节约算法在装配企业采购物流中的应用［ J. ］ 上海交通大学学报， 2007，41（2）： 1420⁃1424.

ZHU Xiaolan，XIE Yifei. Application of C-W Sav⁃ ing Algorithm in Assembly Enterprise Procurement Logistics ［］ J . Journal of Shanghai Jiaotong Universi⁃ ty，2007，41（2）：1420⁃1424.

［ 5 ］ 马建华，房勇，袁杰. 多车场多车型最快完成车辆路径问题的变异蚁群算法［ J. ］系统工程理论与实践， 2011，31（8）：1508⁃1516.

MA Jianhua，FANG Yong，YUAN Jie. The Mutant Ant Colony Algorithm that Can Complete Vehicle Path Problems Quickly for Multi ⁃ vehicle Models ［］ J . System Engineering—Theory and Practice，2011， 31（8）：1508⁃1516.

［ 6 ］ 潘立军，符卓. 求解带时间窗车辆路径问题的插入检测法［ J. ］系统工程理论与实践， 2012，32（12）：319⁃ 322.

PAN Lijun，FU Zhuo. Insertion Detection Method for Vehicle Routing Problem with Time Windows ［］ J . Systems Engineering—Theory&Practice，2012， 32（12）：319⁃322.

［ 7 ］ 范宁宁.烟大滚装甩挂运输牵引车调度优化研究［ D. ］大连：大连海事大学， 2012.

FAN Ningning. Study on Scheduling Optimization of Large Rolling Loading Haulage Tractors ［］ D .Da⁃ lian：Dalian Maritime University，2012.

［ 8 ］ 刘洋.一种应用于物料配送路径选择的改进C-W节约算法［ D. ］长春：吉林大学， 2017.

LIU Yang. An Improved C - W Saving Algorithm Applied to Material Distribution Path Selection ［］ D . Changchun：Jilin University，2017.

［］ 9 COYLE M. Effects of Payload on the Fuel Con⁃ sumption of Trucks. Department for Transport ［ C / OL ］［ . 2018⁃01⁃02 ］ .http：//www.freightbestpractice. org.uk/effects⁃of⁃payload⁃on⁃fuel⁃consumption⁃of⁃ trucks.

（编辑 王艳丽）

作者简介：张笛，男， 1994年生，硕士研究生。研究方向为智能交通。E ⁃ mail：1406838524@qq. com。陈龙（通信作者），男， 1958年生，教授、博士研究生导师。研究方向为车辆动态性能。E ⁃ mail：liang⁃ jun@ujs.edu.cn。