《《数学建模论文送货路线设计问题》》由会员分享，可在线阅读，更多相关《《数学建模论文送货路线设计问题》（17页珍藏版）》请在金锄头文库上搜索。
1、装 订 线送货路线设计问题摘 要本题为路线是赋权无向图的送货路线设计问题，针对本题约束条件逐步复杂的特点，我们为了使送货员找到最短送货路径，建立了优化旅行商（TSP）模型，拉格朗日松弛法模型以及水灾巡视模型。问题一中，通过分析，我们建立了优化TSP模型，其主要目标是使送货员在没有时间限制的条件下找到走遍所有指定点的最短路线。利用Floyed算法，通过Lingo程序我们能够得出:O181319243127392731344045424942433836383532231614172126O即为所求的距离最短的路径，且最短路径为。问题二中，我们建立了拉格朗日松弛法模型，其主要目标是在每个地点的送货
2、时间都有限制的条件下，找到走遍所有指定点的最短路线。此模型在前一模型的基础上，增加了约束条件，利用“松弛”的思想，在第一个问题的基础上，经过计算得出：O1813192431344045424942433835322316141721263127392736即为所求路径。问题三中，由于新增加了很多地点，送货员已经不可能一次携带所有货物，通过分析我们建立了水灾巡视模型。考虑到与O点直接连通的有18,21,26这3个点且送货员最少取货次数为3次，我们将所有点分为3组，利用问题一的算法，分别找出各组的最短路径，然后根据货物重量及体积的限制，对所求数据进行合理修正，即将重量或体积超出要求路线，对位置点进
3、行合理的删减，从而得出最合理路径为:O18131112155243816171091416231721O263124192529222022302833464844413740343126O2117233235384342495040474045362739273126O，其总长为。送货路线设计问题关键字：旅行商问题（TSP） 拉格朗日松弛法 赋权无向图 Floyed算法 水灾巡视路径一 问题背景现今社会,网络越来越普及，作为一种省钱又很大程度上可以节省时间的消费方式，网上购物越来越受到人们的青睐。由此产生的问题是，怎样能让一个送货员沿着连通路线尽快地将货物送到城市中多个离散的地点，并且其货物
4、重量和体积不超过最大承受范围。只有这样才能最大程度地满足消费者的需要，并且不会过多地增加物流公司的开销。二 问题的重述随着网络的逐渐普及，越来越多的人喜欢在网上购物，物流行业也随之兴盛，为了以最快的速度及时将货物送达，合理地规划送货路线就必不可少了。最短路径问题需要遵循的原则是，送货员速度一定且货物体积和重量都不超过送货员承受范围，当然，各个地点间的连通情况也有一定的限制，将货物送往指定地点的路线最优化或者较优化。我们对这个问题进行分析可以得到，130号货物的重量和体积的总和小于送货员的最大载重和货物的最大体积，所以第一个问题和第二个问题得到了简化，即送货员可以一次携带这30件物品。由此得到，
5、我们需要解决的问题是：1、 如何寻找到一条路线，使得送货员可以到达130号货物所需到达的地点，并且路线总长最短。2、 如何寻找到一条路线，使得送货员在规定时间之前将130号货物送到指定地点，并且路线总长最短。3、 如何寻找到一天路线，使得送货员将100件货物全部送到指定地点，并且路线总长最短。 三 基本假设1、 假设天气晴好，送货员在送货途中没有遇到堵车，可以按照平均速度24公里/小时行驶。2、 假设接交货物正常， 全部都可以在三分钟之内完成。 3、 根据道路有限原则，只有在附录1中给出连通信息的两点间，才能有路径通行，否则必须通过折线路径到达。4、 假设送货员在可连通的两点间都走直线，并且熟
6、悉各地点间的连通情况。5、 假设送货员在O点装载货物的时间可以忽略不计。四 符号说明符号 含义G 赋权无向图V 顶点集E 边集i,j 无向图顶点集中任意两点 i,j两点间的距离Z 走遍指定点的总距离Z* 在有时间限制的情况下，走遍 所有指定点的距离Min Z 走遍所有指定点的最短路径S 对所有V的子集 走完i,j两点所用时间T 走遍所有指定点所用的总时间Min t 走遍所有指定点所用的最短时间 五 模型的建立与求解问题一： 这是一个优化旅行商（TSP）模型。第一步：为了利用题中所给的坐标信息求出可连通点间的距离，我们编写了简单的C程序，计算出了具体数据。为了求出出发点到所有指定点的总路径的最小
7、值，我们进行了如下操作：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
8、中所含图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
9、.901000001000001000001000001000001097.901000001000001000001000001000001000001287.401000001000001000001000001000001000001000001017.101000001000001000001000001000001000001000001000001325.701000001000001000001000001000001000001000001000001000003758.501000001000001000001000001000001000001000001000001000
10、0010000010000001000001000001000001000001000001000001000001000001000001000001494.12152.501000001000001000001000004154.61000001000004997.61000001000002735.4236610000001000001000001000001000001000001000001000001000001000001000001000001000001000002601.901000002324.710000010000010000010000010000010000010
11、000010000010000010000010000010000010000001000001000001000001000001000001000001000001000001000001000001000001000001000001000002090.11630.8010000010000010000010000010000010000010000010000010000010000010000049871000001000001000001000003043.50;ENDDATAMIN=SUM(link:d*s);SUM(city(j)|j#GT#1:s(j,1)=2;FOR(cit
12、y(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，并且容易计算出，该路线总长为 m 。具体路径图如下：（标两个箭头的路径为需往返的
