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

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

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

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

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

7、心给每位客户每次的配送量、配送周期与最有车辆行驶路径。三、 模型假设（1） 每个客户的需求只能由一辆配送车满足；（2） 每辆车送货时行驶的路程不超过它所能行驶的最远路程；（3） 中心仓库的车辆总数大于或等于当派送费用最小时所需的车辆数；（4） 从配送中心到各个用户、各个用户之间的运输距离已知；（5） 配送中心有足够的资源以供配送。四、 符号说明：运货车的容量：该配送中心服务的客户总数: 派送费用最小时所需的车辆数：第i位客户所需货物：车k由i驶向j：点i的货运任务友s车完成：第i位客户最早允许接货时间：第i位客户最晚允许接货时间：车辆在第i位客户处等待时间:车辆在第i位客户处迟到时间：第i位客

8、户处车辆到达时间：从第i位客户到第j位客户所需时间：第i位客户处装货（或卸货）所需时间：第i位客户与第j位客户之间的距离：车辆行驶单位距离的运输成本：车辆早到单位时间产生的等待损失：车辆迟到单位时间应承担的惩罚：派送货物产生的总损失A：运输成本B：车辆早到所产生总的等待损失C：车辆迟到所受的总惩罚五、 模型的建立和求解5.1 问题一模型的建立及求解： 5.1.1问题的分析中心仓库为了给N个客户派送货物，供发出m辆车，为了派货的节约和方便，每辆车载着适量的货物出发，可以给某一片的若干个满足约束条件的客户派送货物，见图一：图一 中心仓库派送货物图中心仓如上图库派送货物时，必须满足约束条件：（1）

9、各个客户群的总需求小于或等于运输车的装载量；（2） 每个客户都必须且只能由一辆运输车运输所需货物；（3） 运输车为每位客户开始服务的时间必须尽可能在时间窗内。根据如上的约束条件，我们可以得到很多可行解，但考虑到以所选行车路径产生的总费用最小为目标的情况下，我们可以建立最优化模型确定最佳的车辆派送方案，最优路径产生图如下： 图二 最优路径产生图5.1.2模型的建立（1）中心仓库使用车辆数量的确定设配送中心需要向N个客户送货，每个客户的货物需求量是gi（i1，2，.N），每辆配送车的载重量是Q，且giQ。首先为了安排路线需要对要使用的车辆数有一个估计。在现实情况中，货物装（卸）车越复杂，约束条件越

10、多，一辆车的实际载货量就越小。在本文中使用文献1的公式来确定需要的车辆数m： 表示取整，a为参数，0acitynum s(i,j)=0; end endend%-%主程序function gaf,p=objf(s)gn=1;while gngnmax+1 for j=1:2:inn seln=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,:)=chan

11、g(scnew(j+1,:),pm); end s=smnew; %产生了新的种群 f,p=objf(s,dislist); %计算新种群的适应度 %记录当前代最好和平均的适应度 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); hold on;plot(ymean,b);grid;title(搜索过程);legend(最优解,平均解);function pcc=pro(pc);te

12、st(1:100)=0;l=round(100*pc);test(1:l)=1;n=round(rand*99)+1;pcc=test(n); %-%计算适应度function f,p=objf(s);y=zeros(citynum+1,citynum+1);for i=1:inn-1 a=s(i,:); for j=1:KM-1 m=a(j); n=a(j+1); m=m+1; n=n+1; end y(m,n)=1;y=y;for i=1:citynum for j=1:citynum mubiaob=c(i,j)*y(i,:); endendxuq1=0; for i=1:citynum

13、 for j=1:citynum xuq1=xuq1+s(i)*y(i,:)-q(i); end xuqiu=max(xuq1),0)*M; endendshij1=0;shij2=0;for i=1:citynum for j=1:citynum for l=1:citynum shij1=shij1+t(i)-a(i); shij2=shij12+b(i)-t(i); end shij3=max(shij1),0); shij4=max(shij2),0); shijian=M*shij3+M*shij4; endendf=mubiao+xuqiu+shijian;f=1/f;end%-%

14、计算选择概率fsum=0;for i=1:inn fsum=fsum+f(i);endfor i=1:inn ps(i)=f(i)/fsum;end%计算累积概率p(1)=ps(1);for i=2:inn p(i)=p(i-1)+ps(i);endp=p;p%-%“选择”操作%从种群中选择两个个体function seln=sell(s,p) inn=size(p,1);for i=1:2 r=rand; %产生一个随机数 prand=p-r; j=1; while prand(j)0 j=j+1; end seln(i)=j; %选中个体的序号endsel1=seln(1);sel2=se

15、ln(2);%-%“交叉”操作function snew=cross(A,B,pc)A=s(sel1,:);B=s(sel2,:);c=find(A=0);d=find(B=0);a=sym(A);b=sym(B);k=size(a,2);for i=1:size(a,2) for j=1:k e(i,c(k)=a(i+k-1); endendfor i=1:size(a,2) for j=1:k e(i,d(k)=b(i+k-1); endendc0=round(rand*(k-1)+1;c1=round(rand*(k-1)+1;a=f(:,c0),a;b=e(:,c1),b;for i=

16、1:size(a,2); j=1:size(e,2) if a(i)=e(j) a(i)=; endendfor i=1:size(b,2); j=1:size(f,2) if b(i)=f(j) b(i)=; endenda=double(a);b=double(b);g=zeros(size(A);for i=1:size(a) for j=1:size(c) g(i+j)=a(i); endendh=zeros(size(A);for i=1:size(b) for j=1:size(d) h(i+j)=b(i); endendg=g;h=h;snew=g h;%-%变异function

17、 snew=chang(snew,pm)bn=size(snew,2);snnew=snew;c2=round(rand*(bn-2)+1; %在1,bn-1范围内随机产生一个变异位c3=round(rand*(bn-2)+1;chb1=min(c2,c2);chb2=max(c3,c2);x=snew(chb1+1:chb2);snnew(chb1+1:chb2)=fliplr(x);pmm=pro(pm); %根据变异概率决定是否进行变异操作，1则是，0则否if pmm=1 c2=round(rand*(bn-2)+1; %在1,bn-1范围内随机产生一个变异位 c3=round(rand*(bn-2)+1; chb1=min(c2,c3); chb2=max(c2,c3); x=snew(chb1+1:chb2); snnew(chb1+1:chb2)=fliplr(x);end18