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

物资配送路径问题的研究

摘要

本文建立了物资配送路线最优解问题的数学模型，应用C++软件解决模型问题，结

合森林救火模型与遗传模型，求解该数学模型的算法。该模型就实际问题给出一个合理的优化路线，在需求量、接货时间段、各种费用消耗已知的情况下，引入0-1变量，建立各个约束条件，包括车辆的容量限制，到达每个客户的车辆和离开每个客户的车辆均为1的限制，总车辆数的限制，目标函数为费用的最小化，费用包括车辆的行驶费用，车辆早到或晚到造成的损失，最后求出最优解的近似解，对于初始数据的选取采用带限制条件的随机组合的方法，使模型的求解具有普遍性，这样模型才会有具有可信度。本文提出的算法求解不需要像枚举法那样麻烦，它的高效性、普遍性是无可厚非的。

该模型用C++计算出的结果为： 路线一：0、6、4、0； 路线二：0、3、1、2、0 路线三：0、8、5、7、0

目标函数总成本为910

关键字：物资配送问题、车辆路径、最优解、森林救火模型、遗传算法

一、问题重述

某物流中心拥有一支货运车队，每台货运车辆的载重量（吨）相同、平均速度（千米/小时）相同，该物流中心用这样的车为若干个客户配送物资，物流中心与客户以及客户与客户之间的公路里程（千米）为已知。每天，各客户所需物资的重量（吨）均已知，并且每个客户所需物资的重量都小于一台货运车辆的载重量，所有送货车辆都从物流中心出发，最后回到物流中心，车辆必须在一定时间范围内到达，早于或晚于到达会受到相应的惩罚，要求此配送方案是配送费用最少的。

1. 建立送货车辆每天总运行里程最短的一般数学模型，并给出求解方法。

2. 具体求解以下算例，并给出你们实际使用的软件名称、命令和编写的全部计算机源程序。

〔算例〕载重量为 Q 8 吨、平均速度为 v 50千米/小时 的送货车辆从物流中心（i 0）出发，为编号是 i 1，2， ，8的8个客户配送物资。某日，第i个客户所需物资的重量为

qi

吨（

qi Q

s

），在第i个客户处卸货时间为i小时，第i个客户要求送货

车辆到达的时间范围

ai,bi 给出。

物流中心与各客户以及各客户间的公路里程（单位：

千米）由表2给出。问当日如何安排送货车辆（包括出动车辆的台数以及每一台车辆的

具体行驶路径）才能使总运行里程最短。

二、问题分析

物流中心呢，有一个，同时有八个客户需要该物资，每个客户的需求量都不超过车的最大承载量，货运车队到每个客户点都有一定的卸载停留时间，同时，每个客户都有他的要求车辆到达时间范围，每辆车的最大载重量为8吨，平均速率为50千米/小时，现在要做的就是如何在等待损失最小的情况下，使配送费用最小。本题主要是研究使派送费用最小的车辆行驶路径问题。车辆行驶派送的费用主要包括运输成本、车辆在客户要求到达时间之前到达产生的等待损失和车辆在客户要求到达时间之后到达所受惩罚等等。为满足派送费用最小的需求，即要使所选行车路径产生的总费用最小，从而确定出最佳的车辆派送方案。

客户i的货物需求量Di固定时，首先，我们根据题意，取若干辆车进行送货，然后，主要考虑每辆车各负责哪些客户的送货任务，我们可以给出满足题中限制条件的很多参考方案供选用，并考虑以所选行车路径产生的总费用最小为目标的情况下，建立最优化模型确定最佳的车辆派送方案。

三、基本假设

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】内；

7、Xijk

8、Yijk：

9、f：车辆迟到单位时间应承担的惩罚 ； 10、t车辆早到单位时间产生的等待损失；

11、C运送货物产生的总损失 ；

12、Ui：车辆在第i个客户站点等待的时间； 13、Vi：车辆在第i个客户站点迟到的时间 ；

14、G：车辆行驶单位距离的运输成本 ；

15、S：车辆行驶的路程 。

五、模型建立与分析

5.1 确定约束条件

k

k

①minC= Mij+ f+ t

1

1

②

Di

≤q

③ai≤Tijk≤bi ④Xijk=1 ⑤Yijk=1

5.2模型建立：

本模型思路如下：

I、每条路线客户总需求必须小于等于运输车最大装载量； II、每个客户都必须且只能由一辆车运输货物；

III、每辆车运输到客户站点的时间应尽量在客户要求时间范围内； 由以上分析可以得到很多组解，但我们使用最优解来逼近真实解。 模型图解如下：

5.3模型分析

I、车辆数目的确定：

根据问题要求已知客户总需求量为2+1.5+4.5+3+1.5+4+2.5+3=21，再根据客户所需到货时间段和客户离物流中心距离可以推算出3辆车比较合理，并且满足配送费用及运输成本尽可能最少。 II、引入0—1变量：

1)xijk表示车辆k是否从客户i行驶到客户j。定义其为0—1变量，则

车辆k从客户i行驶到客户j 1

Xijk

0反之

2)yijk表示客户i的任务由车辆k完成。同样定义其为0—1变量，则

客户i的任务由车辆k完成 1

Yijk

0反之

III、目标函数建立：

假设M为运输成本，F为等待损失，E为迟到所受惩罚，则 M G Si

i 1k

F f minVi

i 1n

n

E e minUi

i 1

所以，总费用C最小为：

C=M+F+E 5.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] 蔡常峰，《数学模型建模分析》，科学出版社，1995 [4] 齐欢，《数学模型方法》，华中理工大学出版社，1996 [5] 白其岭，《数学建模案例分析》，海洋出版社，2000

八、附录

附录一：

表1 物资配送任务及其要求

表2 点对之间的公路里程（千米）

说明：qi为第i个客户所需要的物资重量（qi<8） Si为火车在第i个客户处的卸货时间

[ai,bi]为第i个客户要求的货车辆到达时间范围 附录二：

include<stdio.h>

{ float sum,M,cir,k; sum=0;

M=1000000; Inn=100: cir=8; K=2;

Gnmax=1000; Pm=0.8; Pc=o.2;

C[81]={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}; Q[8]={2 1.5 4.5 3 1.5 4 2.5 3} S[8]={1 2 1 3 2 2.5 3 0.8} A[8]={1 4 1 4 3 2 5 1.5} B[8]={4 6 2 7 5.5 5 8 4} }

{m=zeros(1,inn); m=m'; KM=cir+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)>cir s(i,j)=0; end end

end end }

Main() {

[f,p]=objf(s) gn=1;

while gn<gnmax+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; end gn=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,:); 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: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; end end

f=mubiao+xuqiu+shijian; f=1/f; end end }

{ int fsum=0; for i=1:inn fsum=fsum+f(i);

end for i=1:inn ps(i)=f(i)/fsum; p(1)=ps(1); for i=2:inn p(i)=p(i-1)+ps(i); end p=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; end

sel1=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); 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 g=g'; h=h';

c2=round(rand*(bn-2))+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 if pmm==1

c2=round(rand*(bn-2))+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 end }

{printf(“合理路线为d% d% d% d%\n”); System(“pause”); }

本文来源：https://www.bwwdw.com/article/zys4.html