最短路径算法在物流运输中的应用

..本科生毕业设计〔论文〕题目：线性表的设计和实现学生：三学号：3院系：根底科学学院信息技术系专业年级：2012级信息与计算科学专业指导教师：四注：1.论文封面单独打印一X纸；中英文摘要正反打印一X纸；目录、正文、参考文献、致谢、附录均独立正反打印！2.局部专业对格式有特殊要求的，教学院〔系〕可自行商定。注：1.论文封面单独打印一X纸；中英文摘要正反打印一X纸；目录、正文、参考文献、致谢、附录均独立正反打印！2.局部专业对格式有特殊要求的，教学院〔系〕可自行商定。..摘要随着现代物流业的开展，如何优化和配置物流的运输路径成为了一个热点的问题。其中，最具代表性的问题就是如何在一个道路网络中选择两点之间的适宜路径，使其距离最短。为了解决这个问题，本文介绍了两种最常用的最短路径求解方法——Dijkstra算法与Floyd算法，分析了它们的适用围以及时间复杂度。最后，对一个具体的航空公司物流配送问题进展了求解，得到了理论最优路径。关键词：最短路径问题；Dijkstra算法；物流运输ABSTRACTWiththedevelopmentofmodernlogisticsindustry,howtooptimizeandconfigurethetransportpathoflogisticshasbeeahotissue.Amongthem,themostrepresentativeproblemishowtoselecttheappropriatepathbetweentwopointsinaroadnetworktominimizethedistance.Inordertosolvethisproblem,thispaperintroducestwomostmonshortestpathsolutions——DijkstraalgorithmandFloydalgorithm,andanalyzestheirapplicationrangeandtimeplexity.Finally,aspecificairlinelogisticsdistributionproblemissolved,andthetheoreticaloptimalpathisobtained.Keywords：Minimumpathproblem；Dijkstraalgorithm；Logisticstransportation目录第一章引言⑶边权可正可负。2.3.5算法简单实例图3-2无向图根据图3-2，用Floyd算法找出任意两点的最短路径步骤如下表3-2：distk[1]distk[2]distk[3]MINA->B1371A->C135*1A->D3353B->C2262B->D*44*4C->D2462表3-2Floyd算法步骤流程..第三章实际案例分析3.1问题描述3.1.1问题的背景及假设网上购物一直是常见的消费方式，其依托于物流业逐渐蓬勃开展，每个送货人员都需要以最快的速度送货，而且往往会发送多个地方，所以有必要设计耗时最小的路线。现在考虑一个快递公司，总部在地图上的O点，派送人员需要将货物发往城市很多，如何设计交货方案，以便花费最少的时间。物流地图如图1所示，下表中显示了每个点的信息，假设托运人只能沿着这些连接的线行进，而不采取任何其他路线。〔1〕最大承载能力为50公斤，货量最大为1立方米。〔2〕调度员的平均速度为24公里/小时。假设每件货物要交出需要3分钟，为了简单起见，在同一地点有几件商品，这些货物只需每3分钟一次交割即可。现在派送者将向50个地点发送100件货物。问题要求如下：1.假设货物从1到30到指定地点并返回。设计最快的路线和方式来求出结果。要求标记送货线路。2.假设送货人员从上午8点开场交货，1到30天货物交货时间不能超过规定的时间，请设计最快的路线和方式。要求标记送货线。具体数据请参见附录。3.1.2符号说明所载货物的质量总和；所载货物的体积总和；第i件货物的质量；第i件货物的体积；从i点到j点的距离权值；任意两节点之间最短路径距离矩阵；3.2模型的建立与求解3.2.1模型一我们首先对题中所给的数据进展汇总分析，得出=48.5公斤，V30==0.88立方米，所以均未超出送货员的载重，所以送货员可以一次性将货物送完。而题中数据显示送货员需到达的节点数位22个〔包括出发点O〕如下表0131416171821232426273132343638394042434549表3-1节点数利用程序用Floyd算法我们可以得出任意两点之间最短路径的距离矩阵其中〔i,j=1…22〕，〔1〕先根据题目数据给初始矩阵赋值，其中没有给出距离的赋inf，以便于更新。〔2〕进展迭代计算。对任意两点，假设存在，使，那么更新。〔3〕直到所有点的距离不再更新停顿计算。那么得到最短路距离矩阵。由旅行售货员问题(TSP)建立矩阵,；其中表示点i到点j的距离权值。d为对称矩阵，令=0。现求节点0到各节点再到节点0的最短距离，要求各线路上的权值最小。设立变量,其关系如下:当节点和节点连通，=1；当节点和节点不连通，=0；目标函数为寻找一条从起点0到各节点再到节点0的最短距离，要求各线路上的权值和最小，故目标函数为：最短路径〔3-1〕〔1〕对起始点0至少有一条路径出去，故有〔3-2〕〔2〕对其余各节点，恰有一条路径进去，故有〔3-3〕〔3〕所有节点不出现闭合回路，约束为；总的线性规划模型为：〔3-4〕(1)(2)约束条件s.t.(3)(4)利用lingo软件编程算出在各约束条件下的最短路径距离、最短路径所经过的各节点的顺序得：最短距离.最短时间各节点行进路线为：0→26→27→39→36→38→43→42→49→45→40→34→24→13→18→14→16→32→23→17→21→0图3-1节点路线表3.2.2模型二问题2题目增加了时间约束，所以我们需要在模型一的根底上进展改良。送货员从早上8:00出发，需要分别在9:00、9：30、10：15、12:00之前件货物送到各指定点。根据"时间要求越早，先送的原那么〞，将22个节点按时间限制划分为四个区域，然后分阶段依次解决各区域的最短路径，得出各出发点和各终点。从而得出总距离最短路径。首先我们在图中描出各节点坐标，找到各节点位置。如下列图：图3-2节点位置表阶段1：要求9:00送到：限制在此时间段的节点为三个：13、18、24，送货员8:00从O点出发，需选择最短路径在9:00之前将货物送达。根据各节点之间的距离和上图，我们很容易得出此段最短路径出发点为18，终点为24，从而路线为18→13→24，再根据示以及问题1所得数据，确定最优线路为18→13→19→24。最后验证结果：根据路径我们算得此路径距离:2182.0289+3113.4627+5704.3372=10999.83m.从而得出此段用去的时间=10999.83*3/20=27.50min<60min，从而可以知道按此路径送货员能按时将货物送到。阶段2：要求9:30送到：根据题息知，限制在此时间的点为：31,34,40,45。同上阶段一样，结合数据和上图分析的出发点为31，终点为45，从而我们可以得到两种行程路线：31→34→40→45或31→40→34→45。需要对两条路线进展比照优化。两种路线的行程总路程如下：路线124—3131—3434—4040—45路程〔m〕1780.14752324.74731630.7823217.0056路线224—3131—4040—3434—45路程〔m〕1780.14753954.92931630.7824847.7876表3-2行程路线表比照两组数据，可以选定线路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，从而得到两种送货路线：42→49→43→38或42→43→49→38。两种路线的总路程如下：路线145—4242—4949—4343—38各段路程〔m〕2351.72281971.37642889.05012618.4442路线245—4242—4343—4949—38各段路程〔m〕2351.7228917.67372889.05015507.4943表3-3总路程表分析比拟两组数据，可以选定线路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为起点，具体计算过程如下：点36到其他点的距离〔单位：m〕如下：36272139321726231416距离2203.9172880.1783983.844061.1444704.0894808.6965373.0136176.9117470.654表3-4点36距离表所以确定27为第二次所到地点。点27到其他点的距离〔单位：m〕如下：273926213217231416距离1779．9232604.7814796.5216265.066620.4327576.938093.2549674.571表3-5点27距离表所以确定39为第三次所到地点。由线路图可知，离开39后需要回到27，才能送货到其它地点，那么再根据上述表格选取除39外距离27最近的地点的，即是第四次所到地点，易知26为第四次所到地点〔途经31〕。点26到其他点的距离〔单位：m〕如下：26211714233216距离2191.744015.6515488.4735790.1657102.0347887.806表3-6点26距离表可得21为第五次所到地点。点21到其他点的Euclid距离〔单位：m〕如下：211714233216距离1823.9113296.7333598.4254910.2945696.066表3-7点21距离表可得17为第五次所到地点。点17到其他点的Euclid距离〔单位：m〕如下：1723143216距离1774.5149215.7233086.3833872.156表3-8点17距离表理论上讲应该选取点23，但根据线路图以及剩余送货的地点，综合考虑后选取次优解即14为第六次送货地点。点14到其他点的Euclid距离〔单位：m〕如下：14162332距离2607.6813970.2375282.106表3-9点14距离表可得16为第七次所到地点。点16到其他点的距离〔单位：m〕如下：162332距离2097.63409.5表3-10点17距离表可得23为第八次所到地点，32为终点。由以上结果可得最正确送货路线如下：36→27→39→〔27〕→〔31〕→26→21→17→14→16→23→32在图中标出路线：图3-3路线表所以综上考虑将各阶段的路径连接起来形成的最终最短路径为：0→18→13→19→24→31→34→40→45→42→49→43→38→36→27→39→27→31→26→21→17→14→18→23→32。得出最短路径距离minZ=54629.65m时间minT=2.276h第四章总结4.1优点对于题中各数据的处理，采用的工具、方法比拟先进，各种计算方法准确，误差较小。在解决问题时，我们把原图变为完全图，利用全局线性规划法充分发挥lingo软件包求最优解功能。并且成功地对0—1变量进展了使用和约束，简化了模型建立难度，同时给出了在各种约束条件下的最短路径的计算方法，具有较强的实用性和通用性，在日上生活中经常可以用到。4.2缺点由于数据较多，难以对模型结果进展验证，只能一步一步的对模型进展优化。参考文献[1]朱道立.运筹学[M].高等教育,2006.[2]周建兴.MATLAB从入门到精通.第2版[M].人民邮电,2012.[3]徐立华.求解最短路问题的一个计算机算法[J].系统工程,1989(5):46-51.[4]林澜,闫春钢,昌俊,等.动态网络最短路问题的复杂性与近似算法[J].计算机学报,2007,30(4):608-614.[5]牛学勤,王炜.基于最短路搜索的多路径公交客流分配模型研究靠[J].东南大学学报(自然科学版),2002,32(6):917-919.[6]马良河,信斌,廖.城市公交线路网络图的最短路与乘车路线问题[J].数学的实践与认识,2004,34(6):38-44.[7]航,军,凝子.一种求解时变网络下多式联运最短路的算法[J].中国管理科学,2006,14(4):56-63.[8]运河,林柏梁,梁栋,等.优化多式联运问题的一种广义最短路方法研究[J].铁道学报,2006,28(4):22-26.[9]帮义,恩瑜.最短路网络及应用[J].系统工程理论与实践,2000,20(6):104-107.[10]龙光正,建军.改良的最短路算法[J].系统工程与电子技术,2002,24(6):106-108.[11]周经伦,吴唤群.受顶点数限制的最短路问题及其算法[J].系统工程,1996(5):37-44.[12]贺国先.集装箱公铁联运的费用加权最短路计算机算法[J].铁道学报,2006,28(1):1-5...一级标题，中间空4格。致一级标题，中间空4格。空1行空1行大学四年的学习生活即将完毕，在此，我要感所有曾经教诲过我的教师和关心过我的同学，他们在我成长过程中给予了我很大的帮助。本文能够成功的完成，要特别感我的导师XXX教授的关心和教诲。..附录附录A实际案例背景数据图1快递公司送货地点示意图O点为快递公司地点，O点坐标(11000,8250),单位：米表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：0021310.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.049464341.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.0493表250个位置点的坐标位置点X坐标(米)Y坐标(米)191855002144556037270570437356705262099561008014357100252280871602525913845268010119353050117850354512658541851376