送货路线设计问题汇总

《送货路线设计问题汇总》由会员分享，可在线阅读，更多相关《送货路线设计问题汇总（14页珍藏版）》请在装配图网上搜索。

1、期末数学建模报告（A）题姓名：李飞 专业：功能材料 学号：120540214姓名：谭秀松 专业：自动化 学号：1206103172014-6-7送货路线设计问题摘要现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流 行业也渐渐兴盛，每个送货员需要以最快的速度及时将货物送达，针对一个送 货员要去城市多处送货并返回，该图为一个网络图，如何设计线路使送货员所 用时间最少。因为速度是恒定的，并且货物交换时间也相同，所以把求时间最 短问题转化为求路径最短的问题，采用Floyd算法思想、借助矩阵、MATLAB软 件和编程，求出最短距离矩阵和最短路径矩阵。再通过数据的分析、筛选和计 算，从而可在

2、图上标出送货员到各个点的最短路径，得到最优解。针对问题一：采用“D-J模型”。在此模型中，运用Floyd算法求解，然后 套用此模型可以得到最优的结果是：送货员所走过的总路程：54707.5米。针对问题二：采用“分析&递推模型”。在此模型中利用分析法和递归的思 路建立动态的方法求得最优化结果来相结合求解，然后套用此模型可以得到最 优的结果是：送货员所走过的总路程：52004.37米送完全部货物所需时间：3 小时37分01秒。针对问题三：分区送货策略模型”。通过对送货点的分成不同的区域，在 对其继续单独的利用模型二计算，得到最优的结果为：从口出发路程（米）第一妆51440. 5第二轶45913.

3、4窜三森34352. S关键词：分析&递推模型Floyd算法Kruskal算法 最短路径 最小生成树法一、问题重述现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行 业也渐渐兴盛，每个送货员需要以最快的速度及时将货物送达，而且他们往往 一人送多个地方。所以在快递公司送货策略中，确定合理的行走路线是关键的 问题。问题（1）在送货员送货路线设计问题中，送货员从图1中的起点O出发， 将130件货物送到指定目的地并返回，要求所用时间最短。此时送货员可将 30件货物一次性带上，因为这30件货物的总重量48.5kg、总体积0.88m3并没 有超过送货员的最大载重和所带货物的最大体积。问题（2

4、）送货员从早上8点开始送货，要将1到30货物送到指定地点并 且不超过指定时间。而且他们往往要去很多地方，如果在路线上选择不合理的 话，不仅不能按时将货物送到指定地点，反会浪费更多的时间。这样不仅要考 虑将货物送到而且要满足不超过指定时间。问题（3）送货的数量增加由30件增加到100件，不考虑时间限制。但是 要考虑送货员的最大载重和所带货物的最大体积。很明显送货员不可能一次性 将货物带完，必须把货物分批送到，还要满足所走的路线最短。二. 问题分析（1）题目中只从快递公司派出一个送货员，到任意未配送的送货点，然后 将这个送货派到最近的未服务的送货点范围之内，且最大载重不超过50kg，货 物体积不超

5、过1立方米。在问题二中还必须使每一件货物在指定时间内送达。继 续上述指派，直到各点总重量超过50kg或者体积超过1立方米。最后业务员返 回快递公司，记录得到的可行行程（即路线）。对得到的可行的行程安排解中的 每一条路径，计算路线是否最短，时间是否最少。即得到所需的最短路线。（2）为此我们必须制定合理的送货策略一个合理的送货策略是指送 货员每天在有限的时间内，尽量多送货，使日送货量达到最大，让送货员在几个 指定的送货点能最有效率的完成送货任务。每天要将所有的货物全部送到指定点 ，不能出现每天有未接到服务，而货品在邮局积压的情况。送货公司要尽量节约 人力成本，从而使自己的利益最大化。送货安排要合理

6、，不要出现送货点混乱和 兜弯路的情况。根据这些合理性原则，我们需要给送货公司制定出在固定的送货 点上安排好每个送货员的送货和运行线路，以及总的运行公里数，而且是需要的 送货员尽可能少，总路线尽可能短。（3）快递行业正蓬勃发展，为我们的生活带来更多方便。为了保证快件能 够在指定的时间内和规范的条件下送达目的地，设计最快完成路线与方式成为了 快递公司的首要之需。快递公司不但要求每一件货物需要在指定的时间内送达， 而且还要使每个送货员送货的路线最短，因此，如何用最少的时间准时完成所有 的任务是最重要的。在约束条件下，应确定圆满完成每天的送货，保证货物不因 延误时间而耽误到客户的需要，这些都是我们需要

7、考虑的问题。（4）通过以上分析，我们建立了 “D-J模型”，“分析&递推模型”，“分 区送货策略模型”。三. 模型基本假设1. 假设送货员在送货的过程中没有出现把货物弄丢等意外情况，全部货物 都能准确送到；2. 假设送货员在送货的过程中不考虑天气等突变因素影响送货员行进的因 素；3. 假设送货员在送货的过程中没有退货情况，所有的货物都能全部送出；4. 假设送货员在送货的过程中全部把货送到位，忽略把货物送错重送的情 况；5. 假设送货员在送货的过程中不考虑路途中的交通堵塞问题，随时保持速 度恒定不变；6. 假设数据整理后无其他错误。四. 符号说明Inf:表示相应两点不能直接到达勺：各个点之间的坐

8、标距离p :各点之间在有权图上的最短距离矩阵 ijq :各点之间在有权图上的最短路径矩阵jCi；j.:表示此题例图的权矩阵Z M1: 1-30号货物的总重量 n=1Z M2: 1-100号货物的总重量EM :第三问第一次携带货物的总重量 31EM :第三问第二次携带货物的总重量32EM :第三问第三次携带货物的总重量 33E V1: 130号货物的总体积n =1如V2: 1100号货物的总体积n=1EV :第三问第一次携带货物的总体积31EV :第三问第二次携带货物的总体积 32EV :第三问第三次携带货物的总体积 33:第1问的最短路程S2 :第2问的最短路程S3：第3问的最短路程T：第2问

9、所用的总时间五模型建立与求解深度探索此题共有50个目标点，加上出发点原点O共51个点，要求将货物送往目标 点，且用的时间最短，则必须知道目标点和原点O的距离（令O点为第51个点）， 及各个点之间的坐标距离d 。此图并不是每个点都相连，有些点不能直接到达， ij所以要先列出此题的权矩阵Cj，然后求出它们之间的最短距离Pj和最短路径qj。则模型规划如下:p二e e c寸_尤+q i=1 j=1j，i j -厂 j d,j 二 Ex?+，i=1 j=1i=1, ,51； j=1, ,51。利用MATLAB软件进行计算，编程结果得:匕取值情况如下表所示123448495051107740.21916.

10、35452.71660314854148717959.727740.2058252292.61433117770161591226531916.3582503536.41567015212147748537.945452.72292.63536.401449316475152661049956583.61252.94669.41161.41399316758153101108461294.38679.22940.163911628913806140436876.871968.28750.73242.56492.81556612973132006049.1.4615588139681478013

11、9011494.19268.55739.61068847141251533913988144456857.93888.1822.347095.848166031433115670144930106947138.91209449148541777015212164751069403568.86933.950148711615914774152667138.93568.807680.9517959.7122658537.910499120946933.97680.903得取值情况如下表12345474849505110Inf1916.3InfInfInfInfInfInfInf2Inf0Inf22

12、92.61252.9InfInfInfInfInf31916.3Inf03536.4InfInfInfInfInfInf4Inf2292.63536.40InfInfInfInfInfInf5Inf1252.9InfInf0InfInfInfInfInf:47InfInfInfInfInf0InfInfInfInf48InfInfInfInfInfInf0InfInfInf49InfInfInfInfInfInfInf03568.8Inf50InfInfInfInfInfInfInf3568.80Inf51InfInfInfInfInfInfInfInfInf0此表中的Inf表示相应两点不能直

13、接到达，数值表示两点间可以直接到达的距离值，0表示自身到自身的距离利用Floyd算法求得p厂，pj取值情况如下表所示123454748495051107745.31916.35452.78998.3162771876120306169891006827745.305829.12292.61252.9224271800226325227571629631916.35829.103536.47082166761785620705173881046745452.72292.63536.403545.6202122029524242209241400458998.31252.970823545.602

14、117416749250732150416563:4716277224271667620212211740112538943.55374.79215.8481876118002178562029516749112530107087139.6158064920306263252070524242250738943.51070803568.8117225016989227571738820924215045374.77139.63568.809928.15110068162961046714004165639215.815806117229928.10（1）从起点51出发，行遍每一个地点并且要把3

15、0件货物送到指定目的地并返回，要求所用时间最短。由题意得：1-30号货物的总重量为：M1=48.5 50 ；总体 n=1积为：Zv = 0.88 1，所以一次性可将货物全部带完。行走路线如下： 1 n=116000路线51 (O) t 26 21 17 14 16 23 32 35 38 36 38 43路程1392.1+2191.7+1823.9+2195.7+2607.7+2097.6+1311.9+1114+1409.7+1537.4+1537.4+路线42 49 42 45 40 34 31 27 39 27 31 24 19 13路程2618.4+917.67+1971.4+1971

16、.4+2351.7+3217+1630.8+2324.7+1067.8+1779.9+1779.9+路线18 51 (O)路程1067.8+1780.1+2258.6+3455.7+3113.5+2182=54707.5(最短路程)最短路程:S=54707.5（米）（2）5.1问题一：在第一题的基础上，第二题加了限制条件（将货物在指定时间内 送到指定地点），送货员还是可以将货物全部携带，但没有限制必须返回，所以行走路 线如下：24公里/小时二400米/分1阶段1阶段路线51 (O) 18 13 19 24路程2182+3113.5+3455.7+2258.62阶段2阶段路线24 31 34 4

17、0 45路程1780.1+2324.7+1630.8+32173阶段3阶段路线45 42 49 42 43 38路程2351.7+1971.4+1971.4+917.67+2618.44阶段4阶段路线38 36 38 35 32 23 16 14 17 21 26 31 27 39路程1537.4+1537.4+1409.7+1114+1311.9+2097.6+2607.7+2195.7+1823.9+2191+1537+1067.8+1779.9.71 阶段用时：(2182+3113.5+3455.7+2258.6) /400+3*2+3=36.5242min=36 分 31 秒此时刻时间

18、为：8:36:319:00:00满足条件2 阶段用时：(1780.1+2324.7+1630.8+3217)/400+5*3+3=43.382min=43 分 23 秒一二阶段共用时：36分31秒+43分23秒二79分54秒 此时刻时间为：9:19:549:30:00 满足条件3 阶段用时：(2351.7+1971.4+1971.4+917.67+2618.4) /400+4*3+3=39.5672min=39 分 34秒前三阶段共用时：79分54秒+39分34秒二119分28秒 此时刻时间为：9:59:2810:15:00满足条件4 阶段用时：(1537.4+1537.4+1409.7+11

19、14+1311.9+2097.6+2607.7+2195.7+1823.9+2191.7+1537+1067.8+1779.9) /400+13*3+3=97.5483min=97 分 33 秒 总共用时为：119分28秒+97分33秒二217分01秒二3小时37分01秒 此时刻时间为：11:37:01 50 ；总体积为：n=1Zv = 2.8 1,所以至少要三次性才可将货物全部带完。行走路线如下：2n = 1第1次从O出发路线51 (O) 18 13 11 12 15 5 2 4 3 8 1 6 1 7 r 10 r 9 r 14 T 16 r 23 r 17 r 21 r 51 (O)路程

20、2182+3113.5+1669.6+1417.7+4805.8+5004.5+1252.9+2292.6+3536.4+ 1958.1+2863.8+1294.3+1294.3+1968.2+2059.4+1945.5+2681.3+2607.7 +2097.6+1774.5+1823.9+1796.9=51440.5第2次从O出发路线51 (O) r 18r31 r24r 19r25r29r22r20r22r30r28r33 r 46 r 48 r 44 r 41 r 37 r 40 r 47 r 40 r 34 r 31 r 26 r 51 (O)路程2182+2103.7+1780.1

21、+2258.6+1966.2+1885.9+1097.9+1498.9+1498.9+1287.5+1017.9+1325.7+3758.5+1494.1+2152.5+2366+2601.9+2090.1+2331.2+2331.2+1630.8+2324.7+1537+1392.1=45913.4第3次从O出发路线51 (O) r26r31 r27r39r27r36r45r50r49r42r43r38 r 35 r 32 r 23 r 17 r 21 r 51 (O)路程1392+1537+1067.8+1779.9+1779.7+2203.9+3182.5+3102.8+3568.8+1

22、971.+917.67+2618.4+1409.7+1114+1311.9+1774.5+1823.9+1796.9=34352.8红、绿、蓝分别是一条回路，第一次从O点出发，经过18这个地点，但不带 2 号，48 号货物：M31= 49.99 50，Zv =0.94121；第二次从 O点出发经过31，26这两个地点，但不带61号，4号，23号，56号货物 M32 = 49.73 50 , 匕 =0.89971;第 三次从 O 点出发M33 = 48.28 50, 匕广0.95911，满足题目要求。全程总走过的路程为：S3= 51440.5+45913.4+34352.8=131706.7（米

23、）五、模型评价A.优点：1. 在模型求解最短距离过程中用了 MATLAB软件编程，把大量的运算交给计算机处理，提高了计算的准确性。2. 本模型通过转换的思想，把求时间最短转化为求路径最短，使问题变的简 单些，便于求解。3. 定性与定量相结合的方法解决了送货员送货问题。B.缺点：1.由于本模型的计算量大，在计算的过程中，存在数据的处理，比如：四舍 五入导致最后的计算数值可能存在误差。参考文献【1】陈光亭 裘哲勇.数学建模.北京：高等教育出版社【2】肖华勇.实用数学建模与软件应用.西安：西北工业大学出版社2008.11.S1 期，2006年【3】刘承平 数学建模方法 北京：高等教育出版社【4】张秀

24、兰 林峰 数学建模与实验 北京：化学工业出版社附录x=9185 1445 7270 3735 2620 10080 10025 7160 13845 11935 7850 6585 7630 13405 2125 15365 14165 8825 5855 780 12770 2200 14765 7790 4435 10860 10385 565 2580 1565 9395 14835 1250 7280 15305 12390 6410 13915 9510 8345 4930 13265 14180 3030 10915 2330 7735 885 11575 8010 11000;y

25、=500 560 570 670 995 1435 2280 2525 2680 3050 3545 4185 5200 5325 5975 7045 7385 8075 8165 8355 8560 8835 9055 9330 9525 9635 10500 9765 9865 9955 10100 10365 10900 11065 11375 11415 11510 11610 12050 12300 13650 14145 14215 15060 14235 14500 14550 14880 15160 15325 8250;for i=1:51for j=1:51d(i,j)=s

26、qrt(x(i)-x(j)”2+(y(i)-y(j)”2);c(i,j)=inf;c(i,i)=0;endendc(01,08)=d(01,08);c(01,03)=d(01,03);c(02,20)=d(02,20);c(02,04)=d(02,04);c(03,08)=d(03,08);c(03,04)=d(03,04);c(05,15)=d(0 5,15);c(05,02)=d(05,02);c(06,01)=d(06,01);c(07,18)=d(07,18);c(07,01)=d(07,01);c(08,12)=d(08,12);c(09,14)=d(09,14);c(09,10)=

27、d(09, 10)；c(10,07)=d(10,07);c(11,12)=d(11,12);c(12,13)=d(12,13);c(12, 25)=d(12,25);c(12,15)=d(12,15);c(13,18)=d(13,18);c(13,19)=d(13,1 9);c(13,11)=d(13,11);c(14,18)=d(14,18);c(14,16)=d(14,16);c(14,17 )二d(14,17);c(14,21)=d(14,21);c(15,22)=d(15,22);c(15,25)=d(15,2);c(16,23)=d(16,23);c(17,23)=d(17,23);

28、c(18,31)=d(18,31);c(19, 24)=d(19,24);c(20,22)=d(20,22);c(21,26)=d(21,26);c(21,36)=d(21,3 6);c(21,17)=d(21,17);c(22,30)=d(22,30);c(23,17)=d(23,17);c(24,31 )二d(24,31);c(25,41)=d(25,41);c(25,19)=d(25,19);c(25,29)=d(25,29);c(27,31)=d(27,31);c(28,33)=d(28,33);c(29,22)=d(29,22);c(30, 28)=d(30,28);c(30,41)

29、=d(30,41);c(31,26)=d(31,26);c(31,34)=d(31,3 4);c(32,35)=d(32,35);c(32,23)=d(32,23);c(33,46)=d(33,46);c(33,28 )二d(33,28);c(34,40)=d(34,40);c(35,38)=d(35,38);c(36,27)=d(36,27);c(36,45)=d(36,45);c(37,40)=d(37,40);c(38,36)=d(38,36);c(39, 27)=d(39,27);c(40,34)=d(40,34);c(40,45)=d(40,45);c(41,44)=d(41,4 4

30、);c(41,37)=d(41,37);c(41,46)=d(41,46);c(42,43)=d(42,43);c(42,49 )二d(42,49);c(43,38)=d(43,38);c(44,48)=d(44,48);c(44,50)=d(44,50);c(45,50)=d(45,50);c(45,42)=d(45,42);c(46,48)=d(46,48);c(47, 40)=d(47,40);c(48,44)=d(48,44);c(49,50)=d(49,50);c(49,42)=d(49,4 2);c(50,40)=d(50,40);c(51,18)=d(51,18);c(51,21)=d(51,21);c(51,26 )二d(51,26);c(10,18)=d(10,18);for i=1:51for j=1:51if c(i,j) infc(j,i)=c(i,j);endendend程序文件名:floyd.mfunction p,q=floyd(c) n=size(c,1);p=cfor i=1:nfor j=1:nq(i,j)=j;endendfor k=1:nfor i=1:nfor j=1:nif p(i,k) + p(k,j)p(i,j) p(i,j) =p(i,k) + p(k,j); q(i,j)=q(i,k);endendendend