送货路线优秀论文一等奖Word下载.docx
《送货路线优秀论文一等奖Word下载.docx》由会员分享，可在线阅读，更多相关《送货路线优秀论文一等奖Word下载.docx（21页珍藏版）》请在冰点文库上搜索。
可不考虑中午休息时间。
1.2基本假设
1．假设送货员只能沿如图路线图行驶，不能走其他的任何路线。
2．在联通路线中，送货员可自由选择。
3．送货员交接货物只需三分钟，同一地点多次交接也以三分钟计，且同一地区的货物只一次即可全部送达，无需再次回O点取货。
交接完毕立即前往下一处，期间不会耽误任何时间。
4.假设送货员保持２４km/h，不考虑堵车及发生意外的情况。
5.假设相互连通的道路都是双向通道，没有单向的情况。
1.3符号说明
所载货物的质量总和；
所载货物的体积总和；
第i件货物的质量；
第i件货物的体积；
从i点到j点的距离权值；
任意两节点之间最短路径距离矩阵；
1.4问题分析
对于问题1：
我们要选择一条最短的路径在最短的时间内将30件货物送到指定的地点，并且返回出发点，而且需要考虑送货员的载重和各结点之间的连接信息，即所载货物重量之和须小于最大载重50kg即质量之和
体积之和小于1立方米即体积之和
，各点连接情况题中已给出。
从而我们可以将此问题转化为一个TSP最短路径问题。
根据题中所给的数据，我们得出各个点的坐标，在满足结点约束的条件下，根据Floyd算法，得出任意两个节点之间的最短路径距离。
所以我们建立目标函数：
寻找一条从起点0到各节点再返回节点0的最短路径。
对于问题2：
题中增加了“时间”这一约束条件，我们必须在满足各点的时间要求前提下，寻找一条最优的路径。
所以我们需要在模型一得基础上，对模型进行改进（按时间要求分为四个阶段：
30、10:
00），最终得到最优结果。
对于问题3：
由于货物的重量和体积的限制，路线较多时，送货员需要返回出发点取货。
因此我们根据地理位置将所有路线划分为n个区域，根据限制因素对每个区域进行优化，每个区域即可看成类似问题一的问题，因此有解决问题一的方法分区域解决即可：
1.5模型的建立与求解
1.5.1模型一
我们首先对题中所给的数据进行汇总分析，得出
=48.5公斤，V30=
=0.88立方米，所以均未超出送货员的载重，所以送货员可以一次性将货物送完。
而题中数据显示送货员需到达的节点数位22个（包括出发点O）如下表
13
14
16
17
18
21
23
24
26
27
31
32
34
36
38
39
40
42
43
45
49
所以我们需找出一条经过这22个节点的最短路径。
利用MATLAB程序（附录1）可求解出这22点中任意两点之间的直线距离，不能相通者以inf表示，这样我们可以看成典型的TSP问题，运用Floyd算法对其求解。
利用程序（附录2）用Floyd算法我们可以得出任意两点之间最短路径的距离矩阵
其中（i,j=1…22），
1）先根据题目数据给初始矩阵
赋值，其中没有给出距离的赋inf，以便于更新。
2）进行迭代计算。
对任意两点
，若存在
，使
，则
更新
3）直到所有点的距离不再更新停止计算。
则得到最短路距离矩阵
。
由旅行售货员问题（TSP）建立矩阵
=22;
其中
表示点i到点j的距离权值。
为对称矩阵，令
=0。
现求节点0到各节点再到节点0的最短距离，要求各线路上的权值最小。
设立变量
其关系如下:
当节点
和节点
连通，
=1；
不连通，
=0；
目标函数为寻找一条从起点0到各节点再到节点0的最短距离，要求各线路上的权值和最小，故目标函数为：
最短路径
（1）对起始点0至少有一条路径出去，故有
（2）对其余各节点，恰有一条路径进去，故有
（3）所有节点不出现闭合回路，约束为
；
总的线性规划模型为：
（1）
（2）
约束条件s.t.（3）
（4）
利用lingo软件编程（程序见附录3）算出在各约束条件下的最短路径距离、最短路径所经过的各节点的顺序得：
最短距离minZ=58178.58m.
最短时间minT=2.424h
各节点行进路线为：
0→26→27→39→36→38→43→42→49→45→40→34→24→13→18→14→16→32→23→17→21→0
1.5.2模型二
问题2题目增加了时间约束，所以我们需要在模型一的基础上进行改进。
送货员从早上8:
00出发，需要分别在9:
00、9：
00之前件货物送到各指定点。
根据“时间要求越早，先送的原则”，将22个节点按时间限制划分为四个区域，然后分阶段依次解决各区域的最短路径，得出各出发点和各终点。
从而得出总距离最短路径。
首先我们在图中描出各节点坐标，找到各节点位置。
如下图：
阶段1：
要求9:
00送到：
限制在此时间段的节点为三个：
13、18、24，送货员8:
00从O点出发，需选择最短路径在9:
00之前将货物送达。
根据各节点之间的距离和上图，我们很容易得出此段最短路径出发点为18，终点为24，从而路线为18→13→24，再根据示以及问题1所得数据，确定最优线路为18→13→19→24。
最后验证结果：
根据路径我们算得此路径距离:
2182.0289+3113.4627+5704.3372=10999.83m.
从而得出此段用去的时间=10999.83*3/20=27.50min<
60min，从而可以知道按此路径送货员能按时将货物送到。
阶段2：
30送到：
根据题中信息知，限制在此时间的点为：
31,34,40,45。
同上阶段相同，结合数据和上图分析的出发点为31，终点为45，从而我们可以得到两种行程路线：
31→34→40→45或31→40→34→45。
需要对两条路线进行对比优化。
两种路线的行程总路程如下：
路线1
24—31
31—34
34—40
40—45
路程（m）
1780.1475
2324.7473
1630.782
3217.0056
路线2
31—40
40—34
34—45
3954.9293
4847.7876
对比两组数据，可以选定线路1为最佳方案。
按此路径行进距离=1780.1475+3954.9293+1630.782+4847.7876=12213.6464米。
得出耗时=12213.6464*3/20=30.53min<
30min+60min-27.50min。
即得出满足时间要求。
阶段3：
要求10:
15送到：
此时间要求共有四个指定地点：
49，42，43，38。
分析可得起点为42，终点为38，从而得到两种送货路线：
42→49→43→38或
42→43→49→38。
两种路线的总路程如下：
45—42
42—49
49—43
43—38
各段路程（m）
2351.7228
1971.3764
2889.0501
2618.4442
42—43
43—49
49—38
917.6737
5507.4943
分析比较两组数据，可以选定线路1为最佳方案。
同上对数据进行验证：
按此路径行进距离=2351.7228+1971.3764+2889.0501+2618.4442=9830.5935米
得出耗时=9830.5935*3/20=24.58min<
45min.
即能够按时件货物送到。
阶段4：
要求12：
00到达：
此时间段共有十个指定地点：
26，21，14，17，23，32，39，36，27，16。
分析可确定36为起点。
起点确定终点不确定。
对此我们进行迭代算法：
即从出发点开始，找出到出发点的最近距离的一个点，然后依次迭代计算，再以找出的点为出发点，找出到该点的最短距离的点，如此进行下去，则可以找出一条较短的行进路线。
首先以36为起点，具体计算过程如下：
●点36到其他点的距离（单位：
m）如下：
距离
2203.917
2880.178
3983.84
4061.144
4704.089
4808.696
5373.013
6176.911
7470.654
所以确定27为第二次所到地点。
●点27到其他点的距离（单位：
1779．923
2604.781
4796.521
6265.06
6620.432
7576.93
8093.254
9674.571
所以确定39为第三次所到地点。
由线路图可知，离开39后需要回到27，才能送货到其它地点，则再根据上述表格选取除39外距离27最近的地点的，即是第四次所到地点，易知26为第四次所到地点（途经31）。
●点26到其他点的距离（单位：
2191.74
4015.651
5488.473
5790.165
7102.034
7887.806
可得21为第五次所到地点。
●点21到其他点的Euclid距离（单位：
1823.911
3296.733
3598.425
4910.294
5696.066
可得17为第五次所到地点。
●点17到其他点的Euclid距离（单位：
1774.514
9215.723
3086.383
3872.156
理论上讲应该选取点23，但根据线路图以及剩余送货的地点，综合考虑后选取次优解即14为第六次送货地点。
●点14到其他点的Euclid距离（单位：
2607.681
3970.237
5282.106
可得16为第七次所到地点。
●点16到其他点的距离（单位：
2097.6
3409.5
可得23为第八次所到地点，32为终点。
由以上结果可得最佳送货路线如下：
36→27→39→（27）→（31）→26→21→17→14→16→23→32
在图中标出路线：
所以综上考虑将各阶段的路径连接起来形成的最终最短路径为：
得出最短路径距离minZ=54629.65m
时间minT=2.276h
1．5．3模型三3.3
问题3的分析：
送货员将100个包裹最快送到50个指定地点，经过计算100个包裹的总质量
总体积
，送货员每次携带货物质量不能超过50kg，体积不能超过1m3，可将路线划分为n（n>
=3,且n为整数）个片区，相当于n个送货员同时从同一地点出发再返回出发点，考虑到送货员需最快送货完毕，即需要最短送货路线，则每个区域的包裹质量和体积在不超过限制时应尽可能最大，所以考虑选取n=3。
划分方案如下：
（1）按照地理位置将路线划分为A、B、C三个区域。
（2）由送货员所能运载包裹的最大重量和体积限制对三个区域进行优化。
（3）区域的公共地点可以将一个地点的多份包裹进行两次或三次送到，达到区域的优化。
由假设送货员行进速度不变，从而最佳运送方案等价于找出一个遍历每个区域所有目的顶点
并返回出发点的最短路线。
从而可以将该问题转化为TSP（旅
行商）问题（本题可以重复经过某顶点），即寻找一个最短的Hamilton圈。
模型的建立与求解：
由问题3的分析知，本题可以转化为一个TSP（旅行商）问题（本题可以重复经过某顶点），即在每个区域寻找一个最短的Hamilton圈。
而划分区域后问题三就可以转化为与问题一相同的模型,寻找每个区域完备图中的最短Hamilton圈。
在理论上来讲，送货员是送50个包裹，要送往50个地方。
其中区域的划分步骤如下：
（1）将路线划分为东,西北,西南三个区域（分别为A,B,C三个区域）（见附录3）。
（2）对区域进行精细调整，尤其是边界地点，可将区域公共地点的多个包裹分两次送到：
A，B区的公共点42，45，49的多个包裹分两次送到，将地点42的15号包裹，地点45的11号包裹，26号包裹，以及地点49的79号包裹分到B区送达；
将B，C区的公共点31的21号包裹分到C区送达。
（3）划分后每个区域包裹的总重量，总体积如下:
A（东区）：
MA=49.85kgVA=0.9356m3
B（西北区）：
MB=49.41kgVB=0.9542m3
C（西南区）：
MC=48.74kgVC=0.9102m3
A、B、C每个区域包裹的总重量不超过50kg，总体积不超过1m3。
区域划分完成。
借助数学工具Matlab,基本思路是在已知起点终点的情况下，一个点一个点的推出结论。
同时会注意到，每一段都取最小的结果相加后结果并不一定是最小的。
所以需要在计算机推断最短路线的基础上加以改进。
得出最优路线如下：
A区：
O→21→17→14→16→23→32→35→38→43→42→49→45→23→21→O
总长dA=44220.4m
B区：
O→26→31→34→40→47→40→37→41→30→28→33→46→48→44→50→49→42→45→36→27→39→27→31→26→O总长：
所以所走的总长为：
160344.8m.
1．6模型的进一步分析
1.6.1误差分析
针对模型一，首先对于数据的处理，我们采用的是运算功能强大的matlab、lingo软件，所以误差较小，可以忽略不计。
其次对于各个运算的结果，采用的是计算精确的Floyd算法，误差也较小。
模型二中，我们将各个节点按照时间约束条件，划分为四个阶段分析，所以对于最优结果，肯定存在误差，但各阶段的节点比较集中紧密，所以误差较小，因此，此模型可以使用。
模型三中，由于也是分区域求解最优解，与模型二的误差情形相同，但各区域节点比较集中，且送货员的载重和体积均接近临界值。
所以模型可以使用。
1．6．2灵敏度分析
一个好的模型不能由于初始的数据的微小误差而导致结果的较大改变。
模型一，由于约束条件较少，没有质量、体积的约束，所以灵敏度较好。
模型二加入了时间这一约束条件，灵敏度有所下降。
模型三，由于质量、体积均有约束，导致灵敏度较低。
但准确性较高，所以此模型可以使用。
1．7模型的评价和推广
1．7．1优缺点
优点：
对于题中各数据的处理，采用的工具、方法比较先进，各种计算方法精确，误差较小。
，在解决问题时，我们把原图变为完全图，利用全局线性规划法充分发挥lingo软件包求最优解功能。
并且成功地对0—1变量进行了使用和约束，简化了模型建立难度，同时给出了在各种约束条件下的最短路径的计算方法，具有较强的实用性和通用性，在日上生活中经常可以用到。
缺点：
由于数据较多，难以对模型结果进行验证，只能一步一步的对模型进行优化。
1．7．2模型推广
这是典型的TSP问题，在实际生活中，经常会遇到类似的模型要求，如：
物流管理、商业调度、旅游路线等等。
而这些都可以归结为图论问题。
图论问题中还有许多其他问题，如：
VSP线路问题、汉密尔顿回路问题等，这些都可以以此模型为基础进行改进、优化。
所以此模型可以推广到实际生活中，解决许多普遍的问题。
而此模型中所用的软件、及各种精确的算法都是运算中非常好的处理工具。
参考文献
方世昌.离散数学。
西安：
西安电子科技大雪出版社，1996.吴建国，数学建模案例精编。
中国水利水电出版社，2005.5
【1】张威，MATLAB基础与编程入门。
西安电子科技大学出版社，2008.1
西安电子科技大雪出版社，1996.李海龙，遗传算法求解物流配送中带时间窗的VRP问题，吉林大学学报第46卷，第二期2008.3
附录1：
两点间直线距离，不能相通以inf代替
matlab联通点的直线距离程序;
a=[13;
18;
220;
24;
38;
34;
42;
515;
52;
61;
718;
71;
812;
914;
910;
1018;
107;
1112;
1213;
1225;
1215;
1318;
1319;
1311;
1418;
1416;
1417;
1421;
1522;
1525;
1623;
1723;
1831;
1924;
2022;
2126;
2136;
2117;
2230;
2317;
2431;
2541;
2519;
2529;
2731;
2833;
2922;
3028;
3041;
3126;
3134;
3235;
3223;
3346;
3328;
3440;
3538;
3645;
3627;
3740;
3836;
3927;
4034;
4045;
4144;
4137;
4146;
4243;
4249;
4338;
4448;
4450;
4550;
4542;
4648;
4740;
4844;
4950;
4942;
5040;
5118;
5121;
5126;
31;
81;
202;
83;
43;
155;
25;
16;
187;
17;
128;
149;
109;
1810;
710;
1211;
1312;
2512;
1512;
1813;
1913;
1113;
1814;
1614;
1714;
2114;
2215;
2515;
2316;
3118;
2419;
2220;
2621;
3621;
1721;
3022;
3124;
4125;
1925;
2925;
3127;
2229;
2830;
4130;
2631;
3431;
3532;
2332;
4633;
3835;
4536;
2736;
4037;
3638;
2739;
4540;
4441;
3741;
4641;
4342;
3843;
5044;
5045;
4245;
4846;
4047;
5049;
4050;
1851;
2151;
2651;
]
b=[9185500;
1445560;
727057
升级会员 