2013西北大学数学建模竞赛(陈思、李瑶、张瑜).doc

物资配送路径问题的研究摘要 本文建立了物资配送路线最优解问题的数学模型，应用C+软件解决模型问题，结合森林救火模型与遗传模型，求解该数学模型的算法。该模型就实际问题给出一个合理的优化路线，在需求量、接货时间段、各种费用消耗已知的情况下，引入0-1变量，建立各个约束条件，包括车辆的容量限制，到达每个客户的车辆和离开每个客户的车辆均为1的限制，总车辆数的限制，目标函数为费用的最小化，费用包括车辆的行驶费用，车辆早到或晚到造成的损失，最后求出最优解的近似解，对于初始数据的选取采用带限制条件的随机组合的方法，使模型的求解具有普遍性，这样模型才会有具有可信度。本文提出的算法求解不需要像枚举法那样麻烦，它的高效性、普遍性是无可厚非的。该模型用C+计算出的结果为： 路线一：0、6、4、0； 路线二：0、3、1、2、0 路线三：0、8、5、7、0 目标函数总成本为910关键字：物资配送问题、车辆路径、最优解、森林救火模型、遗传算法一、问题重述 某物流中心拥有一支货运车队，每台货运车辆的载重量（吨）相同、平均速度（千米/小时）相同，该物流中心用这样的车为若干个客户配送物资，物流中心与客户以及客户与客户之间的公路里程（千米）为已知。每天，各客户所需物资的重量（吨）均已知，并且每个客户所需物资的重量都小于一台货运车辆的载重量，所有送货车辆都从物流中心出发，最后回到物流中心，车辆必须在一定时间范围内到达，早于或晚于到达会受到相应的惩罚，要求此配送方案是配送费用最少的。1. 建立送货车辆每天总运行里程最短的一般数学模型，并给出求解方法。2. 具体求解以下算例，并给出你们实际使用的软件名称、命令和编写的全部计算机源程序。算例载重量为 8 吨、平均速度为 50千米/小时 的送货车辆从物流中心（0）出发，为编号是 1，2，8的8个客户配送物资。某日，第个客户所需物资的重量为吨（），在第个客户处卸货时间为小时，第个客户要求送货车辆到达的时间范围 给出。物流中心与各客户以及各客户间的公路里程（单位：千米）由表2给出。问当日如何安排送货车辆（包括出动车辆的台数以及每一台车辆的具体行驶路径）才能使总运行里程最短。2、 问题分析 物流中心呢，有一个，同时有八个客户需要该物资，每个客户的需求量都不超过车的最大承载量，货运车队到每个客户点都有一定的卸载停留时间，同时，每个客户都有他的要求车辆到达时间范围，每辆车的最大载重量为8吨，平均速率为50千米/小时，现在要做的就是如何在等待损失最小的情况下，使配送费用最小。本题主要是研究使派送费用最小的车辆行驶路径问题。车辆行驶派送的费用主要包括运输成本、车辆在客户要求到达时间之前到达产生的等待损失和车辆在客户要求到达时间之后到达所受惩罚等等。为满足派送费用最小的需求，即要使所选行车路径产生的总费用最小，从而确定出最佳的车辆派送方案。客户i的货物需求量Di固定时，首先，我们根据题意，取若干辆车进行送货，然后，主要考虑每辆车各负责哪些客户的送货任务，我们可以给出满足题中限制条件的很多参考方案供选用，并考虑以所选行车路径产生的总费用最小为目标的情况下，建立最优化模型确定最佳的车辆派送方案。3、 基本假设A、客户的需求量已知；B、每个车辆的容量都一样，且都已知；C、每个客户站点仅允许一辆车经过一次并配送货物；D、车辆的载货量不允许超过车辆的最大载货量；E、站点和客户的相对位置坐标已知；F、每辆车都从物流中心出发最后回到物流中心；G、配送中心有足够的资源以供配送；H、物流中心的车辆总数大于或等于当派送路程最小时所需的车辆数；I、每辆车送货时行驶的路程不超过它所能行驶的最远路程； G、每个客户要求车辆到达的时间范围已知。四、符号说明1、n：客户或站点的集合 其中i、j分别为两相邻站点的集合2、 k：车辆的集合3、 q：车辆额定载货量4、 Mij：从i到j的运输成本；5、 Di：客户需求量；6、 Tijk：车辆到达客户站点的时间，要求尽量落在【ai，bi】内；1 每个客户站点仅对应一辆车经过0 某个站点车辆经过的次数大于一7、 Xijk：1 每辆车出发自中心仓库回至中心仓库0 某辆车未出发自中心仓库或未回至中心仓库 8、Yijk：9、 f：车辆迟到单位时间应承担的惩罚 ；10、 t车辆早到单位时间产生的等待损失；11、 C运送货物产生的总损失 ；12、 Ui：车辆在第i个客户站点等待的时间；13、 Vi：车辆在第i个客户站点迟到的时间 ；14、 G：车辆行驶单位距离的运输成本 ；15、 S：车辆行驶的路程 。 五、模型建立与分析5.1 确定约束条件 minC=+ q aiTijkbi Xijk=1 Yijk=15.2模型建立： 本模型思路如下： I、每条路线客户总需求必须小于等于运输车最大装载量； II、每个客户都必须且只能由一辆车运输货物； III、每辆车运输到客户站点的时间应尽量在客户要求时间范围内； 由以上分析可以得到很多组解，但我们使用最优解来逼近真实解。 模型图解如下： 路线二路线一路线三 5.3模型分析I、车辆数目的确定：根据问题要求已知客户总需求量为2+1.5+4.5+3+1.5+4+2.5+3=21，再根据客户所需到货时间段和客户离物流中心距离可以推算出3辆车比较合理，并且满足配送费用及运输成本尽可能最少。II、引入01变量：1)表示车辆k是否从客户行驶到客户j。定义其为01变量，则 2)表示客户的任务由车辆k完成。同样定义其为01变量，则 III、目标函数建立： 假设M为运输成本，F为等待损失，E为迟到所受惩罚，则 所以，总费用C最小为： C=M+F+E5.4 模型求解 根据遗传算法、森林救火算法用C+编程【附录二】运行后得结果如下： 路线一：0、6、4、0； 路线二：0、3、1、2、0 路线三：0、8、5、7、0 目标函数总成本为910。六、模型的评价和推广模型的思路清晰，考虑条件全面。但最优解解决起来困难，遗传算法和森林救火算法只是一种相对好的解决方法，可以找出最优解的近似解。因为学识有限，matlab不会使用，只能使用C+来代替，使得问题解决复杂化，方法不够简练，有待提高。七、参考文献 参考文献：1 李建广，姚英学，刘长清，黎世文，基于遗传算法的车削用量优化研究， ，2013年4月28日 2 颜富强，遗传算法在数据挖掘中的应用研究，www.手机知网，2013年4月2 8日3 蔡常峰，数学模型建模分析，科学出版社，19954 齐欢，数学模型方法，华中理工大学出版社，19965 白其岭，数学建模案例分析，海洋出版社，2000八、附录附录一： 表1 物资配送任务及其要求任务12345678 （吨）21.54.531.542.53 （小时）121322.530.81,44,61,24,73,5.52,55,81.5,4 表2 点对之间的公路里程（千米） 01234567801 23456780406075902001001608040065401005075110100606507510010075757575407501005090901509010010010001007575100200501005010007090751007575907570070100160110759075907001008010075150100751001000说明：qi为第i个客户所需要的物资重量（qi8） Si为火车在第i个客户处的卸货时间 ai,bi为第i个客户要求的货车辆到达时间范围附录二： include float sum,M,cir,k;sum=0; M=1000000; Inn=100:cir=8; K=2; Gnmax=1000; Pm=0.8; Pc=o.2;C81=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,100,75,100,100,0;Q8=2 1.5 4.5 3 1.5 4 2.5 3S8=1 2 1 3 2 2.5 3 0.8A8=1 4 1 4 3 2 5 1.5B8=4 6 2 7 5.5 5 8 4m=zeros(1,inn);m=m;KM=cir+K-1;s=zeros(inn,citynum+K-1);for i=1:1:inn s(i,:)=randperm(KM);ends=m s;for i=1:inn for j=1:KM-1 if s(i,j)cir s(i,j)=0; end endendendMain()f,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,:)=chang(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);end; 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 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:cir for j=1:cir for l=1:cir 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;endend int fsum=0;for i=1:inn fsum=fsum+f(i);endfor i=1:inn ps(i)=f(i)/fsum;p(1)=ps(1);for i=2:inn p(i)=p(i-1)+ps(i);endp=p; end; 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=seln(2);end 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=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); endg=g;h=h;c2=round(rand*(bn-2)+1; c3=round(rand*(bn-2)+1;ch