2010年西北工大数模送货路线论文 - 图文

一、问题重述

现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个送货员需要以最快的速度及时将货物送达，而且他们往往一人送多个地方，请设计方案使其耗时最少。 现有一快递公司，库房在图1中的O点，一送货员需将货物送至城市内多处，请设计送货方案，使所用时间最少。该地形图的示意图见图1，各点连通信息见表3。各件货物的相关信息见表1，50个位置点的坐标见表2。

现在送货员要将100件货物送到50个地点。问题如下

问题一： 若将1~30号货物送到指定地点并返回。设计最快完成路线与方式。给出结果。要求标出送货线路。

问题二：假定该送货员从早上8点上班开始送货，要将1~30号货物的送达时间不能超过指定时间，请设计最快完成路线与方式。要求标出送货线路。

问题三： 若不需要考虑所有货物送达时间限制(包括前30件货物)，现在要将100件货物全部送到指定地点并返回。设计最快完成路线与方式。要求标出送货线路，给出送完所有快件的时间。由于受重量和体积限制，送货员可中途返回取货。可不考虑中午休息时间。

图一

2010年西北工业大学“工大正禾杯”送货路线论文 作者 王景

二、 基本假设

1、假设送货员的最大载重是50公斤，所带货物的最大体积为1立方米； 2、假设送货员的路上平均速度为24公里/小时，不会出现意外现象； 3、每件货物交接花费3分钟，同一地点有多件货物也简单按照每件3分钟

交接计算，不会出现特殊情况而延误时间； 4、送货员只沿示意图连线路径行走；

5、假设快递公司地点O为第51个位置点； 6、假设送货员回到出发点O后取货时间不计。

三．符号定义及说明

D 两点最短路径距离矩阵 从O/51点出发，经过Vi中所有点最后回到O/51点的最佳送货路线的权值（即总路程） Vi（1,2，…n） 从1到50个位置点里n个位置点集合 f(Vi) T H 送货员完成一次送货的时间 Vi集合所有位置点要送达的货物件数 四、问题的分析

快递公司的送货员需要把货物送到所有货物交接地点，最后回到出发点。问如何安排送货路线，能最快完成任务，即总的送货行程最短。此即图论中最佳推销员路径问题。

若不考虑送货员最大载重和体积，两个位置点边上的权表示距离，于是问题就成为在加权图中寻找一条经过每个位置点至少一次的最短闭通路问题，即求最佳哈密尔顿圈（H圈），也即是NP-完备问题。

用矩阵翻转方法来实现二边逐次修正法过程，求最佳哈密尔顿圈（H圈）。

五、模型的建立与求解

准备工作：

用MATLAB编程先求出附表给定的相互之间可直接到达地点之间的距离：

序号 1 2 3 位置点1 1 1 2 位置点2 3 8 20 距离（米） 1916 2864 7823 2010年西北工业大学“工大正禾杯”送货路线论文 作者 王景

4 5 6 7 8 9 10 11 12 13 14 ?? 81 82 83 2 3 3 5 5 6 7 7 8 9 9 ?? O/51 O/51 O/51 4 8 4 15 2 1 18 1 12 14 10 ?? 18 21 26 2293 1958 3536 5005 1253 1294 5918 4510 1757 2681 1946 ?? 2182 1797 1392 用上表各地点的距离可构造示意图的带权邻接矩阵，再用Floyd算法求每对地点之间最短路径。

1. Floyd算法的基本思想

直接在示意图的带权邻接矩阵中用插入顶点的方法依次构造出n个矩阵

D(1)、 D(2)、? 、D(n)，使最后得到的矩阵D(n)成为图的距离矩阵，同时也求

出插入点矩阵以便得到两点间的最短路径． 用Matlab编程得D

1 2 3 4 5 6 7 8 ?? 49 50 O/51 1 2 3 4 5 6 7 8 ?? 49 50 O/51 (51)

=（Dij）51×51，其中D(i,j)即为两点最短路径距离，

0 7745 1916 5452 8998 1294 1968 2864 ?? 20306 16989 10068 7745 0 5829 2293 1253 9039 9713 7787 ?? 25570 22001 16296 1916 5829 0 3536 7082 3210 3884 1958 ?? 20705 17388 10467 5452 2293 3536 0 3546 6746 7420 5494 ?? 24241 20924 14003 8998 1253 7082 3546 0 10292 10966 9040 ?? 24317 20748 16563 1294 9039 3210 6746 10292 0 3262 4158 ?? 21600 18283 11362 1968 2864 ?? 9713 7787 ?? 3884 1958 ?? 7420 5494 ?? 10966 9040 ?? 3262 4158 ?? 0 4832 ?? 4832 0 ?? ?? ?? ?? 18338 18747 ?? 15021 15430 ?? 8100 8509 ?? 20306 25570 20705 24241 24317 21600 18338 18747 ?? 0 3569 11721 16989 22001 17388 20924 20748 18283 15021 15430 ?? 3569 0 9928 10068 16296 10467 14003 16563 11362 8100 8509 ?? 11721 9928 0 基本概念

令G=(V,E)为一个加权无向图，其中V=｜v1,v2,??，vn｜为顶点集合，E

2010年西北工业大学“工大正禾杯”送货路线论文 作者 王景

为边集合。图G中每一条边e都对应一个实数w(e)，则称w(e)为该边的权。若任意两点均有边相连，则G为完备图。

哈密尔顿图 设G=(V,E)是连通无向图，经过G的每个顶点正好一次的圈，称为G的一条哈密尔顿圈，简称H圈；含H圈的图成为哈密尔顿图或H图。 最佳H圈 在加权图G=(V，E)中，权最小的哈密尔顿圈称为最佳H圈； 判定一个加权图G=(V，E)是否存在哈密尔顿圈是一个NP问题，而它的完备加权图G'=(V,E') （E'中的每条边（x,y）的权等于顶点x与y在图G中最短路径的权）中一定存在哈密尔顿圈，所以在完备图G'=(V,E')中寻找最佳H圈。该过程采用二边逐次修正法并利用矩阵翻转实现。 二边逐次修正法的算法过程如下：

（1）任取初始H圈: C0?v1,v2,...vi,...vj,..vn,v1 （2）对所有的i,j，若wvv1?i?1?j?n，(,i)v?(vijw即C?v1,v2,...,vi,vj,vj?1,...,vi?1,vj?1,...,vn,v1

（3）对C重复步骤（２），直到条件不满足为止，最终得到的C即为所求．

矩阵翻转 在一个矩阵中，对它的第i行（列）到第j行（列）翻转是以第i行（列）和j行（列的）中心位置为转轴，旋转180度，这样：第i行（列）和第j行（列）的位置互换，第i+1行（列）和第j-1行（列）位置互换，??

问题一 ：

由附录给定的各货物号信息表，1~30号货物总重量48.5公斤、总体积0.88立方米，显然送货员能够一次带上所有货物到达各送货点，而且货物要送达的送货点总共为21个

V（13,14,16,17,18,21,23,24,26,27,31,32,34,36,38,39,40,42,43,45,49）

本模型运用图论中最佳推销员路径问题与最佳Ｈ圈中的相关结论，建立了关于该类问题的优化模型，将出发点O/51和21个送货点结合起来构造完备加权图。

不考虑送货员最大载重和体积，用矩阵翻转方法来实现二边逐次修正法过程，求最佳哈密尔顿圈（H圈）。由完备加权图,确定初始H圈,列出该初始H圈加点序边框的距离矩阵,然后用二边逐次修正法对矩阵进行“翻转”,就可得到近似最优解的距离矩阵,从而确定近似最佳H圈。

由于用矩阵翻转方法来实现二边逐次修正法的结果与初始圈有关，故为了的到得到较优的计算结果，我们用MATLAB编程时，随机搜索出若干个初始H圈，例如1000个。在所有H圈中，找出权最小的一个，此即要找的最佳H圈的近似解。

最佳H圈的近似解 min

j?,11?)wvv(?,i)v(viw1?,?j)j1?,则在C0中删去边(vi,vi?1)和(vj,vj?1)而加入边(vi,vj)和(vi?1,vj?1)，形成新的H圈C，

送货时间 T=

+0.05*H

2010年西北工业大学“工大正禾杯”送货路线论文 作者 王景

图二

下面仅列出几条用MATLAB编程得到的近似最佳送货路线及总路线长度：

编总路线 送货路线 号 长度（米） I O/51→26→21→17→14→16 →23→32→38→36→43→42 →49 54709 →45→40→34→39→27→31 →24→13→18→O/51 II O/51→18→13→24 →31→ 34→40→45→42→49→43→38→32→2354996 →16→14→17→21→36→39→27→26→O/51 O/51→21→17→14→16→23→32→36→38→43→42→49 →45→40 →34→31→39→27→18→13 →24→26→O/51 O/51→18→ 13→24→31 →34→40→ 45→49→42 →43→38→36 57914 →27→39→26→14→16→23→32→17→21→O/51 55773 III IV 结果：选择总路线长度最短的送货路线，即 第I条送货路线（图二）

O/51→26→21→17→14→16→23→32→38→36→43→42→49

→45→40→34→39→27→31 →24→13→18→O/51

2010年西北工业大学“工大正禾杯”送货路线论文 作者 王景

33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 1.63 1.23 1.41 0.54 0.70 0.76 2.14 1.07 1.37 2.39 0.99 1.66 0.45 2.04 1.95 2.12 3.87 2.01 1.38 0.39 1.66 1.24 2.41 1.26 0.42 1.72 1.34 0.06 0.60 2.19 1.89 1.81 1.00 1.24 2.51 2.04 1.07 0.49 0.51 1.38 1.31 1.26 0.98 0.0483 0.0006 0.0387 0.0067 0.0129 0.0346 0.0087 0.0124 0.0510 0.0428 0.0048 0.0491 0.0209 0.0098 0.0324 0.0554 0.0262 0.0324 0.0419 0.0001 0.0502 0.0534 0.0012 0.0059 0.0224 0.0580 0.0372 0.0402 0.0274 0.0503 0.0494 0.0325 0.0055 0.0177 0.0361 0.0110 0.0440 0.0329 0.0094 0.0455 0.0121 0.0005 0.0413 2010年西北工业大学“工大正禾杯”送货路线论文 作者 王景

76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

46 47 48 49 50 25 46 32 23 20 25 19 41 46 37 32 33 36 38 17 11 15 12 10 7 1.35 2.12 0.54 1.01 1.12 0.79 2.12 2.77 2.29 0.21 1.29 1.12 0.90 2.38 1.42 1.01 2.51 1.17 1.82 0.33 0.30 4.43 0.24 1.38 1.98 0.0241 0.0230 0.0542 0.0566 0.0284 0.0011 0.0492 0.0034 0.0054 0.0490 0.0088 0.0249 0.0038 0.0434 0.0020 0.0300 0.0133 0.0020 0.0308 0.0345 0.0172 0.0536 0.0056 0.0175 0.0493 表2 50个位置点的坐标 位置点 1 2 3 4 5 6 7 8 9 10 11 12 13 14 X坐标(米) 9185 1445 7270 3735 2620 10080 10025 7160 13845 11935 7850 6585 7630 13405 Y坐标(米) 500 560 570 670 995 1435 2280 2525 2680 3050 3545 4185 5200 5325 2010年西北工业大学“工大正禾杯”送货路线论文 作者 王景

15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 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 表3 相互到达信息 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 序号 1 2 3 4 位置点1 1 1 2 2 位置点2 3 8 20 4 2010年西北工业大学“工大正禾杯”送货路线论文 作者 王景

5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 3 3 4 5 5 6 7 7 8 9 9 10 10 11 12 12 12 13 13 13 14 14 14 14 15 15 16 17 18 19 20 21 21 21 22 23 24 25 25 25 27 28 29 8 4 2 15 2 1 18 1 12 14 10 18 7 12 13 25 15 18 19 11 18 16 17 21 22 25 23 23 31 24 22 26 36 17 30 17 31 41 19 29 31 33 22 2010年西北工业大学“工大正禾杯”送货路线论文 作者 王景

48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 30 30 31 31 32 32 33 33 34 35 36 36 37 38 39 40 40 41 41 41 42 42 43 44 44 45 45 46 47 48 49 49 50 O O O 28 41 26 34 35 23 46 28 40 38 45 27 40 36 27 34 45 44 37 46 43 49 38 48 50 50 42 48 40 44 50 42 40 18 21 26 2010年西北工业大学“工大正禾杯”送货路线论文 作者 王景

本文来源：https://www.bwwdw.com/article/iqqd.html