最短送货路线的设计论文

1、货物运送线路问题最短送货路线的设计摘要：现今社会网络越来越普及，网购已成为一种常见的消费方式, 随之物流行业也渐渐兴盛。为了配合现代大众的快节奏生活 要求，每个送货员需要以最快的速度及时将货物送达。而这 其中要涉及到送货路径、货物的送达吋间限制等诸多因素。 这就要求在已知要送的货物的相关信息的前提下，怎样设计 出最短的送货路径，以达到以最快的速度及时将货物送达的 冃的。在本文中利用了计算最短距离的最常用的算法dijstra算法 来计算得。在问题的解决中，分别采取多阶段、多区域等讨论 方法，在时间、重量以及体积等因素的限制下利用优化模型求 得是的距离最短的路线。关键字：最短距离 dijkstra

2、算法 优化 图论 路程 吋间 路线fl录一、问题的提出31、问题1的提出3.2、问题2的提出33、问题3的提出3二、问题的分析3三、模型的说明43.1模型的假设.43.3模型介绍4四、模型的建立以及求解44问题1的模型建立和求解44.2问题2的模型建立和求解44.3问题3的模型建立和求解4五、模型的评价11六、参考文献12七、附录12一、问题的提出网络的普及不但方便了人们的交流、对信息的更广阔的涉猎，也在经 济领域掀起了一场销售和消费方式的变革。网购就是反应这种变革的表现 形式z，同时网购的兴起又带动了物流行业的发展。物流公司面对的问题则是在这种销售商和消费者的交易中，如何更加 高效的完成“传

3、递者”的使命。物流公司雇佣的送货员在接收到耍送的货 物以及相关信息(重量、体积、送达地点、送达时间等)之后，要对送货 路线进行规划，以期达到以最快的速度及时将货物送达到消费者手中。 如何选择送货路线便成为送货员面临的最棘手的问题。因此就有以下两个问题的提出：1. 若将130号货物送到指定地点并返冋。设计最快完成路线与方式。给岀 结果。要求标出送货线路。2. 假定该送货员从早上8点上班开始送货，要将130号货物的送达时间不 能超过指定时间，请设计最快完成路线与方式。耍求标出送货线路。3. 若不需要考虑所有货物送达时间限制(包括前30件货物)，现在要将100 件货物全部送到指定地点并返回。设计最快

4、完成路线与方式。要求标出 送货线路，给出送完所有快件的时间。二、问题的分析由于送货员每次所送货的地点是确定的，但乂是不止一个的，因此最 快完成送货任务的要求相应的转变成了在吋间、重量以及体积等限制下的 最短路径的寻找的问题。在最短路径的计算中，最常用的算法是dijkstra算法。利用dijkstra 算法求得送货地点中任意两点之间的距离。而在时间、重量以及体积等限制下的最短路径则是利用优化模型，按 照类似“筛选”的思想，来获取在限制条件下的最短路径的距离、时间以 及路线等结果。三、模型的介绍3模型假设(1) . 一个地点的货物全部一次性带上，不考虑以后再经过此地再带上；(2) .同一地点多个货

5、物的交接也按总共三分钟计算；(3) .到达地点后超过规定时间的计算屮，不考虑交接的三分钟时间；(4) .不考虑休息的时间；(5) .所有的距离都精确到米，而所有的时间都精确到0.0001 h；(6) .送货员的速度是己知的常量；3.2符号说明i, j送货点的标号w从0点回到0点的总路程t从0点回到0点的总时间w(i,j)从i点到j点的最短距离v送货员的平均速度ti从0点到i点对应的最短时间mi到达i点所能带的货物的最大重量vi到达i点所能带的货物的最大体积m每次从0点出发送货员所能携带的货物的最大重量v每次从0点出发送货员所能携带的货物的最大体积i, j=l,2,350m=50 kg v=lm

6、 33.3模型的介绍我们利用图论中常用的dijkstra算法，求出各个点之间的最短路径，。 w(i,j)表示第i个地点到j个地点的最短距离，但若第i个地点和第j个地点 是不连通的则w(i,j)为无穷大，在matlab中用inf表示(在其他的计算机软件 中也可以相应找到表示方式)。在计算中，引入集合t和s。其中，s表示那些己经确定了到i地点最短 路径的地点，而t为全集u和s的差集，即那些还没有确定到i地点的最短 路径的地点。设s的初值为i, t的初值为u-io另外再引入一个标记数组 dn,其屮在某一步dk表示当前从i到k的较短路径，dk的初值为w(i,k)。 整个的计算过程如下：1、在t屮选择一

7、个dk最小的地点k,将其并入s,并从t中剔除k；如 果t为空集,则转到3；2、用k点与t中的其余点分别进行比较，如果di>dk+wki,则用 dk+wki,取代原来的di；重复1；3、算法结束，此时dk中保存的就是从i点到k点的最短路径。四、模型的建立以及求解4.1问题一由给定的表1前面的三十个货物的总重量为：s 48.5kg<50kg总体积为：s v=o.88m3<l m3因此送货员是可以一次性带着所有前三十件货物的。并且可以知道前三十件货物所要送达的地点为：i, j二13, 18, 31, 26, 21, 14, 17, 23, 32, 38, 45, 43, 39, 4

8、5, 42, 43, 32, 36, 27, 24, 31, 27, 26, 34, 40, 45, 49, 32, 23, 16并且运送这30件货物共要经历21个点，运送30件货物3500图2需耍达到的点（红点标注的）目标函数是：t二wfv+tox3o约束条件是：必须全部遍历回到o点即求出从o出发遍历上图的21个点并冋到o的最短距离要距离最短则每一步也要最短，即从o开始找最短的点到达后继续找未遍历的 最短的点则可以求出最短的距离。本题要求出回到o点则可以看到两个开始最短遍历的点在某点重合即可完 成最短的遍历。2模型的求解可以明显得出距离o最近的点是21点和26点，由于32点到38点的 距离小

9、于32点到16点的距离为使从21点出来的线遍历右下的点完后再和26 点出来汇合则安排32点到35点断开。由程序2可得：y+j厂z in】刁厶乙丿 wy：0131121323213143341643615175381618639172174018238421924943202610452127111922顺序为:coluims 1 through 131i581343629141821columns14through232219201615171112101总的路程为;5.3787e+o04总的时i目是：3.7411i遍历节点路线是：0-21-17-23-32-16-14-18-13-24-34

10、-40-45-49-42-43-38-36-39-27-31 -26-0最优路线是：0-21-17-23-32-23-16-14-21 -18-13-19-24-31 -34-40-45-42-49-42-43-38-36-27-39-27 总路程是：w=53787mz最优时间是：t=3.7411h4.2问题二1.问题的分析又第一个模型建立的可以求出到达24时所用的时间是：1(24)=2.0880由表2.1可知必须在9点之前把货物送到24点即t(24)vl,所以模型一不适用 于问题二的求解。由下图可知：3»j图3 考虑时间的点的位置由于右边的点的地点需要的时间要比左边的早，所以先分两

11、个阶段，即先走左边后走左边即先走圈内的元素有程序3可得：从 0 点出发经过 13,18,24,26,27,31,34,39,40 到达 455260.10807310.22206270.31659290.44074240.68353280.89542131.07518311.439310401.557311451.7413而到13点时必须在九点之前到达但1.0751>1,到45点吋必须在9点半之前 到达而1.7412>1.5故分成两个阶段不成功，所以分四个阶段，求出各个阶段的最 短距离和到达时的时间即可。目标函数：ti=wi4-v+z to约束条件是：t到各个点的时间最大值2. 模

12、型的求解3.2模型的求餉3500 厂484715001610®10对四个阶段分别求出到达的时间.由程序4（阳录2.4）训知3180.09092130.27064240.s5872310.73293340.92974401.04775451.23173421.42975491.56184431.73222381.8913 分4个阶段1. 从0出发经过13、18到24。 满足tvl的条件i更仔为213241. 1010e-*-004时i冃是-0. 6087故路线为：0-18-13-242. 从24出发经过31、34、40到45。 满足t<1.5im 申 jtj tt 234 bl

13、9p«3*0o4mfrtfl i in| v i故路线为：24-31-34-40-453. 从45出发经过38、42、43到49。满足t<2.25咂rr为：132. £793004l.9413所以賂线为：45-42-49-43-384. 从 38 出发经过 14、16、17、21. 23、26、27、32、36、39 凹到 610362.00548272-14721139232147262.55405212,74544172<s7146232.99539323a5003163.44202143.6007滿足t<4锻序为:108117546932总的路琨为：

14、5 7912e*004总的时目是:3.91304.3问题三1 模型的建立本题中要遍历所有的50个点但由于m总=147考过，v总=2.8n?而m<50kg ,v< 1 n?故应该以m<50kg和v< 1 m3判断的标准到达的最远的点返回。 目标函数：w=e150w(i, j) 约束条件：m<50kg, v<lm32.模型的求解由0开始尊见依次找出最近的点后再找出离该点直到不满足约束条件。 第一阶段顺序为：0 26 31 27 39 36 38 32 23 17 21 0总的路程为：2.7122e+004总的时间为:1.7301 第二阶段顺序为：columsl

15、through 130 18 13 12 11 8 3 1 67 109 14columsl4 through 2116 43 42 49 50 40 34 0总的路程为：1.5936e+005总的时间为：0.21123 模型的优化由于总的148kg sv=2. 8m2,所以最少要分四个阶段，但由于每次不可能 刚好带满50kg,而如果只要3次则最多只能带150kg只比原货物多2kg,所以不 可能是三次就把货物带完，最少要四次。故只要把上述的模型进行数据处理就好 to过程如下： 由于到21点时m二49 v二0.8757若走过14天则m大于50故直接从21点返回。 第一次带货物顺序为：0 26 3

16、1 27 39 36 38 35 32 23 17 21 0总的路程为：2. 7122e+004总的时间为:1.7310最优路线为：0-26-31-27-36-38-35-32-23-17-21-0走的距离w二27122m。花费的时间为t二1. 7301 若按程序给出的从13到8的路线是13-12-11-12-8而当13-11-12-8时更短 故修改他；同时到达40后如果选择34则45党的周围全被遍历过。到45后 m=46. 83, v=1.0247不满足要求，故从40到34后沿21-26返回。第二次带货物顺序为：columnsl through 130 18 13 12 11 8 3 1 6

17、 7 10 9 14columnsl4 through 2116 43 42 49 50 40 34 0总的路程为:8. 4850e+004总的时间为:4. 5354最优的路线：0-18-13-11-12-8-3-1-6-1-7-10-9-14-16-23-32-35-38-43-42-49-50-40-45-3 6-21-0走的距离w二83220。花费的时间为t二4. 4675 当到达45点时若要去20点放货物的话则需要遍历许多已经遍历过的地点， 故从45点沿36-21-0返冋第三次带货物顺序为：columnsl through 130 24 19 25 29 22 30 28 33 46

18、48 44 41columnsl4 through2137 47 45 20 15 0总的路程为：1. 5936e+005总的时间为：7. 5399最优的路线为：0-26-31-24-19-25-29-22-30-28-33-46-48-44-41-37-40-47-40-45-36-21-0走的距离w二83220。花费的时间为t二4. 4675走的距离w二128970m。花费的时间为t二6. 1238 余下了 5个点，所以由图可知第四次带货物顺序为：0 4 2 5 0总的路成为：1. 9347c+005总的时间为:8.2112路线为:0-26-31-24-19-25-15-22-20-2-5

19、-2-4-3-8-12-13-18-0走的距离w二17150m。花费的时间为t二7. 3964由上面的四个阶段可以知道该问的最优路线为：0-26-31-27-39-27-36-38-35-32-23-17-21-0-18-13-11-12-8-3-1-6-1-7-10-9-14-16-23-32-35-38-43-42-49-50-40-45-36-21-0-26-31-24-19-25-29-22-30-28-33-46-48-44-41-37-40-47-40-45-36-21-0-26-31-24-19-25-22-20-2-5-2-4- 3-8-12-13-18-0走的距离w二1715

20、10m。花费的时间为t=7. 3964五模型的分析1误差分析：对于模型一是使用了精确的dijkstra算法，故误差可以忽略不计。对于模型二假定了 32到38点的断开存在一定的误差，但相对于断开其余的几 个点得到的数值要小，故模型可以使用。对于模型三，由于要分区域的方法很多，故不可避免的存在些误差，但由于区 域越多，路程就越多，故选择分成四个区域最合适；分成的四个不同的时间的到 达区域比较紧密故按照时间的不同划分了四个区域，从而大大的消除了误差，此 模型可以使用。对于模型四的误差比较大，由于未考虑货物的拆分可能会有一定的影响同时 由于四个阶段的划分也是有一定的不确定性，故存在误差。对于该模型简化

21、了考 虑的条件，仅以m和v为判断标准，虽然对准确性存在挑战，但该模型相对于 其他的分类有明确的优越性。故该模型适用于该问的求解。2 灵敏度分析对于模型一二三。灵敏度很好，模型的准确性很高。对于模型四由于质量和体积的制约，使其灵敏度不会很好，但准确性较高，因 此模型可以用。六模型的评价改进和推广1.模型的评价优点：充分利用了已知数据建立模型，使其具有很高的准确性和可行性。 使用准确的算法和适当的假设，使模型的准确性和实用性达到统o 运用功能强大的mat lab工具数据处理误差达到最小。缺点：由于数据较多，没法使用工具进行模型的验证，只能一步一步的精化 模型2 模型的改进对于模型一和模型二主要是进

22、行验证。对于模型二断开的那个点可以取别的点进行。主耍是模型四的改进，可以考虑到不同的地点送的货物进行拆分，从 而渠道最优的解3 模型的推广可充分使用到图的遍历和最短的一系列问题的求解中。七参考文献1. a first course in mathenmatiucal moderling(third editon)frank r.giordiano maurice d.weir williamp.fox2. 图论任韩3. 数学建模案例选集姜启源谢金星4. 图论第三版徳辿斯特尔著5. 大学生教学建模竞赛辅导教材叶其效6. 基于matlab动态规划中最短路线的实现程序 施益昌李自立7. 物流配送问题

23、的混沌优化算法研究中央名族大学学报八附录2.1、dijstra 求解clcclear alla=llcco 825c;9185 5cc;1445 56c;727c 57c；3?35 67c;262c 595;1cc8o1435;lcc25228c;716c 2525;13845 268c;1l935 3c5c;785c 3545;6585 4l85;763052cc;l34c55325;2125 5975/15365 7045;14165 7335/8825 8075;5855 8165;7808355;l277c856c;22c0 8835; 14765 9055;779c 93324435

24、 9525;1c86c9635;1c3851c365;125c1c5oc;565 9765;258c 9865; 1565 92552395 1c1oc;18351090c/728c 11c65;153o5 11375;1239c 11415;641c 1151c;139151161c;951c12c5c;8345 123c-0;4930 13650; 13265 14145;1418c 14215;303c15c6o;1c915 14235;233c 1450c;7735 1455c;885 1488c;11575 1516c;8q1015325) ; 足各个点的坐标for i-1:51fo

25、r j=l:51, j) -sqrt (co )<2) "2)；%r 点之间的頁线距离enda=(l3;l 8;2 20;24;3 8；3 4;42;5 15;5 2;6 1;718;7 1.;8 12;9 14；91o;1q18;107;1l 12;12 13;12 25;l215;1318;13l9;1311;1418;1416;1417;1421; 1522;1525;1623;1723; 1831；i924;2c22;2126；2136；2117;2230;2317;2431;2541;2519;2529;2731;2833;2922;3c28;3041;3126;31

26、34; 3235; 3223; 3346;3328;344c;3538; 3645; 3627;374c;3836; 3927;4c34;4045;4144; 4137;4146;4243;42494338;4448;445c;455c;4542;464b;474c;4844;495c;4942;5c40;018;c 21;0 2-6汪通路表endb-zeros(51);for 1=1:83£ox i=l:51fox j-1:51±± a < j)=oq t土夕 j > =in£ ?endi± i=ja i j > f。,en

27、dendendfox? p= 1:51n®1 );wl=x <pr ： )for i1:nl < i -wl < i)( i) =1 ；ends=( j ;s <1)-1;u s (1 > ;k.= l ;wh.ix«e k<nfor i1 : tifor j =1 :k1r i-s <3i ii)1<±)<u)1)7endendendend11-1;for 1=1:nfor jl:kif i*s(j)11(1)=11(1)；else ll(i)=inf;endendendlv-inf;for i=l:nifl

28、v=ll(i);vi；endends(k+l)-v;k=k*l;u*s(k);endif p=lt=z；elsea-a;l;t=(t；z；endendfor i=l:51a (izd-inf;容把相同的戌駅俏为无穷大endsave w > lxt a -a ; g樑存jt”卜护离save z , txt : -asc :;第保存眾小路径经过的点2.2、问题一得求解clear al 1clcformat snorr.w=数据太多省略)；pl«7;p2-10;sun=c;w(:,p2)=in£w(lfez13)=inf;xl«l,pl);x2叫p2八;ior i

29、=l:15shtll-mincwfpb :);s2, t2=min(w(p2z:);w(:,tl)minf;pl-tl；p2=t2;if tl=9|t2=9 disp到达24时所运的也离t disp(sumt=sum/1000/24+3«i/6c;dlsp(,fj24.»li 用的时间 j disp(t)endifxl*xl|tl;x=：xl,x2);break;endxl=：xlr tl;x2-(t2/x2; x=(xl,x2);enddisp(,顺序为：jdlsp(x)dispu总的路程为) disp(sum)t-sum/1000/24+3*30/60;dispu总的河

30、间屆)dlsp(t)2.3.问题二的2阶段求解clealr all clc± oxrrria 匸 三 he r 二w=敢押:人多省賂;；x = 1 ;sumc;v=w;w i： : , p> =丄n£for ii:10t j =min i：w <pzsumsum» s;t-sum/1000/24+3-i/6c; dlsp < tt w <：r c)-inf;p=t;x= ：x; l;enddisp < 11(姒严为:r )disc <x)disp <、总的路程为=r )dllsp (sum)1 =sum/lc0 0/24

31、4-3-30/60;dlsp < °总的阻间是二* ) disp<l,)2.4问题二4阶段的解法clcclear 11w-inf 5295.49 2182.c3 4709.2452954今218203inf 3113.46 5714.343113,46 in£ 3893.8447c9,24j ；5714.34 3883.34 infdlsp < 第 令i汽域) p*l ；x=l;sum-c;v=w;t=c ;w / p> in f;for 1=1:3s, t-min (w <p,:); sum=sum+s;t=s/lc00/24+t; disp

32、 <tt) t=t3/6c;w 仁夕 t.) -inf ;p-c；x= i； x; t 】;end dispc顺挣为jdisp(x1)dlsp<1 *总路稈是:r)disp <sum)disp (1总时间是)disp (t)disp ('无'id)w=inf 17s0-15 4104.9 5735,68 8234.281730.15 inf 2324.75 3955.53 6454.13mq4.92324.75inf 1630.78 4847.795735.683955.531630.78 inf 3217.cl8234.286454.134847.79 32

33、17.01 inf； p=l; x«1;v=w;w(:,p=inf; t=c.6o87;for i-1:4sum-suini s;t-t+3./6c;t=s/lc0c/24+t;dispdt.t)if (i=l)；t=t+3/6c;endif (i=4);t-t+3/60*2;endw(:,t)=inf;p-t;x=x;t；enddlsp <1顺序为)dlsp(x *)dlsp"总略程是：)dlsp(sum)disp t，总片间是)dlsp(t)disp(' :j)4719.882351-723536.11 ln£ 917.671971.3s3269

34、.392618.44917.67inf 2889.054323.13507-491971.38 2889.c5 infinf 3536.112618.44 5507.49；x=ll 3 5 4 2;t-l.3317;for i-1:4sn=i;s-w(x <i),x <i+l);s：jm=smn+s ;if(i=4)endt-s/1000/24+t; disp<x (i + 1), t) t=t*3/6c;endd±w顺7为f )d.±sp < x )dli_sp < 1 x序丫:；亡：* )d 1 s p < s i j m)<i

35、±sp < * 丘 ii «j 出)disp <t)disp < 绝今<戍)w=毯押;衣多vt日齐2 :w ( : , 12 ) =i/ .9413;for i1:1c匕=sn±n ©3 cp# 二): sum sum+ a;t = s / 1 ooc / 2 4 4-t ;disp < 匸* t >t=t*3/6c 7x=x, l1 ：if 1-2t=t+3/6o;巳ndendif i=7t=t*3/6c;endif i=8t-t+3/6c*2;enddi sp < pz suit.)三nd5vim=sum4-

36、iz ( c r 12 );lisp < ' “贝吓尾；')x-, 1)iiap < *e.足：* )lisp < sum)r-svm/1 ooc/24-1-3 30/6c;lisp < 1总疔间足:* )lisp <t)2 5.问题3的初步设定clcclea.r eil iw-；i = l；while i<5oif i：w 1w<i + lr 1)w i： i, 2 ) i：l, 2) + w i：± + l 2; w(i# 3)-w(i, 3)+w(i + l# 3); w<± + lr : ) = ( j

37、 ;丄=j-l;end1=1+1;endsave xtxt w -ascii;clcclear allload w.txt«a=tx;ror i-1:51a (ir1)=inf;endlocid x .七x匕pl ；x=c ;m-0 ;v-czs±m=c ;va；a : z p/d±sp < '第 i：介鞍 * )for i-1:5os, t j =?nin i： a <p? : ) ； m=-m+w t 1 x 2 ); v-v-»-w t-l , 3);s j.ni= s 丄n+ s ;p=t;if ( i：m>5c) i

38、<v>1) 匕二jilv;endn = i;x;t-1;为 aisp <t-lr mz v)z t)=inf;encisim=55ijin +v fpr 1)；aisp < ' iikf产为:r )disp < x. 0 >disp < '总跖址=r )ci±sp < sum) t-sum/lcoo/24 + 3*i/6c; dlisp ( 所 i jlt< i'hj !el= r > d±sp <t)dxsp < * ；4二.|：介匚址')f>=1；x=c ;m-

39、0 ?v=0 ;f os- x-1 : 50s t 1 =sn± n a < p> :) mm*w <t lr2)z 7=pf <t-l 3);s um= s urn+ s ;if(m>5g)i <v>1)t>r c> dlk ;encin=n*1;q=匕方xlt-11 /冷 c：3-sp t - , m r v j )sl ( : x c ) inf;encihisp < 1 1较!？： h :1 )disp i x，c disp <1总路珂-心r) disp < sun)t-sum/lc00/24+3*i/6

40、g; disp< '所用盯间足：r) disp <1)di吕pl筮三阶段p=l;x-0;m=0；v=o：a(:zpnf;for i=l:hc-nsz t-min (a (p* : ;mfh (t-1 z 2 );v=v*w <l-1 3);seum-suin 十弓;i± ( (m>50) : <v>1)break;encdp-t ;x=(x;l-1：;% csi sp < tz 1 >. mr v:) a <:z c)=±nf i n=t：i+1 ;endssum-*-v (pr 1 > ;d±s

41、p ( 1 mg* .l 尹为y r )disp < x* o disp < '总路和足=* )disp < sum) t=sum/looo/24+3* i/ec;d.±sp (何门；屮：吳上:：) disp <t)aisp < -探;wl；介jn，)p1;x=c ;m=0 ;7-0;ep > =±nf,£c?r i=l 二 5 0 nl s x t -min i： a <p:).m=mw < l 1 jr 2：);wd.匸一 i_ms im= ss um+ s ;i£(m>50)i <v>1)bireak ;endpt;x-x;t-1；a (:z t)=lnf;nn+1;ends -u：i= s u：n+ v (p t 1);disp (1顺序为:')disp < x', 0 disp <1 总距 a. >l_! r) ; disp (sum) t=sum/1000/2 + 31ii/60;disp <，总时间是:r) ;disp(t)2.6、问题三的优化clcclear allload w r txtendp-t;x叫x;t-1;a