第三次交卷12组王柳高兴华

1、车辆路径问题摘要车辆路径问题是现代物流研究中的一项重要内容,它是在已知待服务的客户和出发点的位置、车辆的最大负荷和客户需求的前提下,选取恰当的车辆路径,加快对客户需求的响应程度,同时降低成本,增强客户对物流环节的满意度。本文根据问题要求，首先建立了一个基于模拟算法的数学模型。中产生的总派送费用其归于车辆的费用与不满足运货点时间窗费用（等待、惩罚费）之和。然后以总派送费用最小为目标函数，以货车最大载重量及各送货点的收货时间限制范围为约束建立模型。此模型依据方法采用随机数模拟，产生出满足限定条件的可能载货组合，并求解当前组合下各车辆的消耗费用，再相加得出该组合的总费用。以此重复上述步骤，同时比较前

2、后组合产生的费用，最终选取总费用最小的组合。最后用该算法求出了算例中满足派送费用最小的车辆配送方案为：当路程费用一、 问题重述一个中心仓库，拥有一定数量容量为 Q 的车辆，负责对 N 个客户进行货物派送工作，客户i 的货物需求量为二、 基本假设车辆的行驶速度不变；车辆在仓库等待出车时不产生等待费用；车辆消耗费用由行驶费用、等待惩罚费和超时惩罚费用组成；4时间的等待费用和惩罚费用相等；运货车辆在两客户点间行驶时行驶的路径均为两点间最短路径；不考虑车辆出车费用。三、 问题分析1）问题背景分析：在物流配送供应领域中,一个常见是:已知有一批客户,各客户点的位置坐标和货物需求已知,供应商具有若干可供派送

3、的车辆,运载能力给定,每辆车都从起点出发,完成若干客户点的运送任务然后再回到起点.现要求以最小的车辆数、最小的总行程来完成货物的派送任务,该问题被称为车辆路径问题 (vehicle routing problem,简称 VRP).带时间窗的车辆路径问题(vehicle routing problem with timewindows,简称 VRPTW)是对 VRP 问题的进一步扩展,它是在 VRP 问题的基础上增加了时间窗限制,这里的时间窗是指车辆到达各客户点并为之服务的时间范围.2）问题要求分析该问题的实质是带时间窗的车辆路径问题，即在一系列客户点组成的送货网络中，每辆货车载重量一定,每条路

4、线不超过汽车载重量，同时不能违背时间窗口约束。其目的是要找到一个可行解使得派送费用最小的车辆行驶路径。于是，根据该问题首先可建立一个单目标规划模型，以总费用为目标函数值，需要确定的目标有：出车数量，每辆车的运货点安排以及车辆行驶路径。对问题的约束条件有：各送货点的收货时间限制范围即时间窗，车辆的最大载货量。为节省费用，货车在任意两点间行驶时的路线均为最短路径，由此可采用 Floyd 算法求得在此送货路径网中任意两点之间的最短路径。由于题中并未给出车辆的基本费用及具体的等待费用和惩罚费用，所以在模型里假设时间的等待费用和惩罚费用相等，费用产生的来源为仅为费和等待费及惩罚费。考虑到基于模拟产生随机

5、组合的不确定性和重复组合性，尝试依据蚂蚁算法建立模型二，仍以总费用为目标函数，当在满足限定条件的组合安排为了避免算法过早收敛于非全局最优解,围绕从轨迹i 到j 上的信息素七、模型的优缺点分析7.1 模型一优点：（1）对小规模问题的解决速度快；（2）简明，算法实现度高；（3）对类似问题的求解有一定的帮助性。缺点：（1）模拟产生的随机组合具有不确定性和组合重复性；（2）对规模较大的此类问题，在计算时易产生冗余组合，耗费时间与运货点呈指数关系。模型二优点：基于 MMAS 蚂蚁算法可以最大精度的求得最优解；模型扩展度高，在不同运货点的情况下，无需过多的修改程序主体。缺点：时间复杂度高，在求解过程中需要

6、耗费较多的时间；MMAS 对快速产生一个较好的初始解有较强的依赖性,当问题规模较大(如超过150)时,如果没有较好的初始解,将需要较多迭代次数和较长收敛时间才可以得到最优解。参考文献，带时间窗车辆路径问题的混合蚁群算法，许昌学院学报，第 271卷2，第 2 期：88-90，2008 年 3 月,谭家美,，求解带时间窗的客户需求可分条件下的车辆路径问题，中国管理科学，第 15 卷第 6 期：46-51，2007 年 12 月3, 蚁群算法及其应用, 河北理工学院学报, 第 28 卷第 1 期:42-45，2006 年 2 月附录附录 1附表 1：任意两点之间最短路径附录 2 clc; clear

7、;%三辆车基于卡罗模拟求最小费用源代码（节选：当派车三辆的情况）nn=100000;bb=cell(1,nn); wt=0;for mt=1:nn i=1:8;q=2,1.5, 4.5,3,1.5,4,2.5,3;a1=zeros(3,6);%每一行，为各辆车的行驶路径点 b1=zeros(3,6);%对应给辆车的载重货物 n1=1;n2=1;n3=1;for k=1:3 %安排给三辆车必须的运货点 ii=ceil(length(i)*rand); %在 i 中随机取一个客户 a1(k,1)=i(ii);b1(k,1)=q(i(ii);i=setdiff(i,i(ii); endfor k2=

8、1:5;%取剩余五次客户ii=ceil(length(i)*rand); %在 i 中随机取一个客户w=ceil(3*rand);%随机安排给一辆车 if w=1;n1=n1+1;z=n1;end01234567800.0040.0060.0075.0090.0090.00100.00135.0080.00140.000.0065.0040.00100.0050.0075.00110.00100.00260.0065.000.0075.00100.00100.0075.0075.0075.00375.0040.0075.000.00100.0050.0090.0090.00125.00490.

9、00100.00100.00100.000.00100.0075.0075.00100.00590.0050.00100.0050.00100.000.0070.0090.0075.006100.0075.0075.0090.0075.0070.000.0070.00100.007135.00110.0075.0090.0075.0090.0070.000.00100.00880.00100.0075.00125.00100.0075.00100.00100.000.00if w=2;n2=n2+1;z=n2;endif w=3;n3=n3+1;z=n3;end a1(w,z)=i(ii);b

10、1(w,z)=q(i(ii);i=setdiff(i,i(ii); endif sum(b1(1,:)8.1&sum(b1(2,:)8.1&sum(b1(3,:)(b(car(j)-a(car(j)/2y1=k2*(abs(a(car(j)+b(car(j)/2-t)-(b(car(j)-a(car(j)/2); elsey1=0;end sum0=sum0+y1;endendfor i=1:3car=setdi(i,:),0);car=0,car,0; car=car+1; x1,y1=size(car); for j=1:y1-1y2=L(car(j),car(j+1);%路程 sum0=

11、sum0+y2;end sum1(i)=sum0;end sum2(n)=sum(sum1); n=n+1;if isempty(bb1,n)=1 break;end endmin1=min(sum2) x4,y4=size(sum2); for r=1:y4if sum2(r)=min1 g=bb1,rendend附录 3Floyd 求最短路径clear;源代码b=04060759020010016040 60 75 90200 100 160 80;50 75 110 100;100 75 75 75;50 90 90 150;0 100 75 75 100;0 65 4065 0 754

12、0 75 0100100100100100507510010050 100 0 70 90 75;75 90 75 70 0 70 100;110 75 90 75 90 70 0 100;80 100 75path=zeros(length(b); for k=1:9for i=1:9for j=1:9100 0;if b(i,j)b(i,k)+b(k,j)b(i,j)=b(i,k)+b(k,j); path(i,j)=k;endendend endb, path附录 4 模型二程序代码clc; clear;%三辆车 nn=100000;bb=cell(1,nn); wt=0;for mt=

13、1:nn i=1:8;q=2,1.5, 4.5,3,1.5,4,2.5,3;a1=zeros(3,6);%每一行，为各辆车的行驶路径点 b1=zeros(3,6);%对应给辆车的载重货物 n1=1;n2=1;n3=1;for k=1:3 %安排给三辆车必须的运货点 ii=ceil(length(i)*rand); %在 i 中随机取一个客户a1(k,1)=i(ii);b1(k,1)=q(i(ii);i=setdiff(i,i(ii); endfor k2=1:5;%取剩余五次客户ii=ceil(length(i)*rand); %在 i 中随机取一个客户w=ceil(3*rand);%随机安排

14、给一辆车 if w=1;n1=n1+1;z=n1;endif w=2;n2=n2+1;z=n2;endif w=3;n3=n3+1;z=n3;end a1(w,z)=i(ii);b1(w,z)=q(i(ii);i=setdiff(i,i(ii); endif sum(b1(1,:)8.1&sum(b1(2,:)8.1&sum(b1(3,:)8.1%当每辆车的载重量都小于额定载重量时，显示wt=wt+1; bb(wt)=a1;endend%求最短路程L= 04060759090100135804006540100507511010060650751001007575757540750100509

15、0901250.8;9010010010001007575100905010050100070907510075759075700701001351107590759070010080;100;75;125;100;75;100;100;0;s=1 a=1 b=4n=1;246112347232.52 531.5;8 4;5.5 5v=50;while 1A=bb1,n;sum1=0; flag1=1;flag2=1;fori=1:3car=setdi t2=0;t3=0;(i,:),0);x,y=size(car); for j=1:y%到 k 点前 k-1 点卸货时间for k=2:jt3=t3+s(car(k-1);end car=0,car; car=car+1;t2=t2+L(car(j),car(j+1)/v;%到 j 送货点时间 t=t2+t3; car=car-1;car=setdiff(car,0);if tb(car(j) flag1=0;break;endendif flag1=0 flag2=0; breakendendif flag2=0n=n+1; continue;endfor i=1:3car=setdi su