带时间窗物流配送车辆路径问题
摘要
本题是一个带有时间窗的车辆路径安排问题（VRPTW问题）。根据题目条件，本文建立了一个求解最小派送费用的VRPTW优化模型，采用遗传算法，给出了该模型的求解方法。然后，对一个实际问题进行求解，给出了一个比较好的路线安排方式。
模型一（见5.1.2）针对问题一，在需求量、接货时间段、各种费用消耗已知的情况下，
决定
郑伟家庭教育讲座全集个人独资股东决定成立安全领导小组关于成立临时党支部关于注销分公司决定
采用规划模型，引入0-1变量，建立各个约束条件，包括车辆的容量限制，到达每个客户的车辆和离开每个客户的车辆均为1的限制，总车辆数的限制，目标函数为费用的最小化，费用包括车辆的行驶费用，车辆早到或晚到造成的损失。
模型一的求解采用遗传算法（见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=8
2
0-8-5-7-0
0-1.6-3.9-7.7-13.9
80+75+90+160=405
3+1.5+2.5=7
3
0-6-4-0
0-2-6-10.8
100+75+90=265
4+3=7
考虑在车辆返回时选择最短路线，我们采用Dijkstra算法求出中心仓库到各个客户的最短距离，将结果改进为885公里,具体结果如下：
车辆编号
所执行的任务路线
到达各点的时间
路线长度
货运量
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=8
2
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=7
3
0-6-4-0
0-2-6-10.8
100+75+90=265
4+3=7
模型二考虑需求量随机变化时的安排
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
，假设客户需求量遵循正态分布，首先按照需求期望根据模型一得到一个比较好的方案，然后按照这一方案进行送货，在送货过程中，如果出现需求量过大的情况，允许车辆返回仓库进行补充。
模型一的思路清晰，考虑条件全面。但最优解解决起来困难，遗传算法只是一种相对好的解决方法，可以找出最优解的近似解。模型二的想法比较合理，易于实施，但还有待改进。
关键词：规划 时间窗 物流 车辆路径 遗传算法
1、 问题重述
一个中心仓库，拥有一定数量容量为Q的车辆，负责对N个客户进行货物派送工作，客户i的货物需求量为
，且
，车辆必须在一定的时间范围
内到达，早于
到达将产生等待损失，迟于
到达将处以一定的惩罚，请解决如下问题：
（1）给出使派送费用最小的车辆行驶路径问题的数学模型及其求解算法。并具体求解以下算例：
客户总数N=8,每辆车的容量Q=8（吨/辆）, 各项任务的货运量
（单位：吨）、装货（或卸货）时间
（单位：小时）以及要求每项任务开始执行的时间范围
由附录1给出，车场0与各任务点以及各任务点间的距离（单位：公里）由附件二给出，这里假设车辆的行驶时间与距离成正比，每辆车的平均行驶速度为50公里/小时，问如何安排车辆的行驶路线使总运行距离最短；
（2）进一步请讨论当客户i的货物需求量
为随机参数时的数学模型及处理方法。
2、 问题
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
本题主要在两种不同情况下，研究使派送费用最小的车辆行驶路径问题。车辆行驶派送的费用主要包括运输成本、车辆在客户要求到达时间之前到达产生的等待损失和车辆在客户要求到达时间之后到达所受惩罚等等。为满足派送费用最小的需求，即要使所选行车路径产生的总费用最小，从而确定出最佳的车辆派送方案。
当客户i的货物需求量
固定时，首先，我们根据题意，取若干辆车进行送货，然后，主要考虑每辆车各负责哪些客户的送货任务，我们可以给出满足题中限制条件的很多参考方案供选用，并考虑以所选行车路径产生的总费用最小为目标的情况下，建立最优化模型确定最佳的车辆派送方案。
进一步讨论，当客户i的货物需求量
为随机参数时，我们首先可以简化随机模型，根据客户i的货物需求量的期望与方差，确定每天应该运送给客户i的货物量，即
，再根据第一题，确定最佳的车辆派送方案。
但考虑到客户的储存能力有限及货物在客户处的储存费用，客户不需要将一天的货物一次性接收完，只要满足缺货的情况出现的概率很低，客户可以让配送中心一天几次送货，这样可以得到很多满足约束的方案，考虑以单位时间的储存费用最小为目标，建立最优化模型，确定配送中心给每位客户每次的配送量、配送周期与最有车辆行驶路径。
3、 模型假设
（1） 每个客户的需求只能由一辆配送车满足；
（2） 每辆车送货时行驶的路程不超过它所能行驶的最远路程；
（3） 中心仓库的车辆总数大于或等于当派送费用最小时所需的车辆数；
（4） 从配送中心到各个用户、各个用户之间的运输距离已知；
（5） 配送中心有足够的资源以供配送。
4、 符号说明
：运货车的容量
：该配送中心服务的客户总数
: 派送费用最小时所需的车辆数
：第i位客户所需货物
：车k由i驶向j
：点i的货运任务友s车完成
：第i位客户最早允许接货时间
：第i位客户最晚允许接货时间
：车辆在第i位客户处等待时间
:车辆在第i位客户处迟到时间
：第i位客户处车辆到达时间
：从第i位客户到第j位客户所需时间
：第i位客户处装货（或卸货）所需时间
：第i位客户与第j位客户之间的距离
：车辆行驶单位距离的运输成本
：车辆早到单位时间产生的等待损失
：车辆迟到单位时间应承担的惩罚
：派送货物产生的总损失
A：运输成本
B：车辆早到所产生总的等待损失
C：车辆迟到所受的总惩罚
5、 模型的建立和求解
5.1 问题一模型的建立及求解：
5.1.1问题的分析
中心仓库为了给N个客户派送货物，供发出m辆车，为了派货的节约和方便，每辆车载着适量的货物出发，可以给某一片的若干个满足约束条件的客户派送货物，见图一：
图一 中心仓库派送货物图
中心仓如上图库派送货物时，必须满足约束条件：
（1） 各个客户群的总需求小于或等于运输车的装载量；
（2） 每个客户都必须且只能由一辆运输车运输所需货物；
（3） 运输车为每位客户开始服务的时间必须尽可能在时间窗内。
根据如上的约束条件，我们可以得到很多可行解，但考虑到以所选行车路径产生的总费用最小为目标的情况下，我们可以建立最优化模型确定最佳的车辆派送方案，最优路径产生图如下：
图二 最优路径产生图
5.1.2模型的建立
（1）中心仓库使用车辆数量的确定
设配送中心需要向N个客户送货，每个客户的货物需求量是gi（i＝1，2，…..N），每辆配送车的载重量是Q，且gi
评价
LEC评价法下载LEC评价法下载评价量规免费下载学院评价表文档下载学院评价表文档下载
和推广
6.1 模型的评价
由5.1和5.2建立的模型，我们得到了有软时间限制的物流配送车辆路径问题的解决办法。首先我们对问题进行了合理的假设，模型简化了实际中的复杂问题，考虑了主要的约束条件与目标，思路清晰，结果也基本符合实际。
但是，模型对实际进行简化的同时忽略了实际中很多次要的条件，由累加效果可能会产生很大误差，同时，我们进行模型的求解时只是简单使用了遗传算法，没有对其进行改进。
6.2 模型的推广
1．模型中不合实际的假设：
（1） 在问题一和问题二总费用的组成上，我们没有考虑组织送货的费用，即每组织一辆车进行送货都需要一定的费用，我们设为S元/（次、辆）；
（2） 在问题一中，我们假设每辆车送货时行驶的路程不超过它所能行驶的最远路程，但是实际上，考虑到车辆行驶中的耗油等因素，每辆车的行驶最大距离都有限制，我们设车辆行驶的最大距离为L，我们可以得到约束条件：
（3） 在实际中，为了公平，每位送货车辆司机行驶的路程相差必须控制在一定范围之内，我们取这个差值的最大允许值为M，则有：
2. 模型的推广
根据以上目标函数与约束条件，带入实际数据，由遗传算法即可求解出总费用最小的车辆行驶路径方案。
7、 参考文献
[1] 李军，谢秉磊，郭耀煌，非满载车辆调度问题的遗传算法。系统工程理论与实践，2000，20（3）：235—239；
[2] 邢文训，谢金星编著现代优化计算方法。北京：清华大学出版社，1999.140；
[3] 魏明 高成修 胡润洲，一种带时间窗和容量约束的车辆路线问题及其Tabu Search 算法，运筹与管理，Vol. 11 ,No. 3：P49-P53，2002；
[4] 胡大伟 朱志强 胡勇，车辆路径问题的模拟退火算法，中国公路学报，Vol.1 9 No.4：P123-P126,2006
[5] 阎庆 鲍远律，新型遗传模拟退火算法求解物流配送路径问题，http://epub.cnki.net/grid2008/detail.aspx?filename=HNSZ200804014&dbname=CJFD2008 ，2009/8/16
[6] 张志霞 邵必林，基于改进蚁群算法的运输调度规划，公路交通科技，Vo1．25 No．4：P137-P140，2008；
[7] 杜文 衰庆达 周再玲，一类随机库存/运输联合优化问题求解过程分析，中国公路学报，Vol. 17 No．1：P114-P118，2004.
8、 附录
9.1 附录一
表1 任务的特征及其要求
任务
1
2
3
4
5
6
7
8
（吨）
2
1.5
4.5
3
1.5
4
2.5
3
（小时）
1
2
1
3
2
2.5
3
0.8
[1,4]
[4,6]
[1,2]
[4,7]
[3,5.5]
[2,5]
[5,8]
[1.5,4]
表2 点对之间的距离
0
1
2
3
4
5
6
7
8
0
1
2
3
4
5
6
7
8
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
9.2 附录二
Matlab 7.0 程序：
function gatsp(s)
sum=0;
M=1000000; %无穷大数
inn=100;
citynum=8;
K=2;
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,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=[2 1.5 4.5 3 1.5 4 2.5 3];
s=[1 2 1 3 2 2.5 3 0.8];
a=[1 4 1 4 3 2 5 1];
b=[4 6 2 7 5.5 5 8 4];
%--------------------------------------------------------------------------
%产生初始种群
m=zeros(1,inn);
m=m';
KM=citynum+K-1;
s=zeros(inn,citynum+K-1);
for i=1:1:inn
s(i,:)=randperm(KM);
end
s=[m s];
for i=1:inn
for j=1:KM-1
if s(i,j)>citynum
s(i,j)=0;
end
end
end
%--------------------------------------------------------------------------
%主程序
function ga
[f,p]=objf(s)
gn=1;
while gn
记录
混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载
当前代最好和平均的适应度
[fmax,nmax]=max(f);
ymean(gn)=1/mean(f);
ymax(gn)=1/fmax;
%记录当前代的最佳个体
x=s(nmax,:);
gn=gn+1;
%pause;
end
gn=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: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,:);
end
end
xuq1=0;
for i=1:citynum
for j=1:citynum
xuq1=xuq1+s(i)*y(i,:)-q(i);
end
xuqiu=max((xuq1),0)*M;
end
end
shij1=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;
end
end
f=mubiao+xuqiu+shijian;
f=1/f;
end
%--------------------------------------------------------------------------
%计算选择概率
fsum=0;
for i=1:inn
fsum=fsum+f(i);
end
for i=1:inn
ps(i)=f(i)/fsum;
end
%计算累积概率
p(1)=ps(1);
for i=2:inn
p(i)=p(i-1)+ps(i);
end
p=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; %选中个体的序号
end
sel1=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=sym(B);
k=size(a,2);
for i=1:size(a,2)
for j=1:k
e(i,c(k))=a(i+k-1);
end
end
for i=1:size(a,2)
for j=1:k
e(i,d(k))=b(i+k-1);
end
end
c0=round(rand*(k-1))+1;
c1=round(rand*(k-1))+1;
a=[f(:,c0),a];
b=[e(:,c1),b];
for i=1:size(a,2);
j=1:size(e,2)
if a(i)==e(j)
a(i)==[];
end
end
for i=1:size(b,2);
j=1:size(f,2)
if b(i)==f(j)
b(i)==[];
end
end
a=double(a);
b=double(b);
g=zeros(size(A));
for i=1:size(a)
for j=1:size(c)
g(i+j)=a(i);
end
end
h=zeros(size(A));
for i=1:size(b)
for j=1:size(d)
h(i+j)=b(i);
end
end
g=g';
h=h';
snew=[g h];
%--------------------------------------------------------------------------
%变异
function 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);
end
� EMBED Word.Document.8 \s ���
PAGE
18
_1312029778.unknown
_1312034394.unknown
_1312043354.unknown
_1312045557.unknown
_1312048502.unknown
_1312048747.unknown
_1312049818.doc
各客户总需求小于运货车的装载量
每个客户必须且只能被访问一次
运货车开始服务时间尽量在时间窗内
很多可行解
所选行车路径产生的总费用最小
最优解
_1312048769.unknown
_1312048788.unknown
_1312049528.doc
车
车 车
2
1 3
车
车
4
车
5
n
客户群3
客户群1
客户群2
中心仓库
客户群5
客户群4
······
_1312048759.unknown
_1312048527.unknown
_1312045610.unknown
_1312048313.unknown
_1312048366.unknown
_1312048474.unknown
_1312048333.unknown
_1312045725.unknown
_1312045703.doc
目标函数：
约束条件
_1312044728.unknown
_1312044984.unknown
_1312045054.unknown
_1312045086.unknown
_1312045529.unknown
_1312045563.unknown
_1312045520.unknown
_1312045071.unknown
_1312045025.unknown
_1312045041.unknown
_1312044997.unknown
_1312044951.unknown
_1312044972.unknown
_1312044931.unknown
_1312038935.unknown
_1312043534.unknown
_1312044180.unknown
_1312043512.unknown
_1312033224.unknown
_1312033399.unknown
_1312033154.unknown
_1312045594.unknown
_1312043739.unknown
_1312045393.unknown
_1312045510.unknown
_1312045555.unknown
_1312045440.unknown
_1312043753.unknown
_1312043467.unknown
_1312043647.unknown
_1312043657.unknown
_1312043512.unknown
_1312043534.unknown
_1312043460.unknown
_1312043465.unknown
_1312043450.unknown
_1312043457.unknown
_1312039431.unknown
_1312040192.unknown
_1312040257.unknown
_1312043253.unknown
_1312040324.unknown
_1312040210.unknown
_1312039577.unknown
_1312040130.unknown
_1312039486.unknown
_1312038771.unknown
_1312038935.unknown
_1312039178.unknown
_1312039375.unknown
_1312039425.unknown
_1312039214.unknown
_1312039161.unknown
_1312039083.unknown
_1312038790.unknown
_1312034406.unknown
_1312034489.unknown
_1312034674.unknown
_1312034453.unknown
_1312031590.unknown
_1312034209.unknown
_1312034268.unknown
_1312032821.unknown
_1312033399.unknown
_1312034040.unknown
_1312033384.unknown
_1312033224.unknown
_1312033298.unknown
_1312033180.unknown
_1312032942.unknown
_1312033154.unknown
_1312032117.unknown
_1312032773.unknown
_1312031604.unknown
_1312032013.unknown
_1312031507.unknown
_1312031554.unknown
_1312031578.unknown
_1312031586.unknown
_1312031520.unknown
_1312031406.unknown
_1312031471.unknown
_1312031494.unknown
_1312031438.unknown
_1312031034.unknown
_1312031181.unknown
_1312031221.unknown
_1312031320.unknown
_1312031099.unknown
_1312030902.unknown
_1312030915.unknown
_1312030890.unknown
_1311961607.unknown
_1311963128.unknown
_1311963547.unknown
_1311963641.unknown
_1311963686.unknown
_1311963590.unknown
_1311963366.unknown
_1311963480.unknown
_1311963259.unknown
_1311962595.unknown
_1311962990.unknown
_1311963060.unknown
_1311962608.unknown
_1311961883.unknown
_1311962052.unknown
_1311961623.unknown
_1279961227.unknown
_1279962076.unknown
_1280520466.unknown
_1280521917.unknown
_1311961585.unknown
_1280522658.unknown
_1280520885.unknown
_1279962229.unknown
_1280518260.unknown
_1280520453.unknown
_1279963421.unknown
_1279964068.unknown
_1279962168.unknown
_1279961267.unknown
_1279961190.unknown
浙公网安备 33021202002483