《西工大最优送货路线》由会员分享，可在线阅读，更多相关《西工大最优送货路线（29页珍藏版）》请在金锄头文库上搜索。
1、最优送货路线摘要：建立了最优送货路线的模型，使物流公司在满足一定的社会效益（如按时送达）和获得最大经济效益（如较少的人力物力、较短的时间）的前提下，可以给出理想的送货方案与路线。对问题一，采用了两种模型求解：在模型一中，首先给出三十件货物送达地点的一个完全图，再利用二边逐次修正法的思想，利用Matlab随机产生10000个初始圈并生成哈密顿圈，通过程序自动比较可以很近似地得到本问题的最优路线，得出其最优路线的总路程为54708米。模型二建立了整数规划模型，该模型可以得出本问题的最优路线，其总路程为54707.63米，结果和模型一相差无几，由此也可看出模型一在解决本问题时不失为一个好模型。针对问
2、题二，化繁为简，将截止送货时间和交接货物所用时间等约束条件统一转化为路程约束，于是问题二就转化为判断以下问题：问题一中每次产生的哈密顿圈的每个节点是否满足其路程约束。不满足则跳出继续判断下一个哈密顿圈，如若满足，通过逐次比较各个符合条件的哈密顿圈即可得出最优路线，通过该模型得到的最优路线的总路程为56277米。问题三可以采用多旅行商问题的解决思路，先根据普里姆算法计算出最小生成树，再结合各点的位置坐标和得到的最小生成树，将其分为三组，于是问题三就转化为在满足重量和体积要求的前提下求该送货员三次送货的总时间（送货员在路上花费的时间+送货员交接货物花费的时间）最短的送货路线。分组后的算法和问题一类
3、似，求得其最短送货时间为11.187小时。关键字：图论、哈密顿圈、完全图、最小生成树、分组、规划 一、问题的提出现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个送货员需要以最快的速度及时将货物送达，而且他们往往一人送多个地方，这不仅对于送货公司的效益来说是非常重要的而且对于送货员的薪酬多少等也是至关重要,所以对于路线的优化设计是很有必要的！现有一快递公司，库房在图1中的O点，一送货员需将货物送至城市内多处，合理地设计送货方案，使所用时间最少。该地形图的示意图见图1，各点连通信息见表3，假定送货员只能沿这些连通线路行走，而不能走其它任何路线。各件货物的相关信息见
4、表1，50个位置点的坐标见表2。假定送货员最大载重50公斤，所带货物最大体积1立方米。送货员的平均速度为24公里/小时。假定每件货物交接花费3分钟，为简化起见，同一地点有多件货物也简单按照每件3分钟交接计算。现在送货员要将100件货物送到50个地点，需要分别解决以下问题：问题（1） 若将130号货物送到指定地点并返回。设计最快完成路线与方式。给出结果。要求标出送货线路。问题（2） 假定该送货员从早上8：00上班开始送货，要将130号货物的送达时间不能超过指定时间，请设计最快完成路线与方式。要求标出送货线路。问题（3） 若不需要考虑所有货物送达时间限制(包括前30件货物)，现在要将100件货物全
5、部送到指定地点并返回。设计最快完成路线与方式。要求标出送货线路，给出送完所有快件的时间。由于受重量和体积限制，送货员可中途返回取货。可不考虑中午休息时间。 问题（4） 在上述关于交接时间t和运货速度v的假定下，如果送货人员足够多，完成送货的最短时间是多少？送货路线给出在这种最短时间完成送货的要求下，如何射界运送路线认为最佳？ 二、符号约定v 速度常量24000米/小时a（i，j） i点与j点的最短距离距离，（51=i=51， 51=j=51）S1，S2，S3 分别表示三个分组的路程（问题三）51 O点maxw 最大载重50公斤maxv 最大体积1立方米w1 三十件货物总重量v1 三十件货物总体
6、积w2 一百件货物总重量v2 一百件货物总体积b（i,1） 第i个地点交接货物所花时间转化的路程，（1=i=21）b（i,2） 第i个地点交接货物截止时间距离早上八点的时间间隔（小时）（1=i=21）b（i,3） 第i个地点交接货物截止时间距离早上八点的时间间隔转化的路程（1=i= m（i）这一条件,就得到了一组可行路径，多条路径经过比较可得出最优解。 哈密顿圈路径符合时间要求输出路径与路程对比多组找出最优解说明：程序简明流程图对问题三的分析： 现在要将100件货物全部送到指定地点并返回，这里不需要考虑所有货物送达时间限制(包括前30件货物)，但一百件货物的总重量w2为148公斤，总体积v2为
7、2.8立方米，超出了最大载重maxw和最大体积maxv。由于w2/maxw3,v2/maxv3,可考虑分三次送货。利用表2和表3的信息，使用普里姆算法计算出最小生成树；结合各点的位置坐标和最小生成树，将其分为三组；验证此三组是否皆满足重量和体积要求，如若不满足重复上步至符合为止；对符合条件的三组分别使用求哈密顿圈的算法得出最优解并比较即可。 四、模型建立与求解模型准备： 1. 统计表1的货物信息，其中包括：前三十件货物的送达地点以及每个送达地点的货物数；前三十件货物的总重量和总体积；前三十件货物的截止时间和交接货物时间转化为对应的路程约束；一百件货物的总重量和总体积；一百件货物的送达地点以及每
8、个送达地点的货物数。2.表2中已给出各个送货点的坐标（X，Y），表3已给出各送货点相互到达信息，可求出表3中各个点的距离，其程序代码见附录1，各点之间的距离见附录A。主要运算式如下：S（a，b）= SQRT(a(X)+b(X)2+(a(Y)+b (Y)2)3.图论的原理是佛洛依德算法，利用图论软件输入各连通结点之间的距离算出51个结点（包括起点）之间两两的最短路径与距离，即完全图。模型求解问题一：模型一：因为最佳哈密顿圈不一定是最佳送货路线，同样最佳送货路线也不一定是最佳哈密顿圈，所以首先要将求最佳送货路线的问题转化为求最佳哈密顿圈的问题。又因为在一个加权图中寻求最佳送货路线的问题等价于在一个
9、完备加权图中寻求最佳哈密顿圈，于是可先通过图论软件求得其完全图再通过二边逐次修正法求得其哈密顿圈，即其最佳送货路线。 但是使用二边逐次修正法其结果取决于初始圈的选取，所以为了使所得到结果尽量的接近最优解，可通过随机产生排列的方法得到大量初始圈。（用模型一求解问题一的算法见附录2）经过比较可得以下路径为最佳送货路线：问题一的最优路径： 22-9-6-4-2-3-7-12-4-5-19-21-18-20-17-13-11-10-16-8-1-5-22对应实际地点序号：51-26-21-17-14-16-23-32-36-38-43-49-42-45-40-34-31-27-39-24-13-18-
10、51实际最优送货路线为：51-26-21-17-14-16-23-32-35-38-36-38-43-42-49-42-45-40-34-31-27-39-31-27-24-19-13-18-51得到的最短路程为：5.4708e+004模型二：由题易知此类问题为TSP问题，可以用多种方法把TSP表示成整数规划模型。这里把该问题的每个解（不一定是最优的）看作是一次“巡回”。在下述意义下，引入一些0-1整数变量：其目标只是使为最小。这里有两个明显的必须满足的条件：送货地点i后必须要有一个即将送货的确切送货地点；送货地点j前必须要有一个刚刚送过货物的确切地点。用下面的两组约束分别实现上面的两个条件。到此我们得到了一个模型，它是
