1、送货路线设计问题讲解期末数学建模报告（ A）题120540214120610317姓名：李飞 专业：功能材料 学号：姓名：谭秀松 专业：自动化 学号：2014-6-7送货路线设计问题摘要现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流 行业也渐渐兴盛，每个送货员需要以最快的速度及时将货物送达，针对一个送 货员要去城市多处送货并返回，该图为一个网络图，如何设计线路使送货员所 用时间最少。因为速度是恒定的，并且货物交换时间也相同，所以把求时间最 短问题转化为求路径最短的问题，采用 Floyd 算法思想、借助矩阵、 MATLAB软 件和编程，求出最短距离矩阵和最短路径矩阵。再通过数据的
2、分析、筛选和计 算，从而可在图上标出送货员到各个点的最短路径，得到最优解。针对问题一： 采用“ D-J 模型”。在此模型中，运用 Floyd 算法求解 ,然后 套用此模型可以得到最优的结果是：送货员所走过的总路程： 54707.5 米。针对问题二： 采用“分析 &递推模型”。在此模型中利用分析法和递归的思 路建立动态的方法求得最优化结果来相结合求解 , 然后套用此模型可以得到最 优的结果是：送货员所走过的总路程： 52004.37 米送完全部货物所需时间： 3 小时 37 分 01 秒。针对问题三： 分区送货策略模型”。通过对送货点的分成不同的区域，在 对其继续单独的利用模型二计算，得到最优的
3、结果为：关键词 ：分析&递推模型 Floyd 算法 Kruskal 算法 最短路径 最小生成树法一、问题重述 现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行 业也渐渐兴盛，每个送货员需要以最快的速度及时将货物送达，而且他们往往 一人送多个地方。所以在快递公司送货策略中，确定合理的行走路线是关键的 问题。问题（ 1）在送货员送货路线设计问题中，送货员从图 1 中的起点 O出发， 将 130 件货物送到指定目的地并返回，要求所用时间最短 。此时送货员可将 30件货物一次性带上，因为这 30件货物的总重量 48.5kg 、总体积 0.88 m3并没 有超过送货员的最大载重和所带货物
4、的最大体积。问题（ 2）送货员从早上 8点开始送货，要将 1到 30货物送到指定地点并 且不超过指定时间。而且他们往往要去很多地方，如果在路线上选择不合理的 话，不仅不能按时将货物送到指定地点，反会浪费更多的时间。这样不仅要考 虑将货物送到而且要满足不超过指定时间。问题（ 3）送货的数量增加由 30件增加到 100 件，不考虑时间限制。但是 要考虑送货员的最大载重和所带货物的最大体积。很明显送货员不可能一次性 将货物带完，必须把货物分批送到，还要满足所走的路线最短。2.问题分析（1）题目中只从快递公司派出一个送货员，到任意未配送的送货点，然后将这个送货派到最近的未服务的送货点范围之内，且最大载
5、重不超过 50kg，货物体积不超过 1 立方米。在问题二中还必须使每一件货物在指定时间内送达。 继 续上述指派，直到各点总重量超过 50kg或者体积超过 1 立方米。最后业务员返 回快递公司，记录得到的可行行程（即路线）。对得到的可行的行程安排解中的 每一条路径，计算路线是否最短，时间是否最少。即得到所需的最短路线。（2）为此我们必须制定合理的送货策略一个合理的送货策略是指送 货员每天在有限的时间内， 尽量多送货， 使日送货量达到最大， 让送货员在几个 指定的送货点能最有效率的完成送货任务。 每天要将所有的货物全部送到指定点 ，不能出现每天有未接到服务， 而货品在邮局积压的情况。 送货公司要尽
6、量节约 人力成本， 从而使自己的利益最大化。 送货安排要合理， 不要出现送货点混乱和 兜弯路的情况。 根据这些合理性原则， 我们需要给送货公司制定出在固定的送货 点上安排好每个送货员的送货和运行线路， 以及总的运行公里数， 而且是需要的 送货员尽可能少，总路线尽可能短。（3）快递行业正蓬勃发展，为我们的生活带来更多方便。为了保证快件能 够在指定的时间内和规范的条件下送达目的地， 设计最快完成路线与方式成为了 快递公司的首要之需。快递公司不但要求每一件货物需要在指定的时间内送达，而且还要使每个送货员送货的路线最短， 因此，如何用最少的时间准时完成所有 的任务是最重要的。 在约束条件下， 应确定圆
7、满完成每天的送货， 保证货物不因 延误时间而耽误到客户的需要，这些都是我们需要考虑的问题。（4）通过以上分析，我们建立了“ D-J 模型”，“分析 &递推模型”，“分 区送货策略模型”。3.模型基本假设1假设送货员在送货的过程中没有出现把货物弄丢等意外情况， 全部货物 都能准确送到；2. 假设送货员在送货的过程中不考虑天气等突变因素影响送货员行进的因 素；3 假设送货员在送货的过程中没有退货情况，所有的货物都能全部送出；4 假设送货员在送货的过程中全部把货送到位， 忽略把货物送错重送的情 况；5. 假设送货员在送货的过程中不考虑路途中的交通堵塞问题，随时保持速 度恒定不变；6. 假设数据整理后
8、无其他错误。4.符号说明Inf ：表示相应两点不能直接到达dij ：各个点之间的坐标距离pij ：各点之间在有权图上的最短距离矩阵qij ：各点之间在有权图上的最短路径矩阵cij ：表示此题例图的权矩阵30M1：130号货物的总重量n1100M 2：1100 号货物的总重量n1M 31 ：第三问第一次携带货物的总重量M 32 ：第三问第二次携带货物的总重量M 33 ：第三问第三次携带货物的总重量30V1：130 号货物的总体积n1100V 2 ：1100 号货物的总体积n1V31 ：第三问第一次携带货物的总体积V32 ：第三问第二次携带货物的总体积V33 ：第三问第三次携带货物的总体积S1：第
9、 1 问的最短路程S2：第 2问的最短路程S3：第 3 问的最短路程T：第 2 问所用的总时间5.模型建立与求解深度探索此题共有 50 个目标点，加上出发点原点 O共 51 个点，要求将货物送往目标 点，且用的时间最短，则必须知道目标点和原点 O的距离（令 O点为第 51个点）， 及各个点之间的坐标距离 dij 。此图并不是每个点都相连，有些点不能直接到达， 所以要先列出此题的权矩阵 cij ，然后求出它们之间的最短距离 p ij 和最短路径qij 。则模型规划如下：51 51 51 51dij = xi xj 2 yi y j 2 ， pij = cij xi xj 2 yi yj 2i 1
10、 j 1 i 1 j 1i=1, ,51 ；j=1, ,51。利用 MATLAB软件进行计算，编程结果得： d ij 取值情况如下表所示123448495051107740.21916.35452.71660314854148717959.727740.2058252292.61433117770161591226531916.3582503536.41567015212147748537.945452.72292.63536.401449316475152661049956583.61252.94669.41161.41399316758153101108461294.38679.22940
11、.163911628913806140436876.871968.28750.73242.56492.81556612973132006049.146155881396814780139011494.19268.55739.61068847141251533913988144456857.93888.1822.347095.848166031433115670144930106947138.91209449148541777015212164751069403568.86933.950148711615914774152667138.93568.807680.9517959.712265 85
12、37.9 1499120946933.97680.90cij 得取值情况如下表12345474849505110Inf1916.3InfInfInfInfInfInfInf2Inf0Inf2292.61252.9InfInfInfInfInf31916.3Inf03536.4InfInfInfInfInfInf4Inf2292.63536.40InfInfInfInfInfInf5Inf1252.9InfInf0InfInfInfInfInf47InfInfInfInfInf0InfInfInfInf48InfInfInfInfInfInf0InfInfInf49InfInfInfInfInf
13、InfInf03568.8Inf50InfInfInfInfInfInfInf3568.80Inf51InfInfInfInfInfInfInfInfInf0此表中的 Inf 表示相应两点不能直接到达， 数值表示两点间可以直接到达的距离值， 0 表示自身到自身的距离利用 Floyd 算法求得 pij，pij 取值情况如下表所示123454748495051107745.31916.35452.78998.3162771876120306169891006827745.305829.12292.61252.9224271800226325227571629631916.35829.103536.
14、47082166761785620705173881046745452.72292.63536.403545.6202122029524242209241400458998.31252.970823545.6021174167492507321504165634716277224271667620212211740112538943.55374.79215.8481876118002178562029516749112530107087139.6158064920306263252070524242250738943.51070803568.81172250169892275717388209
15、24215045374.77139.63568.809928.15110068162961046714004165639215.815806117229928.10(1) 从起点 51 出发，行遍每一个地点并且要把 30 件货物送到指定目的地并返回，要30求所用时间最短 。由题意得： 130 号货物的总重量为： M 1 48.5 50；总体 n130积为： V1 0.88 1 ，所以一次性可将货物全部带完。行走路线如下：n1路线51（ O） 26 21 17 14 16 23 32 35 38 36 38 43路程1392.1+2191.7+1823.9+2195.7+2607.7+2097.
16、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.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最（ 短路程 ）最短路程 : S1=54707.5（米）2）5.1 问题一 ：在第一题的基础上，第二题加了限制条件（将货物在指定时间内送到指定地点），送货员还是可以将货物全
17、部携带，但没有限制必须返回，所以行走路 线如下：24公里/小时=400米/ 分1 阶段1 阶段路线51（ O） 18 13 19 24路程2182+3113.5+3455.7+2258.62 阶段2 阶段路线24 31 34 40 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
18、+2607.7+2195.7+1823.9+2191.7 +1537+1067.8+1779.91阶段用时：(2182+3113.5+3455.7+2258.6 ) /400+3*2+3=36.5242min=36 分 31 秒 此时刻时间为： 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+9
19、17.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+1114+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
20、12:00:00 满足条件全程总走过的路程为： S2 =52004.37( 米)全程总用时为： T=3小时 37分 01 秒(3)要将 100 件货物送到指定地点，无时间要求，并要求返回，求最短路 径。30由题意得： 1100 号货物的总重量为： M 2 148 50 ；总体积为：n130V2 2.8 1 ，所以至少要三次性才可将货物全部带完。行走路线如下：n1第1次 从 O 出发路线51（ O） 18 13 11 12 15 5 2 4 3 8 1 6 17 10 9 14 16 23 17 21 51（ O）路程2182+3113.5+1669.6+1417.7+4805.8+5004.5
21、+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） 18 31 24 19 25 29 22 20 22 30 2833 46 48 44 41 37 40 47 40 34 31 26 51（O）路程2182+2103.7+1780.1+2258.6+1966.2+1885.9+1097.9+1498.9+1498.9+1287.5+1017.9+1325.7+3758.
22、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） 26 31 27 39 27 36 45 50 49 42 4338 35 32 23 17 21 51（O）路程1392+1537+1067.8+1779.9+1779.7+2203.9+3182.5+3102.8+3568.8+1971.4+917.67+2618.4+1409.7+1114+1311.9+1774.5+1823.9+1796.9=34352.8红、绿、蓝分别是一条回路，第一次
23、从 O点出发，经过 18 这个地点，但不带 2 号，48 号货物： M31 49.99 50， V31 =0.94121；第二次从 O点出发经过 31，26 这两个地点，但不带 61 号，4 号，23 号， 56 号货物M 32 49.73 50 , V32 =0.89971; 第 三 次 从 O 点 出 发M 33 48.28 50, V33 =0.95911，满足题目要求。全程总走过的路程为： S3= 51440.5+45913.4+34352.8=131706.7（ 米）五、模型评价A优点：1. 在模型求解最短距离过程中用了 MATLAB软件编程，把大量的运算交给计 算机处理，提高了计算
24、的准确性。2. 本模型通过转换的思想， 把求时间最短转化为求路径最短， 使问题变的简 单些，便于求解。3. 定性与定量相结合的方法解决了送货员送货问题。B.缺点：1. 由于本模型的计算量大，在计算的过程中，存在数据的处理，比如：四舍 五入导致最后的计算数值可能存在误差。参考文献【1】陈光亭 裘哲勇. 数学建模 . 北京：高等教育出版社【2】肖华勇. 实用数学建模与软件应用 . 西安：西北工业大学出版社 2008.11.S1 期， 2006年【 3】刘承平 数学建模方法 北京：高等教育出版社【 4】张秀兰 林峰 数学建模与实验 北京：化学工业出版社附录x=9185 1445 7270 3735
25、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=500 560 570 670 995 1435 2280 2525 2680 3050 3
26、545 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)=sqrt(x(i)-x(j)2+(y(i)-y(j)2);c(i,j)=inf;c(i,i)=0
27、;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)=d(09,10);c(10,07)=d(10,07);c(11,12)=d(11,12);c(
28、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);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
