《送货路线问题论》word版.doc

《《送货路线问题论》word版.doc》由会员分享，可在线阅读，更多相关《《送货路线问题论》word版.doc（34页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、送货线路设计模型摘要：针对题目所给关于货物配送的一系列问题，通过已知起点和终点的图的遍历问题来建立合理优化的路线设计，使送货员耗时最少，路程最短，并讨论了在最大载重和最大带货体积一定情况下的有时间限制和无时间限制的最优路径问题。对于问题一，根据题中数据计算30件货品的总质量与体积，得出的结果不超过送货员的最大载重量，在此我们只考虑最短路径问题，我们利用Floyd算法求出任意顶点间的最短路径距离，最后利用MatlabLingo 软件得出从O点出发经过各节点又回到O点的最短路径。对于问题二，在第一问的基础上加入时间限制，根据不同的地点到达的时间不同，对整个路线图进行阶段划分，然后对于不同的阶段转化

2、为一个新的求最短路径的问题。对于问题三，没有时间限制，但是基于重量和体积的要求，论文类比第二问中所用方法对总路线按照体积与重量的限制进行了划分片区（3个区域），在根据地理位置进行优化。关键词：送货路线 最优路径 Floyd算法 区域划分 一问题重述现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个送货员需要以最快的速度及时将货物送达，而且他们往往一人送多个地方，请设计方案使其耗时最少。现有一快递公司，库房在图1中的O点，一送货员需将货物送至城市内多处，请设计送货方案，使所用时间最少。该地形图的示意图见图1，各点连通信息见表3，假定送货员只能沿这些连通线路行走，而

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

4、和体积限制，送货员可中途返回取货。可不考虑中午休息时间。以上各问尽可能给出模型与算法。 图1 快递公司送货地点示意图O点为快递公司地点，O点坐标(11000,8250)表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：15114

5、51.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

6、.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.05463992.140.008740101.070.012441111.370.05142122.390.042843130.990.004844141.660.049145150.450.020946162.040.009847171.950.032448182.

7、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.0447

8、0401.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.024988410.900.003889462.380.043490371.420.00291321.010

9、.041792332.510.013393360.170.037594381.820.030895170.330.034596110.300.017297154.430.053698120.240.005699101.380.017510071.980.0493表2 50个位置点的坐标位置点X坐标(米)Y坐标(米)1918550021445560372705704373567052620995610080143571002522808716025259138452680101193530501178503545126585418513763052001413405532515212559751

10、615365704517141657385188825807519585581652078083552112770856022220088352314765905524779093302544359525261086096352710385105002856597652925809865301565995531939510100321483510365331250109003472801106535153051137536123901141537641011510381391511610399510120504083451230041493013650421326514145431418014

11、215443030150604510915142354623301450047773514550488851488049115751516050801015325表3 相互连通信息序号位置点1位置点211321832204245386347428515952106111718127113812149141591016101817107181112191213201225211215221318231319241311251418261416271417281421291522301525311623321723331831341924352022362126372136382117392230

12、40231741243142254143251944252945273146283347292248302849304150312651313452323553322354334655332856344057353858364559362760374061383662392763403464404565414466413767414668424369424970433871444872445073455074454275464876474077484478495079494280504081O1882O2183O26二模型假设1. 假设送货员的行进速度与所送货物的质量和体积无关，且路上畅通，不

13、发生交通事故等特殊情况，速度均为24公里每时;2. 送货员只能按图示路线进行选择，不能走其他任何路线；3. 在联通路线中，送货员可随意选择路线；4. 假设相互连通的道路都是双向通道，没有单向的情况；5. 送货的路线可以重复经过；6. 送货员交接货物只需三分钟，同一地点多次交接也以三分钟计，且同一地区的货物只一次即可全部送达，无需再次回O点取货。交接完毕立即前往下一处。三符号说明l 所载货物的质量总和；l 所载货物的体积总和；l 第i件货物的质量；l 第i件货物的体积；l 从i点到j点的距离权值；l 任意两节点之间最短路径距离矩阵；四问题的分析对于问题一：由表一我们可以得到到30个包裹的总质量4

14、9.5kg小于送货员的最大载重量，且总体积=0.99m小于送货员的最大载重体积，因而送货员可一次携带30个包裹送到指定地点并返回原点，从而我们可以将此问题转化为一个TSP最短路径问题。根据题中所给的数据，我们得出各个点的坐标，在满足结点约束的条件下，根据Floyd算法，得出任意两个节点之间的最短路径距离。所以我们建立目标函数：寻找一条从起点0到各节点再返回节点0的最短路径。对于问题二：由表一可知，根据指定时间的先后，我们分四个阶段（9:00,9:30,10:15,12:00）去送货。因而最佳的运送方案是找出每个阶段的起点到终点的最佳路径。对于问题三：由表一可知，送货员将100个包裹最快送到50

15、个指定地点，经过计算100个包裹的总质量；总体积，送货员每次携带货物质量不能超过50kg，体积不能超过1m3，可将路线划分为3个片区。 划分方案如下：（1） 按照地理位置将路线划分为A、B、C三个区域。（2） 由送货员所能运载包裹的最大重量和体积限制对三个区域进行优化。（3） 区域的公共地点可以将一个地点的多份包裹进行两次或三次送到，达到区域的优化。由假设送货员行进速度不变，从而最佳运送方案等价于找出一个遍历每个区域所有目的顶点并返回出发点的最短路线。从而可以将该问题转化为TSP（旅行商）问题（本题可以重复经过某顶点），即寻找一个最短的Hamilton圈。五模型的建立与求解模型一：由题中数据显

16、示送货员需到达的节点数位22个（包括出发点O）如下表0131416171821232426273132343638394042434549所以我们需找出一条经过这22个节点的最短路径。利用MATLAB程序（附录1）可求解出这22点中任意两点之间的直线距离，不能相通者以inf表示，这样我们可以看成典型的TSP问题，运用Floyd算法对其求解。利用程序（附录2）用Floyd算法我们可以得出任意两点之间最短路径的距离矩阵其中（i,j=122），1）先根据题目数据给初始矩阵赋值，其中没有给出距离的赋inf，以便于更新。2)进行迭代计算。对任意两点，若存在，使，则更新3)直到所有点的距离不再更新停止计算

17、。则得到最短路距离矩阵 。由旅行售货员问题(TSP)建立矩阵, =22;其中表示点i到点j的距离权值。为对称矩阵，令=0。现求节点0到各节点再到节点0的最短距离，要求各线路上的权值最小。设立变量, 其关系如下:当节点到节点的路径被选择，=1；当节点到节点的路径被不选择，=0；目标函数为寻找一条从起点0到各节点再到节点0的最短距离，要求各线路上的权值和最小，故目标函数为：最短路径 （1） 对起始点0至少有一条路径出去，故有 （2） 对其余各节点，恰有一条路径进去，故有 （3） 所有节点不出现闭合回路，约束为； 总的线性规划模型为 ：(1) (2) ,约束条件s.t.(3) ,(4)利用lingo

18、软件编程（程序见附录3）出在各约束条件下的最短路径距离、最短路径所经过的各节点的顺序得：最短距离 minZ=54707.64m.各节点行进路线为：0181319243127392731344045424942433836383532-23-16-14-17-21-26-0图一 模型二：（图二）（表三）各顶点的路径求解详见附录1依题意得将22个节点按时间限制划分为四个区域，然后分阶段依次解决各区域的最短路径，得出各出发点和各终点。从而得出总距离最短路径。首先我们在图中描出各节点坐标，找到各节点位置。如上图。阶段一：要求9：00送到，限制在此阶段的节点有1318242739，送货员从8：00出发，

19、要求选择最短的路径在九点之前送到，根据各节点间的距离（图三）及他们的位置（图二），我们容易得出此阶段的最短路径的出发点为 0 ，终止点为 39，再根据问题一确定的数据，确定最优路径：0-18-13-（19）-24-（31）-27-39（）阶段一路线行程路程:路线0-1818-1313-1919-2424-3131-2727-39路程（m）2102311334562259178010681780根据路径我们算得此路径距离：S1=15558m从而得出第一阶段用去的时间T1=1558/400+4*3=38.895+12=50.895min2117141623323538-4342494536O片区总

20、路线长dA=32048m（图示如下）B 区：路线图如下图:O263134404740374130283346484450494245-362739 273126O片区总路线长dB=56807m（图示如下）C 区：路线如下：O26 31 24 19 25 29 22 20 22 15 5 2 43 1 6 1 7 10 9 10 7 1812 11 13 18 O片区总长dC=59317.67m（图示如下）所以送完100 件货物所走总路程：d A + dB + dC =148170m六模型的评价与推广模型的优点： 对于题中各数据的处理，采用的工具、方法比较先进，各种计算方法精确，误差较小。在解决

21、问题时，我们把原图变为完全图，利用全局线性规划法充分发挥lingo软件包求最优解功能。并且成功地对01变量进行了使用和约束，简化了模型建立难度，同时给出了在各种约束条件下的最短路径的计算方法，具有较强的实用性和通用性，在日上生活中经常可以用到。模型的缺点：由于数据较多，难以对模型结果进行验证，只能一步一步的对模型进行优化。模型的改进：模型的建立还可以进一步的考虑如送货员因所携带的货物重量体积不一样，速度改变等因素影响下的最佳送货路线的求解。还可以进一步考虑其于精确算法的结合，如将近似最优解作为分枝定界法的商界，使分枝定界法大为简化后求解，从而得到精确解。模型推广： 这是典型的TSP问题，在实际

22、生活中，经常会遇到类似的模型要求，如：物流管理、商业调度、旅游路线等等。而这些都可以归结为图论问题。图论问题中还有许多其他问题，如：VSP线路问题、汉密尔顿回路问题等，这些都可以以此模型为基础进行改进、优化。所以此模型可以推广到实际生活中，解决许多普遍的问题。而此模型中所用的软件、及各种精确的算法都是运算中非常好的处理工具。参考文献【1】数学软件与数学实验 汪晓银 邹庭荣 主编【2】谭永基. 数学模型. 上海：复旦大学出版社【3】张威，MATLAB基础与编程入门。西安电子科技大学出版社附录附录一%求五十一个点的直线距离（见文件夹“readme”之51juli.xls），挑出22个点的直线距离a

23、=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

24、;4137;4146;4243;4249;4338;4448;4450;4550;4542;4648;4740;4844;4950;4942;5040;51 18; 51 21; 51 26;31;81;202;42;83;43;24;155;25;16;187;17;128;149;109;1810;710;1211;1312;2512;1512;1813;1913;1113;1814;1614;1714;2114;2215;2515;2316;2317;3118;2419;2220;2621;3621;1721;3022;1723;3124;4125;1925;2925;3127;3328

25、;2229;2830;4130;2631;3431;3532;2332;4633;2833;4034;3835;4536;2736;4037;3638;2739;3440;4540;4441;3741;4641;4342;4942;3843;4844;5044;5045;4245;4846;4047;4448;5049;4249;4050;1851;2151;2651;b=9185 500;1445 560;7270 570;3735 670;2620 995;10080 1435;10025 2280;7160 2525;13845 2680;11935 3050; 7850 3545;65

26、85 4185;7630 5200;13405 5325;2125 5975;15365 7045;14165 7385;8825 8075;5855 8165;780 8355;12770 8560; 2200 8835;14765 9055;7790 9330;4435 9525;10860 9635;10385 10500;565 9765;2580 9865;1565 9955;9395 10100;14835 10365; 1250 10900;7280 11065;15305 11375;12390 11415;6410 11510;13915 11610;9510 12050;8

27、345 12300;4930 13650;13265 14145; 14180 14215;3030 15060;10915 14235;2330 14500;7735 14550;885 14880;11575 15160;8010 15325;11000,8250;for i=1:166 c(a(i,1),a(i,2)=sqrt(b(a(i,1),1)-b(a(i,2),1)2+(b(a(i,1),2)-b(a(i,2),2)2);endfor i=1:51 for j=1:51 if c(i,j)=0 c(i,j)=inf; end if i=j c(i,j)=0; end endend

28、str=c; disp(str)得到22个点的初始矩阵Bij（见文件夹“readme”之Bij.xls）附录二用Flyod算法求22个点的最短距离a=Bij; n=size(a,1);d=a;for k=1:n for i=1:n for j=1:n if d(i,k)+d(k,j)=1;sum(cities(j)|j#ne#i:x(i,j)=1;for(cities(j)|j #gt# 1 #and# j #ne# i:level(j)=level(i)+x(i,j)-(n-2)*(1-x(i,j)+(n-3)*x(j,i););); for(link:bin(x);for(cities(i

29、)|i#gt#1:level(i)=1+(n-2)*x(i,1););end附录四model:sets:stage/1.3/;node/1.50/:weight,volume;road(node,node):distance;stage_node_choice(stage,node):c,test;stage_path(stage,road):x;endsetsdata:weight=ole(I:songhuodian.xls,weight); （见文件夹“readme”之songhuodian.xls）volume= ole(I:songhuodian.xls,tiji);distance=

30、 ole(I:songhuodian.xls,distance);enddata!目标函数，寻求最佳路径，即最短距离;min = sum(stage(i) : sum(road(j,k) | j #ne# k : x(i,j,k)*distance(j,k);!限定C为O-1变量;for(stage_node_choice : bin(c);!限定X为O-1变量;for(stage_path : bin(x);!将每阶段的出发点都限定为O点;for(stage(i) : for(node(j) | j #eq# 0 : c(i,j) = 1);!送货员每阶段所送货物的总重受最大载重约束;for

31、(stage(i) : sum(node(j) : c(i,j) * weight(j) = 50);!送货员每阶段所送货物的总体积受最大体积约束;for(stage(i) : sum(node(j) : c(i,j) * volume(j) = 1000);!每阶段中只有某两点都被选中，它们间的路段才能被选择;for(stage(i) : for(node(j) : for(node(k) | k #ne# j : x(i,j,k) =1);!每阶段每个被选中的送货点，送货员都要至少到达一次;for(stage(i) : for(node(j) : sum(node(k) | k #ne# j : x(i,j,k) =1);!每阶段除起点和终点外不构成任何子回路;for(stage(i) : for(node(j) | j #gt# 1 : test(i,j) = 1 + 49 * x(i,j,1);for(stage(i) : for(node(j) : for(node(k) | k #ne# j #and# k #gt# 1: test(i,k) =test(i,j) + x(i,j,k) - 49 * (1 - x(i,j,k) + 48 * x(i,k,j);end