物流管理中送货路线问题研究论文.doc

物流管理中送货路线问题研究摘要针对题目所提要求，我们建立了相应的模型来解决最优路径问题，使送货员耗时最少，路程最短。并讨论了在最大载重和最大带货体积一定情况下的有时间限制和无时间限制的最优路径问题。对于第一问，我们将问题分析转化为TSP最短路径问题，首先根据题中所给数据求出30件货物质量之和、体积之和，得出结果不超过送货员的载重。所以这里不用考虑质量、体积的约束。另外根据各节点线路连接信息，我们知道需要将30见货物送到的地点为22个。在满足此约束条件的情况下，运用Floyd算法得出22个点之间的最短路径距离矩阵（i,j=1.22），最后利用lingo软件处理数据，计算出一条从O点出发经过各节点又返回O点的一条最短路径。依据程序运行结果，最后得出具体路径为O2117233216142118131924313440454249424338362739273126O. 最短距离 minZ=58178.58m. 最短时间minT=2.424h对于问题二，题中增加了“时间”这一约束条件，而没有要求返回出发点。所以我们必须在满足各点的时间要求前提下，寻找一条最优的路径。对于此种情况的解决方法，我们将22个节点按时间限制划分为四个阶段，分别为：9:00、9:30、10：15、12:00 ，然后按照“时间要求越早，先送到”的原则。分析各时间段所需到达的节点，在各区域得出最短路径。依据各分区域“路径均较短，则总路径较短”的原则，最后得出总距离最短的具体路径为：0181319243134404542494338362739273126211714182332。得出最短路径距离minZ=54629.65m时间minT=2.276h对于第三问，送货员送货受到包裹最大重量和最大体积的限制，因此送货员必须返回原点取货，因此我们首先根据地理位置将全局划分为三个区域，再根据重量和体积进行优化，问题即转化类似于第一题的的问题，运用第一题的解题方法即可。通过lingo最终求得三个区域的最优路线，三个区域总路程和为最短路程为160344.8m，其中A区域最优路径为：O2117141623323538434249452321O路径长44220.3。B区域最优路径为：O263134404740374130283346484450494245362739273126O 总长：59317.5mC区：O18109107161342515222022292512812111319243126O 总长：56807.0m论文最后对模型的优缺点进行了分析和评价，并提出了模型的改进方向和思路。关键词：送货路线、最优路径、Floyd算法、TSP模型、1.1问题背景及重述网购已作为一种常见的消费方式，随之物流行业也渐渐兴盛，每个送货员需要以最快的速度及时将货物送达，而且他们往往一人送多个地方，故需设计方案使其耗时最少。现考虑一快递公司，库房在图中的O点，一送货员需将货物送至城市内多处，请设计送货方案，使所用时间最少。该地形图的示意图见图1，各点连通信息见表3，假定送货员只能沿这些连通线路行走，而不能走其它任何路线。各件货物的相关信息见表1，50个位置点的坐标见表2。 已知（） 送货员最大载重50公斤，所带货物最大体积1立方米。（） 送货员的平均速度为24公里/小时。假定每件货物交接花费3分钟，为简化起见，同一地点有多件货物也简单按照每件3分钟交接计算。现在送货员要将100件货物送到50个地点。请完成以下问题。1. 若将130号货物送到指定地点并返回。设计最快完成路线与方式。给出结果。要求标出送货线路。2. 假定该送货员从早上8点上班开始送货，要将130号货物的送达时间不能超过指定时间，请设计最快完成路线与方式。要求标出送货线路。3. 若不需要考虑所有货物送达时间限制(包括前30件货物)，现在要将100件货物全部送到指定地点并返回。设计最快完成路线与方式。要求标出送货线路，给出送完所有快件的时间。由于受重量和体积限制，送货员可中途返回取货。可不考虑中午休息时间。1.2基本假设1假设送货员只能沿如图路线图行驶，不能走其他的任何路线。2在联通路线中，送货员可自由选择。3送货员交接货物只需三分钟，同一地点多次交接也以三分钟计，且同一地区的货物只一次即可全部送达，无需再次回O点取货。交接完毕立即前往下一处，期间不会耽误任何时间。4.假设送货员保持km/h，不考虑堵车及发生意外的情况。5.假设相互连通的道路都是双向通道，没有单向的情况。1.3符号说明 所载货物的质量总和； 所载货物的体积总和； 第i件货物的质量； 第i件货物的体积； 从i点到j点的距离权值； 任意两节点之间最短路径距离矩阵；1.4问题分析 对于问题1：我们要选择一条最短的路径在最短的时间内将30件货物送到指定的地点，并且返回出发点，而且需要考虑送货员的载重和各结点之间的连接信息，即所载货物重量之和须小于最大载重50kg即质量之和体积之和小于1立方米即体积之和，各点连接情况题中已给出。从而我们可以将此问题转化为一个TSP最短路径问题。根据题中所给的数据，我们得出各个点的坐标，在满足结点约束的条件下，根据Floyd算法，得出任意两个节点之间的最短路径距离。所以我们建立目标函数：寻找一条从起点0到各节点再返回节点0的最短路径。对于问题2：题中增加了“时间”这一约束条件，我们必须在满足各点的时间要求前提下，寻找一条最优的路径。所以我们需要在模型一得基础上，对模型进行改进（按时间要求分为四个阶段：9:00、9:30、10:15、12:00），最终得到最优结果。对于问题3：由于货物的重量和体积的限制，路线较多时，送货员需要返回出发点取货。因此我们根据地理位置将所有路线划分为n个区域，根据限制因素对每个区域进行优化，每个区域即可看成类似问题一的问题，因此有解决问题一的方法分区域解决即可： 1.5模型的建立与求解1.5.1 模型一我们首先对题中所给的数据进行汇总分析，得出=48.5公斤，V30=0.88立方米，所以均未超出送货员的载重，所以送货员可以一次性将货物送完。而题中数据显示送货员需到达的节点数位22个（包括出发点O）如下表0131416171821232426273132343638394042434549所以我们需找出一条经过这22个节点的最短路径。利用MATLAB程序（附录1）可求解出这22点中任意两点之间的直线距离，不能相通者以inf表示，这样我们可以看成典型的TSP问题，运用Floyd算法对其求解。利用程序（附录2）用Floyd算法我们可以得出任意两点之间最短路径的距离矩阵其中（i,j=122），1）先根据题目数据给初始矩阵赋值，其中没有给出距离的赋inf，以便于更新。2)进行迭代计算。对任意两点，若存在，使，则更新3)直到所有点的距离不再更新停止计算。则得到最短路距离矩阵 。由旅行售货员问题(TSP)建立矩阵, =22;其中表示点i到点j的距离权值。为对称矩阵，令=0。现求节点0到各节点再到节点0的最短距离，要求各线路上的权值最小。设立变量, 其关系如下:当节点和节点连通，=1；当节点和节点不连通，=0；目标函数为寻找一条从起点0到各节点再到节点0的最短距离，要求各线路上的权值和最小，故目标函数为：最短路径 （1） 对起始点0至少有一条路径出去，故有 （2） 对其余各节点，恰有一条路径进去，故有 （3） 所有节点不出现闭合回路，约束为； 总的线性规划模型为 ：(1)(2)约束条件s.t. (3) (4)利用lingo软件编程（程序见附录3）算出在各约束条件下的最短路径距离、最短路径所经过的各节点的顺序得：最短距离 minZ=58178.58m.最短时间minT=2.424h各节点行进路线为：0262739363843424945403424131814163223172101.5.2 模型二问题2题目增加了时间约束，所以我们需要在模型一的基础上进行改进。送货员从早上8:00出发，需要分别在9:00、9：30、10：15、12:00之前件货物送到各指定点。根据“时间要求越早，先送的原则”，将22个节点按时间限制划分为四个区域，然后分阶段依次解决各区域的最短路径，得出各出发点和各终点。从而得出总距离最短路径。首先我们在图中描出各节点坐标，找到各节点位置。如下图：阶段1：要求9:00送到：限制在此时间段的节点为三个：13、18、24，送货员8:00从O点出发，需选择最短路径在9:00之前将货物送达。根据各节点之间的距离和上图，我们很容易得出此段最短路径出发点为18，终点为24，从而路线为181324，再根据示以及问题1所得数据，确定最优线路为18131924。最后验证结果：根据路径我们算得此路径距离:2182.0289+3113.4627+5704.3372=10999.83 m.从而得出此段用去的时间=10999.83*3/20=27.50min<60min，从而可以知道按此路径送货员能按时将货物送到。阶段2：要求9:30送到： 根据题中信息知，限制在此时间的点为：31,34,40,45。同上阶段相同，结合数据和上图分析的出发点为31，终点为45，从而我们可以得到两种行程路线：31344045或31403445。需要对两条路线进行对比优化。两种路线的行程总路程如下：路线12431313434404045路程（m）1780.14752324.74731630.7823217.0056路线22431314040343445路程（m）1780.14753954.92931630.7824847.7876对比两组数据，可以选定线路1为最佳方案。按此路径行进距离=1780.1475+3954.9293+1630.782+4847.7876=12213.6464米。得出耗时=12213.6464*3/20=30.53min<30min+60min-27.50min。即得出满足时间要求。阶段3：要求10:15送到：此时间要求共有四个指定地点：49，42，43，38。分析可得起点为42，终点为38，从而得到两种送货路线：42494338或42434938。两种路线的总路程如下：路线14542424949434338各段路程（m）2351.72281971.37642889.05012618.4442路线24542424343494938各段路程（m）2351.7228917.67372889.05015507.4943分析比较两组数据，可以选定线路1为最佳方案。同上对数据进行验证：按此路径行进距离=2351.7228+1971.3764+2889.0501+2618.4442=9830.5935米得出耗时=9830.5935*3/20=24.58min<45min.即能够按时件货物送到。阶段4：要求12：00到达：此时间段共有十个指定地点：26，21，14，17，23，32，39，36，27，16。分析可确定36为起点。起点确定终点不确定。对此我们进行迭代算法：即从出发点开始，找出到出发点的最近距离的一个点，然后依次迭代计算，再以找出的点为出发点，找出到该点的最短距离的点，如此进行下去，则可以找出一条较短的行进路线。首先以36为起点，具体计算过程如下：l 点36 到其他点的距离（单位：m）如下：36272139321726231416距离2203.9172880.1783983.844061.1444704.0894808.6965373.0136176.9117470.654所以确定27为第二次所到地点。l 点27到其他点的距离（单位：m）如下： 273926213217231416距离17799232604.7814796.5216265.066620.4327576.938093.2549674.571所以确定39为第三次所到地点。由线路图可知，离开39后需要回到27，才能送货到其它地点，则再根据上述表格选取除39外距离27最近的地点的，即是第四次所到地点，易知26为第四次所到地点（途经31）。l 点26到其他点的距离（单位：m）如下：26211714233216距离2191.744015.6515488.4735790.1657102.0347887.806可得21为第五次所到地点。l 点21到其他点的Euclid距离（单位：m）如下：211714233216距离1823.9113296.7333598.4254910.2945696.066可得17为第五次所到地点。l 点17到其他点的Euclid距离（单位：m）如下：1723143216距离1774.5149215.7233086.3833872.156理论上讲应该选取点23，但根据线路图以及剩余送货的地点，综合考虑后选取次优解即14为第六次送货地点。l 点14到其他点的Euclid距离（单位：m）如下：14162332距离2607.6813970.2375282.106可得16为第七次所到地点。l 点16到其他点的距离（单位：m）如下：162332距离2097.63409.5可得23为第八次所到地点，32为终点。由以上结果可得最佳送货路线如下：362739（27）（31）26211714162332在图中标出路线： 所以综上考虑将各阶段的路径连接起来形成的最终最短路径为：0181319243134404542494338362739273126211714182332。得出最短路径距离minZ=54629.65m 时间minT=2.276h153 模型三3.3 问题3的分析：送货员将100个包裹最快送到50个指定地点，经过计算100个包裹的总质量；总体积，送货员每次携带货物质量不能超过50kg，体积不能超过1m3，可将路线划分为n（n>=3,且n为整数）个片区，相当于n个送货员同时从同一地点出发再返回出发点，考虑到送货员需最快送货完毕，即需要最短送货路线，则每个区域的包裹质量和体积在不超过限制时应尽可能最大，所以考虑选取n=3。划分方案如下：（1） 按照地理位置将路线划分为A、B、C三个区域。（2） 由送货员所能运载包裹的最大重量和体积限制对三个区域进行优化。（3） 区域的公共地点可以将一个地点的多份包裹进行两次或三次送到，达到区域的优化。由假设送货员行进速度不变，从而最佳运送方案等价于找出一个遍历每个区域所有目的顶点并返回出发点的最短路线。从而可以将该问题转化为TSP（旅行商）问题（本题可以重复经过某顶点），即寻找一个最短的Hamilton圈。模型的建立与求解：由问题3的分析知，本题可以转化为一个TSP（旅行商）问题（本题可以重复经过某顶点），即在每个区域寻找一个最短的Hamilton圈。而划分区域后问题三就可以转化为与问题一相同的模型,寻找每个区域完备图中的最短Hamilton圈。在理论上来讲，送货员是送50 个包裹，要送往50个地方。其中区域的划分步骤如下：（1）将路线划分为东,西北, 西南三个区域（分别为A,B,C三个区域）（见附录3）。（2）对区域进行精细调整，尤其是边界地点，可将区域公共地点的多个包裹分两次送到：A，B区的公共点42，45，49的多个包裹分两次送到，将地点42的15号包裹，地点45的11号包裹，26号包裹，以及地点49的79号包裹分到B区送达；将B，C区的公共点31的21号包裹分到C区送达。（3）划分后每个区域包裹的总重量，总体积如下:A（东区）： MA=49.85kg VA=0.9356m3B（西北区）：MB=49.41kg VB=0.9542m3 C (西南区)：MC=48.74kg VC=0.9102 m3 A、B、C每个区域包裹的总重量不超过50kg，总体积不超过1m3。区域划分完成。借助数学工具Matlab, 基本思路是在已知起点终点的情况下，一个点一个点的推出结论。同时会注意到，每一段都取最小的结果相加后结果并不一定是最小的。所以需要在计算机推断最短路线的基础上加以改进。得出最优路线如下：A区：O2117141623323538434249452321O总长dA=44220.4mB区： O263134404740374130283346484450494245362739273126O 总长：59317.5mC区：O18109107161342515222022292512812111319243126O 总长：56807.0m所以所走的总长为：160344.8 m.16 模型的进一步分析1.6.1 误差分析 针对模型一，首先对于数据的处理，我们采用的是运算功能强大的matlab、lingo软件，所以误差较小，可以忽略不计。其次对于各个运算的结果，采用的是计算精确的Floyd算法，误差也较小。模型二中，我们将各个节点按照时间约束条件，划分为四个阶段分析，所以对于最优结果，肯定存在误差，但各阶段的节点比较集中紧密，所以误差较小，因此，此模型可以使用。模型三中，由于也是分区域求解最优解，与模型二的误差情形相同，但各区域节点比较集中，且送货员的载重和体积均接近临界值。所以模型可以使用。162 灵敏度分析 一个好的模型不能由于初始的数据的微小误差而导致结果的较大改变。模型一，由于约束条件较少，没有质量、体积的约束，所以灵敏度较好。模型二加入了时间这一约束条件，灵敏度有所下降。模型三，由于质量、体积均有约束，导致灵敏度较低。但准确性较高，所以此模型可以使用。17 模型的评价和推广171 优缺点优点： 对于题中各数据的处理，采用的工具、方法比较先进，各种计算方法精确，误差较小。，在解决问题时，我们把原图变为完全图，利用全局线性规划法充分发挥lingo软件包求最优解功能。并且成功地对01变量进行了使用和约束，简化了模型建立难度，同时给出了在各种约束条件下的最短路径的计算方法，具有较强的实用性和通用性，在日上生活中经常可以用到。缺点：由于数据较多，难以对模型结果进行验证，只能一步一步的对模型进行优化。172 模型推广 这是典型的TSP问题，在实际生活中，经常会遇到类似的模型要求，如：物流管理、商业调度、旅游路线等等。而这些都可以归结为图论问题。图论问题中还有许多其他问题，如：VSP线路问题、汉密尔顿回路问题等，这些都可以以此模型为基础进行改进、优化。所以此模型可以推广到实际生活中，解决许多普遍的问题。而此模型中所用的软件、及各种精确的算法都是运算中非常好的处理工具。参考文献【1】 吴建国，数学建模案例精编。中国水利水电出版社，2005.5【2】 张威，MATLAB基础与编程入门。西安电子科技大学出版社，2008.1【3】 李海龙，遗传算法求解物流配送中带时间窗的VRP问题，吉林大学学报第46卷，第二期2008.3附录1：两点间直线距离，不能相通以inf代替 matlab 联通点的直线距离程序; a=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;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;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;6585 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;8345 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 endendstr=c; disp(str)附录2 任两点间最短路径长最短路径程序！function d,r=floyd(a)%floyd.m%采用floyd算法计算图a中每对顶点最短路%d是矩离矩阵%r是路由矩阵 a=;n=size(a,1);d=a;for i=1:n for j=1:n r(i,j)=j; end end r;for k=1:n for i=1:n for j=1:n if d(i,k)+d(k,j)<d(i,j) d(i,j)=d(i,k)+d(k,j); r(i,j)=r(i,k); end end end k; d; r;end附录3 最优路径lingo求解程序model:sets: city / 1. 5/: u; link( city, city): dist, ! 距离矩阵; x;endsets n = size( city);data: !距离矩阵，它并不需要是对称的; dist = ; !这里输入最短距离;enddata !目标函数; min = sum( link: dist * x); FOR( city( K): !进入城市K; sum( city( I)| I #ne# K: x( I, K) = 1; !离开城市K; sum( city( J)| J #ne# K: x( K, J) = 1; ); !保证不出现子圈; for(city(I)|I #gt# 1: for( city( J)| J#gt#1 #and# I #ne# J: u(I)-u(J)+n*x(I,J)<=n-1); ); !限制u的范围以加速模型的求解，保证所加限制并不排除掉TSP问题的最优解; for(city(I) | I #gt# 1: u(I)<=n-2 ); !定义X为01变量; for( link: bin( x);end14