送货员送货最优路径

2012高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）： 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 参赛队员 (打印并签名) ：1. 2. 3. 指导教师或指导教师组负责人 (打印并签名)： 日期： 年 月 日赛区评阅编号（由赛区组委会评阅前进行编号）：2012高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：送货路线设计问题摘要本文讨论了送货员的送货路线的最优路线问题，即在给定的地点，线路的条件下，结合考虑最大载重范围、最大带货体积及各个货物送货实现，确定送货员的最佳送货路线。对于问题一，我们针对号货物所涉及的个站点建立了最小生成树模型，结合算法算出的各顶点间的最短路径矩阵，画出了最佳线路，并求出了所用时间。在问题二的求解中先进行假设在问题一中找到的路线符合要求，并进行检验。接着我们采用分区域讨论以及最小生成树的方法进行寻找最佳路径，根据所得的数据进行分析，最后寻找到最佳路径，并得出路径的距离以及送货员完成任务并返回的时间。对于第三问，要将100件货物全部送到指定地点并返回，由于送货员一次送货的重量和体积有限制，所以我们考虑分区域送货。首先我们根据最小生成树将图上区域在满足条件下划分为尽可能少的区域块，在此基础上实现区域线路最短，从而实现全局最短。根据我们划分的区域，我们在每个区域里找出最短路径的回路。我们尽量用最小生成树的主干，如果遇到分支，考虑送货员要遍历区域内所有的点，同时利用模型，选择一条比较短的路径。通过我们的分析和比较，最终得出了最优路径。关键词：；最小生成树；最短路径；划分区域；送货问题一、问题重述现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛。现有一快递公司，要求送货员以最快的速度及时将货物送达，且可以一人送多个地方，要求设计方案耗时最少。该地形图及图中各点的连通信息，各点的坐标，货物的相关信息，送货员的平均速度，和每件货物的交接时间都已给出。货物员最大载重50公斤，所带货物最大体积1立方米。同一地点有多件货物也按每件3分钟交接计算。现在该送货员要将100件货物送到50个地点，要求如下：1. 设计最快将130号货物送到指定地点并返回的完成路线与方式，结果要求标出送货线路。 2. 若该送货员从早上8点上班开始要将130号货物的送达，时间不能超过指定时间，设计出最快完成路线与方式。 3. 若不考虑所有货物送达时间限制(包括前30件货物)，将100件货物全部送到指定地点并返回。设计最快完成路线与方式。结果要求标出送货线路，给出送完所有快件的时间，另外，送货员可中途返回取货，不考虑中午休息时间。二、问题分析由题目已知条件可将送货问题看做是图论求解最佳路径问题。第一问要求算出将130号货物送到指定地点并返回的最快完成路线与方式，即最短时间。通过计算我们得出130号货物的总重量和总体积并没有超过送货员的最大承载量，且第一问没有货物送达的时间要求，故此问题转化为于找出一个遍历所有目的顶点并返回出发点的最短路径问题。在解决问题二的过程中，我们将件货物按照不能超过的时间进行排序，并在图中标出相应的点，根据各个地点的位置分布，以及时间的要求，我们将这个点进行区域划分，找到各个区域的最佳路径，最终将其连接就找到了送货员按时完成任务的最佳送货路径第三问由于送货员一次送货的重量和体积有限制，所以我们不仅要考虑最短路径的问题，还要考虑送货员一次带的货物的重量和体积。通过分析，我们考虑用最小生成树划分区域，要实现区域线路最短，从而实现全局最短。三、模型假设及符号说明3.1模型假设(1)送货员只能走题目中给定的连通路线，不能走其他的任何路线；(2)假定送货员最大载重50公斤，所带货物最大体积1立方米；(3)假定送货员的平均速度为24公里/小时；(4)假定每件货物交接花费3分钟，为简化起见，同一地点有多件货物也简单按照每件3分钟交接计算； (5)送货员在送货期间无堵车现象，即送货员送货途中不受任何外界因素影响；(6)送货员送货期间不考虑中午休息时间；(7)假设送货员到达送货点后就将此站点上的所有货物交付；(8)到同一地点的货物要一次拿上；(9) 送货员回到0点时不考虑取货时间。3.2符号说明：第个货物的重量；：序号为的送货点的坐标；：第个货物的体积； ：赋权连通图；：的第个子图；：子图中的最佳回路；：边的边权；：点的点权；：的各点权之和； ；点权.四、模型的建立与求解4.1模型的建立我们先后建立了最小生成树模型和模型，二者结合求解。我们先通过Matlab编程可得到坐标系中各站点的点号（程序见附录1），如图1所示：坐标系中各站点的点号（图1）把快递公司送货地点示意图抽象为一赋权连通图，在权图中，对应示意图中的快递公司地点及货物送达点，表示快递公司所在地，对应示意图中路径.边权对应示意图中的路径长度.建立的最小生成树数学模型如下：求中回路使得满足：（1）（2）（3） 我们将与某顶点关联的边数称为该顶点的度。连通的无圈图叫做树。设是无向连通带权图，即一个网络。中的每一条边（）的权为。如果的子图是一棵包含的所有顶点的树，则称为的生成树。生成树上各边权的总和称为生成树的耗费。在的所有生成树中，耗费最小的生成树称为的最小生成树，我们在此基础上建立了最小生成树模型。我们使用的是最小生成树的算法,算法是从图中一条一条地选择边，并将他们加入到支撑树中。它的算法思想如下：假设是图中顶点的集合,是图中边的集合,为最小生成树中的边的集合,则算法通过以下步骤可以得到最小生成树:首先初始化: ,此步骤设立一个只有结点的结点集和一个空的边集作为最小生成树的初始行态,在随后的算法执行中,这个行态会不断的发生变化,直到得到最小生成树为止。然后在所有,的边中,找一条权最小的边(，将此边加进集合中，并将此边的非中顶点加入中。此步骤的功能是在边集中找一条边,要求这条边满足以下条件:首先边的两个顶点要分别在顶点集合和中,其次边的权要最小。找到这条边以后,把这条边放到边集中,并把这条边上不在中的那个顶点加入到中。这一步骤在算法中应执行多次,每执行一次,集合和都将发生变化,分别增加一条边和一个顶点,因此, 和是两个动态的集合。如果,则算法结束;否则重复步骤2。可以把本步骤看成循环终止条件。我们可以算出当时,步骤2共执行了次(设为图中顶点的数目), 中也增加了条边,这条边就是需要求出的最小生成树的边。最后，我们用得出的最小生成树结合算法算出22个点的最短距离（程序见附录2）。模型的建立：令表示一个矩阵，它的元素是（1）将图中各顶点编为确定矩阵，其中元素等于从顶点到顶点最短弧的长度(如果有最短弧的话)如果没有这样的弧，则令对于，令（2）对，依次由的元素确定的元素，应用递归公式每当确定一个元素时，就记下它所表示的路在算法终止时，矩阵的元素就表示从顶点到顶点最短路的长度 4.2模型的求解4.2.1问题一的求解针对问题一我们先在图中标出了130号货物对应的站点号和（如图2所示）。130号货物对应的站点号（图2）算出130号货物的总重量为48.550，总体积为0.88 1，故送货员无需返回取货，一次送达即可。我们先用最小生成树法求出这22点的最小生成树，如图3：（程序见附录3）。图3：22个点的最小生成树。然后我们根据图中的路线得到的22个点的最小生成树，找出一个最短的回路。我们的原则是，尽量用最小生成树的主干，如果遇到分支，考虑送货员要遍历所有的点，同时利用我们前面的floyd模型，选择一条比较短的路径。通过我们的分析和比较，得出的最优路径如图4：图4则问题一的最优路径为：路线最短总长度为 用的时间为4.2.2问题二的求解在问题二中，路线的设计受到了时间的约束。我们在解决问题一的过程中找到了一条运送件货物的最快的路线，假设这条路线也可以按时完成任务，我们对其进行检验。由题意可知，货物最早到达地点的时间不能超过,不超过的货物送达地点有。从问题一所得的路线可以看出，不超过的货物最先送达的是地点，到达地点时，送货员已走的距离为米，所经历的时间为个小时，此时的时间为10.9221时（约为）已经超过时间的限制，所以，假设不成立，即问题一中所得的路线能按时完成送货。我们将个货物按不能超过的时间进行排序（见附录），根据表一，我们将送货的过程分为四个阶段,即。在图中表示如图5：图5故选择最佳的送货方案就是找到每个阶段的起点和终点。我们从图中可以看出，这四个阶段的过渡点如下：第一个阶段与第二个阶段的过渡点：和第二个阶段与第三个阶段的过渡点：第三个阶段与第四个阶段的过渡点：这样我们就可以知道各个阶段的起点与终点，此外，我们从表一中可以看出，第四个阶段内需送的货物最多，但是分配的时间也是最多的，所以可以考虑按照时间顺序行走。在第一个阶段，送货时间不能超过，货物送达的地点有。由图中可以看出，送货路线为：，相应的数据如表1：送达路径两点距离(米)所需时间(h)到达时间(h)表1 (到达时间是指在到达该地点并完成交接后的时间)到达地点的时间为时（约为），交接完成后时间为时（约为）。在第一个阶段中，总的距离为米 花费的时间为个小时在第二个阶段，送货的时间不能超过，货物送达的地点有。其中有件货物送至,件货物送至，从图中可以看出，阶段的送货路线为，相应的数据如表2：送达路径两点距离(米)所需时间()到达时间()表2(到达时间是指在到达该地点并完成交接后的时间)达到地点时的时间为时（约为），交接完成后的时间为时（约为）。在第二个阶段中，总的距离为米 花费的时间为个小时在第三个阶段，送货的时间不能超过，货物送达的地点有。其中有件货物送至，从图中可以看出，阶段的送货路线为，相应的数据如表3：送达路径两点距离(米)所需时间()到达时间()9表3(到达时间是指在到达该地点并完成交接后的时间)到达地点时的时间为时（约为），交接完成后的时间为时（约为）.在第三个阶段中，总的距离为米 花费的时间为个小时在第四个阶段，送货的时间不能超过，货物送达的地点有。其中，有件货物需要送到，有件货物需要送到，有件货物需要送到，有件货物需要送到 在解决第四个阶段的路线的问题中，我们采用最小生成树的方法（程序见附录）分别得到货物到达地点的最短路径，根据图中各个货物送达地点的位置，以及最小生成树得出的结果，我们进行寻找路径，通过比较，我们找到第四阶段的最佳路径为：其相应的数据如表4：送达地点38353532322323161614两点距离(米)1409.7251114.0021131.8692097.6422607.681所需时间(h)0.05870.04640.05470.08740.1087到达时间(h)10.049910.246310.40110.538410.6971送达地点14171721213636272739两点距离(米)2195.7231823.9112880.1782203.9171779.923所需时间(h)0.09150.0760.120.09180.0742到达时间(h)10.838610.964611.134611.326411.4506送达地点392727313126260两点距离(米)1779.9231067.7551537.0261392.058所需时间(h)0.07420.04450.0640.058到达时间(h)11.524811.569311.733311.7913表4(到达时间是指在到达该地点并完成交接后的时间)货物到达地点时的时间为时（约为），在地点交接完成后的时间是时（约为）。在第四个阶段中，总的距离为米 花费的时间为个小时所以，综合以上四个阶段，送货员把货物送至各个地点并返回的最佳路线为：在图中标记如图6：图6（图解：在上图中，蓝色的点代表的是阶段一的货物到达地点，绿色的点代表阶段二的货物到达的地点，橙色点代表的是阶段三的货物送达地点，红色点代表的是阶段四货物送达的地点）送货员把所有的货物送完并返回，所走的总路程为：花费的总时间为：4.2.3问题三的求解本问同样是图上点的行遍性问题。此问题的限制条件是送货员一次送货的重量和体积，由此限制，将图上区域在满足条件下划分为尽可能少的区域块，在此基础上实现区域线路最短，从而实现全局最短。运行MATLAB 程序，得到以0点为源点的最小生成树（程序见附录5），见图7：图7：以0点为源点的最小生成树因为这50个地方要送的货物总重量为公斤，总体积为立方米，送货员每次最大载重公斤，所带货物最大体积立方米，所以可以分三次送货物。首先根据生成的最小生成树将图上的点划分区域，我们以为原点，把个地方划分成了个区域，又根据送货员最大载重公斤，所带货物最大体积立方米的约束调整边界点，最终划分的区域如下：第一区域（包括边界点）：第二区域（包括边界点）：第三区域（包括边界点）：如图8：图8根据我们划分的区域，我们在每个区域里找出最短路径的回路。我们尽量用最小生成树的主干，如果遇到分支，考虑送货员要遍历区域内所有的点，同时利用floyd模型算出的每两个点之间的最短距离（程序见附录6），选择一条比较短的路径。通过我们的分析和比较，得出的最优路径如下：（1）、送货员去第一区域个送货（共有货物33件）的地方为：总重量：公斤，总体积：立方米。路线为：如图9（用线描成回路的部分）：图9路线总长度为：米，总时间为：小时。（2）、送货员去第二区域13个地方送货（共有货物件）的地方为：总重量：公斤，总体积：立方米。路线为：如图10（用线描成回路的部分）：图10路线总长度为：米，总时间为：小时。（3）、送货员去第三区域送货（共有货物33件）的地方为：总重量：公斤，总体积：立方米。路线为：如图11（用线描成回路的部分）：图11路线总长度为：米，总时间为：小时。综上所述，送货员要送完这件货物，要小时。五、模型的评价与推广我们采用最小生成树模型和模型结合的方法求有返回的最短路径，最大的优点是直观易懂，两种模型互补相得益彰，且该模型适用于求其他最短路径。但是，这种方法并不能直接得出最短的回路，需要进一步讨论和改进。在第二问中，我们按照送达货物不能超过的时间的顺序将路线为四个阶段，并按照区域讨论的方法找到最佳路径，这种方法比较简单易懂，但是，由于不能完全掌握实际的数据，故计算结果与实际存在一定的差距。其中分类讨论的方法可以用于解决类似的问题。第三问，我们先利用最小生成数把区域划分为三个区域，这种分区域的方法比较简单，而且比较准确，简单明了，结合floyd模型找出最短回路。但是不足的是，我们找的最短路径回路比较麻烦需要一步步找，适合数据少的题目，如果数据很多会不适合。参考文献1 司守奎 孙玺菁，数学建模算法与应用，北京；国防工业出版社，2011年2 薛毅，数学建模基础，北京；北京工业大学出版社，2005年3 姜启源，数学建模教程M，北京；清华大学出版社，2005年4 吴建国，汪名杰，李虎军，刘仁云，数学建模案例精编（第一版），北京，中国水利水电出版社，2005年5 陈东彦, 李冬梅, 王树忠, 数学建模，北京，科学出版社，2007年6 刘来福 曾文艺,数学模型与数学建模（第二版），北京；北京师范大学出版社，2002 7 谭永基，数学模型上海；复旦大学出版社，2005附录1、做出51个站点的图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= 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;plot(x,y,o)hold onfor i=1:50text(x(i)+100,y(i)+100,num2str(i);text(11000+50,8250+200,0);enda=;b=zeros(51,51);for i=1:length(a) b(a(i,1),a(i,2)=1;endxy=x,y;gplot(b,xy)2、最小生成树模型：clc;clear;a=zeros(22);a(1,5)=3113.463;a(1,8)=5714.337;a(17,20)=3217.006;a=a+a;a(a=0)=inf;result=;p=1;tb=2:length(a);while size(result,2)=length(a)-1 temp=a(p,tb);temp=temp(:); d=min(temp); jb,kb=find(a(p,tb)=d); j=p(jb(1);k=tb(kb(1); result=result,j;k;d;p=p,k;tb(find(tb=k)=;endresult3、Floyd算法n=22; a=zeros(n);a(1,5)=3113.463;a(5,11)=2103.693;a(5,22)=2182.029;a(20,18)=2351.723;a(18,21)=1971.376;a(17,20)=3217.006;a=a+a; a(a=0)=inf; a(1:n+1:n2)=0; path=zeros(n);for k=1:n for i=1:n for j=1:n if a(i,j)a(i,k)+a(k,j) a(i,j)=a(i,k)+a(k,j); path(i,j)=k; end end endenda, path4、将30个按时间进行排序表不超过时间货物号送达地点9:0011321820249:3033111451445213124342540264510:151038124315421643274912:00426521614717823932133917321836192722272326283229233016问题二中阶段四的地点排序表01416172123261234567（续表）27313235363839891011121314问题2最小生成树的程序及结果：clc;c