数学建模优秀论文

1参赛密码（由组委会填写）第十二届“中关村青联杯”全国研究生数学建模竞赛学校上海交通大学参赛队号10248085队员姓名1.鲁斯嘉2.关士托3.王朝静2参赛密码（由组委会填写）第十二届“中关村青联杯”全国研究生数学建模竞赛题目2015年全国研究生数学建模竞赛F题旅游路线规划问题摘要随着国民经济的快速发展，旅游活动成为现代生活的重要组成部分。本题要求为自驾游爱好者制定全国201个5A景点旅游计划。本文采用分层优化方法，建立两层带两个时间窗的旅行商问题模型、修正的带时间窗多车辆路径问题模型，采用改进的遗传算法并借助MATLAB编程求解，在第一问中得到以出游年数最短为目标的自驾出游方案。第二问中，在对两层模型目标和约束修正的基础上，为旅游者提供以体验最佳、费用最优的多交通方式出行的旅游规划。第三问中，本文将模型进行推广，为北京的自驾游游客制定了游览全国5A景点的十年旅游计划，并为旅游者和相关旅游部门提供可借鉴性建议。第四问中，基于第二问所建立的模型，增加游览时间比（游览时间占总出游时间的比例）最大的目标，将4A景区纳入出游考虑范围，制定了更为合理的十年旅游计划。对于问题1，本文采用分层优化的思想，下层为各省会城市辐射区内景点的路径规划，以出行时间最短为目标，在景点开放时间、车行区间等限制因素下，建立带两个时间窗的旅行商问题模型，采用双种群遗传算法并借助MATLAB编程软件进行求解，得到每个省会城市辐射区内景点的最短时间游览路线。在下层优化的基础上，上层模型以旅游年数最少为目标，将201个景点出游路径规划简化为31个省市游览路线优化，对带时间窗的多车辆路径问题（MVRPTW）模型进行修正，使同一城市游览时间超过15天限制时拆分为两次游览。采用遗传算3法并借助MATLAB编程求解，得到201个5A景区出游总时间为11年零10天，并给出每天出发地、行车时间里程、游览景区等信息。对于问题2，本文首先比较“自驾”、“飞机+租车”和“高铁+租车”三种交通方式的费用-距离曲线，得到高铁优先考虑、一天车程范围内采用自驾方式出游，两天以上车程选用飞机出行的结论。在此基础上，对第一问两层优化模型进行修正，以总游览年数最少、自驾出行次数最少和费用最优为一、二级目标，增加票价、车油费过路费、住宿费、租车费等费用约束。通过双种群遗传算法和MATLAB软件进行求解，得到最优的十年出游计划总花费为338447.96元，并给出每次出行方式、每天出发地、行车时间里程、游览景区等信息。对于问题3，本文将前两问中的模型进行推广，将出发地由西安改为北京，运用问题2中的模型和算法进行求解，得到最优的十年旅游计划，并给出每次出行方式、出行行程、天数和游览景区信息，有效验证了模型的可行性和适用性。最后根据不同优化目标的最优旅游计划为旅游者和旅游部门分别提出三条和四条建议。对于问题4，基于问题2中模型，在游览5A级景区的基础上，将4A级景区纳入考虑范围，并引入游览时间比（游览时间/总出行时间）为目标函数，对问题2中得到的出行规划进行优化，有效利用了“间隙”时间，得到出行体验更佳、更加合理的出行规划，并给出十年出行规划。关键词：旅行商问题(TSP)多车辆路径问题(MVRP)遗传算法(GA)旅游计划4目录一、问题重述.....................................................5二、问题分析.....................................................62.1问题一的分析................................................62.2问题二的分析................................................62.3问题三的分析................................................62.4问题四的分析................................................6三、符号定义与说明...............................................7四、模型假设.....................................................9五、模型的建立与求解............................................105.1问题一的求解...............................................105.1.1下层路径优化.........................................105.1.2上层路径优化.........................................135.2问题二的求解...............................................315.2.1交通方式选择.........................................315.2.2下层路径优化.........................................335.2.3上层路径优化.........................................365.3问题三的求解...............................................525.3.1模型的求解...........................................525.3.2建议的提出...........................................575.4模型四的求解...............................................585.4.1问题分析.............................................585.4.2问题假设..............................................595.4.3模型建立..............................................59六、模型总结与评价..............................................62七、参考文献....................................................63八、附录........................................................64附录一31个省市景点邻近城市OD矩阵...............................64附录二MATLAB核心程序...........................................695一、问题重述一位自驾游爱好者拟制定旅游计划遍历全国201个5A级景区。该旅游爱好者自身的限制条件：（1）每年外出旅游时间不超过30天；（2）每年外出旅游的次数不超过4次；（3）每次旅游的时间不超过15天；（4）根据个人偏好，每个5A景区有最少游览时间；时间窗限制条件为：（5）行车时间限定于每天7:00至19:00之间，每天开车时间不超过8小时；（6）景区开放时间统一为8:00至18:00。在每天的行程安排上，有以下规则：（7）若安排全天游览，开车时间控制在3小时内；（8）若安排半天景点游览，开车时间控制在5小时内；（9）在每个省会城市至少停留24小时感受风土人情（不安排景区浏览）；对于道路行车，速度限制如下：（10）高速公路上的行车平均速度为90公里/小时；（11）普通公路上的行车平均速度为40公里/小时。需要考虑如下问题：（1）行车线路采用高速优先原则，即先通过高速公路到达与景区邻近的城市，再自驾到景区，以常住地在西安市为例，规划设计游遍201个5A级景区旅游线路，确定花费年数及每一次旅游的具体行程。（2）出行方式综合考虑全程自驾、先乘坐高铁或飞机到达省会城市后再租车自驾到景区等出行方式，租车费用300元/天，油费和高速过路费另计，租车和还车需在同一城市。住宿费简化为省会城市和旅游景区200元/人•天，地级市150元/人•天，县城100元/人•天。高速公路的油耗加过路费平均为1.00元/公里，普通公路上油耗平均为0.60元/公里。假设每一个景区最长逗留时间不超过最少时间的2倍，选择高铁出行要求当天乘坐高铁的时间不超过6个小时，且至多安排半天的游览。该旅游爱好者一家3人同行，要求设计一个十年游遍所有201个5A景区的费用最优、旅游体验最好的旅游线路，并给出每一次旅游的具体线路。（3）能否在第二问所建立的模型基础上加以推广，可以为全国的自驾游爱好者规划设计类似的旅游线路，进而给出常住地在北京市的自驾游爱好者的十年旅游计划；根据上述三问的结果给旅游爱好者和旅游有关部门提出建议。（4）自2007年3月7日至2015年7月13日，全国旅游景区质量等级评定委员会分29批共批准了201家景区为国家5A级旅游景区。结合国家4A级景区名单，请更为合理地规划该旅游爱好者的十年旅游计划。6二、问题分析本题要求根据不同的条件约束不同的目标规划旅游路线，具体问题分析如下：2.1问题一的分析本问中要求制定以西安为常驻地的最短年数201个5A景点出游计划，并给出每次具体行程。本文采用分层优化思想，下层以出行时间最短为目标，建立带两个时间窗的旅行商问题模型，求每个省会城市辐射区内景点的最短时间游览路线。上层模型以旅游年数最少为目标，将201个景点出游路径规划简化为31个省市游览路线优化，对带时间窗的多车辆路径问题模型进行修正，采用遗传算法并借助MATLAB编程求解，得到201个5A景区出游总年数最少的出游计划。2.2问题二的分析比较“自驾”、“飞机+租车”和“高铁+租车”三种交通方式的费用-距离曲线，求得出行方式选择与距离关系。在此基础上，对第一问两层优化模型进行目标、约束的修正，以总游览年数最少、自驾出行次数最少和费用最优为一、二级目标，增加票价、车油费过路费、住宿费、租车费等费用约束，以求最优的十年出游计划。2.3问题三的分析本题将前两问中的模型进行推广，将出发地由西安改为北京，运用问题2中的模型和算法进行求解，得到最优的十年旅游计划，以此验证模型的可行性和适用性，最后根据不同优化目标的最优旅游计划为旅游者和旅游部门提出可行性建议。2.4问题四的分析本题基于问题2中模型，在游览5A级景区的基础上，将4A级景区纳入考虑范围，并引入游览时间比（游览时间/总出行时间）为目标函数，对问题2中得到的出行规划进行优化，有效利用了“间隙”时间，从而得到出行体验更佳、更加合理的十年出行规划。7三、符号定义与说明符号定义F={l,2,...,n}表示省会城市m辐射区内与景点邻近的城市点集，其中i=1表示省会城市；𝑇𝑖表示与i城市邻近景点的游览时间(天)；𝑇𝑚𝑖表示与i城市邻近景点的最少游览时间(天)；𝑇𝑖𝑗表示游客驾车从i城市邻近景点到j城市邻近景点的驾车行驶时间(天)；𝑃𝑇𝑖𝑗表示游客驾车从i城市到达邻近景点的驾车行驶时间(天)；𝑆𝑖𝑗表示游客驾车从i景点邻近城市到j景点邻近城市的驾车行驶距离（公里）；𝑋𝑖𝑗表示0-1决策变量，游客从i城市邻近景点到j城市邻近景点参观时，𝑋_𝑖𝑗=1S表示集合S中的元素个数；𝐴𝑇𝑖表示游客抵达i城市邻近景点的时刻；𝑒𝑖表示为允许最早游览时刻，由题意知景点开放时间为8:00-18:00，取𝑒𝑖=8:00𝑙𝑖表示为允许最迟游览时刻,即景点开放结束时间与景点最少游览时间之差，有𝑙𝑖=18−𝑇𝑚𝑖；[𝑒𝑖,𝑙𝑖]表示景点i的时间窗；𝐷𝑇𝑖表示游客从i邻近城市景点驾驶出发