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

《数学建模论文-送货路线设计问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、装订线送货路线设计问题摘要本题为路线是赋权无向图的送货路线设计问题，针对本题约束条件逐步复杂的特点，我们为了使送货员找到最短送货路径，建立了优化旅行商（TSP）模型，拉格朗日松弛法模型以及水灾巡视模型。问题一中，通过分析，我们建立了优化TSP模型，其主要目标是使送货员在没有时间限制的条件下找到走遍所有指定点的最短路线。利用Floyed算法，通过Lingo程序我们能够得出:O—18—13—19—24—31—27—39—27—31—34—40—45—42—49—42—43—38—36—38—35—32—23—16—14—17—21—26—O即为所求的

2、距离最短的路径，且最短路径为53709.96m。问题二中，我们建立了拉格朗日松弛法模型，其主要目标是在每个地点的送货时间都有限制的条件下，找到走遍所有指定点的最短路线。此模型在前一模型的基础上，增加了约束条件，利用“松弛”的思想，在第一个问题的基础上，经过计算得出：O—18—13—19—24—31—34—40—45—42—49—42—43—38—35—32—23—16—14—17—21—26—31—27—39—27—36即为所求路径。问题三中，由于新增加了很多地点，送货员已经不可能一次携带所有货物，通过分析我们建立了水灾巡视模型。考虑到与O点直接

3、连通的有18,21,26这3个点且送货员最少取货次数为3次，我们将所有点分为3组，利用问题一的算法，分别找出各组的最短路径，然后根据货物重量及体积的限制，对所求数据进行合理修正，即将重量或体积超出要求路线，对位置点进行合理的删减，从而得出最合理路径为:O—18—13—11—12—15—5—2—4—3—8—1—6—1—7—10—9—14—16—23—17—21—O—26—31—24—19—25—29—22—20—22—30—28—33—46—48—44—41—37—40—34—31—26—O—21—17—23—32—35—38—43—42—49—5

4、0—40—47—40—45—36—27—39—27—31—26—O，其总长为135647.57m。送货路线设计问题关键字：旅行商问题（TSP）拉格朗日松弛法赋权无向图Floyed算法水灾巡视路径一问题背景现今社会,网络越来越普及，作为一种省钱又很大程度上可以节省时间的消费方式，网上购物越来越受到人们的青睐。由此产生的问题是，怎样能让一个送货员沿着连通路线尽快地将货物送到城市中多个离散的地点，并且其货物重量和体积不超过最大承受范围。只有这样才能最大程度地满足消费者的需要，并且不会过多地增加物流公司的开销。二问题的重述随着网络的逐渐普及，越来越多的人

5、喜欢在网上购物，物流行业也随之兴盛，为了以最快的速度及时将货物送达，合理地规划送货路线就必不可少了。最短路径问题需要遵循的原则是，送货员速度一定且货物体积和重量都不超过送货员承受范围，当然，各个地点间的连通情况也有一定的限制，将货物送往指定地点的路线最优化或者较优化。我们对这个问题进行分析可以得到，1～30号货物的重量和体积的总和小于送货员的最大载重和货物的最大体积，所以第一个问题和第二个问题得到了简化，即送货员可以一次携带这30件物品。由此得到，我们需要解决的问题是：1、如何寻找到一条路线，使得送货员可以到达1～30号货物所需到达的地点，并且路

6、线总长最短。2、如何寻找到一条路线，使得送货员在规定时间之前将1～30号货物送到指定地点，并且路线总长最短。3、如何寻找到一天路线，使得送货员将100件货物全部送到指定地点，并且路线总长最短。三基本假设1、假设天气晴好，送货员在送货途中没有遇到堵车，可以按照平均速度24公里/小时行驶。2、假设接交货物正常，全部都可以在三分钟之内完成。3、根据道路有限原则，只有在附录1中给出连通信息的两点间，才能有路径通行，否则必须通过折线路径到达。1、假设送货员在可连通的两点间都走直线，并且熟悉各地点间的连通情况。2、假设送货员在O点装载货物的时间可以忽略不计。

7、四符号说明符号含义G赋权无向图V顶点集E边集i,j无向图顶点集中任意两点i,j两点间的距离Z走遍指定点的总距离Z*在有时间限制的情况下，走遍所有指定点的距离MinZ走遍所有指定点的最短路径S对所有V的子集走完i,j两点所用时间T走遍所有指定点所用的总时间Mint走遍所有指定点所用的最短时间五模型的建立与求解问题一：这是一个优化旅行商（TSP）模型。第一步：为了利用题中所给的坐标信息求出可连通点间的距离，我们编写了简单的C程序，计算出了具体数据。为了求出出发点到所有指定点的总路径的最小值，我们进行了如下操作：1、设计一个50*50的矩阵M=，表示序

8、号为i的点与序号为j的点之间的距离，若题中两点间存在路径，则直接取值；若不存在路径（即无法直接到达），则；若两点为同一点即i=j，则。在