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

装订线第九届西安电子科技大学数学建模竞赛暨全国大学生数学建模竞赛选拔赛题目A(B)题密封号2010年5月4日剪切线密封号2010年5月4日通信工程学院第队队员1队员2队员3姓名邓晓光谭正中刘春燕班级 送货路线设计问题1、问题重述现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个送货员需要以最快的速度及时将货物送达，而且他们往往一人送多个地方，请设计方案使其耗时最少。现有一快递公司，库房在图1中的O点，一送货员需将货物送至城市内多处，请设计送货方案，使所用时间最少。该地形图的示意图见图1，各点连通信息见表3，假定送货员只能沿这些连通线路行走，而不能走其它任何路线。各件货物的相关信息见表1，50个位置点的坐标见表2。假定送货员最大载重50公斤，所带货物最大体积1立方米。送货员的平均速度为24公里/小时。假定每件货物交接花费3分钟，为简化起见，同一地点有多件货物也简单按照每件3分钟交接计算。现在送货员要将100件货物送到50个地点。请完成以下问题。1.若将1~30号货物送到指定地点并返回。设计最快完成路线与方式。给出结果。要求标出送货线路。2.假定该送货员从早上8点上班开始送货，要将1~30号货物的送达时间不能超过指定时间，请设计最快完成路线与方式。要求标出送货线路。3.若不需要考虑所有货物送达时间限制(包括前30件货物)，现在要将100件货物全部送到指定地点并返回。设计最快完成路线与方式。要求标出送货线路，给出送完所有快件的时间。由于受重量和体积限制，送货员可中途返回取货。可不考虑中午休息时间。2、问题分析送货路线问题可以理解为：已知起点和终点的图的遍历问题的合理优化的路线设计。图的遍历问题的指标：路程和到达的时间，货物的质量和体积，以及最大可以负载的质量和体积。在路线的安排问题中，考虑所走的路程的最短即为最合理的优化指标。对于问题二要考虑到所到的点的时间的要求是否满足题意即采用多次分区域的假设模型从而找出最优的解 对于问题三则要考虑到体积和质量的双重影响，每次到达后找到达到最大的体积和质量的点然后返回，再依次分析各个步骤中可能存在的不合理因素达到模型的进一步合理优化得到最合理的解。1、模型假设与符号说明3.1、模型的假设（1）、到同一地点的货物要一次拿上，即不考虑再以后又经过时再带些货物（2）、要求达到不超过的时间不包括此次在该点交易的时间。（3）、所用的距离数据都精确到米而时间则精确到0.0001h（4）、同一地点有多件货物也简单按照每件3分钟交接计算。3.2、符号说明其中i，j=1、2、3……50并且M=50kgV=12、模型的建立及求解模型四模型三模型二模型一最短路径模型图的遍历模型多区域最短路多阶段最短路任意两点之间的最短路距离由起始点遍历路径回到原点多区域无返回起点的最短路多阶段有返回起点的最短路 模型一1.1模型的建立我们为了求出各个点的之间的最短的路径，使用Dijstra算法求解。Dijkstra算法是图论中非常有名的一个算法。　图采用邻接矩阵的形式描述，w（i,j）表示结点i到结点j间的最短距离，如果没有直接连通，则为无穷大，计算机中可以用一个很大的数据代替（如matlab中的inf）。　但dijkstra算法只能求出从结点i到其它各结点的最短路径。算法引入这样两个集合s和t，s是那些已经确定了到i结点的最短路径的结点，t为全集u和s的差集，即那些还未确定最短路径的结点。而且s的初值是{i}，t的初值是u-{i}。另外再引入一个标记数组d[n]，其中在某一步d[k]表示当前从i到k的较短路径，d[k]的初值为w（i，k）。整个算法过程如下：　１、在t中选择一个d[k]最小的结点k，将k并入s，并从t中去掉，如果t为｛｝则转到３；　２、用k结点和t中其余结点进行一遍比较，如果d[i]>d[k]+m[k][i]，则用d[k]+m[k][i]取代原来的d[i]，重复１；　３、算法结束，此时d[k]中保存的就是从i到k结点的最短路径。　算法就以这样非常简单的形式完成了求解，时间复杂度是O(n^2)，确定了从i到其余各结点的最短路径。1.2模型的求解根据算法和相邻的点的距离可以用dijkstra求出任意两点的最短路径。 图1相邻的点的距离使用循环的结构求出1-50各个点之间的最短距离。程序1见附录2.1可以求出w和aa为最短路径是的所过的的地点如从O开始到其余50个点的a(0)=[074831511812141813131821122321024220291731190313025222623283138214036273437433841364140464240]要从O点到16点则要先到23即0-23-16要从O点到23点则要先到17即0-17-23-16要从o点到17点则要先到21即0-21-17-23-16而O可以直接到21所以从0到16的最优路径是0-21-17-23-16最短的距离是w（0,16）=7493m模型二—对于问题一的求解2.1模型的建立由前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需要达到的点（红点标注的）其中共经过21个点，运送30件货物该30件货物=47.3kg<50kg=0.8371,所以可以一次把货物携带进行运送。由T与W关系可知要使所用的时间最小即所走的距离最短。即目标函数是：T=W÷V+×30约束条件是：必须全部遍历回到0点即求出从O出发遍历这图的21个点的并回到o的最短的距离要距离最短则每一步也要最短，即从O开始找最短的点到达后继续找未遍历的最短的点则可求出最短的距离。本题要求出回到O点则可以看到两个开始最短遍历的点在某点重合即可完成最短的遍历。2.2模型的求解 由图可以明显得出距离O最近的点是21点和26点。由于32点到38点的距离小于32点到16点的距离为使从21点出来的线遍历右下的点完后再和26点出来的汇合则安排32点到35点断开。有程序2（附录2.2）可得：013112132321314334141643615175381618639172174018238421924943202610452127114922遍历节点路线是：0-21-17-23-32-16-14-18-13-24-34-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-31-26-0总路程是：W=53787m最优时间是：T=3.7411h模型三—对于问题二的求解3.1模型的建立由第一个模型建立的可以求出到达24时所用的时间是: 可知到24点的时间是：t(24)=2.0880由表2.1可知必须在9点之前把货物送到24点即t(24)<1故模型一不适用于问题二的求解.由下图3可知：图3.考虑时间的点的位置由于右边的点的地点需要的时间要比左边的早，所以先分两个阶段，即先走左边后走右边即先走圈内的元素由程序3（附录2.3）可得：从O出发经过13、18、24、26、27、31、34、39、40到达455260.10807310.22206270.31659290.44074240.68353280.89542131.07518311.439310401.557311451.7413而到13点时必须在9点之前到达但1.0751>1，到45点时必须在9点半之前到达而1.7412>1.5故分成两个阶段不成功，所以分四个阶段，求出各个阶段的最短距离和到达时的时间即可。 目标函数：=÷v+约束条件是：T到个点的时间最大值3.2模型的求解①④③②图4.4个阶段的圈图对四个阶段分别求出到达的时间，由程序4（附录2.4）可知l分4个阶段3180.09092130.27064240.55871.从0出发经过13、18到24。满足t<1的条件故路线为：0-18-13-242310.73293340.92974401.0477 5451.23171.从24出发经过31、34、40到45。满足t<1.5故路线为：24-31-34-40-453421.42975491.56184431.73222381.89132.从45出发经过38、42、43到49。满足t<2.25所以路线为：45-42-49-43-383.从38出发经过14、16、17、21、23、26、27、32、36、39回到O。10362.00548272.147211392.32147262.55405212.74544172.87146232.99539323.15003163.44202143.6007满足t<4故路线为：38-36-27-39-27-31-26-21-17-23-32-16-14-21-0所以总的遍历点顺序是：0-18-13-24-31-34-40-45-42-49-43-38-36-27-39-26-21-17-23-32-16-14-0总时间是T=3.9130h总距离是W=57912m最优路线是：0-18-13-19-24-31-34-40-45-42-49-42-43-38-36-27-39-27-31-26-21-17-23-32-23-16-14-21-0到每个点的时间见附录1.4 模型四—对于问题三的求解4.1．模型的建立本题中要遍历所有的50个点但由于=147kg，=2.8而M<50kg,V<1故应该以M<50kg和V<1判断的标准到达的最远的点后返回。目标函数：W=约束条件：M<50kg,V<14.2模型的求解由O开始逐渐依次找出最近的点后再找出离该点最近的点直到不满足约束条件。见程序5（附录2.5）图5.改进后的遍历图1第一阶段2.第二阶段 3.第三阶段4.第四阶段4.3模型的优化由于总的=148kg=2.8所以最少要分四个阶段，但由于每次不可能刚好带满50kg而如果只要3次则最多只能带150kg只比原货物多2kg所以不可能是三次就把货物带完，最少要四次。故只需要把上述的模型进行数据处理就好了。过程如下：1.由于到21点时M=49V=0.8757若走过14则M大于了50故直接从21点返回。最优路线为：0-26-31-27-39-27-36-38-35-32-23-17-21-0走的距离W=27122m，花费的时间T=1.73012.若按程序给出的从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返回。 最优路线为: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走得距离是：W=83220，所用的时间是T=4.46753.当到达45点时若要去20点放货物的话则需要遍历许多已经遍历过的地点，故从45点沿36-21-0返回最优路线为：0-26-31-24-19-25-29-22-30-28-33-46-48-44-41-37-40-47-40-45-36-21-0所走的距离为：W=128970m，所用的时间是：T=6.12384.只余下了5个点,所以由图可知路线为：0-26-31-24-19-25-15-22-20-2-5-2-4-3-8-12-13-18-o总路程是：W=171510m所用的时间是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-15-22-20-2-5-2-4-3-8-12-13-18-o总路程是：W=171510m所用的时间是T=7.3964 1、模型的分析①误差分析：对于模型一是使用了精确地Dijkstra算法，故误差可以忽略不计对于模型二假定了32到38点的断开存在一定的误差，但相对于断开其余的几点得到的数值要小，故该模型可以使用。对于模型三，由于分区域的方法有很多，故不可避免的存在些许误差，但由于区域越多，路程越多，故选择分成4个区域最合适；分成的四个不同的时间的到达区域比较紧密故按照时间的不同划分了四个区域，从而大大的消除了误差，此模型可以使用。对于模型四的误差比较大，由于未考虑货物的拆分可能会有一定的影响同时由于4个阶段的划分也是有一定的不确定性故误差存在。对于该模型简化了考虑的条件，仅以M和V为判断标准，虽对准确性存在挑战，但该模型相对与其他的分类有明显的优越性。故该模型适用于该问的求解。②灵敏度分析对于模型一、二、三，灵敏度很好，模型的准确性很高。对于模型四由于质量和体积的制约，使其灵敏度不会很好，但准确性较高，因此模型可以使用。2、模型评价、改进和推广6.1模型的评价优点：l充分利用了已知数据建立模型，使其具有很高的准确性和可行性l使用了准确的算法和适当的假设，使模型的准确性和实用性到达统一l运用功能强大的Matlab工具使数据处理误差达到最小缺点l由于数据较多，没法使用工具进行模型的验证，只能一步一步的精化模型6.2模型的改进对于模型一和三主要是进行验证。对于模型二断开的那个点可以去取别的点进行。主要是模型四的改进，可以考虑到不同的地点送的货物进行拆分，从而渠道最优的解6.3模型的推广可充分使用到图的遍历和最短路的一系列问题的求解中。 1、参考文献1.AFirstCourseinMathenmaticalModerling(ThirdEdition)FrankR.GiordianoMauriceD.weirWilliamP.Fox2.图论任韩。3.数学建模案例选集姜启源谢金星4.图论第3版德迪斯特尔　著5.大学生数学建模竞赛辅导教材叶其效6.基于matlab动态规划中最短路线的实现程序[J]电脑学习施益昌郑贤斌李自立7.物流配送问题的混沌优化算法研究中央民族大学学报(自然科学版)2009年11月第18卷第4期8.Dijkstra算法在企业物流运输网络中的应用湖南农业大学学报(自然科学版)2005年8月第29卷4期附录附录1.、表格1.1各货物号信息表货物号送达地点重量(公斤)体积(立方米)不超过时间1132.500.03169：002180.500.03549：003311.180.02409：304261.560.035012：005212.150.030512：006141.720.010012：007171.380.010912：008231.400.042612：009320.700.048112：0010381.330.021910：1511451.100.02879：3012430.950.022810：1513392.560.059512：0014452.280.03019：3015422.850.019010：1516431.700.078210：1517320.250.041212：0018361.790.018412：0019272.450.044512：0020242.930.04209：00 21310.800.01089：3022272.250.001812：0023261.570.021012：0024342.800.01039：3025401.140.01559：3026450.680.03829：3027491.350.014410：1528320.520.002012：0029232.910.048712：0030161.200.042912：003111.260.02503221.150.05013331.630.04833441.230.00063551.410.03873660.540.00673770.700.01293880.760.03463992.140.008740101.070.012441111.370.051042122.390.042843130.990.004844141.660.049145150.450.020946162.040.009847171.950.032448182.120.055449193.870.026250202.010.032451211.380.041952220.390.000153231.660.050254241.240.053455252.410.001256261.260.005957270.420.022458281.720.058059291.340.037260300.060.040261310.600.027462322.190.050363331.890.0494 64341.810.032565351.000.005566361.240.017767372.510.036168382.040.011069391.070.044070400.490.032971410.510.009472421.380.045573431.310.012174441.260.000575450.980.041376461.350.024177472.120.023078480.540.054279491.010.056680501.120.028481250.790.001182462.120.049283322.770.003484232.290.005485200.210.049086251.290.008887191.120.024988410.900.003889462.380.043490371.420.002091321.010.030092332.510.013393361.170.002094381.820.030895170.330.034596110.300.017297154.430.053698120.240.005699101.380.017510071.980.04931.250个位置点的坐标位置点X坐标(米)Y坐标(米)19185500214455603727057043735670 52620995610080143571002522808716025259138452680101193530501178503545126585418513763052001413405532515212559751615365704517141657385188825807519585581652078083552112770856022220088352314765905524779093302544359525261086096352710385105002856597652925809865301565995531939510100321483510365331250109003472801106535153051137536123901141537641011510381391511610399510120504083451230041493013650421326514145431418014215443030150604510915142354623301450047773514550 4888514880491157515160508010153251.3相互到达信息序号位置点1位置点211321832204245386347428515952106111718127113812149141591016101817107181112191213201225211215221318231319241311251418261416271417281421291522301525311623321723331831341924352022362126372136 382117392230402317412431422541432519442529452731462833472922483028493041503126513134523235533223543346553328563440573538583645593627603740613836623927634034644045654144664137674146684243694249704338714448724450734550744542754648764740774844784950794942805040 81O1882O2183O261.4模型二中到达时的时间点到的时间最大允许的时间000180.09091130.27061240.55871310.73291.5340.92971.5401.04771.5451.23171.5421.42972.25491.56182.25431.73222.25381.89132.25362.00544272.14724392.32144262.5544212.74544172.87144232.99534323.154163.4424143.6007403.9031附录2、MATLAB程序代码2.1、Dijstra求解clcclearalla=[110008250;9185500;1445560;7270570;3735670;2620995;100801435;100252280;71602525;138452680;119353050;78503545;65854185;76305200;134055325;21255975;153657045;141657385;88258075;58558165;7808355;127708560;22008835;147659055;77909330;44359525;108609635;1038510500;5659765;25809865;15659955;939510100;1483510365;125010900;728011065;1530511375;1239011415;641011510;1391511610;951012050;834512300;493013650;1326514145;1418014215;303015060;1091514235;233014500;773514550;88514880;1157515160;801015325];%a是各个点的坐标 fori=1:51forj=1:51t=a(i,:)-a(j,:);c(i,j)=sqrt(t(1)^2+t(2)^2);%两点之间的直线距离endenda=[[13;18;220;24;38;34;42;515;52;61;718;71;812;914;910;1018;107;1112;1213;1225;1215;1318;1319;1311;1418;1416;1417;1421;1522;1525;1623;1723;1831;1924;2022;2126;2136;2117;2230;2317;2431;2541;2519;2529;2731;2833;2922;3028;3041;3126;3134;3235;3223;3346;3328;3440;3538;3645;3627;3740;3836;3927;4034;4045;4144;4137;4146;4243;4249;4338;4448;4450;4550;4542;4648;4740;4844;4950;4942;5040;018;021;026];%通路表b=zeros(51);fori=1:83b(a(i,1)+1,a(i,2)+1)=1;b(a(i,2)+1,a(i,1)+1)=1;enda=b.*c; fori=1:51forj=1:51ifa(i,j)==0a(i,j)=inf;endifi==ja(i,j)=0;endendendw=a;forp=1:51n=size(w,1);w1=w(p,:);fori=1:nl(i)=w1(i);z(i)=1;ends=[];s(1)=1;u=s(1);k=1;whilekl(u)+w(u,i)l(i)=l(u)+w(u,i);z(i)=u;endendendendll=l;fori=1:nforj=1:kifi~=s(j)ll(i)=ll(i);elsell(i)=inf;endendendlv=inf;fori=1:nifll(i)50)|(V>1))break;endn=i;x=[x;t-1];%disp([t-1,M,V])a(:,t)=inf;endsum=sum+v(p,1);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;fori=1:50[s,t]=min(a(p,:));M=M+w(t-1,2);V=V+w(t-1,3);sum=sum+s;if((M>50)|(V>1))break;endn=n+1;p=t;x=[x;t-1];%disp([t-1,M,V])a(:,t)=inf;enddisp("顺序为：")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;fori=1:50-n[s,t]=min(a(p,:));M=M+w(t-1,2);V=V+w(t-1,3);sum=sum+s;if((M>50)|(V>1))break;endp=t;x=[x;t-1];%disp([t-1,M,V])a(:,t)=inf;n=n+1;endsum=sum+v(p,1);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;fori=1:50-n[s,t]=min(a(p,:));M=M+w(t-1,2);V=V+w(t-1,3);sum=sum+s;if((M>50)|(V>1))break;endp=t;x=[x;t-1];a(:,t)=inf;n=n+1;endsum=sum+v(p,1);disp("顺序为：")disp([x",0])disp("总距离是：");disp(sum)T=sum/1000/24+3*i/60;disp("总时间是：");disp(T)2.6、问题三的优化clcclearallloadw.txta=w;loadx.txtw=x;p=1;x=0;M=0;V=0;sum=0;v=a;a(:,p)=inf;fori=1:50[s,t]=min(a(p,:)); M=M+w(t-1,2);V=V+w(t-1,3);sum=sum+s;p=t;if((M>50)|(V>1))break;endn=i;x=[x;t-1];disp([t-1,M,V])a(:,t)=inf;endsum=sum+v(p,1);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;fori=1:50[s,t]=min(a(p,:));M=M+w(t-1,2);V=V+w(t-1,3);sum=sum+s;if((M>50)|(V>1))break;endn=n+1;p=t;x=[x;t-1];disp([t-1,M,V])a(:,t)=inf;endsum=sum+v(p,1)-1630.4;sum=sum+v(p,1);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;fori=1:50-n[s,t]=min(a(p,:));M=M+w(t-1,2);V=V+w(t-1,3);sum=sum+s;if((M>50)|(V>1))break;endp=t;x=[x;t-1];disp([t-1,M,V])a(:,t)=inf;n=n+1;ift==46break;endendsum=sum+v(p,1);sum=sum+v(p,1);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;fori=1:50-n[s,t]=min(a(p,:));M=M+w(t-1,2);V=V+w(t-1,3);sum=sum+s;if((M>50)|(V>1)) break;endp=t;x=[x;t-1];disp([t-1,M,V])a(:,t)=inf;n=n+1;endsum=sum+v(p,1);sum=sum+v(p,1);disp("顺序为：")disp([x",0])disp("总路程是：")disp(sum)T=sum/1000/24+3*i/60;disp("所用时间是：")disp(T)