《带时间窗物流配送车辆路径问题》由会员分享，可在线阅读，更多相关《带时间窗物流配送车辆路径问题（19页珍藏版）》请在金锄头文库上搜索。
1、带时间窗物流配送车辆路径问题摘要本题是一个带有时间窗的车辆路径安排问题（VRPTW 问题） 。根据题目条件，本文建立了一个求解最小派送费用的 VRPTW 优化模型，采用遗传算法，给出了该模型的求解方法。然后，对一个实际问题进行求解，给出了一个比较好的路线安排方式。模型一（见 5.1.2）针对问题一，在需求量、接货时间段、各种费用消耗已知的情况下，决定采用规划模型，引入 0-1 变量，建立各个约束条件，包括车辆的容量限制，到达每个客户的车辆和离开每个客户的车辆均为 1 的限制，总车辆数的限制，目标函数为费用的最小化，费用包括车辆的行驶费用，车辆早到或晚到造成的损失。模型一的求解采用遗传算法（见
2、5.1.3） ，对题目给出的实际问题进行求解，得到 3 条行车路线，总路线长度为 910 公里，具体结果如下：车辆编号所执行的任务路线 到达各点的时间 路线长度 货运量1 0-3-1-2-0 0-1.5-3.3-5.6-8.8 75+40+65+60=240 4.5+2+1.5=82 0-8-5-7-0 0-1.6-3.9-7.7-13.9 80+75+90+160=405 3+1.5+2.5=73 0-6-4-0 0-2-6-10.8 100+75+90=265 4+3=7考虑在车辆返回时选择最短路线，我们采用 Dijkstra 算法求出中心仓库到各个客户的最短距离，将结果改进为 885 公
3、里,具体结果如下：车辆编号所执行的任务路线 到达各点的时间 路线长度 货运量1 0-3-1-2-0 0-1.5-3.3-5.6-8.8 75+40+65+60=240 4.5+2+1.5=82 0-8-5-7-2-0 0-1.6-3.9-7.7-13.9 80+75+90+135=380 3+1.5+2.5=73 0-6-4-0 0-2-6-10.8 100+75+90=265 4+3=7模型二考虑需求量随机变化时的安排方案，假设客户需求量遵循正态分布，首先按照需求期望根据模型一得到一个比较好的方案，然后按照这一方案进行送货，在送货过程中，如果出现需求量过大的情况，允许车辆返回仓库进行补充。模
4、型一的思路清晰，考虑条件全面。但最优解解决起来困难，遗传算法只是一种相对好的解决方法，可以找出最优解的近似解。模型二的想法比较合理，易于实施，但还有待改进。1关键词：规划 时间窗 物流 车辆路径 遗传算法一、 问题重述一个中心仓库，拥有一定数量容量为 Q 的车辆，负责对 N 个客户进行货物派送工作，客户 i 的货物需求量为 ，且 ，车辆必须在一定的时间范iqi围 内到达，早于 到达将产生等待损失，迟于 到达将处以一定的惩罚，,iabiaib请解决如下问题：（1）给出使派送费用最小的车辆行驶路径问题的数学模型及其求解算法。并具体求解以下算例：客户总数 N=8,每辆车的容量 Q=8（吨/辆）, 各
5、项任务的货运量 （单位：iq吨） 、装货（或卸货）时间 （单位：小时）以及要求每项任务开始执行的时间is范围 由附录 1 给出，车场 0 与各任务点以及各任务点间的距离（单位：,iab公里）由附件二给出，这里假设车辆的行驶时间与距离成正比，每辆车的平均行驶速度为 50 公里/小时，问如何安排车辆的行驶路线使总运行距离最短；（2）进一步请讨论当客户 i 的货物需求量 为随机参数时的数学模型及处理方iq法。二、 问题分析本题主要在两种不同情况下，研究使派送费用最小的车辆行驶路径问题。车辆行驶派送的费用主要包括运输成本、车辆在客户要求到达时间之前到达产生的等待损失和车辆在客户要求到达时间之后到达所受
6、惩罚等等。为满足派送费用最小的需求，即要使所选行车路径产生的总费用最小，从而确定出最佳的车辆派送方案。当客户 i 的货物需求量 固定时，首先，我们根据题意，取若干辆车进行iq送货，然后，主要考虑每辆车各负责哪些客户的送货任务，我们可以给出满足题中限制条件的很多参考方案供选用，并考虑以所选行车路径产生的总费用最小为目标的情况下，建立最优化模型确定最佳的车辆派送方案。进一步讨论，当客户 i 的货物需求量 为随机参数时，我们首先可以简化iq随机模型，根据客户 i 的货物需求量的期望与方差，确定每天应该运送给客户 i的货物量，即 ，再根据第一题，确定最佳的车辆派送方案。iq但考虑到客户的储存能力有限及
7、货物在客户处的储存费用，客户不需要将一天的货物一次性接收完，只要满足缺货的情况出现的概率很低，客户可以让配送中心一天几次送货，这样可以得到很多满足约束的方案，考虑以单位时间2的储存费用最小为目标，建立最优化模型，确定配送中心给每位客户每次的配送量、配送周期与最有车辆行驶路径。三、 模型假设（1） 每个客户的需求只能由一辆配送车满足；（2） 每辆车送货时行驶的路程不超过它所能行驶的最远路程；（3） 中心仓库的车辆总数大于或等于当派送费用最小时所需的车辆数；（4） 从配送中心到各个用户、各个用户之间的运输距离已知；（5） 配送中心有足够的资源以供配送。四、 符号说明：运货车的容量Q：该配送中心服务
8、的客户总数N: 派送费用最小时所需的车辆数m：第 i 位客户所需货物iq：车 k 由 i 驶向 jijx ：点 i 的货运任务友 s 车完成isy：第 i 位客户最早允许接货时间ia ：第 i 位客户最晚允许接货时间ib：车辆在第 i 位客户处等待时间iD:车辆在第 i 位客户处迟到时间iX：第 i 位客户处车辆到达时间it ：从第 i 位客户到第 j 位客户所需时ijt间：第 i 位客户处装货（或卸货）所需is时间：第 i 位客户与第 j 位客户之间的距ijc离：车辆行驶单位距离的运输成本c ：车辆早到单位时间产生的等待损d失：车辆迟到单位时间应承担的惩罚e ：派送货物产生的总损失ZA：运输
9、成本 B：车辆早到所产生总的等待损失C：车辆迟到所受的总惩罚五、 模型的建立和求解5.1 问题一模型的建立及求解： 5.1.1 问题的分析中心仓库为了给 N 个客户派送货物，供发出 m 辆车，为了派货的节约和方便，每辆车载着适量的货物出发，可以给某一片的若干个满足约束条件的客户派送货物，见图一：3图一 中心仓库派送货物图中心仓如上图库派送货物时，必须满足约束条件：（1） 各个客户群的总需求小于或等于运输车的装载量；（2） 每个客户都必须且只能由一辆运输车运输所需货物；（3） 运输车为每位客户开始服务的时间必须尽可能在时间窗内。根据如上的约束条件，我们可以得到很多可行解，但考虑到以所选行车路径产
10、生的总费用最小为目标的情况下，我们可以建立最优化模型确定最佳的车辆派送方案，最优路径产生图如下：车 车 车213 车 车 4 车 5 n 中 心 仓 库客 户 群 2 客 户 群 客 户 群 5 客 户 群 1 客 户 群 3 4各 客 户 总 需 求 小 于运 货 车 的 装 载 量 每 个 客 户 必 须 且 只能 被 访 问 一 次 运 货 车 开 始 服 务 时间 尽 量 在 时 间 窗 内 很 多 可 行 解 所 选行 车路 径产 生的 总费 用最 小 最 优 解 图二 最优路径产生图5.1.2 模型的建立（1）中心仓库使用车辆数量的确定设配送中心需要向 N 个客户送货，每个客户的货
11、物需求量是gi（i1，2，.N） ，每辆配送车的载重量是 Q，且 gicitynums(i,j)=0;endendend%-%主程序function gaf,p=objf(s)gn=1;while gngnmax+1for j=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=sm
12、new; %产生了新的种群f,p=objf(s,dislist); %计算新种群的适应度%记录当前代最好和平均的适应度fmax,nmax=max(f);ymean(gn)=1/mean(f);ymax(gn)=1/fmax;%记录当前代的最佳个体15x=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);test(1:100)=0;l=round(100*pc);test(1
13、: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-1a=s(i,:);for j=1:KM-1m=a(j);n=a(j+1);m=m+1;n=n+1;endy(m,n)=1;y=y;for i=1:citynumfor j=1:citynummubiaob=c(i,j)*y(i,:);endendxuq1=0;for i=1:citynumfor j=1:citynumxuq1=xuq1+s(i)*y(i,:)-q(i);endx
14、uqiu=max(xuq1),0)*M;endend16shij1=0;shij2=0;for i=1:citynumfor j=1:citynumfor l=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;for i=1:innfsum=fsum+f(i);endfor i=1:innps(i)
15、=f(i)/fsum;end%计算累积概率p(1)=ps(1);for i=2:innp(i)=p(i-1)+ps(i);endp=p;p%-%“选择 ”操作%从种群中选择两个个体function seln=sell(s,p)inn=size(p,1);for i=1:2r=rand; %产生一个随机数prand=p-r;j=1;while prand(j)0j=j+1;17endseln(i)=j; %选中个体的序号endsel1=seln(1);sel2=seln(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
