带时间窗车辆路径问题的改进节约算法

带时间窗车辆路径问题的改进节约算法

崔宏志 龚加安

（陕西省商洛职业技术学院 陕西 商洛 726000） 摘 要: 本文对节约算法进行了改进, 并利用改进的节约算法解决了带时间窗约束的多类型车辆路径问题.首先讨论了带时间窗约束的单类型车辆路径问题,给出其模型,并归纳了几种通过改进传统的节约算法得到的用于求解带有具体约束车辆路径问题的改进节约算法。 关键词: 运筹学; 车辆路径问题; 时间窗; 改进; 节约算法

The improved saving methods of vehicle routing problem

with time window

QIAN Long-jiang GONG Jia-an

(Shaanxi Shangluo Vocational And Technical Instituion Shangluo 726000)

Abstract: In this paper, the saving method is improved, and the improved saving method is used to solve the multi-type vehicle routing problem with time window. The single-type vehicle routing problem with time window constraints and its model are given, and some improved saving methods are also given to solve the deficiency of C-W heuristic algorithm.

Key words: operational research; vehicle routing problem; time window; saving method; improvement

节约算法由Clarke和Wright于1964年提出[1],该算法为解决车辆路径问题提供了一个简单易行的途径,但由于当时车辆路径问题还未衍生各种具体约束,故传统的节约算法无法直接应用于现今的车辆路径问题.本文先归纳了各种针对单类 型车辆路径问题的改进节约算法,然后对传统节约算法进行了改进,使之可以解决 带时间窗约束的多类型车辆路径问题

—–——————————

作者简介：崔宏志（1965-),男,陕西商州人,商洛职业技术学院副教授，人文管理系系主任，结业于西北大学研究生课程班，研究方向：数学建模。

1

车辆路径问题(Vehicle Routing Problem)是由Dantzig和Ramser于1959年

提出的,最初是为了解决在满足一组预选确定的客户需求的条件下, 同时决定不同种类的车辆的组成和线路,以达到运输费用最少.该类问题在现实中有着很强的应用背景,像生产制造业、航空服务业、物流运输业、炼钢工业中的许多问题都可以转化为此类形式.比如在制造业, 某机械加工车间拥有不同种类的车床,其功能不完全相同,相应可加工的工件任务既有相同的也有不同的.如果有一批加工任务等待处理,且每件工件具有到达和完工时间的约束,如何安排这些工件的加工设备和加工顺序使总的消耗费用最低就可以转化为此类模型.

此类问题虽经多人潜心研究,但由于其复杂性巨大,目前仍未找到多项式算法, 专家们多把精力集中于研究高质量的启发式算法方面.车辆路径问题已由最初的简单车辆运输衍生出各种具体问题,有了更细的划分,比如根据可用车场数分为单车场问题与多车场问题,根据可用车辆的车型数分为单车型问题与多车型问题, 根据决策者的要求分为单目标问题与多目标问题等[2].再具体就比如带冷藏系统的车辆运输问题[3].随着VRP问题的持续发展,考虑需求点对于车辆到达的时间有所要求之下,在车辆途程问题之中加入时间窗的限制,便形成了一个新的种类——有时间窗车辆路径问题(VRP with Time Window,VRPTW),此类问题中,车辆除满足VRP问题的限制外,还必须满足需求点的时间窗限制,即由于早到某个客户而引起的等待时间和客户需要的服务时间.自从Savelsbergh[4]证明了VRPTW 是N-P难题后,对其算法的研究就集中在了各种启发式算法上.

从文献中可以看到,对于车辆路径问题,国内外已经有了深入的研究,近些年比较流行的遗传算法[5]~[6],蚁群算法[7]都已在VRP问题中得到应用,但这些研究主要集中于单一类型车辆,国内关于多类型车辆路径问题的研究较少,与这方面研究相关的文献有Golden et al.[8](1984), J.A.Ferland and P.Michelon[9](1988),F.H.Liu and S.Y.Shen[10](1999),于波,丁源[11](2006).

前面提到的各种文献中有很多采用了灵感来自生物界的遗传算法和蚁群算法.遗传算法运行方式和实现步骤规范,便于具体实用,适用于复杂优化问题,比较而言,节约启发式算法可提高车辆的利用率,能解决大规模问题[12],而且节约算法的思想更为简单易懂.这里我们着重讨论了通过对简单易行的C-W节约算法进行修正得来的改进型节约算法,在对单类型带时间窗车辆路径问题的改进节约算法进行总结归纳后,我们根据Golden et al. 在1984年提到的节约值计算表达式[8],并结合邻域搜索的思想, 提出了一种改进型节约算法,然后将改进节约算法应用于多类型车辆路径问题,通过具体算例说明了该算法的可行性.

2

1.问题提出及模型建立

这里我们假设服务中心的车辆只有一种类型,且该类型货车的装载容量为q,服务中心共有K辆车可用于服务.该中心向n个客户送货,第i个客户需货量为g(i),且g(i)

1) 所有任务都是事先安排的,调度问题是静态的.

2) 每辆车在执行任务完毕后必须再回到原来所在位置,即再回到集货中

心.

3) 成本简化为运输成本(与路径有关). 为建立模型,定义二进制变量如下：

xijk?1，一辆k类型车辆从点i行驶到点j；?? ?0，否则。?1，一辆k类型车辆给客户点i送货；yki??

0，否则。?则车辆路径问题的模型建立如下： 目标函数:min Z=?i??cjkijxijk

3

??giyki?q,?k (1)?i?ET?RT?LT,i?1,2,?,n (2)ii?i?K??yki?1,i?1,2,?,n (3)?k?1约束条件:?n

??xijk?yki,i?0,1,2,?,n;k?1,2,?,K (4)?j?1n?n??xihk??xhjk,h?1,2,?,n;k?1,2,?,K (5)?i?0j?0???X?(xijk)?S (6)其中,(1)式约束每条路线上客户需求总量不超过车辆的载重;(2)式约束车辆到达时间需满足客户的时间窗要求;(3)~(4)式约束每个客户仅由一辆车服务,即每个客户在且仅在一条服务路线上;(5)式约束每个客户点h前后各只有一个客户点与h相连;式(6)为支路消去约束,S表示消去支路约束的集合,以保证解的连通性. 2. 用于解决车辆路径问题的C-W节约算法

我们采用简单、易实现的节约算法,其基本思想可由图1表示.首先将各客户点分别与集货中心相连,形成n条初始路线,然后计算连接其中任意两点i和j的节约值:s(i,j)= c1i+c1j-cij. s(i,j)越大,说明将i,j两点连接后节约的费用越多.把s(i,j)排序后,尽量首先选取使得s(i,j)最大的两个点i和j,然后按照s(i,j)由大到小的顺序依次连接各点,这样使得总路程最小.若连接过程中出现该路线运货总量超过车辆载重,则结束该路线的连接.

图1 连接任务点前后的路线比较

2.1

C-W节约算法的改进

4

由于C-W节约算法起初是为解决旅行商问题提出的,它不考虑各种约束条件,故无法直接用来求解VRP问题.但我们可以通过加入检验车辆载重约束和时间窗约束来完善C-W节约算法,使之能够求解单类型车辆路径问题.

车辆载重约束:在连接点i和点j之前,先检验连接后的车辆装载量是否超过车辆的载重,若不超过,则可以连接,否则,不允许连接这两点,并转向其他可能的连接.用数学表达式来表述,即为:设路线\0???i?0\的货运量为Gi,路线

\0?j???0\的货运量为Gj,只有当Gi+Gj?q时,才允许连接点i和点j,形成

路线\0??i?j???0\.Gi和Gj通过累加线路上各客户点的需求得到.

时间窗约束:时间窗约束主要考虑由于点j与点i连接而引起的车辆到达点j及j后面各点(如果有的话)的时间变化.为方便对时间窗约束进行计算,我们做出以下假设[12]:令EFi表示连接点i和点j后车辆到达点j的时间变化量,则:EFj=RTi+UTi+tij-RTj.

当EFj<0时,车辆到达点j的时间提前; EFj=0说明车辆到达点j的时间不变; EFj>0,车辆到达点j的时间推迟.令r表示同一线路中j及以后各点,?j?表示车辆到达j及其后面各点不违反时间窗约束的最大允许时间提前量, ?j?表示车辆到达j及其后面各点不违反时间窗约束的最大允许时间推迟量,则有:

?j?=min{RTr-ETi} ?j?=min{LTr-RTr}

改进后的节约算法可表示如下:

1) 计算s(i,j),并令M={s(i,j)|s(i,j)>0,i,j=1,2,…,n},并将集合M中的元素由大至小排序.

2) 选择M中的第一个元素s(i,j),考察点i和点j,是否满足下列条件之一: ①点i和j均处在初始化线路中;②点i和点j一个在初始化线路中,一个在已构点成线路中,且直接与车场相连;③点i和点j均在已构成线路中,且都直接与车场相连.

若满足,则转向步骤3),否则,转向步骤6).

3) 计算连接点i和点j后车辆总装载量G,若G?q,转向步骤4),否则,转向步骤6).

5

本文来源：https://www.bwwdw.com/article/xl6v.html