最佳旅游路线.pdf

基于模拟退火法的最佳旅游路线 摘要 本文对云南省最佳旅游路线问题进行了建模、求解和相关分析。 针对问题一，首先根据旅游城市的个数进行分类，在旅游的城市的个数确定 的情况下，以旅游费用最小为目标函数，用枚举法遍历所有情况，筛选出最优解。 发现在旅游的城市个数小于8 的时候，用MATLAB 编程能够迅速得出答案；当旅 游的城市个数大于等于9 的时候运行时间大大增加，此时枚举法已经不再适用。 针对问题二，由于旅游时间是两个暑假，说明时间是充足的，在这个基础上 求花钱最少的旅游路线，这是典型的TSP 问题，因为城市个数已经大于9 个，本 文分别采用模拟退火法和遗传算法对该问题进行求解。发现在本题中城市的个数 不是很多导致模拟退火法和遗传算法求出来的解是相同的，这说明都已经求得了 精确解。 针对问题三，题中并没有说清楚考察组最多能分几组，在不限制分组的数的 情况下分 15 组，每组去一个地方能达到最快的效果。但这和现实不太符合，结 合生活经验，本文讨论了分为1-5 组的情况下，以花费时间最小为约束条件，同 时考虑各组去的城市数量相差不大，改进模拟退火法分别算出每个分组花的最大 时间，结果发现随着分组的个数增加，最大调研时间是单调下降的，下降的速度 越来越慢，从图中可以看出，当分组为3、4 的时候下降速度已经明显减缓，因 此选择分为3 或者4 组是最佳的选择。 针对问题四， 在不同城市容量不同的情况下，考虑不同的旅客有长途、和 短途两种不同的需求，为此本文以长途、短途旅行展开分析，以最小的交通费为 目标，兼顾旅游时间小于10 天，给出了长途、短途的旅行方案供旅客自由选择。 1 目录 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 2 1 问题重述 1.1 问题背景 云南，即 “彩云之南”“七彩云南”，是著名的旅游大省，昆明、大理、丽 江、香格里拉、西双版纳，自然风光迤逦、文人景观精彩、少数民族的节日丰富、 时光悠闲，让人一去就想永远留在那里。王先生夫妇是北京某高校的年轻教师， 打算暑假到云南旅游。 1.2 需要解决的问题 （1）请为他们设计合适的旅游路线，使他们在暑假一个月的时间里花最少的钱 游览尽可能多的地方，并估算除吃饭之外的费用。 （2）如果他们打算今、明两年暑假完成对云南的旅游，请你为他们设计合适的 旅游线路，使在云南境内的交通费用尽量的节省。 （3）如果某高校的少数民族研究所组织对云南文化考察，用于交通的时间和前 两种情况相同，单考察时间是旅游观光时间的四倍，请您们为他们设计合适的考 察路线，为便于尽早完成考察任务，最少需要分几组考察。 （4）旅游部门迎接 “十一黄金周” （考虑