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

装 订 线 送货路线设计问题 摘 要 本题为路线是赋权无向图的送货路线设计问题，针对本题约束条件逐步复杂的特点，我们为了使送货员找到最短送货路径，建立了优化旅行商（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即为所求的距离最短的路径，且最短路径为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点直接连通的有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—50—40—47—40—45—36—27—39—27—31—26—O，其总长为.57m。 送货路线设计问题 关键字：旅行商问题（TSP）i,j 无向图顶点集中任意两点 i,j两点间的距离 Z 走遍指定点的总距离 Z* 在有时间限制的情况下，走遍 所有指定点的距离 Min Z 走遍所有指定点的最短路径 S 对所有V的子集 走完i,j两点所用时间 T 走遍所有指定点所用的总时间 Min t 走遍所有指定点所用的最短时间 五 模型的建立与求解 问题一： 这是一个优化旅行商（TSP）模型。 第一步：为了利用题中所给的坐标信息求出可连通点间的距离，我们编写了简单的C程序，计算出了具体数据。 为了求出出发点到所有指定点的总路径的最小值，我们进行了如下操作： 设计一个50*50的矩阵M=，表示序号为i的点与序号为j的点之间的距离，若题中两点间存在路径，则直接取值；若不存在路径（即无法直接到达），则；若两点为同一点即i=j，则。在此问中只涉及22个点，鉴于此，我们截取其中所需点的距离，生成一个22*22的矩阵M。 我们运用线性规划的思想，通过优化TSP算法，令Z=∑ * ，其中 当边（i,j）在最优路线上时， =1， 其他情况时， =0， 则 TSP的数学模型可写成如下的线性规划模型： Min Z= * S.T. xij=1, i∈V xij=1, j∈V ≤|S|-1 对所有子集S x, y ∈{0,1} 这里, |S|为集合S 中所含图G 的顶点个数1 前两个约束意味着对每个顶点而言, 仅有一条边进和一条边出, 后一约束则保证了没有任何子回路解的