数学建模送货线路设计问题答案仅供参考

1、第九届西安电子科技大学数学建模竞赛暨全国大学生数学建模竞赛选拔赛题目A (B)题密封号2010年5月4日密封号2010年5月4日通信工程学院第 队队员1队员2队员3姓名邓晓光谭正中刘春燕班级送货路线设计问题1、问题重述现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业 也渐渐兴盛，每个送货员需要以最快的速度及时将货物送达，而且他们往往一人 送多个地方，请设计方案使其耗时最少。现有一快递公司，库房在图1中的。点，一送货员需将货物送至城市内多处，请设计送货方案，使所用时间最少。该地形图的示意图见图1,各点连通信息见表3,假定送货员只能沿这些连通线路行走，而不能走其它任何路线。各件货

2、物 的相关信息见表1, 50个位置点的坐标见表2。假定送货员最大载重50公斤，所带货物最大体积1立方米。送货员的平均 速度为24公里/小时。假定每件货物交接花费3分钟，为简化起见，同一地点有 多件货物也简单按照每件3分钟交接计算。现在送货员要将100件货物送到50个地点。请完成以下问题。.若将130号货物送到指定地点并返回。设计最快完成路线与方式。给出 结果。要求标出送货线路。.假定该送货员从早上8点上班开始送货，要将130号货物的送达时间不 能超过指定时间，请设计最快完成路线与方式。要求标出送货线路。.若不需要考虑所有货物送达时间限制（包括前30件货物），现在要将100 件货物全部送到指定地

3、点并返回。设计最快完成路线与方式。要求标出送货线路， 给出送完所有快件的时间。由于受重量和体积限制，送货员可中途返回取货。可不考虑中午休息时间。问题分析送货路线问题可以理解为：已知起点和终点的图的遍历问题的合理优化的路线设计。图的遍历问题的指标：路程和到达的时间，货物的质量和体积，以及最大可以负载的质量和体积。在路线的安排问题中，考虑所走的路程的最短即为最合理的优化指标。对于问题二要考虑到所到的点的时间的要求是否满足题意即采用多次分区域的假设模型从而找出最优的解对于问题三则要考虑到体积和质量的双重影响，每次到达后找到达到最大的体积和质量的点然后返回，再依次分析各个步骤中可能存在的不合理因素达到

4、模型的进一步合理优化得到最合理的解。模型假设与符号说明、模型的假设、到同一地点的货物要一次拿上，即不考虑再以后又经过时再带些货物、要求达到不超过的时间不包括此次在该点交易的时间。、所用的距离数据都精确到米而时间则精确到、同一地点有多件货物也简单按照每件3 分钟交接计算。、符号说明符号囚(ij)符号说明送货点的稀号从。开始函”。的总的路程从口开始醺耳。的生的B寸间从,治到j的最短路程送货员的平均速度从白开始到t的所用最理面间到达可以带的最暑的货物的质量到达i可以带的最大的货物物携一次可以摭带的最多货物的总高质量一次可以携带的最多货物的总高质鬓v=W其中i , j=1、2、350 并且 M=50k

5、g模型的建立我们为了求出各个点的之间的最短的路径，使用Dijstra算法求解。Dijkstra算法是图论中非常有名的一个算法。图采用邻接矩阵的形式描述，w (i,j )表示结点i到结点j间的最短距离,如果没有直接连通，则为无穷大，计算机中可以用一个很大的数据代替(如 matlab 中的 inf ）。但dijkstra 算法只能求出从结点i到其它各结点的最短路径。算法引入这样 两个集合s和t, s是那些已经确定了到i结点的最短路径的结点，t为全集u 和s的差集，即那些还未确定最短路径的结点。而且 s的初值是i , t的初值 是u-i o另外再引入一个标记数组dn,其中在某一步dk表示当前从i到k

6、 的较短路径，dk的初值为w (i , k)0整个算法过程如下：1、在t中选择一个dk最小的结点k,将k并入s,并从t中去掉，如果 t为什则转到3 ;2、用k结点和t中其余结点进行一遍比较，如果 didk+mki,则用dk+mki取代原来的di，重复1 ;3、算法结束，此时dk中保存的就是从i到k结点的最短路径。算法就以这样非常简单的形式完成了求解，时间复杂度是O(n),确定了从i到其余各结点的最短路径。模型的求解根据算法和相邻的点的距离可以用dijkstra求出任意两点的最短路径。1 相邻的点的距离使用循环的结构求出1-50 各个点之间的最短距离。程序1 见附录可以求出w和aa 为最短路径是

7、的所过的的地点如从。开始到其余 50个点的 a(0)= 0 7 4 8 3 15 1 18 12 14 18 13 13 1821 12 23 21 0 24 22 0 29 17 31 19 0 31 30 25 22 26 23 28 31 38 21 40 3627 34 37 43 38 41 36 41 40 46 42 40要从。点到16点则要先到23即0-23-16要从。点到23点则要先到17即 0-17-23-16要从。点到17点则要先到21即0-21-17-23-16 而。可以直接到21 所以从 0 到 16 的最优路径是0-21-17-23-16 最短的距离是w( 0,16

8、) =7493m模型二 对于问题一的求解模型的建立30件货物可以到达的地点可以知道i ， j= 13、 14、 16、 17、 18、 21、23、 24、 26、 27、 31、 32、 34、 36、 38、 39、 40、 42、 43、 45、 49。图2需要达到的点（红点标注的）目标函数是：T=MW- V+o x 30约束条件是:必须全部遍历回到0点即求出从。出发遍历这图的21个点的并回到o的最短的距离要距离最短则每一步也要最短，即从O开始找最短的点到达后继续找未遍历的最短的点则可求出最短的距离本题要求出回到。点则可以看到两个开始最短遍历的点在某点重合即可完成其中共经过21个点，运送

9、30件货物该30件货物“50kg v=n*所以可以一次把货物携带进行运送。由T与W关系可知要使所用的时间最小即所走的距离最短。即3SOO最短的遍历。模型的求解由图可以明显得出距离 。最近的点是21点和26点。由于32点到38点的距离小于32点到16点的距离为使从21点出来的线遍历右下的点完后再和 26点出 来的汇合则安排32点到35点断开。有程序2 （附录）可得：013112132321314334141643615175381618639172174018238421924943202610452127114922顺序和Columns 1 through 13I758134362&14132

10、1CqIluiuie 14 thr&ugh 2322192QIS15171112IQ1总的路程为：S. 3787+004总的时间是：3.7411遍历节点路线是:0-2-4-40-45-49-42-43-38-36-39-27-31-26-0最优的路线是：0-2-3-0-45-42-49-42-43-38-36-27-39-27-31-26-0总路程是：W=53787m最优时间是：T=模型三一对于问题二的求解模型的建立由第一个模型建立的可以求出到达24时所用的时间是：轲达2时所走的距黄U51，。十口口4到所用的时间0390可知到24点的时间是：t(24)二由表可知必须在9点之前把货物送到24点即

11、t(24)1故模型一不适用于问题二 的求解.由下图3可知：图3.考虑时间的点的位置由于右边的点的地点需要的时间要比左边的早，所以先分两个阶段，即先走左边后走右边即先走圈内的元素由程序 3 （附录）可得：从。出发经过 13、18、24、26、27、31、34、39、40 到达 4552673162792942432821383110401145而到13点时必须在9点之前到达但1,到45点时必须在9点半之前到达而 故分成两个阶段不成功，所以分四个阶段，求出各个阶段的最短距离和到达时的时间即可。目标函数:约束条件是:tj=Wi +v+2 toT到个点的时间最大值模型的求解图个阶段的圈图对四个阶段分别

12、求出到达的时间，由程序 4 （附录）可知分4个阶段1.从0出发经过13、18到24满足t1的条件31821342423133444054534254944323826、27、32、36、39 回到。II幡序为:目的暗程为二1. 101 04-0 0 1总的口寸E足：O. CJ0S7故路线为：0-18-13-24 2.从24出发经过31、34、40到45满足t顺回为I N 34 乒行的睹程为：1. 9S63e-*-UQ-l 忌啊日寸闻急：3317|故路线为：24-31-34-40-45 3.从45出发经过38、42、43到49满足t啡柿为1 13542总的跖耨沌：#703*4-0 04总附时向足

13、J9413所以路线为：45-42-49-43-38 4. 从 38 出发经过 14、16、17、21、23、1036827113972652141762393231614满足t4雁席为二总的馅程为：揖 7912ct0,04总的附间是；3.9130故路线为：38-36-27-39-27-3-32-16-14-21-0所以总的遍历点顺序是：0-4-40-45-42-49-43-38-36-27-39-26-2-14-0总时间是T=总距离是W=57912m最优路线是：0-49-42-43-38-36-27-39-27-3-32-23-16-14-21-0到每个点的时间见附录模型四一对于问题三的求解.

14、模型的建立本题中要遍历所有的50个点但由于M总= 147kg, v总=巾3而M50kg,V13故应该以M50k酢口 丫仔判断的标准到达的最远的点后返回目标函数：约束条件：M50kg,V13 模型的求解由。开始逐渐依次找出最近的点后再找出离该点最近的点直到不满足约束条件。见程序5 （附录）J50C图5.改进后的遍历图1第一阶段顺序用J031373936 3S 3532231721息的路程为：7122+004总的用词息：L. 73C1.第二阶段N顺序为黑 C o L muri1 t! Kr c ugH 1. 31JSSO40j G 710o01S1312C o L Lutaiu 1 1 Hul 0

15、-ig.lv 21 16434249忌日勺晤代为u3. 4.85Oe-i-Q04 短白勺白寸间早： 1. 5351.第三阶段顺序力E1 t Hr ouigh 1302 419Z 后29230 N 日 33 4E 当日 4441o l-umn s ithiraiiEh. I. 9374T45N。15口后的;蹈程为J：1,5 9366+0 057* 53994.第四阶段顺亨为I C 4250%的造偃力： ,1, 总的时间是： 2112模型的优化由于总的L =148kg卜:v=/所以最少要分四个阶段，但由于每次不可能刚好带满 50kg而如果只要3次则 最多只能带150kg只比原货物多2kg所以不可能

16、是三次就把货物带完，最少要四 次。故只需要把上述的模型进行数据处理就好了。过程如下：1.由于到21点时M=49 V若走过14则M大于了 50故直接从21点返回。第一次存货物 顺序为S0263127393638 3B 322317210总韵路程为： 2. 7122e+OOd 总的时间是士1, ?301最优路线为：0-26-3-38-35-32-23-17-21-0走的距离 W=27122m花费的时间T=2.若按程序给出的从13到8的路线是而当为13-11-12-8时更短故修改之；同时 到达40后如果选择34则45的周围全被遍历过。到45后M=,V坏满足要求，故从40到34后沿21-26返回。第2

17、次用培物顺耳为士Co Iwiltle 1 ttircuEh 13Q181312118316710 S 14Colunuvs 13 Through_ 21IC434249SO4034Q总总J 程为：8. 4850eT004总射时河是，4.C3E54最优路线为：0-3-5-38-43-42-49-50-40-45-36-21-0走得距离是：W=83220所用的时间是T=3.当到达45点时若要去20点放货物的话则需要遍历许多已经遍历过的地点,故从45点沿36-21-0返回第3次带货物顺序为：Cclwnns I through 130241925292230283346 到 4441Columns 1

18、4 through 1937474520150息的路程为：1. 5936 e+005总的时诃是E1 539gl最优路线为: 0-26-3-22-30-28-33-46-48-44-4-45-36-21-0所走的距离为：W=128970m所用的时间是：T=4.只余下了 5个点，所以由图可知第&次帚货物咂序为：04250总的路程为：L9347t+005总的时间是：8.2112路线为:0-26-3-22-20-2-5-2-4-3-8-12-13-18-O总路程是：W= 171510nW用的时间是T=由上面的四个阶段可以知道该问的 最优路线是： 0-26-3-38-35-32-23-6-23-32-3

19、5-38-43-42-49-50-40-45-36-20-28-33-46-4 8-44-4-45-36-20-2-5-2-4-3-8-12-13-18-0总路程是：W= 171510m所用的时间是T=5、模型的分析误差分析:对于模型一是使用了精确地 Dijkstra 算法，故误差可以忽略不计对于模型二假定了 32到38点的断开存在一定的误差，但相对于断开其余 的几点得到的数值要小，故该模型可以使用。对于模型三，由于分区域的方法有很多，故不可避免的存在些许误差，但由于区域越多，路程越多，故选择分成 4个区域最合适；分成的四个不同 的时间的到达区域比较紧密故按照时间的不同划分了四个区域，从而大大

20、的消除了误差，此模型可以使用。对于模型四的误差比较大，由于未考虑货物的拆分可能会有一定的影响同 时由于4个阶段的划分也是有一定的不确定性故误差存在。对于该模型简化 了考虑的条件，仅以M和V为判断标准，虽对准确性存在挑战，但该模型相 对与其他的分类有明显的优越性。故该模型适用于该问的求解。灵敏度分析对于模型一、二、三，灵敏度很好，模型的准确性很高。对于模型四由于质量和体积的制约，使其灵敏度不会很好，但准确性较高，因此模型可以使用。6、模型评价、改进和推广模型的评价优点：充分利用了已知数据建立模型，使其具有很高的准确性和可行性 使用了准确的算法和适当的假设，使模型的准确性和实用性到达统一运用功能强

21、大的Matlab工具使数据处理误差达到最小缺点由于数据较多，没法使用工具进行模型的验证，只能一步一步的精化模型模型的改进对于模型一和三主要是进行验证。对于模型二断开的那个点可以去取别的点进行。主要是模型四的改进，可以考虑到不同的地点送的货物进行拆分，从而渠道最优的解模型的推广可充分使用到图的遍历和最短路的一系列问题的求解中。参考文献First Course in Mathenmatical Moderling （Third Edition）Frank Maurice William图论任韩。数学建模案例选集姜启源 谢金星 TOC o 1-5 h z 图论 第 3 版 德 迪斯特尔著大学生数学建

22、模竞赛辅导教材叶其效基于 matlab 动态规划中最短路线的实现程序J 电脑学习施益昌 郑贤斌 李自立物流配送问题的混沌优化算法研究中央民族大学学报（ 自然科学版）2009年 11月第18卷第4期Dijkstra 算法在企业物流运输网络中的应用湖南农业大学学报（ 自然科学版） 2005 年 8月第29卷 4期附录附录 1. 、表格各货物号信息表货物号送达地点重里（公斤）体积（立方米）不超过时间1139: 002189: 003319: 3042612: 0052112: 0061412: 0071712: 0082312: 0093212: 00103810: 1511459: 3012431

23、0: 15133912: 0014459: 30154210: 15164310: 15173212: 00183612: 00192712: 0020249: 0021319: 30222712: 00232612: 0024349: 3025409: 3026459: 30274910: 15283212: 00292312: 00301612: 003113223333443553663773883994010411142124313441445154616471748184919502051215222532354245525562657275828592960306131623263

24、33643465356636673768386939704071417242734374447545764677477848794980508125824683328423852086258719884189469037913292339336943895179611971598129910100750个位置点的坐标位置点X坐标（米）丫坐标（米）191855002144556037270570437356705262099561008014357100252280871602525913845268010119353050117850354512658541851376305200141340

25、553251521255975161536570451714165738518882580751958558165207808355211277085602222008835231476590552477909330254435952526108609635271038510500285659765292580986530156599553193951010032148351036533125010900347280110653515305113753612390114153764101151038139151161039951012050408345123004149301365042132

26、6514145431418014215443030150604510915142354623301450047773514550488851488049115751516050801015325相互到达信息序号位直点1位置点21132183220424538634742851595210611171812711381214914159101610181710718111219121320122521121522131823131924131125141826141627141728142129152230152531162332172333183134192435202236212637213

27、638211739223040231741243142254143251944252945273146283347292248302849304150312651313452323553322354334655332856344057353858364559362760374061383662392763403464404565414466413767414668424369424970433871444872445073455074454275464876474077484478495079494280504081O1882O2183O26模型二中到达时的时间点到的时间最大允许的时间0001

28、8113124131344045424943383642743942642141742343241641440附录2、MATLABS序代码、Dijstra 求解clcclear alla=11000 8250;9185500;1445 560;7270570;3735 670;2620 995;10080 1435;10025 2280;71602525;13845 2680;11935 3050;7850 3545;6585 4185;7630 5200;13405 5325;2125 5975;153657045;14165 7385;8825 8075;5855 8165;780 835

29、5;12770 8560;2200 8835;14765 9055;77909330;4435 9525;10860 9635;10385 10500;565 9765;2580 9865;1565 9955;9395 10100;1483510365;1250 10900;7280 11065;15305 11375;12390 11415;6410 11510;13915 11610;951012050;8345 12300;4930 13650;13265 14145;14180 14215;3030 15060;10915 14235;233014500;7735 14550;885

30、14880;11575 15160;8010 15325;%a是各个点的坐标for i=1:51for j=1:51t=a(i,:)-a(j,:);c(i,j尸sqrt(t(1)A2+t(22);%两点之间的直线距离endend TOC o 1-5 h z a=13;1 8;2 20;2 4;3 8;3 4;42;5 15;5 2;6 1;718;7 1;8 12;9 14;910;10 18;107;1112;1213;1225;12 15;13 18;13 19;1311;14 18;14 16;1417;14 21;15 22;1525;16 23;1723;1831;1924;2022

31、;21 26;21 36;21 17;2230;23 17;24 31;2541;25 19;25 29;2731;28 33;2922;3028;30 41;31 26;31 34;32 35;32 23;33 46;33 28;34 40;35 38;36 45;36 27;37 40;38 36;39 27;40 34;40通路表45;41 44;41 37;41 46;42 43;42 49;43 38;44 48;44 50;45 50;45 42;46 48;47 40;48 44;49 50;49 42;50 40;0 18;0 21;0 26;%b=zeros(51);for

32、i=1:83b(a(i,1)+1,a(i,2)+1)=1;b(a(i,2)+1,a(i,1)+1)=1;enda=b.*c;for i=1:51for j=1:51if a(i,j)=0a(i,j)=inf;endif i=ja(i,j)=0;endendendw=a;for p=1:51n=size(w,1);w1=w(p,:);for i=1:nl(i)=w1(i);z(i)=1;ends=;s(1)=1;u=s(1);k=1;while kl(u)+w(u,i)l(i)=l(u)+w(u,i);z(i)=u;endendendendll=l;for i=1:nfor j=1:kif i=

33、s(j)ll(i)=ll(i);elsell(i)=inf;endendendlv=inf;for i=1:nif ll(i)lvlv=ll(i);v=i;endends(k+1)=v;k=k+1;u=s(k);endif p=1a=l;t=z;elsea=a;l;t=t;z;endendfor i=1:51a(i,i)=inf;% 把相同的点赋值为无穷大endsavea -ascii ; % 保存最小距离savet -ascii ; % 保存最小路径经过的点、问题一得求解clear allclcformat shortw=数据太多省略；p1=7;p2=10;sum=0;w(:,1)=inf;

34、w(:,p1)=inf;w(:,p2)=inf;w(13,16)=inf;w(16,13)=inf;x1=1,p1;x2=p2,1;for i=1:15s1,t1=min(w(p1,:);disp( 总的时间是： )s2,t2=min(w(p2,:);sum=sum+s1+s2;w(:,t1)=inf;w(:,t2)=inf;p1=t1;p2=t2;if t1=9|t2=9disp( 到达24时所走的距离 )disp(sum)T=sum/1000/24+3*i/60;disp( 到 24所用的时间 )disp(T)endif t1=t2x1=x1,t1;x=x1,x2;break ;endx1

35、=x1,t1;x2=t2,x2;x=x1,x2;enddisp( 顺序为： )disp(x)disp( 总的路程为： )disp(sum)T=sum/1000/24+3*30/60;disp(T)、问题二的2阶段求解clear allclcformat shortw=数据太多省略；p=1;x=1;sum=0;v=w;w(:,p)=inf;for i=1:10s,t=min(w(p,:);sum=sum+s;T=sum/1000/24+3*i/60;disp(t,T)w(:,t)=inf;p=t;x=x;t;end TOC o 1-5 h z disp( 顺序为： )disp(x)disp( 总

36、的路程为： )disp(sum)T=sum/1000/24+3*30/60;disp( 总的时间是： )disp(T)4阶段的解法disp(sum)clc clear allw=infinfinfinf;disp( 第一个区域 )p=1;x=1;sum=0;v=w;T=0;w(:,p)=inf;for i=1:3s,t=min(w(p,:);sum=sum+s;T=s/1000/24+T;disp(t,T)T=T+3/60;w(:,t)=inf;p=t;x=x;t;enddisp( 顺序为 )disp(x)disp( x总路程是：disp( 总时间是)disp(T)disp( 第二个区域 )w

37、=infinfinfinfinf;p=1;x=1;v=w;w(:,p)=inf;T=;for i=1:4s,t=min(w(p,:);sum=sum+s;T=T+3/60;T=s/1000/24+T;disp(t,T)if (i=1);T=T+3/60;endif (i=4);T=T+3/60*2;endw(:,t)=inf;p=t;endx=x;t;enddisp( 顺序为 )disp(x)disp( x总路程是：)disp(sum)disp( 总时间是)disp(T)disp( 第三个区域 )w=infinfinfinfinf;x=1 3 5 4 2;T=;for i=1:4m=i;s=w

38、(x(i),x(i+1);sum=sum+s;if (i=4)m=m+1;endT=s/1000/24+T;disp(x(i+1),T)T=T+3/60;enddisp( 顺序为 )T=T+3/60;disp(x)disp( x总路程是：)disp(sum)disp( 总时间是)disp(T)disp( 第四个区域 )w=数据太多省略；p=1;x=1;v=w;w(:,p)=inf;w(:,12)=inf;T=;for i=1:10s,t=min(w(p,:);sum=sum+s;T=s/1000/24+T;disp(t,T)T=T+3/60;w(:,t)=inf;p=t;x=x;t;if i=

39、2T=T+3/60;endif i=4if i=7T=T+3/60;endif i=8T=T+3/60*2;enddisp(p,sum)endsum=sum+v(t,12); TOC o 1-5 h z disp( 顺序是： )disp(x,1)disp( 总距离是： )disp(sum)T=sum/1000/24+3*30/60;disp( 总时间是： )disp(T)、问题 3 的初步设定clcclear allw=；i=1;while i50)|(V1)i=i+1;endsave w -ascii ;clcclear allloada=w;for i=1:51a(i,i)=inf;end

40、loadw=x;p=1;x=0;M=0;V=0;sum=0;v=a;a(:,p)=inf;disp( 第一阶段 )for i=1:50s,t=min(a(p,:);M=M+w(t-1,2);V=V+w(t-1,3);sum=sum+s;p=t;break ;endn=i;x=x;t-1;% disp(t-1,M,V) a(:,t)=inf;endsum=sum+v(p,1); TOC o 1-5 h z disp( 顺序为： )disp(x,0)disp( 总路程是： )disp(sum)T=sum/1000/24+3*i/60;disp( 所用时间是： )disp(T)disp( 第二阶段

41、)p=1;x=0;M=0;V=0;a(:,p)=inf;for i=1:50s,t=min(a(p,:);M=M+w(t-1,2);V=V+w(t-1,3);sum=sum+s;if (M50)|(V1)break ;break ;endendbreak ;endn=n+1;p=t;x=x;t-1;% disp(t-1,M,V)a(:,t)=inf;end TOC o 1-5 h z disp( 顺序为： )disp(x,0)disp( 总路程是： )disp(sum)T=sum/1000/24+3*i/60;disp( 所用时间是： )disp(T)disp( 第三阶段 )p=1;x=0;M

42、=0;V=0;a(:,p)=inf;for i=1:50-ns,t=min(a(p,:);M=M+w(t-1,2);V=V+w(t-1,3);sum=sum+s;if (M50)|(V1)p=t;x=x;t-1;% disp(t-1,M,V)a(:,t)=inf;n=n+1;endsum=sum+v(p,1); TOC o 1-5 h z disp( 顺序为： )disp(x,0)disp( 总路程是： )disp(sum)T=sum/1000/24+3*i/60;disp( 所用时间是： )disp(T)disp( 第四阶段 )p=1;x=0;M=0;V=0;a(:,p)=inf;for i=1:50-ns,t=min(a(p,:);M