运筹学大作业.pdf

: .
武汉市旅游景点路线的设计
根据对第一方面问题的分析可知，问题目的在于当时间（费用）
不限的情况下求游完所有景点并回到出发地点所用的费用（时间）
的最小值。该问题属于旅行商问题。为了建立数学模型，首先应
该将各个景点转化为纯数学形式的点线的集合，进行图论方面的
分析。下面给出旅行商问题的定义：
旅行商问题：一位销售商从N个城市的某个城市出发，不重复的走
完其余N-1个城市并回到原出发点，在所有可能路径中求出路径长
度最短的一条。用数学语言描述TSP，即给定一组N个城市和它们
两两之间的直达距离，寻找一条闭合的旅程，使得每个城市刚好
经过一次且总的旅行距离最短。用图语言描述TSP：给出一个图G=
（V，E），每边上有非负权值w（e）， 寻找G的Hamilton圈C，
使得C的总权最小。TSP问题是一个典型的组合优化问题，其可能
的搜索路径随着城市数目N的增加呈指数增长，属于NP完全问题。
了解了以上只是后，我们更加确定了该问题就是旅行商问题。只
是在实际的处理中，我们把两景点的最省路费（最短时间）最为
赋权值w（e），在一定程度上，各景点间的距离与两点间的单程
最省路费（单程最短时间）是成正比的，所以把两景点的最省路
（最短时间）作为权值w（e）是可行的。
第二方面
这一方面要解决的问题是在费用（时间）有限制或两者都有限制
的情况的情况下观赏的景点近可能多，根据这种要求可从以下方
案入手：
建立多目标规划模型，通过适当的拟合或线性加权，把多目标转
化为单目标 : .
武汉市旅游景点路线的设计
————最短路问题研究
091300716 杜雨珊
091300717 黄湘婕
091300718 夏王钰
091300719 贾梦菲 : .
武汉市旅游景点路线的设计
————最短路问题研究
091300716 杜雨珊
091300717 黄湘婕
091300718 夏王钰
091300719 贾梦菲 : .
摘要
旅游线路设计是旅游规划设计的一部分，当今旅游线路设计的成
果研究还比较少，大部分重实际，轻理论。对于一个旅游者而言，
对旅游路线的期望是最大化的满足其消费需要，即时间最短，成
本最小，。我们着重围绕运筹学在旅游线路规划中的运用来发掘