分块分层优化的旅游路线规划问题研究

《分块分层优化的旅游路线规划问题研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、参赛密码（由组委会填写）第十二届“中关村青联杯”全国研究生数学建模竞赛学校西南石油大学参赛队号106150031.陈琳队员姓名2.刘浩生3.罗仕明参赛密码（由组委会填写）第十二届“中关村青联杯”全国研究生数学建模竞赛题目分块分层优化的旅游路线规划问题研究摘要旅游活动不仅能够驱动全球经济的发展，而且是人民追求幸福生活的最重要方式之一。我国特别将发展旅游业作为经济结构转型、驱动内需和提升人民生活品质的目标之一。研究旅游路线规划问题，对普及旅游活动和发展旅游业起着举足轻重的作用。本文为了更好地解决旅游路线规划问题，利用聚类分块和分块分层优化的思想，根据图论、最优化和模糊数学等的理论与

2、方法，在将景点间的公路统一转化为普通公路、省会城市间统一为高速公路及对问题四用模糊综合评价排序挑选出旅游景点后，针对不同问题，利用邻近距离聚类构建了具有不同权值含义的分块加权网络图和分块动态网络图；建立了改进的单目标和多目标的旅行商问题（TSP）模型、改进的多旅行商问题（MTSP）模型、最少旅游年数的优化模型、旅游体验最好和费用最少优化模型等；设计了它们的求解算法，特别针对改进的TSP模型，提出了解单目标TSP模型的改进模拟退火算法和基于分层序列法的改进模拟退火算法；并借助元胞数据提取技术和Matlab软件编程，获得了满足各问题要求的旅游路线最佳规划方案。主要工作如下：针对问题

3、一，利用图论中的组合优化、单目标和多目标优化及模拟退火等的理论和方法，为常驻西安市的旅游者游遍201个5A级景区规划了最少年数的最佳旅行路线。首先，利用近邻聚类的思想对景点进行区块划分，构建了含区块划分的旅游网络图（见图5）；然后，对每次旅游时间、旅行过程中的行车和游览时间进行约束，建立了基于TSP的最佳旅游路线规划模型对各区块内景点进行最佳路线规划，再建立基于MTSP的改进模型寻求各区块间的最佳旅游路线；其次，以旅游总年数最少、每年旅行时间接近30天为目标，建立一个关于旅游年数的分堆优化模型；再其次，分析了各模型的特点，提出了解决这些模型的算法思想和求解步骤，特别针对改进的T

4、SP模型具有多约束条件的特点，依据求解TSP模型的模拟退火算法的思想，提出了改进的模拟退火算法；最后，利用元胞数据方法和Matlab软件编程，计算得到了旅游者至少需11年才能游遍所有5A级景点，并获得了每一年中旅游的次数、每一次旅游的区块和时间（见表4）、以及每次旅行中每天的具体行程方案。文中仅以旅游河北省区块为例示意说明，表5和图6展示了游览河北省区块的景点需要9天及9天中每天的旅游行程，其余28次旅游路线规划方案见附件1。针对问题二，综合考虑多种出行方式，为旅游者规划费用最优、旅游体验最好的十1年旅游路线。在问题一的基础上，首先，基于各区块内的最少旅游时间，建立各区块内租车

5、费用、耗油费、住宿费用的计算模型；然后，基于建立的旅行十年期限中剩余最大出行时间的计算模型，考虑出行方式所产生的费用和时间的矛盾，建立基于出行时间的最小费用的旅游路线规划的多目标TSP优化模型，规划各个省之间进行旅行时的最佳旅游路线、获得十年内最少的出行时间；其次，基于十年内游遍所有5A景点剩余的游览时间，提出了分配剩余时间来增加各景点的至少游览时间，使得旅游者达到最好旅游体验的方案；最后，利用元胞数据方法和Matlab软件编程，计算得到十年之旅的最少费用为32.6万元，并给出了旅游北京、天津区块的费用最优、旅游体验最好的旅游线路，含每天所需费用以及每天具体行程（见表7、图9）

6、的示例说明，其余26次旅游路线见附件2。针对问题三，依据自驾游的特点，采用动态赋权的方法对第二问所建立的模型加以改进和推广，为了刻画旅游者的出发位置对整个网络图的影响，首先构建了动态的旅游网络图；然后基于动态的旅游网络图，根据自驾游的特点确定动态网络图的权值；其次利用问题二中的基于旅游时间年限的多目标优化模型及求解算法，通过编程计算，为常住地在北京市的旅游者规划十年游遍所有5A景点的旅游方案，以四川省区块为例示意说明（见表10、图11）；最后根据旅游方案结果，为自驾游爱好者和旅游相关部门给出了相关建议。针对问题四，基于用模糊综合评价从众多不同级别景点筛选出的旅游景点，综合采用问

7、题一和二的方法为旅游爱好者规划旅游路线。首先依据旅游者在面对众多不同级别景点作旅行计划时，并不一定是以景点级别高优先选择的原则，而往往是通过对比景点的相应指标与自身旅游偏好进行优先挑选，通过分析附件6、7中的旅游景区评定的相关信息和旅游者对旅游的偏好，建立旅游景点选择的评价指标体系；然后建立挑选景点的模糊综合评价模型，确定旅游者对每个景点的优先级排序，进而确定出十年内计划旅游的景点；其次针对选中的旅游景点，按问题一和二中的方法为旅游爱好者做出十年最优旅游路线的规划；最后通过Matlab软件编