数学建模论文-送货路线设计问题.doc

装 订 线送货路线设计问题摘 要本题为路线是赋权无向图的送货路线设计问题，针对本题约束条件逐步复杂的特点，我们为了使送货员找到最短送货路径，建立了优化旅行商（TSP）模型，拉格朗日松弛法模型以及水灾巡视模型。问题一中，通过分析，我们建立了优化TSP模型，其主要目标是使送货员在没有时间限制的条件下找到走遍所有指定点的最短路线。利用Floyed算法，通过Lingo程序我们能够得出:O181319243127392731344045424942433836383532231614172126O即为所求的距离最短的路径，且最短路径为53709.96m。问题二中，我们建立了拉格朗日松弛法模型，其主要目标是在每个地点的送货时间都有限制的条件下，找到走遍所有指定点的最短路线。此模型在前一模型的基础上，增加了约束条件，利用“松弛”的思想，在第一个问题的基础上，经过计算得出：O1813192431344045424942433835322316141721263127392736即为所求路径。问题三中，由于新增加了很多地点，送货员已经不可能一次携带所有货物，通过分析我们建立了水灾巡视模型。考虑到与O点直接连通的有18,21,26这3个点且送货员最少取货次数为3次，我们将所有点分为3组，利用问题一的算法，分别找出各组的最短路径，然后根据货物重量及体积的限制，对所求数据进行合理修正，即将重量或体积超出要求路线，对位置点进行合理的删减，从而得出最合理路径为:O18131112155243816171091416231721O263124192529222022302833464844413740343126O2117233235384342495040474045362739273126O，其总长为135647.57m。送货路线设计问题关键字：旅行商问题（TSP） 拉格朗日松弛法 赋权无向图 Floyed算法 水灾巡视路径一 问题背景现今社会,网络越来越普及，作为一种省钱又很大程度上可以节省时间的消费方式，网上购物越来越受到人们的青睐。由此产生的问题是，怎样能让一个送货员沿着连通路线尽快地将货物送到城市中多个离散的地点，并且其货物重量和体积不超过最大承受范围。只有这样才能最大程度地满足消费者的需要，并且不会过多地增加物流公司的开销。二 问题的重述随着网络的逐渐普及，越来越多的人喜欢在网上购物，物流行业也随之兴盛，为了以最快的速度及时将货物送达，合理地规划送货路线就必不可少了。最短路径问题需要遵循的原则是，送货员速度一定且货物体积和重量都不超过送货员承受范围，当然，各个地点间的连通情况也有一定的限制，将货物送往指定地点的路线最优化或者较优化。我们对这个问题进行分析可以得到，130号货物的重量和体积的总和小于送货员的最大载重和货物的最大体积，所以第一个问题和第二个问题得到了简化，即送货员可以一次携带这30件物品。由此得到，我们需要解决的问题是：1、 如何寻找到一条路线，使得送货员可以到达130号货物所需到达的地点，并且路线总长最短。2、 如何寻找到一条路线，使得送货员在规定时间之前将130号货物送到指定地点，并且路线总长最短。3、 如何寻找到一天路线，使得送货员将100件货物全部送到指定地点，并且路线总长最短。 三 基本假设1、 假设天气晴好，送货员在送货途中没有遇到堵车，可以按照平均速度24公里/小时行驶。2、 假设接交货物正常， 全部都可以在三分钟之内完成。 3、 根据道路有限原则，只有在附录1中给出连通信息的两点间，才能有路径通行，否则必须通过折线路径到达。4、 假设送货员在可连通的两点间都走直线，并且熟悉各地点间的连通情况。5、 假设送货员在O点装载货物的时间可以忽略不计。四 符号说明符号 含义G 赋权无向图V 顶点集E 边集i,j 无向图顶点集中任意两点 i,j两点间的距离Z 走遍指定点的总距离Z* 在有时间限制的情况下，走遍 所有指定点的距离Min Z 走遍所有指定点的最短路径S 对所有V的子集 走完i,j两点所用时间T 走遍所有指定点所用的总时间Min t 走遍所有指定点所用的最短时间 五 模型的建立与求解问题一： 这是一个优化旅行商（TSP）模型。第一步：为了利用题中所给的坐标信息求出可连通点间的距离，我们编写了简单的C程序，计算出了具体数据。为了求出出发点到所有指定点的总路径的最小值，我们进行了如下操作：1、 设计一个50*50的矩阵M=，表示序号为i的点与序号为j的点之间的距离，若题中两点间存在路径，则直接取值；若不存在路径（即无法直接到达），则；若两点为同一点即i=j，则。在此问中只涉及22个点，鉴于此，我们截取其中所需点的距离，生成一个22*22的矩阵M。2、 我们运用线性规划的思想，通过优化TSP算法，令Z= * ，其中 当边（i,j）在最优路线上时， =1，其他情况时， =0， 则 TSP的数学模型可写成如下的线性规划模型： Min Z= * S.T. xij=1, iV xij=1, jV |S|-1 对所有子集S x, y 0,1 这里, |S|为集合S 中所含图G 的顶点个数1 前两个约束意味着对每个顶点而言, 仅有一条边进和一条边出, 后一约束则保证了没有任何子回路解的产生1 于是, 满足上述约束的解构成了一条Ham ilton 回路。存在路径的两点间距离表见附录1。Lingo程序的核心程序如下：!TSP question; MODEL: SETS: city/1.18/; link(city,city)|&1#GE#&2:d,s; ENDSETSDATA:d=0153701000001780.101000001000002258.301000001000001000001966.201000001000001000001000001885.901000001000001000001000001000001097.901000001000001000001000001000001000001287.401000001000001000001000001000001000001000001017.101000001000001000001000001000001000001000001000001325.701000001000001000001000001000001000001000001000001000003758.5010000010000010000010000010000010000010000010000010000010000010000001000001000001000001000001000001000001000001000001000001000001494.12152.501000001000001000001000004154.61000001000004997.61000001000002735.4236610000001000001000001000001000001000001000001000001000001000001000001000001000001000002601.901000002324.710000010000010000010000010000010000010000010000010000010000010000010000010000001000001000001000001000001000001000001000001000001000001000001000001000001000001000002090.11630.8010000010000010000010000010000010000010000010000010000010000010000049871000001000001000001000003043.50;ENDDATAMIN=SUM(link:d*s);SUM(city(j)|j#GT#1:s(j,1)=2;FOR(city(i)|i#GT#1:SUM(city(j)|j#GT#i:s(j,i)+SUM(city(k)|k#LT#i:s(i,k)=2);FOR(link:BIN(s);3、结果 通过lingo计算，我们容易得出，所求的距离最短的路线为：O1813192431-27313440454243383532231614172126O，由于点39、49、36单连通边界点，在lingo程序计算中已被人为去掉，现将这几个点加入路径中，有：O1813192431-27392731344045424942433836383532231614172126O，并且容易计算出，该路线总长为53709.96 m 。具体路径图如下：（标两个箭头的路径为需往返的路径）问题二：这是一个拉格朗日松弛法的问题。第一步： 1、 经分析知，如果第一问的解能够满足第二问中的复杂约束，那么对这个问题来说，它就是最优解。 在第一个问题的基础上增加了对时间的约束条件： S.T. xij=1, iV xij=1, jV |S|-1 对所有子集S x, y 0,1 - 为了得到第二题答案，我们将“松弛”第二个问题中的复杂约束，即第一个问题，通过计算我们发现问题一中的最优解不符合时间约束条件，通过对第一个问题中与最优解最接近的路径的计算，我们很容易发现路径：O1813192431344045424942433835322316141721263127392736即为所求路径。具体路路径图如下：问题三：这是一个类似水灾巡视问题。第一步：1、 通过与前两问的比较，我们可以发现，该问没有对时间的限制，但是送货员不能一次携带所有货物，经计算可知，至少需取货三次，而且与O点直接连通的点只有18、21、26三个，所以我们易将所有点分为分别以18、21、26为起点的三组路径A、B、C。分组的依据是，若某点与A组的起点18的折线距离最短，则将该点归为A组。但是B组中46、48两点距该组中其他点较远，于是我们将它们归为较近的C组。2、我们将该问分解为三个问题一，于是，利用1中的lingo程序，分别计算出每组中的最短路径，按照1中的算法，把程序中未涉及到的边界点补上。但是经过计算我们可以发现，B、C组中送货员一次需携带的货物的体积和质量都超出范围。通过对上述数据的合理修正，我们将B组中14、16、23、17、21归入A组中，将C组中47、40、50、39归入B组中。从而得到了最优解:O18131112155243816171091416231721O263124192529222022302833464844413740343126O2117233235384342495040474045362739273126O(若路径需重复经过，则第一次经过时卸货)，其总长为135647.57m，送完所有货物所需的总时间为639.12min。具体路径见下图：六 模型优缺点优点：1、本文的基本算法为Floyed算法，可以求出问题一和问题三的较优化解，模型较简单，过程也很清晰，更重要的是，该算法具有一定的灵活性，虽然第二个问题约束条件较复杂，不能直接利用该算法，但只要将其“松弛”，用该算法得到几组较优解，再进行一定的分析比较，即可得到合理的结果。2、该模型的解法充分考虑了题中所给的限制条件，在复杂约束下，求出了最优解。缺点：1、计算过程中，某些点需要人为增减，程序的智能化还有待提高。七 参考文献1、何涛， 王锁萍， 张明 一种基于拉格朗日松弛法的QoS 路由算法 （南京邮电大学 ，江苏 南京 210003）2、朱献文李福荣 求解旅行商问题的几种智能算法 (黄淮学院国际学院驻马店463000)3、伍建华祁文青晏伯武 单汇最短路径问题的一种算法 (黄石高等专科学校计算机与信息工程系,湖北黄石435003)4、马良 旅行推销员问题的算法综述 (上海理工大学, 上海200093)附录1 ：有连通路径点间的距离（往返路径只写一次）附录2 ：各个货物号信表附录3 ：各个位置点的坐标附录4 ：快递公司送货地点示意图附录5：100个包裹的体积及质量整合表附录1 有连通路径点间的距离（往返路径只写一次） 位置点一位置点二距离1 31916.28182683.782207823031242292.64381958.093435360415155004.54521252.94611294.317185917.9711968.258121756.779142681.359101945.5110185909.551072059.3711126297.6012131456.8012255756.5712154805.8013187387.4013193455.7013111669.5614185342.1814162607.6814172195.7214213296.7315222860.9315254235.4016232097.6417231774.5118312103.7019242258.6420221420.0021262190.6021362880.1821171820.9122301287.4823171774.51位置点一位置点二距离24311780.1525414154.5925191966.2125291885.9027311067.7528331325.6929221097.8630281017.8930414997.6231261540.0031342324.7532351114.0032231311.8733463758.5133281325.6934401630.7835381409.7336453182.4636272203.9237402090.0538361537.4239271779.9240341630.7840453217.0041442366.0341372601.9241462375.424243917.6742491971.3843383565.8444482152.5444504986.7845503102.7645422351.7246481494.1347402331.2248442152.5449503568.8250403043.49O182182.03O211796.94O261392.03附录2 （各个货物号信表）货物号送达地点重量(公斤)体积(立方米)不超过时间1132.500.03169：002180.500.03549：003311.180.02409：304261.560.035012：005212.150.030512：006141.720.010012：007171.380.010912：008231.400.042612：009320.700.048112：0010381.330.021910：1511451.100.02879：3012430.950.022810：1513392.560.059512：0014452.280.03019：3015422.850.019010：1516431.700.078210：1517320.250.041212：0018361.790.018412：0019272.450.044512：0020242.930.04209：0021310.800.01089：3022272.250.001812：0023261.570.021012：0024342.800.01039：3025401.140.01559：3026450.680.03829：3027491.350.014410：1528320.520.002012：0029232.910.048712：0030161.200.042912：003111.260.02503221.150.05013331.630.04833441.230.00063551.410.03873660.540.00673770.700.01293880.760.03463992.140.008740101.070.012441111.370.051042122.390.042843130.990.004844141.660.049145150.450.020946162.040.009847171.950.032448182.120.055449193.870.026250202.010.032451211.380.041952220.390.000153231.660.050254241.240.053455252.410.001256261.260.005957270.420.022458281.720.058059291.340.037260300.060.040261310.600.027462322.190.050363331.890.049464341.810.032565351.000.005566361.240.017767372.510.036168382.040.011069391.070.044070400.490.032971410.510.009472421.380.045573431.310.012174441.260.000575450.980.041376461.350.024177472.120.023078480.540.054279491.010.056680501.120.028481250.790.001182462.120.049283322.770.003484232.290.005485200.210.049086251.290.008887191.120.024988410.900.003889462.380.043490371.420.002091321.010.030092332.510.013393361.170.002094381.820.030895170.330.034596110.300.017297154.430.053698120.240.005699101.380.017510071.980.0493 附录3 （各个位置点的坐标）位置点X坐标(米)Y坐标(米)1918550021445560372705704373567052620995610080143571002522808716025259138452680101193530501178503545126585418513763052001413405532515212559751615365704517141657385188825807519585581652078083552112770856022220088352314765905524779093302544359525261086096352710385105002856597652925809865301565995531939510100321483510365331250109003472801106535153051137536123901141537641011510381391511610399510120504083451230041493013650421326514145431418014215443030150604510915142354623301450047773514550488851488049115751516050801015325附录4 （快递公司送货地点示意图）附录5 （100个包裹的体积及质量整合表）送达地点重量(公斤)体积(立方米)11.260.02521.150.050131.630.048341.230.000651.410.038760.540.006772.680.062280.760.034692.140.0087102.450.0299111.670.0682122.630.0484133.490.0364143.380.0591154.880.0745163.240.05271730660.0778182.620.0908194.990.0511202.220.0814213.530.0724送达地点重量(公斤)体积(立方米)220.390.0001238.260.1469244.170.0954254.490.0111264.390.0619275.120.0687281.720.058291.340.0372300.060.0402312.580.0622327.440.175334.40.0627344.610.04283510.0055364.20.0381373.930.0381385.190.0637393.630.1035402.120.0484411.410.0132424.230.0645433.960.1131441.260.0005455.040.1383465.850.1167472.120.023480.540.0542492.360.071501.120.0284