物流管理中送货路线问题研究论文.doc
《物流管理中送货路线问题研究论文.doc》由会员分享,可在线阅读,更多相关《物流管理中送货路线问题研究论文.doc(14页珍藏版)》请在三一文库上搜索。
1、物流管理中送货路线问题研究摘要针对题目所提要求,我们建立了相应的模型来解决最优路径问题,使送货员耗时最少,路程最短。并讨论了在最大载重和最大带货体积一定情况下的有时间限制和无时间限制的最优路径问题。对于第一问,我们将问题分析转化为TSP最短路径问题,首先根据题中所给数据求出30件货物质量之和、体积之和,得出结果不超过送货员的载重。所以这里不用考虑质量、体积的约束。另外根据各节点线路连接信息,我们知道需要将30见货物送到的地点为22个。在满足此约束条件的情况下,运用Floyd算法得出22个点之间的最短路径距离矩阵(i,j=1.22),最后利用lingo软件处理数据,计算出一条从O点出发经过各节点
2、又返回O点的一条最短路径。依据程序运行结果,最后得出具体路径为O2117233216142118131924313440454249424338362739273126O. 最短距离 minZ=58178.58m. 最短时间minT=2.424h对于问题二,题中增加了“时间”这一约束条件,而没有要求返回出发点。所以我们必须在满足各点的时间要求前提下,寻找一条最优的路径。对于此种情况的解决方法,我们将22个节点按时间限制划分为四个阶段,分别为:9:00、9:30、10:15、12:00 ,然后按照“时间要求越早,先送到”的原则。分析各时间段所需到达的节点,在各区域得出最短路径。依据各分区域“路径
3、均较短,则总路径较短”的原则,最后得出总距离最短的具体路径为:0181319243134404542494338362739273126211714182332。得出最短路径距离minZ=54629.65m时间minT=2.276h对于第三问,送货员送货受到包裹最大重量和最大体积的限制,因此送货员必须返回原点取货,因此我们首先根据地理位置将全局划分为三个区域,再根据重量和体积进行优化,问题即转化类似于第一题的的问题,运用第一题的解题方法即可。通过lingo最终求得三个区域的最优路线,三个区域总路程和为最短路程为160344.8m,其中A区域最优路径为:O21171416233235384342
4、49452321O路径长44220.3。B区域最优路径为:O263134404740374130283346484450494245362739273126O 总长:59317.5mC区:O18109107161342515222022292512812111319243126O 总长:56807.0m论文最后对模型的优缺点进行了分析和评价,并提出了模型的改进方向和思路。关键词:送货路线、最优路径、Floyd算法、TSP模型、1.1问题背景及重述网购已作为一种常见的消费方式,随之物流行业也渐渐兴盛,每个送货员需要以最快的速度及时将货物送达,而且他们往往一人送多个地方,故需设计方案使其耗时最少。
5、现考虑一快递公司,库房在图中的O点,一送货员需将货物送至城市内多处,请设计送货方案,使所用时间最少。该地形图的示意图见图1,各点连通信息见表3,假定送货员只能沿这些连通线路行走,而不能走其它任何路线。各件货物的相关信息见表1,50个位置点的坐标见表2。 已知() 送货员最大载重50公斤,所带货物最大体积1立方米。() 送货员的平均速度为24公里/小时。假定每件货物交接花费3分钟,为简化起见,同一地点有多件货物也简单按照每件3分钟交接计算。现在送货员要将100件货物送到50个地点。请完成以下问题。1. 若将130号货物送到指定地点并返回。设计最快完成路线与方式。给出结果。要求标出送货线路。2.
6、假定该送货员从早上8点上班开始送货,要将130号货物的送达时间不能超过指定时间,请设计最快完成路线与方式。要求标出送货线路。3. 若不需要考虑所有货物送达时间限制(包括前30件货物),现在要将100件货物全部送到指定地点并返回。设计最快完成路线与方式。要求标出送货线路,给出送完所有快件的时间。由于受重量和体积限制,送货员可中途返回取货。可不考虑中午休息时间。1.2基本假设1假设送货员只能沿如图路线图行驶,不能走其他的任何路线。2在联通路线中,送货员可自由选择。3送货员交接货物只需三分钟,同一地点多次交接也以三分钟计,且同一地区的货物只一次即可全部送达,无需再次回O点取货。交接完毕立即前往下一处
7、,期间不会耽误任何时间。4.假设送货员保持km/h,不考虑堵车及发生意外的情况。5.假设相互连通的道路都是双向通道,没有单向的情况。1.3符号说明 所载货物的质量总和; 所载货物的体积总和; 第i件货物的质量; 第i件货物的体积; 从i点到j点的距离权值; 任意两节点之间最短路径距离矩阵;1.4问题分析 对于问题1:我们要选择一条最短的路径在最短的时间内将30件货物送到指定的地点,并且返回出发点,而且需要考虑送货员的载重和各结点之间的连接信息,即所载货物重量之和须小于最大载重50kg即质量之和体积之和小于1立方米即体积之和,各点连接情况题中已给出。从而我们可以将此问题转化为一个TSP最短路径问
8、题。根据题中所给的数据,我们得出各个点的坐标,在满足结点约束的条件下,根据Floyd算法,得出任意两个节点之间的最短路径距离。所以我们建立目标函数:寻找一条从起点0到各节点再返回节点0的最短路径。对于问题2:题中增加了“时间”这一约束条件,我们必须在满足各点的时间要求前提下,寻找一条最优的路径。所以我们需要在模型一得基础上,对模型进行改进(按时间要求分为四个阶段:9:00、9:30、10:15、12:00),最终得到最优结果。对于问题3:由于货物的重量和体积的限制,路线较多时,送货员需要返回出发点取货。因此我们根据地理位置将所有路线划分为n个区域,根据限制因素对每个区域进行优化,每个区域即可看
9、成类似问题一的问题,因此有解决问题一的方法分区域解决即可: 1.5模型的建立与求解1.5.1 模型一我们首先对题中所给的数据进行汇总分析,得出=48.5公斤,V30=0.88立方米,所以均未超出送货员的载重,所以送货员可以一次性将货物送完。而题中数据显示送货员需到达的节点数位22个(包括出发点O)如下表0131416171821232426273132343638394042434549所以我们需找出一条经过这22个节点的最短路径。利用MATLAB程序(附录1)可求解出这22点中任意两点之间的直线距离,不能相通者以inf表示,这样我们可以看成典型的TSP问题,运用Floyd算法对其求解。利用程
10、序(附录2)用Floyd算法我们可以得出任意两点之间最短路径的距离矩阵其中(i,j=122),1)先根据题目数据给初始矩阵赋值,其中没有给出距离的赋inf,以便于更新。2)进行迭代计算。对任意两点,若存在,使,则更新3)直到所有点的距离不再更新停止计算。则得到最短路距离矩阵 。由旅行售货员问题(TSP)建立矩阵, =22;其中表示点i到点j的距离权值。为对称矩阵,令=0。现求节点0到各节点再到节点0的最短距离,要求各线路上的权值最小。设立变量, 其关系如下:当节点和节点连通,=1;当节点和节点不连通,=0;目标函数为寻找一条从起点0到各节点再到节点0的最短距离,要求各线路上的权值和最小,故目标
11、函数为:最短路径 (1) 对起始点0至少有一条路径出去,故有 (2) 对其余各节点,恰有一条路径进去,故有 (3) 所有节点不出现闭合回路,约束为; 总的线性规划模型为 :(1)(2)约束条件s.t. (3) (4)利用lingo软件编程(程序见附录3)算出在各约束条件下的最短路径距离、最短路径所经过的各节点的顺序得:最短距离 minZ=58178.58m.最短时间minT=2.424h各节点行进路线为:0262739363843424945403424131814163223172101.5.2 模型二问题2题目增加了时间约束,所以我们需要在模型一的基础上进行改进。送货员从早上8:00出发,
12、需要分别在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。最后验证结果:
13、根据路径我们算得此路径距离:2182.0289+3113.4627+5704.3372=10999.83 m.从而得出此段用去的时间=10999.83*3/20=27.50min60min,从而可以知道按此路径送货员能按时将货物送到。阶段2:要求9:30送到: 根据题中信息知,限制在此时间的点为:31,34,40,45。同上阶段相同,结合数据和上图分析的出发点为31,终点为45,从而我们可以得到两种行程路线:31344045或31403445。需要对两条路线进行对比优化。两种路线的行程总路程如下:路线12431313434404045路程(m)1780.14752324.74731630.78
14、23217.0056路线22431314040343445路程(m)1780.14753954.92931630.7824847.7876对比两组数据,可以选定线路1为最佳方案。按此路径行进距离=1780.1475+3954.9293+1630.782+4847.7876=12213.6464米。得出耗时=12213.6464*3/20=30.53min30min+60min-27.50min。即得出满足时间要求。阶段3:要求10:15送到:此时间要求共有四个指定地点:49,42,43,38。分析可得起点为42,终点为38,从而得到两种送货路线:42494338或42434938。两种路线的总
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 物流 管理 送货 路线 问题 研究 论文
链接地址:https://www.31doc.com/p-2530923.html