文档介绍：2015年全国研究生数学建模竞赛F题
旅游路线规划问题
张娜 1506102058 蒋毛宁 1506102079 朱亮 15061020xx
摘要：本文针对最优旅游路线规划的数学建模问题，以TSP旅商问题的研究现状为出发点， 根据给定总费用
n表示浏览的景点数目；
问题一的解答
、模型的基本假设
对于所研究问题的时间窗和约束条件，本文作如下几点假设和限定：(1)考虑到任意两地
间的理想化交通路线为直线，因此以景点之间的经纬度坐标作为计算距离的标准。
把每个省会看作一个景点数据，对应的游览时间为一天。
在同一市区内的景点，，只取一个作为建模数据。在模
型求解过程中再加入时间窗。
以15天作为每一次出行的花费时间，其中包括从西安出发以及返回西安的路线。
以百度地图查询所得的两地之间车程作为模型参考。(6)行车时间2天及以上的，
对路途中间的住宿予以忽略。
(7)不考虑堵车、抛锚、交通意外以及其他弱相干因素对建模的影响。
问题1要求建立旅游路线的模型，对西安的一名自驾游爱好者规划一份201家5A级景区的 游览路线。这是一个典型的组合优化问题，也可以看作是一个带有时间窗的类似TSP的问 题。由于TSP问题已被证明具有NPC计算复杂性，有很大的难度，因此对TSP的求解算法 大多是寻求近似最游解，例如在文献
LU-LIO］中，学者研究的热点集中在遗传算法、神经网络算法、模拟退火算法、贪婪算法以 及图论相关算法等。
本文根据现有文献的研究成果以及检索得到的有关数据，从实际情况出发，采用改良圈算法, 对最优路径问题进行了仿真研究。
寻找最优路径，首先要获取所有数据两两之间的距离。由于景点较多，如果每两个景点之间 的距离都按照实际路况来算，有大约数万个数据，不便于处理。因此对条件适当简化。考虑 到两景点之间的距离，一般情况下，直线距离短的话，相对应的实际路程也比较短，即景点 之间的路程可以用直线距离来代替实际路程进行分析比较。题目限定的车速为公路40和高 速80,与现实生活中的行车速度相差不大。因此在建立模型的时候，取两景点之间的经纬 度为坐标，查阅资料可知根据经纬度求两地距离的公式为：
sin()*sin()*cos()cos()*cos()CLatALatBLonALonBLatALatB
tan*cos() */180DisceRArcCpi
其中R为地球半径，,latA和lonA分别是经度和纬度坐标值(角度),Distance 的单位为公里。
现实情况中有多个景点在同一城市的情况，二者距离较短，车程往往在半个小时到一个小时 之间，对其他游览计划影响不大，若一起求解，既不符合实际情况，又增加了模型的复杂程 度，因此将其归为一个数据点进行计算。
将旅游景点看作图中的定点，各个景点之间的交通路线看作顶点之间的边，边上的权重代表 从一个景点到另一个景点的距离，这就是图论的基本思想。图论中的Dijkstra算法和Floyd 算法是最常用的两种求旅游最优路线的问题，而本题要求是设计一个周游型线路优化方案， 即从某地出发，不重复地游览完所有景点，然后回到出发地，行程一个闭合的环形的旅游路 线。问题的特殊之处在于起点与中点重合，中间各景点不重复游览。
结