运输组织学课程设计-有时间窗约束的车辆调度优化方法.doc

运输组织学课程设计说明书运输组织学课 程 设 计 说 明 书题目： 有时间窗约束的车辆调度优化方法 姓名： 班级： 441205 学号：指导教师： 吉林大学交通学院二零一四年十一月目录第1章 绪论1.1车辆优化调度问题（VSP）31.2 C-W节约启发式算法3第2章 优化方法2.1 问题描述32.2 算法原理42.3 算法步骤5第3章 具体案例应用3.1 问题重述53.2 解决过程7第4章 总结与感想参考文献9附录 程序代码1. Lingo程序代码92. C语言代码113.Floyd算法程序15第1章 绪论1.1车辆优化调度问题（VSP）车辆路径问题(Vehicle Routing Problem, VRP)最早是于1959年首次提出的,它是指有一定数量的客户,各自有不同数量的货物需求,一个中心仓库提供这些货物,并有一个车队负责分送货物,要求组织适当的行车路线,使客户的需求得到满足,并能在满足一定的约束条件下,达到诸如路程最短、成本最小、耗费时间最少等目的。 有时间窗车辆路径问题(Vehicle Routing Problem with Time Window,VRPTW ) 是在基本VRP中对每个客户的开始服务时间范围加以约束,与实际情况更加吻合, 因此有很强的实用背景。在配送运输上，时间窗口显得越来越重要。因此，降低 运输成本，提高配送的及时性和配送的服务质量，优化车辆路径问题，是降低企 业成本的迫切需要。相对一般的集货或送货非满载 VSP 来说，对于有时间约束的集货或送货的非满载 VSP 问题越来越受到人们的关注。本文针对多点配送调度问题，引用了一个实际案例，对旅行 商的C-W 算法进行修正，采用C-W 节约启发式算法对带有时间要求的硬时间窗车辆优化调 度问题进行了求解和分析，得到了满足货运需求的费用最小的运输路线，从而在一定程度上实现了非满载车辆的优化调度。1.2 C-W节约启发式算法12 C-W 节约算法的主要思想是:首先将各个客户点与中心仓库相连，构成一条仅含一个客户点的送货路线，并计算总路程;然后计算将两个客户点连接在一条线路上的路程节约值，节约值越大，说明将两个客户点连在一起的总路程减少得越多，直到节约值0为止。该算法可以很快求出较优解，但不一定会是最优解。第2章 优化方法2.1 问题描述一般地，非满载VSP可描述为：有一个车场，有L个（1,2，L）客户。第i个客户的货运量为gi(i=1,2，L)，需从车场派出载重量为q的货车来承运，已知giq，求满足货运需求的最短行车路线。为了安排路线，需要预先对需要的车辆数进行估计。可通过下式确定车辆数， m=inti=1Lgi/aq+1 (1)式中，int表示不大于括号内数字的最大整数；0a1，是对装车（或卸车）的复杂程度及约束多少的估计。将车场编号为0，客户及车场以点i（i=0,1,L）来表示。以Cij表示为从点i到点j的运输成本（距离、费用、时间等），在此采用客户i,j之间的距离dij，目标为使车辆的总运输距离最短。设tij为车辆从客户i行驶到客户j的时间，用Ei表示客户i的运货任务的开始时间，Li表示该任务的终止时间，Ti为完成该任务所需的时间（装货或卸货）。设任务i的开始时间需要在一定的时间范围内ETi,LTi,其中，ETi 为任务i 允许最早开始的时间，LTi 为任务i 允许最迟开始的时间。2.2算法原理3定义变量xijk=1，车辆k由点i驶向点j；0，否则yik=1，点i的货运任务由车辆k完成；0，否则则得到数学模型如下：目标函数：minz=i=0lj=0lk=1mcijxij； （2），约束条件：k=1myik=1，i=1,2，l； （3）i=0lxijk=yjk，j=0,1，l；k=1,2，m； （4）j=0lxijk=yjk，i=0,1，l；k=1,2，m （5）xijk=0或1，i,j=0,1,l；k=1,2,m； （6）yki=0或1，i=0,1,l；k=1,2,m； （7）ETiSiLTi, i=0,1,l； （8）giykiq, i=0,1,l；k=1,2,m。 （9）在上面的模型中，式（2）为模型的目标函数，即，使车辆在完成全部配送任务时的所需要的最短的运行距离或运行时间；式（3）为点i的客户由车辆k完成的唯一性约束；式（4），（5）为到达某个客户的车辆唯一性约束；式（6）表示车辆k是否从点i行驶到点j；式（7）表示点i的客户是否由车辆k完成；式（8）为客户对配送车辆的时间窗约束，式（9）为车辆的载重约束，即某辆车所访问的全部客户的需求量不能超过车辆本身的载重量。在实际配送活动中，还会存在很多复杂的条件，需要考虑的约束会更多。我们考虑的是比较理想的情况。以Cij 表示车辆从点i 到点j 的费用，由C-W 算法得到点i 和点j 连接在一条线路上的节约值：S(i,j)=Ci0+C0j-Cij。 上述案例问题描述已经假设以si 表示车辆到达点i 的时间，tij 表示车辆由点i 行驶到j 的时间，则有下列关系式：s0=0，ETisiLTi。 以 EF 表示连接点 i 和点 j 所在的线路后，车辆到达j的时间比原线路上车辆到达j 点时间的推迟（或提前量），则EFj 可表示为：EFj=si+Ti+tij-sj。显然，EFj0 时，到达时间推迟。 为说明问题方便，定义参数如下：- j 车辆在线路上 j 点后面的各任务均不需要等待的 j 点的到达时间的最大可以提前量； + j 线路上j 点后面的任务不违反时间窗约束的j 点的到达时间的最大允许推迟量。 分别可以按下式计算：- j = minsr-ETr ，+ j = minLTr-sr ，rj当考虑连接点i 和点j 所在的线路时，需检查是否违反时间窗约束。 （1） 当EFj0 时，若有|EFj|+ j，则 j 后面的任务的执行不会延迟，否则，要延迟进行。2.3 算法步骤 根据上述算法原理，设计具体求解步骤如下：Step1:计算s(i,j),令M =s(i,j)|s(i,j)0; Step2:在M 内按s(i,j)从大到小的顺序排列； Step3:若 M = ，则终止，否则对第一项 s(i,j),考察对应的（i，j）,若满足下述条件之一：（1）点i 和点j 均不在已构成的线路上；（2）点i 或点j 在已构成的线路上，但不是线路的内点（即不与配送中心相连）；（3）点i 和点j 位于已构成的不同线路上，均不是内点，且一个是起点，一个是终点,则转下步，否则转step7。 Step4:考察点i 和点j 连接后的线路上总货运量Q，若Qq,则转下步，否则转step7。 Step5:计算EFj。（1）若EFj =0，则转step6; （2）若EFj 0，则计算 +j ，当|EFj|+j，则转step6，否则转step7; Step6:连接点i 和点j,计算车辆到达各任务点的新时间,转step7。Step7:令M=M-s(i,j),转step3。第3章 具体案例应用3.1问题重述现在我们引用一个实际案例，假设了相应的时间约束与各配送点的任务量，采用 C-W 节约启发式算法求解和分析了此种带有时间窗约束的非满载车辆优化调度问题，得到了最优路线，从而在一定程度上达到了总运行费用最少的目标，实现了非满载车辆的优化调度。 案例问题描述与情景假设 ：有8项货物运输任务（编号为1，2，8），各任务的货运量gi（单位：吨）。装货（或卸货）时间Ti（单位：小时）以及要求每项任务开始执行的时间范围ETi,LTi(单位：时刻)由表1给出。这些任务由车场0发出的容量为8吨的车辆来完成，车场0与各任务点间的距离（单位：公里）由表2给出。表1 任务的特性及要求任务i12345678gi21.54.531.542.53Ti121322.530.8ETi,LTi1,44,61,24,73,5.52,55,81.5,4 表2 点对之间的距离0123456780040607590200100160801400654010050751101002606507510010075757537540750100509090150490100100100010075751005200501005010007090756100757590757007010071601107590759070010088010075150100751001000这里，假设车辆的行驶时间与距离成正比，每辆车的平均行驶速度为50 公里/小时，则从点i 到j 的行驶时间，tij=dij/50，见表3。又把各点之间的距离作为费用，即cij=dij（i,j=0,1,8）,安排车辆的行驶路线，使总运行费用最少。表3点对点之间车辆行驶时间3.2解决过程3.2.1 计算所需车辆及节约里程 由式（1）得，此问题所需车辆为： m=int(2+1.5+4.5+3+1.5+4+2.5+3)/8+1=3（辆)计算各点之间的连接费用节约值s（i，j）并按从大到小的顺序示于表4中。 表4 各点对之间的连接费用节约值 单位：km（I,j）（5，7）（5，6）（3，5）（5，8）（4，5）（1，5）（6，7）s(i，j)270230225205190190190（I,j）（4，7）（2，5）（2，7）（3，7）（7，8）（4，6）（1，7）s(i，j)17516014514514011590（I,j）（2，6）（3，6）（6，8）（1，3）（4，8）（1，6）（2，8）s(i，j)85858075706565（I,j）（3，4）（2，3）（2，4）（1，2）（1，4）（1，8）（3，8）s(i，j)65605035302053.2.2构造线路初始时，当车辆从车场0开往任务i时，若EFit0iLTi，取si=t0i，若t0iETi，取si=ETi。构造过程见表5。表5 点对之间连接过程i-j两点位置Q=qiEFi=Si+Ti+tij-Sj-j或+j是否连接Sk=Sk+EFj（kj)57非线路上Q=q5+q7=4885非线路上，外点Q=7825一点为内点7273外点，非线路上Q846不在线路上Q=7868两起点13非线路上Q=6.5823非线路上，外点Q=8EF3=6+3=342非线路上，外点Q812非线路上，外点Q=8EF2=1.6+2=2312S2=5.63.2.3 求解结果与分析由表5我们得出具体路线:表6 具体路线车辆编号行驶路径总路程(km)10-8-5-7-091020-6-4-030-3-1-2-0进一步，我们来检验我们的解，列出到达每个任务号的时间及其时间窗。表7 到达每个任务号的时间及其时间窗任务号1234到达时间3.35.61.56时间窗1,44,61,24,7任务号5678到达时间3.527.71.6时间窗3.5,52,55,81.5,4显然，各任务的开始时间均满足时间窗的约束。3.2.4 结果分析通过以上的车辆行驶路径方案发现，所有的车辆都是在送完货后直接回到车场0，但是若不规定车辆送完货后就直接回到车场0，则车辆在回去的过程中可能绕过某个任务区域回去更近。采用组合策略的Floyd算法，求出各点间的最短行驶距离。列出各个点间最短路径经过的中间点，如表8所示。表8 各点间最短路径所经过的中间点点号012345678000000102010000000002000000000300000000540000000005100000000600000000072000000008000500000表8中，0表示这两点间直接行驶最近，数字则表达要经过的点号。这样，我们可以求出一个更优的车辆行驶路线安排方案： 表9改进车辆的行驶路径安排方案车辆编号行驶路径总路程（km）10-8-5-7-2-088520-6-4-030-3-1-2-0第4章 总结与感想C-W启发式算法能够较好地解决有硬时间窗约束的车辆优化调度问题。在解 决算例后，我们还提出了最短路的修正。在物流配送中，有一定的参考价值。但 硬时间窗始终比较理想化，我们应将其软，早到和迟到都加上惩罚因子(相当于以一定的速度在路上跑)，算入总路程，以新目标函数和软时间窗约束再进行优化。我们在解决问题时设定在单一物流配送中心、单一车型、单一商品等条件下进行配送服务，而物流配送社会化、共同化是其发展趋势，商品种类空前增加，实际中用户的时间窗也是不确定的，所以有必要研究多配送中心、多车型、多种商品和随机时间窗等条件下车辆路径优化问题的动态规划模型。就C-W算法而言，具有在计算机上容易实现、编程简单,易于调整,理念朴素、方法易行、效果理想等优点,并获得了最优解。在小规模的站点不太多的客户配 送优化中,节约算法得到的解与精确最优解很接近,并且能够很快给出结果。但规模变大后，精度变差。这时可以选择人工免疫算法等更现代的方法。参考文献 :1 李军.有时间窗的车辆路线安排问题的启发式算法J.系统工程，1996。 2 宋伟刚,张宏霞,佟玲.有时间窗约束非满载车辆调度问题的节约算法J. 东北大学学报( 自然科学版)，2006。 3 马华伟.带时间窗车辆路径问题及其启发式算法研究,博士论文,合肥工业 大学,2008。附录：程序代码1.lingo程序代码：model:sets:kehu/k0.k8/:time1,time2,xiehuo,q,T;car/car1.car3/;drive(kehu,kehu):time,distance;plan(kehu,kehu,car):x;endsetsdata:time1=0 1 4 1 4 3.5 2 5 1.5;time2=15 4 6 2 7 5 5 8 4;xiehuo=0 1 2 1 3 2 2.5 3 0.8;q=0 2 1.5 4.5 3 1.5 4 2.5 3;distance=0 40 60 75 90 200 100 160 8040 0 65 40 100 50 75 110 10060 65 0 75 100 100 75 75 7575 40 75 0 100 50 90 90 12590 100 100 100 0 100 75 75 100200 50 100 50 100 0 70 90 75100 75 75 90 75 70 0 70 100160 110 75 90 75 90 70 0 10080 100 75 150 100 75 100 100 0;time=0 0.8000 1.2000 1.5000 1.8000 4.0000 2.0000 3.2000 1.60000.8000 0 1.3000 0.8000 2.0000 1.0000 1.5000 2.2000 2.00001.2000 1.3000 0 1.5000 2.0000 2.0000 1.5000 1.5000 1.50001.5000 0.8000 1.5000 0 2.0000 1.0000 1.8000 1.8000 2.50001.8000 2.0000 2.0000 2.0000 0 2.0000 1.5000 1.5000 2.00004.0000 1.0000 2.0000 1.0000 2.0000 0 1.4000 1.8000 1.50002.0000 1.5000 1.5000 1.8000 1.5000 1.4000 0 1.4000 2.00003.2000 2.2000 1.5000 1.8000 1.5000 1.8000 1.4000 0 2.00001.6000 2.0000 1.5000 3.0000 2.0000 1.5000 2.0000 2.0000 0;enddatamin=sum(plan(I,J,K):distance(I,J)*x(I,J,K); sum(kehu(J)|J#gt#1: sum(car(K):x(1,J,K)=3;for(car(K): sum(kehu(I): q(I)*sum(kehu(J):x(I,J,K)=8);for(car(K):sum(kehu(J)|J#gt#1:x(1,J,K)=1);for(car(K):sum(kehu(J)|J#gt#1:x(J,1,K)=1);for(kehu(I)|I#gt#1: sum(kehu(J): sum(car(K):x(I,J,K)=1);for(kehu(J)|J#gt#1: sum(kehu(I): sum(car(K):x(I,J,K)=1);for(kehu(J)|J#gt#1: sum(kehu(I): sum(car(K):x(I,J,K)*(T(I)+xiehuo(I)+time(I,J)-T(J)=0);for(kehu(I)|I#gt#1: BND(time1(I),T(I),time2(I);for(plan:BIN(x);End2.C语言代码：#include#include#includeint main()float min(float,float);inti,j,s99=0,n=8,L9=0,Q=8,Ln=0,M4=0,jb=0,ib=0,a=0,b=0,N=5=0,x=0,y=0;float t99=0,DERTAa1,DERTAa2,DERTAb1,DERTAb2,k9,EF100,qq=0,q8=0;float g9=0,2,1.5,4.5,3,1.5,4,2.5,3;float T9=0,1,2,1,3,2,2.5,3,0.8;float ET9=0,1,4,1,4,3,2,5,1.5;float LT9=0,4,6,2,7,5.5,5,8,4;int d99=0 40 60 75 90 200 100 160 80 40 0 65 40 100 50 75 110 100 60 65 0 75 100 100 75 75 75 75 40 75 0 100 50 90 90 150 90 100 100 100 0 100 75 75 100 200 50 100 50 100 0 70 90 75 100 75 75 90 75 70 0 70 100 160 110 75 90 75 90 70 0 100 80 100 75 150 100 75 100 100 0;printf(“各任务的货运量gi如下：n”;for(i=1;i=n;i+)printf(“g%d=%-5.1f”,i,gi);printf(“nnn”)；printf(“各任务的装货（或卸货）时间Ti为:n”);for(i=1;i=n;i+)printf(“g%d=%-5.1f”,i,Ti);printf(“nnn”)；Printf(“各任务的开始执行时间范围ETi,LTi为:n”);For（i=1;i=n;i+）printf(“ET%d,LT%d=%-3.1f,%-3.1fn”,i,i,ETi,LTi);Printf（“nnn”）;Printf(“车场0与个任务点间的距离dij为:n”);For(i=0;j=8;i+);for(j=0,j=8;j+);printf(“%5d,dij;);Printf(“n”);Printf(“nn”);Printf(“点对之间连接费用的节约值sij为:n”);For(i=1;i=8;i+);for(j=i+1;j=8;j+);sij=di0+d0j-dij;For(i=1;i=8;i+);for(j=i+1;j=8;j+);printf(“s%d%d=%-5d”,i,j,sij);Printf(“n”);Printf(“n”);For(i=0;i=8;i+);for(j=0;j=8;j+);tij=(float)dij/50;For(i=0;i=ETi)&(t0i=LTi)ki=t0i;If(t0iETi)ki=ETi;While(1)ib=0;jb=0;for(i=1;i=8;i+)for(j=i+1;jsab) a=i;b=j;If(sab=0)break;N1=0;N2=M1;N3=M1+M2;N4=M1+M2+M3;for(i=0;i8;i+)if(Li=a)jb=1;x=i;for(j=0;jQ)sab=0;continue;EFb=ka+Ta+tab-kb;EFa=kb+Tb+tab-ka;DERTAb1=LTb-kb;DERTAb2=kb-ETb;DERTAa1=LTa-ka;DERTAa2=ka-ETa;If(EFb=0;&(DERTAb1=EFb)|(EFb=(0-EFb)LN4=a;LN4+1=b;Ln=Ln+1;qLn=qq;Kb=kb+EFb;Sab=0;MLn=MLn+2;Continue;else if (EFa=0;&DERTAa1=EFa)|(EFa=(0-EFa)LN4=b;LN4+1=a;Ln=Ln+1;qLn=qq;ka=ka+EFa;sab=0;MLn=MLn+2;Continue;if(ib=0&jb=1)i=a;a=b;b=i;x=y;ib=1;jb=0;if(ib=1&jb=0)if(x=N1|x=N2|x=N3i=a;a=b;b=i;for(i=1;iQ)sab=0;contin