数学建模送货路线设计问题文档格式.docx

1、1.将仓库视为第51个点，参与计算。2.送货员在路上无特殊情况，不会因抛锚等现象而耽误时间；3.同一地点要送多件货物，那么这些物品在同一次中运送；4.要求到达的时间不包括此次在该点交接的时间；5.送货员只沿着已知的路线行走；6.道路是双向的，无单向路线；7.送货员取货的时间不计。三、符号说明1问中涉及到的符号a各货物号信息（货物号、运送地点、重量、体积和最晚时间）矩阵b 50个位置点的坐标矩阵c互通点信息矩阵d任意两相通两点间距离e对应两相通两点间距离e1对e进行去重后得到的矩阵f带权邻接矩阵D任意两点间最小距离矩阵u初始H圈mzong货物的总质量vzong货物的总体积luxian最短路线lu

2、cheng最小路程t1最短时间t货物交接时所需时间（3分钟）v送货员的行驶速度（24千米每小时）2问中涉及到的符号luxian2最短路线lucheng2最小路程t2最短时间3问中涉及到的符号luxian3最短路线lucheng3最小路程t3最短时间D3分组矩阵 四、问题的分析与模型的建立将快递网图中，每个投递点看作图中的一个节点，各投点之间的公路看作图中对应节点间的边，各条路的长度（或行驶时间）看作对应边上的权，所给快递网就转化为加权网络图，问题就转化为在给定的加权网络图中寻找从给定点0出发，行遍所有顶点至少一次再回到O点，使得总权（路程或时间）最小，此即最佳推销员回路问题。1）问题一是需将3

3、0个货物送达21个固定点并返回，O点和另外21个点构成了一个典型的最短路问题。即先利用Floyd计算两点间的最短距离，再随机构造哈密顿圈，利用优化算法对此H圈优化，使H圈的权最小。2）问题二本小问是在一问的基础上加入时间的限制，解题思想是以第一问的过程为基础，从随机产生的H圈中选出符合时间要求的多条路线，再从中学出事的路程权重最小的路线。并检验其是否符合时间的要求。3）问题三主要是对路线的分组,分组后检验，调整使得每组货物质量小于50kg，体积小于1m3，然后利用问题一，解出每组的最佳H圈。五、模型的分析与求解1.5.1 由附录1给定的数据知，前30号货物由于货物的总质量mzong和总体积vz

4、ong 分别为48.5和0.88均未超出最大限度50和1，显然送货员能够一次带上所有货物到达各送货点，且货物要送达总共为21个，如下：13,14,16,17,18,21,23,24,26,27,31,32,34,36,38,39,40,42,43,45,49本模型运用图论中Floyd算法与最佳圈中的相关结论，建立了关于该类问题的优化模型，将出发点O和21个送货点结合起来构造完备加权图。用矩阵翻转来实现二边逐次修正，求最佳哈密尔顿圈（H圈）。由完备加权图,确定初始H圈,列出该初始H圈加点序边框的距离矩阵,然后用二边逐次修正法对矩阵进行“翻转”,就可得到近似最优解的距离矩阵,从而确定近似最佳H圈。

5、由于用矩阵翻转方法来实现二边逐次修正法的结果与初始圈有关，故为了的到得到较优的计算结果，在用MATLAB编程时，随机搜索出200个初始H圈。在所有H圈中，找出权最小的一个，即要找的最佳H圈的近似解。最佳H圈的近似解 minH0，H1，H2,H99 送货路线：送货时间： lucheng =5.4707e+004米 t=lucheng/24000+3*21/60=3.3295小时1.5.2本小问是在一问的基础上加入时间的限制，解题思想是以第一问的过程为基础，从随机产生的H圈中选出符合时间要求的多条路线，即选择符合每个点时间要求的最佳H圈。为了更有针对性，可将一问的最佳路线作为初始的H圈进行计算。得

6、到结果，如下：lucheng2= 5.4707e+004 t2=lucheng2/24000+3*21/60= 3.3295小时1.5.3现根据距离分组，在调整，然后求解。51号到各个地点的最小距离如下： 1 2 3 4 5 6 7 8 9 10 10068 16296 10467 14004 16563 11362 8100 8509 7775 8092 11 12 13 14 15 16 17 18 19 20 6965 6752 5295 5094 11558 7493 3621 2182 6968 13417 21 22 23 24 25 26 27 28 29 30 1797 119

7、18 5395 4709 8934 1392 3997 14223 10820 13205 31 32 33 34 35 36 37 38 39 40 2929 6707 15549 5254 7624 4677 8975 6214 5777 6885 41 42 43 44 45 46 47 48 49 50 11577 9751 8833 13943 7860 14312 9216 15806 11722 9928026312739273645404740504942433835322317210； 02631344037414448463328302220222925192431260；

8、 021172316149107161834251512111318110。计算三个区域各自送货员走的总路程:1 42173.27m 2 39894.58m 3 51440.73m 计算时间:（51440.73+39905.76+42173.27）/24000+3/60*100=10.563小时六、模型的不足及改进的方向不足：由于数据量大，且最佳H圈与原始圈的选取有关，只能去近似最佳圈，因此对于第二问随机性很强，只能多设置一下循环次数，以求精确。第三问的手动画图、分组比较麻烦，要尝试多次才能找出符合要求的点。参考文献【1】赵静、但琦，数学建模与数学实验（第3版）高等教育出版社【2】姜启源、谢金

9、星、叶俊，数学模型，北京：高等教育出版社，2003相关程序数据图1 快递公司送货地点示意图表1 各货物号信息表货物号送达地点重量（公斤）体积（立方米）不超过时间1132.500.03169：002180.500.03543311.180.0240304261.560.035012：5212.150.03056141.720.01007171.380.01098231.400.04269320.700.048110381.330.021910：1511451.100.028712430.950.0228392.560.05952.280.0301422.850.0190161.700.07820

10、.250.0412361.790.018419272.450.044520242.930.04200.800.0108222.250.00181.570.0210342.800.010325401.140.01550.680.0382491.350.0144280.520.0020292.910.04871.200.04291.260.02501.150.0501331.630.04831.230.0006351.410.03870.540.0067370.01290.760.03462.140.00871.070.0124411.370.05102.390.04280.990.0048441

11、.660.04910.450.0209462.040.0098471.950.0324482.120.05543.870.0262502.01510.0419520.390.0001530.0502541.240.0534552.410.0012560.0059570.420.0224580.0580591.340.0372600.060.0402610.600.0274622.190.0503631.890.0494641.810.0325651.000.0055660.0177672.510.0361680.0110690.0440700.490.0329710.510.0094720.0

12、455731.310.0121740.0005750.980.0413760.0241770.0230780.0542791.010.0566801.120.0284810.790.0011820.0492832.770.0034842.290.0054850.210.0490861.290.0088870.0249880.900.0038892.380.0434901.42910.0300920.0133931.17941.820.0308950.330.0345960.300.0172974.430.0536980.240.0056990.01751001.980.0493表2 50个位置

13、点的坐标位置点X坐标（米）Y坐标（米）91855001445560727057037356702620995100801435100252280716025251384526801193530507850354565854185763052001340553252125597515365704514165738588258075585581657808355127708560220088351476590557790933044359525108609635103851050056597652580986515659955939510100148351036512501090072801106

14、5153051137512390114156410115101391511610951012050834512300493013650132651414514180142153030150601091514235233014500773514550885148801157515160801015325表3 相互到达信息序号位置点1位置点2O程序问题一的程序1.%作图，标号，标距离clc;a = %货物信息数据1 13.0000 2.5000 0.0316 9.0000 2 18.0000 0.5000 0.0354 9.0000 3 31.0000 1.1800 0.0240 9.3000 4

15、 26.0000 1.5600 0.0350 12.0000 5 21.0000 2.1500 0.0305 12.0000 6 14.0000 1.7200 0.0100 12.00007 17.0000 1.3800 0.0109 12.00008 23.0000 1.4000 0.0426 12.00009 32.0000 0.7000 0.0481 12.000010 38.0000 1.3300 0.0219 10.150011 45.0000 1.1000 0.0287 9.300012 43.0000 0.9500 0.0228 10.150013 39.0000 2.5600

16、0.0595 12.000014 45.0000 2.2800 0.0301 9.300015 42.0000 2.8500 0.0190 10.150016 43.0000 1.7000 0.0782 10.150017 32.0000 0.2500 0.0412 12.000018 36.0000 1.7900 0.0184 12.000019 27.0000 2.4500 0.0445 12.000020 24.0000 2.9300 0.0420 9.000021 31.0000 0.8000 0.0108 9.300022 27.0000 2.2500 0.0018 12.000023 26.0000 1.5700 0.0210 12.000024