2015年全国研究生数学建模大赛优秀论文F题3

参赛密码（由组委会填写）第十二届“中关村青联杯”全国研究生数学建模竞赛学校江南大学参赛队号10295002队员姓名1.智月明2.周超洁3.范雪峰参赛密码（由组委会填写）第十二届“中关村青联杯”全国研究生数学建模竞赛题目旅游路线规划问题摘要：本文主要以自驾游爱好者游遍全国201个5A级景区的旅游路线安排为研究对象，综合考虑时间约束（景区开放时间、行车时间、年旅行次数、旅行天数等），行车路线（高速优先）和旅行费用（包括住宿花费，行车油耗，飞机机票和高铁车票等）等复杂条件，建立多个模型并通过相应算法求解，以满足不同旅游者对于旅行的差异化需求。本文的主要创新点：以局部优化简化复杂的全局优化，从而得到旅游路线设计的近似最优解；将自驾游爱好者进行分类，根据不同的旅游偏好设计相应的模型求解出合适的景区游览路线及方式。本文完成的主要工作总结如下：一．问题一主要考虑了居住在西安的自驾游爱好者采取全程自驾游遍201个5A级景区时间最短的旅游路线规划问题。在考虑多个限制条件的情况下，本文建立了基于时间最优的多旅行商（mTSP）数字规划模型，并通过蚁群算法求解出该模型的最优解，安排出该旅行者的时间最优旅行路线。对于本问题，本文考虑先局部优化最后全局优化的主要思路。首先以省为单位对旅游时间进行局部优化：利用解决旅行商问题（TSP）的改良圈（又称Hamilton圈）算法分别求得各省旅游时间最优的旅游路线。其次考虑全国范围内的全局优化问题：首先建立mTSP时间最优模型，利用蚁群算法求解该模型得到每次旅行的最佳路线，根据所得结果拆分部分省份，然后被拆分省份与邻近省份重新生成一个新的改良圈进行优化，最终得到从西安出发游遍全国各景区需要10.5年，并整合出具体旅游路线。二．问题二主要是综合考虑旅行费用和旅游体验度双重指标，设计出一家三口10年游遍201个5A景区的旅游线路。在保证10年前提条件下，本问主要采取尽可能提高旅游体验，减少旅游花费的思想。在结合约束条件的前提下，建立了基于多目标优化的规划模型，通过归一化、函数拟合等方法，利用基本粒子群优化算法计算得到接近于最优的次优解，给出该家庭的十年出行路线。首先对时间、花费进行归一化处理，构造体现旅行者对出行要求的参数；其次根据已知信息，采用函数拟合方法求得机票、高铁价格与两城距离之间的定量关系；再者针对全国范围内的全局优化，建立花费最少、体验度最优的多目标模型，利用基本粒子群优化算法优化得到出行的最佳路线和合理交通方式，辅以局部修改，得到最终方案。最终，通过对所得出行方案的整理计算，得出家庭十年旅行路线安排、最优花费和最佳旅行体验度，最少花费为318362元，最佳时间满意度为0.82。三．问题三主要是在问题二所得模型的基础上进行推广，建立起适用于全国范围旅游爱好者旅游路线规划的推广模型。根据问题二中出行方式花费函数，考虑人数和行车路程两个因素对模型的影响。通过分析问题一和问题二中所得结果，定性地分析了在旅游过程中对旅游总时间和旅游费用的影响较大的关键因素。并且本文中还利用问题一中所得模型求解出北京为旅行首末站城市的全程自驾游行车时间最短为124.5天，与第二问所得结果（行车时间为66天）定量的进行对比，增加约束条件对问题二中的多目标优化模型进行推广。接着以北京作为首末站城市的旅游路线为例，考虑一人出行的情况，同样通过基本粒子群优化算法求解所得多目标优化推广模型，得到十年旅行费用和体验度最优旅游路线且行车时间为65.5天（小于66天）。最后分别针对费用和旅游人气等向旅游爱好者和旅游部门分别给出相关建议。四．问题四首先根据景点特色将所有自驾游爱好者分为5类，然后基于该旅游者偏好确定在每个5A级景区最少的游览时间分析出此自驾游爱好者属于观光休闲类。增加约束条件剔除5个离省会较远的5A级景点，然后安排适量的4A级名胜风景区在该自驾游爱好者的十年旅游计划中，根据Hamilton圈方法进行优化，最终得到合理的旅游规划。最后对所建立的模型进行优缺点分析，并提出改进意见。关键字：多旅行商；改良圈；蚁群算法；基本粒子群优化算法目录1.前言.....................................................................................................................................11.1问题背景与问题描述.................................................................................................11.2问题分析.....................................................................................................................11.3基本假设.....................................................................................................................22.问题一的模型建立与求解.................................................................................................22.1数据分析.....................................................................................................................22.2各省时间最优旅游路线求取.....................................................................................32.3全国时间最优旅游路线求取.....................................................................................62.3.1mTSP时间最优模型建立................................................................................62.3.2基于蚁群算法的模型求解..............................................................................73.问题二的模型建立与求解...............................................................................................103.1模型建立...................................................................................................................103.2模型求解与结果分析...............................................................................................133.3最终模型方案...........................................................................................................174.问题三的模型建立与求解...............................................................................................204.1数据分析...................................................................................................................204.2模型推广...................................................................................................................224.3模型求解...................................................................................................................234.4旅游建议...................................................................................................................255.问题四的模型建立与求解...............................................................................................255.1数据分析...................................................................................................................255.2模型建立....................................................................................................................265.3模型求解....................................................................................................................276.模型评价与改进...............................................................................................................28参考文献..................................................................................................................................30附录..........................................................................................................................................3111.前言1.1问题背景与问题描述旅游活动正在成为全球经济发展的重要动力之一，它加速国际资金流转和信息、技术管理的传播，创造高效率消费行为模式、需求和价值等。随着我国国民经济的快速发展，人们生活水平得到很大提升，越来越多的人积极参与有益于身心健康的旅游活动。故而为旅游爱好者科学并且合理地规划旅游路线是一个热点问题。本文主要解决以下问题：问题一：在行车线路的设计上采用高速优先的策略，考虑多种时间约束，设计出合适的方法，建立数学模型，以该旅游爱好者的