送货路线设计问题111 16页

送货路线设计问题摘要我们建立了相应的模型来解决最优路径问题，使送货员耗时最少，路程最短。并讨论了在最大载重和最大带货体积一定情况下的有时间限制和无时间限制的最优路径问题。问题一，根据题中所给数据可求出30件货物质量之和为49.5公斤、体积之和为0.99立方米，故在问题一的模型建立中我们不用考虑质量、体积的约束。本文可以将该问题转化为TSP（旅行商）问题（本题可以重复经过某顶点），建立了求最小Hamilton圈模型，先利用Floyd算法求出任意顶点间最短路，构造连接各顶点的一个无向赋权完全图。再寻找该完全图中的最小Hamilton圈。本文用LINGO软件寻找该完备图中的最小Hamilton圈，从而得到问题一的最优解。依据程序运行结果，最后得出具体路径为：0—>2—>21—>17—>14—>16—>23—>32—>35—>38—>36—>38—>43—>42—>49—>42—>45—>40—>34—>31—>27—>39—>27—>31—>24—>19—>13—>18—>0且得到最短送货路线的总长d=54600m，总的时间为：226.50分钟。问题二中增加了’时间〃这一约束条件，而没有要求返回出发点。所以我们必须在满足各点的时间要求前提下，寻找一条最优的路径。我们根据时间优先的原则，即优先送货到时间要求较紧的地点，将所有货物送达点进行分块分组，我们将22个节点按时间限制划分为四个阶段：9:00、9:30.10:15.12:00四个阶段。分阶段后，由于各阶段所要求进过的地点个数较少，故在此问题中采用穷举法比较出其中耗时最短的路线，即为所求结果，最佳路线为：->18->13->19->24^>31->27->27->39->27->31->31->34^>40->45->45->45->42->49->42->43->43->38->36->38->35->32->32->32->23->23->16->14->17->21->26,总路程：53208米，总用时为（包括交货时间）：223.02分钟。问题三中由于考虑到送货员送货受到包裹最大重量和最大体积的限制，因此送货员必须返回原点取货，根据题中所给数据可求出100件货物质量之和为148公斤、体积之和为2.98立方米，因此送货员最少要三次返回0点取货，故我们首先将最小生成树的枝节点靠近主干划分为三个区域，在每个区域中求出最优Hamilton回路，从而得到最短送完所有货物的线路图的满意解，并标出送货路线。三个区域总路程和为最短路程为133509m,总时间为63378分钟。其中：红色线路区域最短回路为：0->26->引->27t39t27t36t45t40t47t40t50t49t42t43t38t35t32t23->17t21t0;路径长：42173米。绿色线路区域最短回路为：0t26t31t34t40t37t41t44t48t46t33t28t30t22t20t22t29t25t19t24t31t26t0;路径长：39895米。橙色线路区域最短回路为：0t21t17t23t16t14t9t10t7t1t6t1t8t3t4t2->5->15->12->11->13->18->0o路径长：51441米。即有：总路线长W=vv,+W2+W3=133509米总时间T二W*+3x“633.78分钟关键词：送货路线、最优路径、Floyd算法、TSP问题、穷举法一、问题重述现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛,每个送货员需要以最快的速度及时将货物送达，而且他们往往一人送多个地方，请设计方案使其耗时最少。现有一快递公司，库房在图I中的0点，一送货员需将货物送至城市内多处，请设计送 货方案，使所用吋间最少。该地形图的示意图见图1,各点连通信息见表3,假定送货员只能沿这些连通线路行走，而不能走其它任何路线。各件货物的相关信息见表1,50个位置点的坐标见表2。假定送货员最大载重50公斤，所带货物最大体积1立方米。送货员的平均速度为24公里/小吋。假定每件货物交接花费3分钟，为简化起见，同一地点有多件货物也简单按照每件3分钟交接计算。现在送货员要将100件货物送到50个地点。请完成以下问题。1.若将「30号货物送到指定地点并返回。设计最快完成路线与方式。给出结杲。标出行走路线。2.假定该送货员从早上8点上班开始送货，要广30号货物还需要按照预定时间内完成，请设计最快完成路线与方式。标出行走路线。3.若将100件货物全部送到指定地点并返回。设计最快完成路线与方式。由于受重量和体积限制，送货员可中途返冋取货。可不考虑中午休息时间。二、问题假设1.假设送货员只能沿如图路线图行驶，不能走其他的任何路线2.在联通路线中，送货员可自由选择3.送货员交接货物只需三分钟，同一地点多次交接也以三分钟计，且同一地区的货物只一次即可全部送达，无需再次回0点取货。交接完毕立即前往下一处，不会出现特殊情况而延误时间4.假设送货员的路上平均速度为24km/h,不考虑堵车及发生意外的情况5.假设相互连通的道路都是双向通道，没有单向的情况三、变量说明M,：所载i件货物的质量总和；V-:所载i件货物的体积总和；m；:第i件货物的质量；丹：第i件货物的体积；Ai：第i个顶点Dj：从i到j的最短路径长度v：送货员的平均速度dt.:从i点到j点的距离权值；w,:问题三中红色路线的总路程>v2：绿色路线的总路程%:橙色路线的总路程四、问题分析分析问题一：根据附表1所给数据可求出30件货物质量之和为49.5公斤、体积之和为0.99立方米，即此吋送货员可一次性携带30个包裹送货到指定地点并返回。故在此模型建立中我们不用考虑质量、体积的约束。，从而最佳运送方案等价于找出一个遍历所有目的顶点人并返回出发点的最短路线。首先我们可以根据两点间的坐标，利用Matlab软件编程，计算出各连通顶点 （Ai,A.J间的距离，并赋其相应边的距离权值为〃“，再利用Floyd算法求出任意两点间最短路径。构造连接各顶点的一个无向赋权完全图。再用LINGO软件寻找该完备图中的最小Hamilton圈，从而得到问题一的最优解。分析问题二：问题二屮加上了时间限制后，首先我们将22个节点按时间限制划分为四个阶段：9:00、9:30、10：15、12:00四个阶段。分阶段后，由于各阶段所要求进过的地点个数较少，故在此问题中采用穷举法就可以比较出其中耗时最短的路线。第一时间段即8:00——9:00Z间送到的站点为：13、18、39、27、24第二时间段即9:00——9:30之间送到的站点为：31、34、40、45第三时间段即9:30——10:15之间送到的站点为：42、49、43、38第四时间段即10:15——12:00之间送到的站点为：36、32、23、16、14、17、21、26分析问题三：对于问题三要在体积和质量的双重限制下得到送货员最快完成送货的路线，1・・・ioo号货物的总重量是148公斤，总体积是2.98公斤，根据是时间和体积的限制，送货员至少要往返三次送货，又由于要求最快完成，则可通过在满足时间和体积的条件下划分区域求局部最短回路，从而得到全局最短路的满意解。五、模型的建立与求解㈠问题一模型的建立与求解⑴根据各顶点的坐标,利用Matlab软件编程（附表二），计算出各连通顶点（A“Aj）间的距离，并赋其相应边的距离权值为，如下表:序号位置点1位置点2距离（米）1131916218286432207823424229353819586343536751550058521253961129410718591811714510128121757139142681149101946810/51182182820/51211797830/51261392 ⑵利用Eloyd算法求出任意两个顶点A,Aj之间的距离权值（最短路径长度）％,如下表：1234567849500/511077451916545289981294196828642030616989100682774505829229312539039971377872557022001162963191658290353670823210388419582070517388104674545222933536035466746742054942424120924140035899812537082354601029210966904024317207481656361294903932106746102920326241582160018283113627196897133884742010966326204832183381502181008286477871958549490404158483201874715430850949203062557020705242412431721600183381874703569117215016989220011738820924207481828315021154303569099280/51100681629610467140031656311362810085091172199280⑶根据完全图再用LINGO软件（附表三）图屮的最小Hamilton圈，从而得到问题一的最优解。模型求解借助数学工具LTNGO,求出最优解如下：路线：0—>26—>21—>17—>14—>16—>23—>32—>35—>38—>36—>38—>43—>42一>49一>42一>45—>40一>34—>31一>27—>39一>27一>31一>24—>19一>13一>18—>0得到最短送货路线的总长d二54600m，总的时间为：226.50分钟。送货员行走路线如图所示： 40193724124537313223180图例:21h35往返118315002000-9——路线°送达地点250030003500㈡问题二模型的建立与求解问题二我们利用分块思想，将22个节点按时间限制划分为四个阶段：9:00、9:30、10：15、12:00,用局部全排列穷举法求解每一块的最佳路径。如下图为分块示意图： 由于考虑到送货时间运输限制，我们优先考虑送货时间，即以送货时间对所有货物进行分块，并在每一块内部釆用局部全排列穷举法求取路径，并判断其总的送货时间是否满足指定的吋间。其基本步骤为：(1)第一时间段为8:00——9:00之间送到的站点为：13、18、39、27、24,不计重复站点总共有5个站点利用穷举法比较后得到最佳路线0->18->13->19->24->31->27->39,考虑交货吋间在内总吋间为57.1分钟，走完后此吋的时间为8:57。(2)第二时间段为9:00——9:30之间送到的站点为：31、34、40、45,不计重复站点，总共有4个站点，利用穷举法比较后得到最佳路线为：39->27->31->34->40->45,考虑交货吋I"可在内总吋间为46.05分钟。走完后此吋的吋间为9:43。所以即使按最佳路径走也无法按要求完成，但为了满足吋间优先原则，使货物尽早到达相应地点，选择的最佳路线为：39->27->31->34->40->45。(3)第三时间段为9:30——10:15之间送到的站点为:42、49、43、38,不计重复站点,总共有4个站点，利用穷举法比较后得到最佳路径为：45->42->49->42->43->3&考虑交货时间在内总时间为39.3钟。走完后此时的时间为10:22。所以即使按最佳路径走也无法按要求完成，但为了满足时间优先原则，使货物尽早到达相应地点，选择的最佳路线为：45->42->49->42->43->38o(4)第四时间段为10:15——12:00之间送到的站点为：36、32、23、16、14、17、21、26,不计重复站点，总共有8个站点，利用穷举法比较后得到最佳路径为：38->36->38->35>32->23->16->14->17->21->26o考虑交货时间在内总时间为80.6分钟。走完后此时的时间为11:43。因此，根据题冃所给的时间段分块所得结果：最佳送货路线为：0->18->13->19->24->31->27->39->27->31->34->40->45->42->49->42->43->38->36->38->35>32->23->16->14->17->21->26总路程：53208米用时为(包括交货时间)：223.02分钟送货员行走路线示意图为：asoor ㈢问题三模型的建立与求解本问同样是图上点的行遍性问题。此问题的限制条件是送货员一次送货的重量和体积，由此限制，将图上区域在满足条件下划分为尽可能少的区域块，在此基础上实现区域线路最短，从而实现全局最短。最小支撑树的定义：加权连通图里权和最小的支撑树称为最小支撑树。首先用fATLAB程序生成最小支撑树，再根据最小支撑树将图划分区域，并根据送货员一次送货质量和体积的限值对区域边界上的点进行调整，是各区域满足质量和体积的限制，当无法满足条件时就要通过增加划分的块数实现。求出各区域的最优哈米尔顿冋路，将各区域回路并起来得到满意的送货线路。模型的求解运行C语言程序，得到以0点为源点的最小支撐树，见下图根据表中数据可得100件货物的总重量为148公斤，体积为2.98立方米，按照对送货重量和体积的限制，一次送货总量不得超过50公斤，体积不得超过1立方米，可知送货员至少往返三次，即至少要划分为三个区域，根据最小生成树先将图划分为三个区域，使最小支撑树的相连路线尽可能的归于同一个区域，在此基础上再根据质量和体积调整临界点，从而得到三个区域（见下图，分别用红、绿、橙线表示）。三个区域的最短回路分别为：红色线路区域最短回路为：0-26-31-27-39-27-36-45-40-47-40-50-49-42->43->38-*35->32-*23-*17-*21->0；路径总长％=42173米。绿色线路区域最短回路为：0-26->31->34-40-37-41-44-48-46-33-28-30-22—20-22-29-25—19~24~31~26~0；路径总长W2=39895米。橙色线路区域最短回路为：0->21->17->23->16->14->9->10->7->1->6->1->8->3->4->2-5-15-12-11-13-18-0。路径总长旳二51441米。总路线长W=yv,+M+加=133509米总时间T=W-v+3x/?=633.78分钟线路图为： 16000°i14000-12000-10000-8000-6000-40002000200040006000800010000120001400016000六、对模型的评价与推广㈠对模型的评价1.本模型在建模过程中，对送货员送货的过程以及交接吋间做了合理的简化，建立了最短路模型，模型简单、清晰，具有一定的普遍意义。2.在具体问题中，根据限制条件合理划分区域处理，使问题得以简化，同时在分类时提出了理论依据，不是简单的依据经验，客观性很强，具有一定的创新性和先进性。3.本文所建模型中，提供了较多的图形解说，使得文章直观易懂，可读性较强。4.有很多其他影响因素没有考虑在模型中，例如售货员在回到库房取货，期间必有停留，但在模型中我们并未考虑这段吋间。㈡对模型的推广1、本模型不但适合于快递公司送货问题，还是用于一般的送货以及运输问题，只紺要稍微改动模型即可；2、模型方便、直观，可以实现计算机模拟；3、建模的方法和思想可以推广到其他类型，如午辆调度问题等。参考文献[1]唐焕文，数学模型引论（第三版）,北京：高等教育出版社，2005。[2]《运筹学》教材编写组，运筹学（修订版），北京：清华大学出版社，1982。[3]汪晓银，数学软件与数学实验，北京，科学出版社，2008。 [1]姜启源.《数学建模教程》[M].北京:清华大学出版社2005.附表一表1各货物号信息表货物号送达地点重量（公斤）体积（立方米）不超过时间1132.500.03169：002180.500.03549：003311.180.02689：304261.560.035012：005212.150.037712：006141.720.010012：007171.380.010912：008231.400.042612：009320.700.048112：0010381.330.031910：1511451.100.02879：3012430.950.022810：1513392.560.05959：0014452.280.05019：3015422.850.019010：1516431.700.078210：1517320.250.051212：0018361.790.018412：0019272.450.05459：0020242.930.05209：0021310.800.01089：3022272.250.00189：0023261.570.021012：0024342.800.01039：3025402.140.01559：3026450.680.06829：3027491.350.014410：1528320.520.002012：0029232.910.058712：0030161.200.042912：003111.260.0253221.150.05013331.630.04833441.230.00063551.410.03873660.540.00673770.700.01293880.760.0546 3992.140.008740101.070.012441111.370.05142122.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.05859291.340.037260300.060.040261310.600.027462322.190.050363331.890.049464341.810.032565351.000.005566361.240.017767372.510.036168382.040.01169391.070.04470401.490.032971410.510.009472421.380.055573431.310.012174441.260.000575450.980.041376461.350.024177472.120.02378480.540.054279491.010.056680501.120.028481250.790.001182462.120.049283321.770.003484232.290.005485200.210.041886251.290.008887191.120.0249 88410.900.003889462.380.043490371.420.00291321.010.041792332.510.013393360.170.037594381.820.030895170.330.034596110.300.017297154.430.053698120.240.005699101.380.017510071.980.0493表250个位置点的坐标位置点X坐标（米）Y坐标（米）191855002144556037270570437356705262099561008014357100252280871602525913845268010119353050117850354512658541851376305200141340553251521255975161536570451714165738518882580751958558165207808355211277085602222008835231476590552477909330254435952526108609635271038510500285659765292580986530156599553193951010032148351036533125010900 3472801106535153051137536123901141537641011510381391511610399510120504083451230041493013650421326514145431418014215443030150604510915142354623301450047773514550488851488049115751516050801015325表3相互连通信息序号位置点1位置点211321832204245386347428515952106111718127113812149141591016101817107181112191213201225211215221318231319241311251418261416271417281421291522 75177O6968$6665636266O595005655535255O494OC£4645444344O393CO373635333233O49400464545444342424444O4O393OC3636353433333232333O3O2928bO25252524232222g8s冷5O444O48425O5O483004943464445to364ObO45384O200462335M264»_fc2OC2233329E43►—a3Oh—*3626223232325 794942805040810188202183026附表二p二[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;110008250];nod二zeros(51)nod(13,18)=1;nod(14,18)=1;nod(14,16)=1;nod(14,17)=1;nod(14,21)=1;nod(16,23)=1;nod(17,23)=1;nod(18,31)=1;nod(21,26)=1;nod(21,36)=1;nod(21,17)=1;nod(23,17)=1;nod(24,31)=1;nod(27,31)=1;nod(31,26)=1;nod(31,34)=1; nod(32,23)二1nod(34,40)=1nod(36,45)=1nod(36,27)=1nod(38,36)=1nod(39,27)=1nod(40,34)=1nod(40,45)=1nod(42,43)=1nod(42,49)=1nod(43,38)=1nod(45,42)=1nod(49,42)=1nod(51,21)=1nod(51,26)=1nod(18,13)=1nod(18,14)=1nod(16,14)=1nod(17,14)=1nod(21,14)=1nod(23,16)=1nod(23,17)=1nod(31,18)=1nod(26,21)=1nod(36,21)=1nod(17,21)=1nod(17,23)=1nod(31,24)=1nod(31,27)=1nod(26,31)=1nod(34,31)=1nod(23,32)=1nod(40,34)=1nod(45,36)=1nod(27,36)=1;nod(36,38)=1; nod(27,39)=1;nod(34,40)=1;nod(45,40)=1;nod(43,42)=1;nod(49,42)=1;nod(3&43)=1;nod(42,45)=1;nod(42,49)=1;nod(21,51)=1;nod(26,51)=1;gplot(nod,p,"-o")a=l:51;fori=l:51text(p(i,1),p(i,2),num2str(a(i)))endA=nchoosek(l:51,2);A=full(sparse(A(:,1),A(:,2),pdist(p),51,51))A二A+A"fori=l:51forj=l:51for21:51ifA(i,k)+A(k,j)