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

1带时间窗车辆路径问题的改进节约算法崔宏志龚加安（陕西省商洛职业技术学院陕西商洛726000）摘要:本文对节约算法进行了改进,并利用改进的节约算法解决了带时间窗约束的多类型车辆路径问题.首先讨论了带时间窗约束的单类型车辆路径问题,给出其模型,并归纳了几种通过改进传统的节约算法得到的用于求解带有具体约束车辆路径问题的改进节约算法。关键词:运筹学;车辆路径问题;时间窗;改进;节约算法TheimprovedsavingmethodsofvehicleroutingproblemwithtimewindowQIANLong-jiangGONGJia-an(ShaanxiShangluoVocationalAndTechnicalInstituionShangluo726000)Abstract:Inthispaper,thesavingmethodisimproved,andtheimprovedsavingmethodisusedtosolvethemulti-typevehicleroutingproblemwithtimewindow.Thesingle-typevehicleroutingproblemwithtimewindowconstraintsanditsmodelaregiven,andsomeimprovedsavingmethodsarealsogiventosolvethedeficiencyofC-Wheuristicalgorithm.Keywords:operationalresearch;vehicleroutingproblem;timewindow;savingmethod;improvement节约算法由Clarke和Wright于1964年提出[1],该算法为解决车辆路径问题提供了一个简单易行的途径,但由于当时车辆路径问题还未衍生各种具体约束,故传统的节约算法无法直接应用于现今的车辆路径问题.本文先归纳了各种针对单类型车辆路径问题的改进节约算法,然后对传统节约算法进行了改进,使之可以解决带时间窗约束的多类型车辆路径问题—–——————————作者简介：崔宏志（1965-),男,陕西商州人,商洛职业技术学院副教授，人文管理系系主任，结业于西北大学研究生课程班，研究方向：数学建模。2车辆路径问题(VehicleRoutingProblem)是由Dantzig和Ramser于1959年提出的,最初是为了解决在满足一组预选确定的客户需求的条件下,同时决定不同种类的车辆的组成和线路,以达到运输费用最少.该类问题在现实中有着很强的应用背景,像生产制造业、航空服务业、物流运输业、炼钢工业中的许多问题都可以转化为此类形式.比如在制造业,某机械加工车间拥有不同种类的车床,其功能不完全相同,相应可加工的工件任务既有相同的也有不同的.如果有一批加工任务等待处理,且每件工件具有到达和完工时间的约束,如何安排这些工件的加工设备和加工顺序使总的消耗费用最低就可以转化为此类模型.此类问题虽经多人潜心研究,但由于其复杂性巨大,目前仍未找到多项式算法,专家们多把精力集中于研究高质量的启发式算法方面.车辆路径问题已由最初的简单车辆运输衍生出各种具体问题,有了更细的划分,比如根据可用车场数分为单车场问题与多车场问题,根据可用车辆的车型数分为单车型问题与多车型问题,根据决策者的要求分为单目标问题与多目标问题等[2].再具体就比如带冷藏系统的车辆运输问题[3].随着VRP问题的持续发展,考虑需求点对于车辆到达的时间有所要求之下,在车辆途程问题之中加入时间窗的限制,便形成了一个新的种类——有时间窗车辆路径问题(VRPwithTimeWindow,VRPTW),此类问题中,车辆除满足VRP问题的限制外,还必须满足需求点的时间窗限制,即由于早到某个客户而引起的等待时间和客户需要的服务时间.自从Savelsbergh[4]证明了VRPTW是N-P难题后,对其算法的研究就集中在了各种启发式算法上.从文献中可以看到,对于车辆路径问题,国内外已经有了深入的研究,近些年比较流行的遗传算法[5]~[6],蚁群算法[7]都已在VRP问题中得到应用,但这些研究主要集中于单一类型车辆,国内关于多类型车辆路径问题的研究较少,与这方面研究相关的文献有Goldenetal.[8](1984),J.A.FerlandandP.Michelon[9](1988),F.H.LiuandS.Y.Shen[10](1999),于波,丁源[11](2006).前面提到的各种文献中有很多采用了灵感来自生物界的遗传算法和蚁群算法.遗传算法运行方式和实现步骤规范,便于具体实用,适用于复杂优化问题,比较而言,节约启发式算法可提高车辆的利用率,能解决大规模问题[12],而且节约算法的思想更为简单易懂.这里我们着重讨论了通过对简单易行的C-W节约算法进行修正得来的改进型节约算法,在对单类型带时间窗车辆路径问题的改进节约算法进行总结归纳后,我们根据Goldenetal.在1984年提到的节约值计算表达式[8],并结合邻域搜索的思想,提出了一种改进型节约算法,然后将改进节约算法应用于多类型车辆路径问题,通过具体算例说明了该算法的可行性.31.问题提出及模型建立这里我们假设服务中心的车辆只有一种类型,且该类型货车的装载容量为q,服务中心共有K辆车可用于服务.该中心向n个客户送货,第i个客户需货量为g(i),且g(i)q,(i=1,2,…,n),这是为了保证由一辆车辆服务一个客户点的合理性.客户点i的卸货时间为UTi,允许车辆服务的时间窗约束为[ETi,LTi],即最早允许车辆到达时间为ETi,最迟允许车辆到达时间为LTi.(我们这里考虑的是硬时窗限制,即车辆必须于此时间窗内到达,否则不予接受,与硬时窗对应的是软时窗限制,软时窗限制下,车辆若提前到达客户点,则需等待,若迟到,则需交纳一定罚金.)中心与客户、客户与客户之间的广义运输费用为cij,运输时间为tij(i,j=0,1,2,…,n,服务中心编号为0,客户编号为1,2,…,n).此时车辆路径问题的目标就是合理安排运输车辆并确定每辆车的运输路线,使得总费用最低.另外为简化和明确问题,我们给出以下假设：1)所有任务都是事先安排的,调度问题是静态的.2)每辆车在执行任务完毕后必须再回到原来所在位置,即再回到集货中心.3)成本简化为运输成本(与路径有关).为建立模型,定义二进制变量如下：1k0ijkijx，一辆类型车辆从点行驶到点；，否则。1k0kiiy，一辆类型车辆给客户点送货；，否则。则车辆路径问题的模型建立如下：目标函数:minZ=ijijkijkcx4约束条件:11,(1),1,2,,(2)1,1,2,,(3),0,1,2,,;ikiiiiiKkiknijkkijgyqkETRTLTinyinxyink001,2,,(4),1,2,,;1,2,,(5)()(6)nnihkhjkijijkKxxhnkKXxS其中,(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.1C-W节约算法的改进5由于C-W节约算法起初是为解决旅行商问题提出的,它不考虑各种约束条件,故无法直接用来求解VRP问题.但我们可以通过加入检验车辆载重约束和时间窗约束来完善C-W节约算法,使之能够求解单类型车辆路径问题.车辆载重约束:在连接点i和点j之前,先检验连接后的车辆装载量是否超过车辆的载重,若不超过,则可以连接,否则,不允许连接这两点,并转向其他可能的连接.用数学表达式来表述,即为:设路线00i的货运量为Gi,路线00j的货运量为Gj,只有当Gi+Gjq时,才允许连接点i和点j,形成路线00ij.Gi和Gj通过累加线路上各客户点的需求得到.时间窗约束:时间窗约束主要考虑由于点j与点i连接而引起的车辆到达点j及j后面各点(如果有的话)的时间变化.为方便对时间窗约束进行计算,我们做出以下假设[12]:令EFi表示连接点i和点j后车辆到达点j的时间变化量,则:EFj=RTi+UTi+tij-RTj.当EFj0时,车辆到达点j的时间提前;EFj=0说明车辆到达点j的时间不变;EFj0,车辆到达点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).64)计算将点i点j连接所引起的时间变化量EFj:①若EFj=0,转向步骤5);②若EFj0,计算j,若|EFj|j,则转向步骤5),否则转向步骤6);③若EFj0,计算j,若|EFj|j,则转向步骤5),否则转向步骤6).5)连接点i和点j,并计算该路线上车辆到达各个客户的时间.6)消去集合M中的元素s(i,j),且点i和点j分别不能作为车辆的发点和收点,故对i,将s(i,p)(p=1,2,…,n)消去,同法消去元素s(p,j).若M=,则算法终止,否则转向步骤2).2.2针对其他具体约束所作的改进上述对C-K节约算法的改进是比较基本的,也有很多文献在经典VRP问题中加入新的条件和约束,使之与实际联系更加紧密,如王海丽等[3]建立了易腐食品冷藏车辆配送模型,与传统车辆路线相比,该种模型中增加了冷藏费用,且冷藏成本不仅与路程有关,还与卸货时间有关,因为卸货时会产生热交换,造成制冷成本增加.而且由于送货过程中冷气打开,而送货结束返回服务中心时车辆没有货物,冷气关闭,造成初始路径0-i-0中,00iicc,则节约成本需严格按照原有格式进行计算,连接任意两点的节约值为00ijijijsccfc(其中f为派出一辆车的固定成本).可重复路径优化问题也得到了一定的研究,该类问题取消了每个客户只能有一辆车服务的约束条件,这样在某些情况下可减少出车的数量.丁宝录等[14]研究了在最少车辆的情况下,如何来降低行车距离.可重复运输的思想可由图2表示:7图2实施可重复运输前后比较示意图3.结语C-W节约算法思想简单,在解决旅行商问题时是一种很好的算法,可以快速得到问题的满意解.通过对此算法进行改进,加入车辆装载量约束和客户需求时间窗约束,我们即可利用其解决带时间窗约束的车辆路径问题.本文对应用于单类型车辆路径问题的节约算法进行了推广