最佳旅游路线.pdf

1 基于模拟退火法的最佳旅游路线 摘要 本文对云南省最佳旅游路线问题进行了建模、求解和相关分析 针对问题一，首先根据旅游城市的个数进行分类，在旅游的城市的个数确定 的情况下， 以旅游费用最小为目标函数， 用枚举法遍历所有情况， 筛选出最优解 发现在旅游的城市个数小于 8 的时候，用 MATLAB 编程能够迅速得出答案；当旅 游的城市个数大于等于 9 的时候运行时间大大增加，此时枚举法已经不再适用 针对问题二，由于旅游时间是两个暑假，说明时间是充足的，在这个基础上 求花钱最少的旅游路线，这是典型的 TSP 问题，因为城市个数已经大于 9 个，本 文分别采用模拟退火法和遗传算法对该问题进行求解 发现在本题中城市的个数 不是很多导致模拟退火法和遗传算法求出来的解是相同的， 这说明都已经求得了 精确解 针对问题三，题中并没有说清楚考察组最多能分几组，在不限制分组的数的 情况下分 15 组，每组去一个地方能达到最快的效果但这和现实不太符合，结 合生活经验，本文讨论了分为 1-5 组的情况下，以花费时间最小为约束条件，同 时考虑各组去的城市数量相差不大， 改进模拟退火法分别算出每个分组花的最大 时间，结果发现随着分组的个数增加，最大调研时间是单调下降的，下降的速度 越来越慢，从图中可以看出，当分组为 3、4 的时候下降速度已经明显减缓，因 此选择分为 3 或者 4 组是最佳的选择。

针对问题四， 在不同城市容量不同的情况下，考虑不同的旅客有长途、和 短途两种不同的需求，为此本文以长途、短途旅行展开分析，以最小的交通费为 目标， 兼顾旅游时间小于 10 天， 给出了长途、 短途的旅行方案供旅客自由选择 2 目录 1 问题重述 3 1.1 问题背景. 3 1.2 需要解决的问题 . 3 2 问题分析. 3 3 模型假设和符号系统 4 3.1 模型假设. 4 3.2 符号系统 4 4 问题一的建模与求解 . 5 4.1 问题一的分析 . 5 4.2 数据的处理 . 5 4.3 模型一的建立 5 4.4 模型一的求解 . 6 4.5 模型一的结果分析 . 7 5 问题二的建模与求解 . 7 5.1 问题二的分析 . 7 5.2 模型二的建立 7 5.3 模型二的求解 . 8 5.4 模型二的结果分析 . 10 5.5 模型三的建立 . 10 5.6 模型三的求解 . 11 5.7 模型二和模型三的对比 12 6 问题三的建模与求解 . 12 6.1 问题三的分析 . 12 6.2 模型四的建立 12 6.3 模型四的求解 . 13 7 问题四的建模与求解 . 16 7.1 问题四的分析 . 16 7.2 模型五的建立 16 7.3 模型五的求解 . 16 8 模型评价 21 9 参考文献 21 10 附录 . 21 3 1 问题重述 1.1 问题背景 云南，即“彩云之南”“七彩云南”，是著名的旅游大省，昆明、大理、丽 江、 香格里拉、 西双版纳， 自然风光迤逦、 文人景观精彩、 少数民族的节日丰富、 时光悠闲，让人一去就想永远留在那里。

王先生夫妇是北京某高校的年轻教师， 打算暑假到云南旅游 1.2 需要解决的问题 （1）请为他们设计合适的旅游路线，使他们在暑假一个月的时间里花最少的钱 游览尽可能多的地方，并估算除吃饭之外的费用 （2）如果他们打算今、明两年暑假完成对云南的旅游，请你为他们设计合适的 旅游线路，使在云南境内的交通费用尽量的节省 （3）如果某高校的少数民族研究所组织对云南文化考察，用于交通的时间和前 两种情况相同，单考察时间是旅游观光时间的四倍，请您们为他们设计合适的考 察路线，为便于尽早完成考察任务，最少需要分几组考察 （4）旅游部门迎接“十一黄金周”（考虑到远途旅游，游程延长为 10 天） ，准 备为云南省外的游客组织多条旅游路线以分散游客，提高接待的质量在假设参 加你们设计的各条路线的游客人数与整条路线的接待能力成比例的条件小， 请你 们为旅游部门设计合适的、准备向游客推介的全部旅游路线 2 问题分析 针对问题一，要求在一个月的时间范围内，以花钱少玩的地方多为目标函 数展开分析，考虑到旅游的城市个数不是很多（当旅游城市大于 9 个的时候时间 超过限制） ，本文采用枚举法，分别多旅游 3、4、5、6、7、8、9 个城市的情况 展开分析，最终得到了最佳旅行路线。

针对问题二，是在时间充足的情况下，求旅费最少的旅游路线，这是典型的 TSP 问题由于旅游城市的增加，用枚举法的话时间是不允许的，本文采用模拟 退火法和遗传算法，经过多次迭代改进能得到该路途的最优解 针对问题三，题中并没有说清楚考察组最多能分几组，在不限制分组的数的 情况下分 15 组，每组去一个地方能达到最快的效果但这和现实不太符合，结 合生活经验，本文讨论了分为 1-5 组的情况下，以花费时间最小为约束条件，同 时考虑各组去的城市数量相差不大，修正模拟退火法算出了旅途 4 针对问题四,在不同城市容量不同的情况下，考虑不同的旅客有长途、和短 途两种不同的需求，为此本文以长途、短途旅行展开分析，以最小的交通费为目 标，兼顾旅游时间小于 10 天，给出了长途、短途的旅行方案供旅客自由选择 3 模型假设和符号系统 3.1 模型假设 （1）游客们所乘坐的旅游大巴平均时速为 80km/h，平均费用为 0.3 元/km； （2）各个城市之间往返的时间相等 （3）假设昆明是起始站，但不要求旅游完以后返回，可以直接回北京 （4）游客们在途中和游览景点的时间为 12 小时，而另外 12 小时为休息、用餐 及其他琐事时间。

（5）一个景点直接到达另外一个景点是指，途中经过的其他地方并不进行游 览； 3.2 符号系统 符号 含义 1 昆明 2 楚雄 3 大理 4 保山 5 丽江 6 曲靖 7 版纳 8 昭通 9 玉溪 10 普洱 11 文山 12 红河 13 迪庆 14 德宏 15 临沧 表 3.2 5 4 问题一的建模与求解 4.1 问题一的分析 问题的要求是花费最少的钱旅游尽量多的景点，根据提供的图形，可以看 出各个景点都是在城市的周边，各个小景点之间的距离不是很远，若用各个小景 点之间的距离做为模型的建立既花费算法的运行时间又没有必要，本文采取 15 个主要城市，在 15 个城市之间进行选择，以花费金钱最少为目标函数，遍历完 所有情况求得最佳旅行方案的精度解 4.2 数据的处理 4.2.1 旅途费的计算 根据提供的云南地图选择主要的 15 个城市如下：昆明、楚雄、大理、保山、丽 江、曲靖、版纳、昭通、玉溪、普洱、文山、红河、迪庆、德宏、临沧交通费 （见附录 1）用各个城市之间的距离乘高速路每公里收费系数，同时考虑到各个 景点都有门票费（见附录 2） ，简单地认为旅游费等于交通费加各个景点的门票 费。

4.2.2 旅途起点的设置 考虑到昆明是云南的省会城市，旅游的人往往会去此处参观，选择此城市 做为北京到云南的终点站 考虑从昆明出发， 旅游几个城市的景点之后返回北京 4.3 模型一的建立 4.3.1 旅游城市的确定 按照上述方法的假设，认为昆明是旅游起点，假设剩下在剩下 14 个城市中 选择 n 个进行旅游，一共就有 14 n C种选择方案，用 MATLAB 自带的 combntns 函数 从 2 到 14 中选择 n 个城市 4.3.2 旅游费的计算 在选定 n 个城市之后，用 MATLAB 自带 perms 函数给 n 个城市全排列，也就 是产生 n n A种不同的解，每个不同的解有对应的交通费，再加上这个 n 个城市的 门票费就成了旅游费 4.3.3 目标函数的设置 每个解都对应一个旅游费，遍历完 14 n A种情况，选择旅游费用最少的那个解 就得到了：旅游 n 个城市费用最少的一组解 6 4.4 模型一的求解 4.4.1 算法的基本流程 参数初始化 产生n个城市的所有解 计算解的旅游费 是否更新最优解 是否遍历完成 输出最优解 是 否 Step1：输入要旅游的城市个数 Step2：根据全排列产生 14 n A 组解。

Step3：计算每组解的旅游费 Step4：判断这组解的旅游费是否小于现在的最优解，假如是的话，把当前解赋 给最优解 Step5：判断是否遍历完毕，是则输出最优解，否则继续迭代 4.4.2 模型一的求解结果 旅游城市设置在 4 个以上，9 个以下，当旅游城市达到 9 个以上时用模型二 的模拟退火算法更加省计算时间用 MATLAB 编程得到如下最优解： 旅游城市个数 旅游路线 旅游费用 4 1-2-3-15 1169.9 5 1-3-15-4-14 1563.8 6 1-2-3-15-4-14 1983.8 7 1-15-4-14-3-5-13 2432.9 7 8 2-14-4-15-3-5-13 2853.9 9 1-9-2-15-4-14-3-5-13 3310.5 随着更新次数的增加解的旅游费变化趋势图： 图 4.4.2-1 模型一的求解结果 4.5 模型一的结果分析 该模型用的是枚举法，虽然一共才 14 个城市，用枚举法可以算出来，不适 合推广到更多的城市的情况 考虑到家庭旅游不太可能旅游非常多的城市和景点， 针对这种情况用枚举法是完全可以的，求出来的是最优解而不是近似最优解。

从 图 4.4.2-1 中看出随着更新次数的增加，从近似解慢慢得到最优解 5 问题二的建模与求解 5.1 问题二的分析 问题二是在时间充足的情况下（等价于能完成所有城市的旅行） ，考虑旅 途费用最少，这是典型的 TSP 问题，本文采用模拟退火法求出近似最优解 5.2 模型二的建立 5.2.1 解空间 解空间 s 可以表示为｛1，…｝固定起点的循环排列集合，即起点固定是昆 明， 每一个特解都对应一条路线，本文先使用蒙特卡拉方法求的了一个较好的初 始解 5.2.2 目标函数 8 目标函数是旅途过程中的交通费加上各个城市景点的门票费，其中后者是 固定的数字，相当于目标函数是交通费最少 15 1 minf(1.) ij i d   每产生一个特解都要计算一次交通费，若交通费比近似最优解更好，则更新近似 最优解 5.2.3 新解的产生 设上一步迭代的解为 1111115 . uuuvvv     ，任意产生两个 序号 u,v，交换他们之间的顺序变成逆序，此时新的解变成： 1111115 . uvvuuv     5.2.4 接受准则 计算出新解的交通费，若交通费比近似最优解更好，则更新近似最优解。

以 一定的概率接受新的路径 5.2.5 降温、输出 利用选定的降温系数进行降温，取得新的温度 T，本文选择降温系数为 0.999当温度小于终止温度或者大于最大迭代次数的时候输出结果本文的最 大迭代次数设置为 20000，退火温度是 30 10e   5.3 模型二的求解 5.3.1 算法的基本流程 9 参数初始化 蒙特卡洛法得初始解 2变换法新解的产生 是否接受新解 是否退火 输出近似最优解 否 降温 是 Step1：输入要旅游的城市个数，最大迭代次数，初始温度，降温系数等 Step2：用蒙特卡洛法循环 1000 次得到较好的初始解 Step3：用 2 变换法产生新解 Step4：根据交通费判断是否接受 Step5：温度乘降温系数 Step6： 判断是否已经达到最大迭代次数或者达到了退火的温度， 是则输出结果， 否则继续迭代 5.3.2 模型二的求解结果 （1）旅途的最佳路径 用 MATLAB 编程求得最佳近似解的旅游路径为： 1-8-11-9-7-10-12-6-2-14-4-15-3-5-13 交通费加上门票费等于 7033.1 元总费用随着更新次数的变化趋势如图 5.3.2-1 所示： 10 图 5.3.2-1 旅游费变化趋势 （2）旅途消耗时间 从图 5.3.2-2 中可以发先， 随着旅游经过城市的个数的增加消耗的时间也 是。