带时间窗物流配送车辆路径问题

1、文档来源为 :从网络收集整理.word 版本可编辑.欢迎下载支持带时间窗物流配送车辆路径问题摘要本题是一个带有时间窗的车辆路径安排问题（VRPTW题）。根据题目条件,本文建立了一个求解最小派送费用的VRPT怵化模型，采用遗传算法，给出了该模型的求解方法。然后，对一个实际问题进行求解，给出了一个比较好的路线安排方式。模型一（见，在需求量、接货时间段、各种费用消耗已知的情况下，决定采用规划模型，引入0-1变量，建立各个约束条件，包括车辆的容量限制，到达每个客户的车辆和离开每个客户的车辆均为1的限制，总车辆数的限制，目标函数为费用的最小化，费用包括车辆的行驶费用，车辆早到或晚到造成的损失。模型一的求

2、解采用遗传算法（见，对题目给出的实际问题进行求解，得到3条行车路线，总路线长度为910公里，具体结果如下：车辆编号所执行的任务路线到达各点的时间路线长度货运量10-3-1-2-00-1.5-3.3-5.6-8.875+40+65+60=2404.5+2+1.5=820-8-5-7-00-1.6-3.9-7.7-13.980+75+90+160=405F3+1.5+2.5=730-6-4-00-2-6-10.8100+75+90=2654+3=7考虑在车辆返回时选择最短路线，我们采用Dijkstra算法求出中心仓库到各个客户的最短距离，将结果改进为885公里,具体结果如下：车辆编号所执行的任务路

3、线到达各点的时间路线长度货运量10-3-1-2-00-1.5-3.3-5.6-8.875+40+65+60=24014.5+2+1.5=820-8-5-7-2-00-1.6-3.9-7.7-13.980+75+90+135=3803+1.5+2.5=730-6-4-00-2-6-10.8100+75+90=2654+3=7模型二考虑需求量随机变化时的安排方案，假设客户需求量遵循正态分布，首先按照需求期望根据模型一得到一个比较好的方案，然后按照这一方案进行送货，在送货过程中，如果出现需求量过大的情况，允许车辆返回仓库进行补充。模型一的思路清晰，考虑条件全面。但最优解解决起来困难，遗传算法只是一种

4、相对好的解决方法，可以找出最优解的近似解。模型二的想法比较合理，易于实施，但还有待改进。关键词：规划时间窗物流车辆路径遗传算法1、 问题重述一个中心仓库，拥有一定数量容量为Q的车辆，负责对N个客户进行货物派送工作，客户i的货物需求量为q,且qQ,车辆必须在一定的时间范围ai,b内到达，早于ai到达将产生等待损失，迟于bi到达将处以一定的惩罚,请解决如下问题：（1）给出使派送费用最小的车辆行驶路径问题的数学模型及其求解算法。并具体求解以下算例：客户总数N=8,每辆车的容量Q=8（吨/辆），各项任务的货运量qi（单位:吨）、装货（或卸货）时间si（单位：小时）以及要求每项任务开始执行的时间范围ai

5、,bi由附录1给出，车场0与各任务点以及各任务点间的距离（单位：公里）由附件二给出，这里假设车辆的行驶时间与距离成正比，每辆车的平均行驶速度为50公里/小时，问如何安排车辆的行驶路线使总运行距离最短；（2）进一步请讨论当客户i的货物需求量qi为随机参数时的数学模型及处理方法。2、 问题分析本题主要在两种不同情况下，研究使派送费用最小的车辆行驶路径问题。车辆行驶派送的费用主要包括运输成本、车辆在客户要求到达时间之前到达产生的等待损失和车辆在客户要求到达时间之后到达所受惩罚等等。为满足派送费用最小的需求，即要使所选行车路径产生的总费用最小，从而确定出最佳的车辆派送方案。当客户i的货物需求量qi固定

6、时，首先，我们根据题意，取若干辆车进行送货，然后，主要考虑每辆车各负责哪些客户的送货任务，我们可以给出满足题中限制条件的很多参考方案供选用，并考虑以所选行车路径产生的总费用最小为目标的情况下，建立最优化模型确定最佳的车辆派送方案。进一步讨论，当客户i的货物需求量qi为随机参数时，我们首先可以简化随机模型，根据客户i的货物需求量的期望与方差，确定每天应该运送给客户i的货物量，即qi，再根据第一题，确定最佳的车辆派送方案。但考虑到客户的储存能力有限及货物在客户处的储存费用，客户不需要将一天的货物一次性接收完，只要满足缺货的情况出现的概率很低，客户可以让配送中心一天几次送货，这样可以得到很多满足约束

7、的方案，考虑以单位时间的储存费用最小为目标，建立最优化模型，确定配送中心给每位客户每次的配送量、配送周期与最有车辆行驶路径。三、模型假设1） 每个客户的需求只能由一辆配送车满足；2） 每辆车送货时行驶的路程不超过它所能行驶的最远路程；3） 中心仓库的车辆总数大于或等于当派送费用最小时所需的车辆数；4） 从配送中心到各个用户、各个用户之间的运输距离已知；5） 配送中心有足够的资源以供配送。四、符号说明Q:运货车的容量N:该配送中心服务的客户总数m:派送费用最小时所需的车辆数q：第i位客户所需货物Xjk：车k由i驶向jyis:点i的货运任务友s车完成ai：第i位客户最早允许接货时间bi：第i位客户

8、最晚允许接货时间D:车辆在第i位客户处等待时间Xi车辆在第i位客户处迟到时间ti：第i位客户处车辆到达时间tj:从第i位客户到第j位客户所需时问Si：第i位客户处装货(或卸货)所需时间Cj：第i位客户与第j位客户之间的距离c：车辆行驶单位跑离的运输成本d:车辆早到单位时间产生的等待损失e：车辆迟到单位时间应承担的惩罚Z:派送货物产生的总损失A:运输成本B：车辆早到所产生总的等待损失C:车辆迟到所受的总惩罚五、模型的建立和求解5.1 问题一模型的建立及求解：中心仓库为了给N个客户派送货物，供发出m辆车，为了派货的节约和方便,每辆车载着适量的货物出发，可以给某一片的若干个满足约束条件的客户派送货物

9、，见图一：图一中心仓库派送货物图中心仓如上图库派送货物时，必须满足约束条件：(1)各个客户群的总需求小于或等于运输车的装载量；(2)每个客户都必须且只能由一辆运输车运输所需货物；(3)运输车为每位客户开始服务的时间必须尽可能在时间窗内。根据如上的约束条件，我们可以得到很多可行解，但考虑到以所选行车路径产生的总费用最小为目标的情况下，我们可以建立最优化模型确定最佳的车辆派送方案，最优路径产生图如下：1 文档收集于互联网，如有不妥请联系删除文档来源为：从网络收集整理.word版本可编辑.欢迎下载支持图二最优路径产生图(1)中心仓库使用车辆数量的确定设配送中心需要向N个客户送货，每个客户的货物需求量

10、是gi(i=1,2,.小)，每辆配送车的载重量是Q,且gi<Q0首先为了安排路线需要对要使用的车辆数有一个估计。在现实情况中，货物装(卸)车越复杂，约束条件越多，一辆车的实际载货量就越小。在本文中使用文献1的公式来确定需要的车辆数m：表示取整，a为参数,0<a<1。约束条件越多，货物装(卸)越复杂，a值越小。参考文献2,取a为0.85。(2)引入01变量：1)Xjs表示车辆s是否从客户i行驶到客户jo定义其为01变量，则2)yis表示客户i的任务由车辆s完成。同样定义其为01变量，则(3)非线性规划模型的建立：a.目标函数的确定。题目要求所选行车路径产生的总费用最小，我们确定

11、总费用为目标函数，记为Z。总费用由运输成本A、等待损失B和迟到所收惩罚C组成，根据题意有：所以，总费用Z最小化为：b.约束条件的确定。约束1:车辆k的运送总重量应不超过车辆的最大载重，即车辆有一定的运送能力,则可引入约束条件，NqiyisQ(k1,2,m)i1约束2:每个客户只能由一辆车来配送，则可引入约束条件，约束3:保证到达一个客户的车辆也离开该客户，则可引入约束条件，mN。1(j1,2,3,N;)s1i1mNxijk1(i1,2,3,|,N;)s1j1C.变量之间关系的确定由上可确定等待时间Di,超时时间Xi为：车辆k从客户i到客户j需经过两段时间tj为：设车辆为客户i运送完货物后即为客

12、户j运送，则到达客户i处时间t和到达客户j处时间tj之间的关系为：d.此非线性规划模型为：我们采用遗传算法解决上面的问题：1 .编码采用自然数编码，即序数编码。货物运输路线可以编成长度为N+m勺染色体(0,i11,i12,|,i1s,0,i21|,i2t,0,|,0,im1,|,imw),其中，iik表示第iik项任务。0表示车场，m表示完成任务所需的车辆数。2 .出生初始群体初始群体随机产生，即产生N项货物运输任务点的全排列，如i1,i2,|,iN,s1s如果qjQ,且qjQ,将s至N的数向后移动一位，将0插入第s位。j1j1接着，继续上述操作，直到m个0全部插入为止。这样就构成了一条初始染

13、色体。用这种方法构造一个群体的染色体。如：82576314,该编码插零之后变成08250763014。它代表着需要三辆车运输货物。其中，第1辆车行走路线为08250,即从仓库出发到依次到8、2、5商店再回到仓库。第2辆车行走路线为07630,第3辆车行走路线为0140。3 .适应度函数bz'适应度函数取fkbz,其中fk为染色体Vk的适应度，b为常数，z'为初Zk始种群中最好的染色体的运输成本，Zk为染色体Vk对应的运输成本。4 .遗传算子选取最佳保留的轮盘赌复制法进行染色体的复制。变异算子采用反转变异。交叉算子用最大保留交叉，具操作过程为：a)若染色体交叉点处的两个基因都为0

14、,则直接进行顺序交叉运算；b)若染色体交叉点处的基因不全为0,则将交叉点左移(右移)，直到左右两个交叉处的基因都为0,再进行顺序交叉运算。5 .算法的实现步骤Stepl:采用自然数编码的方式，构造表示可行车路线的染色体；Step2：设置控制参数，包括交叉率pc0.7、变异率pm0.1、群体规模n10；Step3：初始化，令d0,随机产生初始群体p(0),群体中包括n个染色体，每个染色体代表一条行车线路；Step4:令i1；Step5：将群体p(d)中的第i个染色体译为线路长度；Step6：计算适应度；Step7:若满足算法终止条件，则停止，否则继续；Step8:ii1;Step9:若in,回至

15、Ustep5,否贝U,转step10;Step11:进行最大保留交叉、基于位的变异和倒位操作；Step12:dd1；Step13:若满足算法终止条件，则停止，否则转step4。运用matlab软件编写程序得到在车辆总行程最短的条件小的派送方案为:车辆编号所执行的任务路线到达各点的时间路线长度货运量10-3-1-2-00-1.5-3.3-5.6-8.875+40+65+60=24014.5+2+1.5=820-8-5-7-00-1.6-3.9-7.7-13.980+75+90+160=4053+1.5+2.5=730-6-4-00-2-6-10.8100+75+90=2654+3=7从上表可以看

16、出，按照上表的行车路线，总路线长度为910公里。从上面解出的派送方案可以看出，上面的每条路线在车辆送完货物后，直接从最后一个客户处返回中心仓库，我们通过求中心仓库到各个客户的最短路径可以发现，上面的返回路线不是最优的，返回路线可以经过某些客户使得所走路线最短。我们用Dijkstra算法求出中心仓库到各个客户的最短路径如下:编号012|3145678取短距离0406075909010013580根据上表，我们对，得到下表:车辆编号所执行的任务路线到达各点的时间路线长度货运量10-3-1-2-00-1.5-3.3-5.6-8.875+40+65+60=2404.5+2+1.5=820-8-5-7-

17、2-00-1.6-3.9-7.7-13.980+75+90+135=380F3+1.5+2.5=730-6-4-00-2-6-10.8100+75+90=2654+3=7根据上表计算结果，我们在不改变原路线的情况下，使总路线减小为885公里。5.2问题二模型的建立及求解：在问题一中，根据已知的各个商店的需求分布，根据遗传算法求解，预先确定一条总费用最小的路径（或者虽不是最优路径，但是此结果能够接受的）车辆沿该路径服务商店，因此服务商店的顺序固定不变。而问题二中，在车辆服务商店的过程中，事先并不知道商店的需求量。而这个不确定信息要随着车辆的服务逐步确定，商店具体的需求只有车辆到达用户后才确定。这

18、样第一问的求解方法得到的路径并不适用于第二问的求解。假设：（1）商店的需求变化符合正态分布，第i个商店的需求量的期望和方差分别为（2）商店的供货可以分为多次补充但在每次供货中最大程度满足用户需求，即只有出现当前车载余量小于用户需求量时才出现下一次的供货。基于第一问解决了在已知用户需求概率情况下，确定一个服务方案，满足所有n个商店的需求并且使车辆期望行程费用最小这个问题。我们由假设可知，第i个商店的需求量的期望为则由需求量的期望得到一个使车辆期望行程费用最小的服务方案，称该方案为Ao当用户的需求未知（当车辆服务商店时需求变成已知量）时，由于用户的需求量在区间（i3i）的概率是96%而在区间外的事

19、件可以看成小概率事件，由小概率事件定理可知，在一次试验中，小概率事件可以看成不可能事件。由此可知，用户需求量就在区间（i3i）里。由上面可知，服务方i2越小时（说明需求量用户需求在区间（i3i）里，而需求决定服务方案。案在A方案附近变化，而变化的幅度由方差；决定。当5文档收集于互联网，如有不妥请联系删除.文档来源为：从网络收集整理.word版本可编辑.欢迎下载支持接近一个常数期望J,最优方案（或满意方案）与A方案越接近（即在A方案上面稍作改动即可）。反之，A方案需作较大的方案。由假设（2）知，车辆只要满足当前用户部分需求，就服务该用户，用户未满足的部分以后再服务。在服务用户后，车辆根据当前的位

20、置信息、车载余量以及需要服务用户的信息，决定下一个服务用户（包括当前还未满足需求的用户）或回库房装载货物。先按A方案进行分配车辆路线（若增加车辆数目虽可以更好满足条件，但会增加多于开支）。假设m辆车都从仓库0出发，按A方案中的预定路线进行服务，当服务完第一个商店时，再判断剩余的货物量。此时货物量为Q'Qqi（其中Q为货车满载量，qi为车辆到达商店i时确定了i个商店的需求量）。然后判断该剩余量是否在大于下一个商店需求量（i3i），若大于则进行下一个商店服务，若小于则判断下个商店是否满足大于（i3i）这个条件，若满足，则对其进行服务，否则继续下个判断，直至其所有负责区域遍历完一遍。当判断其

21、负责区域所有的商店不满足条件时再判断该剩余量是否大于下一个商店需求量（i3i），若大于则进行下一个商店服务，若小于则判断下个商店是否满足大于（i3i）这个条件，若满足，则对其进行服务，否则继续下个判断，直至其所有负责区域遍历完一遍。若所有商店的需求量（i3i）大于车辆货物剩余量，则说明此车辆的剩余量不能满足其所负责的区域，因此该车辆需要回仓库进行货物补充。当货物补充完之后进行判断剩余未服务商店的时间窗口和路程距离进行判断（产生方法同于第二问A方案的产生方法），然后再进行服务。服务商店之后再进行前面的判断，直至其所有负责商店都被服务完回到仓库。六、模型的评价和推广6.1 模型的评价由5.1和5.

22、2建立的模型，我们得到了有软时间限制的物流配送车辆路径问题的解决办法。首先我们对问题进行了合理的假设，模型简化了实际中的复杂问题，考虑了主要的约束条件与目标，思路清晰，结果也基本符合实际。但是，模型对实际进行简化的同时忽略了实际中很多次要的条件，由累加效果可能会产生很大误差，同时，我们进行模型的求解时只是简单使用了遗传算法，没有对其进行改进。6.2 模型的推广1模型中不合实际的假设：（ 1） 在问题一和问题二总费用的组成上，我们没有考虑组织送货的费用，即每组织一辆车进行送货都需要一定的费用，我们设为S元/（次、辆）；（ 2） 在问题一中，我们假设每辆车送货时行驶的路程不超过它所能行驶的最远路程

23、，但是实际上，考虑到车辆行驶中的耗油等因素，每辆车的行驶最大距离都有限制，我们设车辆行驶的最大距离为L,我们可以得到约束条件：(3)在实际中，为了公平，每位送货车辆司机行驶的路程相差必须控制在一定范围之内，我们取这个差值的最大允许值为M则有：2.模型的推广目标函数：Nmin Z ci 0mcij xijss 1Nd * maxDi,0Ne* max Xi,0 mS1qiMs i 11,2,mmyiss 11,2,3,.N 0约束条件DiXiNxijs i 1Nxijk1aititibi1,2,3,|,N;1,2,3,|,N;1,2,.N1,2,. N9文档收集于互联网，如有不妥请联系删除.ti

24、jCj/Vi,j1,2,.NNmtjxjs(timaxDi,0tjs)i1s1NNxijscijLs1,2,.,mi0j0N Nxijs cij i 0 j 0N Nxijk cij i 0 j 0s, k 1,2,., m带入实际数据，由遗传算法即可求解出总费根据以上目标函数与约束条件,用最小的车辆行驶路径方案。七、参考文献1李军，谢秉磊，郭耀煌，非满载车辆调度问题的遗传算法。系统工程理论与实践，2000,20(3):235239;2邢文训，谢金星编著现代优化计算方法。北京：清华大学出版社，1999.140;3魏明高成修胡润洲，一种带时间窗和容量约束的车辆路线问题及其TabuSearch算法

25、，运筹与管理，Vol.11,No.3:P49-P53,2002;4胡大伟朱志强胡勇，车辆路径问题的模拟退火算法，中国公路学报，Vol.19No.4:P123-P126,20065阎庆鲍远律，新型遗传模拟退火算法求解物流配送路径问题，/detail.aspx?filename=HNSZ4&dbname=CJFD2008,2009/8/166张志霞邵必林，基于改进蚁群算法的运输调度规划，公路交通科技，Vo1.25No.4:P137-P140,2008;7杜文衰庆达周冉玲，一类随机库存/运输联合优化问题求解过程分析，中国公路学报，Vol.17No.1:P114-P118,2004.八、附录9

26、.1 附录一表1任务的特征及其要求任务i12345678qi（吨）21.54.531.542.53S（小时）121322.530.81,44,61,24,73,5.52,55,81.5,4表2点对之间的距离01234567800406075902001001608014006540100507511010026065075100100757575375407501005090901504901001001000100757510052005010050100070907561007575907570070100716011075907590700100880100751501007510010

27、009.2 附录二Matlab7.0程序：functiongatsp（s）sum=0;M=1000000;%无穷大数inn=100;citynum=8;K=2;文档来源为 :从网络收集整理.word 版本可编辑.欢迎下载支持gnmax=1000;%最大代数pm=0.8;%变异概率pc=0.2;c=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

28、,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;q=21.54.531.542.53;s=121322.530.8;a=14143251;b=46275.5584;%产生初始种群m=zeros(1,inn);m=m'KM=citynum+K-1;s=zeros(inn,citynum+K-1);fori=1:1:inns(i,:)=randperm(KM);ends=ms;fori=1:innforj=1:KM-1

29、ifs(i,j)>citynums(i,j)=0;endendend%主程序functiongaf,p=objf(s)gn=1;whilegn<gnmax+1forj=1:2:innseln=sell(s,ps);%选择操作scro=cross(s,seln,pc);%交叉操作scnew(j,:)=scross(1,:);scnew(j+1,:)=scross(2,:);smnew(j,:)=chang(scnew(j,:),pm);%变异操作smnew(j+1,:)=chang(scnew(j+1,:),pm);ends=smnew;%产生了新的种群f,p=objf(s,disl

30、ist);%计算新种群的适应度%记录当前代最好和平均的适应度fmax,nmax=max(f);ymean(gn)=1/mean(f);ymax(gn)=1/fmax;%记录当前代的最佳个体x=s(nmax,:);gn=gn+1;%pause;endgn=gn-1;figure(2);plot(ymax,'r');holdon;plot(ymean,'b');grid;title('搜索过程)；legend(最优解','平均解');functionpcc=pro(pc);test(1:100)=0;l=round(100*pc);t

31、est(1:l)=1;n=round(rand*99)+1;pcc=test(n);%计算适应度functionf,p=objf(s);y=zeros(citynum+1,citynum+1);fori=1:inn-1a=s(i,:);forj=1:KM-1m=a(j);n=a(j+1);m=m+1;n=n+1;endy(m,n)=1;y=y'fori=1:citynumforj=1:citynummubiaob=c(i,j)*y(i,:);endendxuq1=0;fori=1:citynumforj=1:citynumxuq1=xuq1+s(i)*y(i,:)-q(i);endxu

32、qiu=max(xuq1),0)*M;endendshij1=0;shij2=0;fori=1:citynumforj=1:citynumforl=1:citynumshij1=shij1+t(i)-a(i);shij2=shij12+b(i)-t(i);endshij3=max(shij1),0);shij4=max(shij2),0);shijian=M*shij3+M*shij4;endendf=mubiao+xuqiu+shijian;f=1/f;end%计算选择概率fsum=0;fori=1:innfsum=fsum+f(i);endfori=1:innps(i)=f(i)/fsum;end%计算累积概率p(1)=ps(1);fori=2:innp(i)=p(i-1)+ps(i);endp=p'p%“选择”操作%从种群中选择两个个体functionseln=sell(s,p)inn=size(p,1);fori=1: