旅游路线规划问题-2015年研究生数学建模竞赛

参赛密码 （由组委会填写）第十二届“中关村青联杯”全国研究生

数学建模竞赛西南大学参赛队号队员姓名参赛密码 （由组委会填写）第十二届“中关村青联杯”全国研究生

数学建模竞赛题目 旅游路线规划问题摘要：近年来随着科技的进步和社会的不断发展，旅游活动正在成为全球经济发展的动力之一，它加速国际资金流转和信息、技术管理的传播，创造高效率消费行为模式、需求和价值等。随着人们生活水平提升，越来越多的人积极参与有益于身心健康的旅游活动。国家旅游局公布了201个5A级景区名单，但是当前人们对旅游路线规划的问题还比较盲目，如何选择最优路线游遍201个5A级景区的旅游还不够清楚。针对这些问题本文着重进行了以下几个方面的工作：问题一，旅游爱好者常住西安市，采用高速优先的策略自驾到景区，规划设计最短路线游遍201个5A级景区。根据附件1我们利用图论和运筹学的相关知识对景区构建赋权图。由附件2的信息统计得出从西安到各省会的公路长度，结合附件一和百度地图上的高速路距离，对于分块的景区利用改良圈法建立TSP问题的旅游路优化设计模型，运用Lingo软件编程求出最短路径。对于旅游者每年有不超出30天的外出旅游时间，每次不超过15天，每年不超过4次的旅行条件，采用目标规划算法编写Java语言求出游完201个5A级景区的最佳途径。通过该程序给出了每次旅游的具体行程表。问题二，除了高速优先之外，人们还可以考虑乘坐高铁或飞机到达与景区相邻的省会城市，再采用租车的方式自驾到景区游览，考虑旅游费用规划一个十年游遍所有201个5A级景区费用最低、旅游体验最好的旅游路线。根据附件3和附件4统计出高铁和飞机的费用，运用层次分析法在Excel中求解出从出发点到省会的最佳交通方式。利用模型一中改良圈法建立TSP问题的旅游路优化设计的路线，根据题上约束条件采用多目标规划运用Java语言编程求出游完201个5A级景区的最佳路径。由以上结果在Excel算出每次旅行的花费，规划出每次旅行的具体行程。问题三，将模型二推广至常住北京的自驾游爱好者的十年旅游计划，根据上述三问结果分别给旅游爱好者和旅游部门提建议。考虑住宿，耗油加过路费，同样采用层次分析法确定每次旅游时旅游者的最合理的旅途方式，根据确定好的方式利用模型一中改良圈法建立的旅游优化模型，采用目标规划用Java语言给出了北京自驾游的十年旅行计划。最后结和已建立的模型考虑费用、时间等因素给出合理建议。问题四，根据附件6和附件7给出的信息，采用改进的蚁群算法，使对景区选择能实现动态规划、从而实现旅游景区的负载均衡，用概率对景区的选择做目标规划，从而确定旅游最佳路径，求解出更为合理地规划该旅游爱好者的十年旅游计划。关键词：图论；改良圈法；TSP问题；Java语言；目标规划；层次分析法；最优化问题改进蚁群算法；动态规划；Lingo软件目录TOC\o"1-5"\h\z\o"CurrentDocument"一、问题背景与重述 34\o"CurrentDocument"问题背景. 34\o"CurrentDocument"需要解决的问题 35\o"CurrentDocument"二、模型假设与符号说明 35模型假设 35\o"CurrentDocument"符号说明 36\o"CurrentDocument"三、问题分析 37\o"CurrentDocument"针对问题一 37\o"CurrentDocument"针对问题二 38\o"CurrentDocument"针对问题三 38针对问题四 38\o"CurrentDocument"四、模型的建立 39\o"CurrentDocument"问题一模型的建立和求解 39问题一模型的建立 39\o"CurrentDocument"问题一模型的求解 40问题二模型的建立和求解 45问题二模型的建立 45\o"CurrentDocument"问题二模型的求解 45问题三模型的建立和求解 47问题三模型的建立 47问题三主要模型的求解 47\o"CurrentDocument"问题三给旅游者和旅游部门的建议 48问题三模型的建立和求解 49问题三模型的建立 49\o"CurrentDocument"五、模型的优缺点 51\o"CurrentDocument"模型的优点 51\o"CurrentDocument"模型的缺点 51\o"CurrentDocument"参考文献 52\o"CurrentDocument"附录 52一、问题背景与重述问题背景近年来随着科技的进步和社会的不断发展，旅游已然成为人们的一种生活方式各种旅游服务业的不断发展成熟，让人民外出旅游变得十分便捷，一方面是旅行社提供的团队游产品日益丰富；另一方面是旅游个性化的自助游，随着旅游业的日益成熟，旅游环境让旅行者渴望尝试。不管是团队游还是自助游，旅游路线都是连接旅游客源地与旅游目的地的重要环节。设计合理的旅游线路既有利于旅游者有目的的选择、安排自己的旅游活动，又有利于发挥各个旅游点的功能以及旅游者合理利用时间，还有利于旅游者有计划地支配自己的旅游费用等等。设计合理的旅游线路技术性和经验性非常强，大多数旅游者出游过程中都希望在感觉舒适和体力充沛的情况下，采用较短路程、花费较少时间和费用来游览更多的旅游景区。因此依据旅行者自身的间、旅游计划经费、准备采用的出行方式和期望的旅游地点，设计科学合理及体检最佳的旅游线路不管是对旅游组织者还是旅游者，都具有重要的意义。需要解决的问题为了给旅游爱好者规划出费用最优、旅游体验最好的的旅游路线，本文将利用数学方法解决以下数学问题：.采用高速优先，设计出游遍201个5A景区的具体行程安排表。(1)旅游者采用自驾高速优先的方式，依据题目要求关于该旅游者旅游次数、旅游时间，自驾时间、自驾速度、游玩时间等规定，及附件1,2,3中相关参考信息，将201个5A级景区划分为小的分块，确定旅行完每一个小的分块的最佳旅行途径，求出该旅行者游遍201个5A级景区至少需要年数。(2)建立数学模型对该旅行者每一次旅游中每一天的出发地、行车时间、行车里程及游览的景区做出详细的行程安排表。2.采用多元化出行方式，设计出游遍5A景区，费用最优、体验最好的具体行程安排表。(1)考虑全程自驾或者乘坐高铁或飞机到达与景区相邻的省会城市然后再租车到达景区游览等，建立数学模型分别计算在10年里游遍5A级景点所产生的旅游成本。(2)综合考虑旅游成本及旅游体验，设计规划出最优的线路，并给出每一次旅行的具体行程，包括每次具体的出游方式、每一天的出发地、旅游成本、路途时间。游览景区及旅行者在每个景区的游览时间。.推广所建数学模型，规划出常住地在北京的自驾旅游者十年的旅行计划。(1)将第二问中所建立的数学模型加以推广，为常住地在北京的自驾爱好者规划出十年的旅游计划，并给出每一次旅行的具体行程，包括每次具体的出游方式、每一天的出发地、旅游成本、路途时间，游览景区及旅行者在每个景区的游览时间(2)结合前三问所建立的数学模型得出的旅游规划，分别给旅游爱好者和旅游有关部门提出合理的建议.针对附件6、附件7建立数学模型，采用多元化的出行方式，为该旅游者规划出十年游览5A及4A景区的行程表。(1)优化上述数学模型，考虑在旅游成本最优及旅游体验最佳的情况下，采用多元化的出行方式，规划出旅游者十年内尽量多游览5A及4A景区的旅游线路设计。(2)在此模型下给出每一次旅行的具体行程，包括每次具体的出游方式、每一天的出发地、旅游成本、路途时间，游览景区及旅行者在每个景区的游览时间。二、模型假设与符号说明模型假设.附件中的数据都是准确无误的实测数据，没有经过改动。.本文自行检索收集的网络资料、数据和信息都是准确无误的。.该旅行者在每个省会至少停留24小时，在这24小时之内不安排景区游览。.景区开放时间统一为8:00至18:00。.该旅游者在每个景区的游览时间严格按附件一中的最少游览时间计算，不出现特殊情况。.天气等一切突发情况不纳入考虑范围，对于道路的拥挤程度不予考虑，认为是通畅的。.对于高铁及航班的晚点情况不予考虑，认为是准点的，忽略一切等车时间。.不考虑旅途中可能突发的汽车故障及旅行者身体不适等因素。.假设旅游时间只包括交通乘车时间和在景点的旅游时间，不包括住宿时间。

.假设全国所有5A级旅游景区门票费用都一样，所有4A级旅游景区门票费用都一样。.该旅行者的住宿费简化为:省会城市和景区每人每天200元，地级市每人每天150元，县城每人每天100元。符号说明符号 符号说明第m个省内的第i个旅游景区=1第m个省内的所有景区游览时间=2第m个省内景区间线路花费时间第m个省内的从第i个旅游景区到第j个旅游景区距离第m个省内的从第i个旅游景区到第j个旅游景区驾车所花费的第m个省内的从第i个旅游景区到第j个旅游景区所花费的交通ri广1游客从第i个景点到第j个景点第昨个省的旅游总费用 jij旅游总成本第m个省内的第i个旅游景区住宿费第m个省内景区间路程上花费的时间游览总时间第m个省旅游景区的数目各5A级旅游景区的门票费用各4A级旅游景区的门票费用第m个省的最短路径长度从西安市到第m个省会城市高速路所需要的时间第m个省内游览景区花费的时间第m个省内所产生的景区门票、交通费、住宿费的总和imtmimtmdmjtmCmjrijMmMMZmTmTnmb1b2dmTmTmPmDmDm 第m个省内的普通公路里程数Pm 从西安到第m个省会的高铁费用1Pm 从西安到第m个省会的航班费用2tm 从西安到各个省会的交通时间J 第i个景区中的最大人流量maxT9) 第i个景区在t时刻旅游景区的人数P t时刻旅游景区人数与最大人流量比值1L 第i个旅游景区到当地省会的距离L 所有景点到当地省会的总距离P 旅游景区到当地省会的距离与总距离的比值2Y. 第j次旅行花费的总费用JY.(t) 第j次旅游t时刻剩余的费用jP 费用花费率3X 是否去第i个景点i三、问题分析针对问题一采用高速优先，设计出游遍5A景区的具体行程安排表，分析问题得知求游遍201个5A级景区最少需要的年数，先不考虑旅行成本，由附件1假设该旅行者在各个景区游览时间按最少游览时间计算，该问题实际就是在一定的约束条件下求出最短的行程问题。从整体上来说，题目实际上研究的就是运筹学及图论中的组合优化问题。将各个景区看成图中的一个顶点，边表示连通各个景区之间的路，边上的权表示距离(或时间或费用)，由此形成了旅行问题的加权网络图，那问题就转化成了求这个简单的网络加权图的最佳推销员回路问题，也就是TSP问题。又根据附件一中该旅游者计划在每个省会城市至少停留24小时，且各个省会城市的交通高速网相对完善发达，故考虑将各个省会城市作为从西安市到各个省份旅游景区的中转站，将各个省会划分为独立的小板块。针对多局部最优的最优化问题，目前解法主要有遗传算法、最小生成法、模拟退火法、蚁群法、局部搜索及神经网络等，因为简化模型后各个小板块内顶点不多，考虑对该TSP问题用一般方法求Hamilton圈，建立数学规划模型用lingo程序求出精确的最短圈长度及最短路径，从而求出走完这一小版块的最短时间。然后将各个省看成节点，由于自驾游爱好者每年有不超过30天的外出旅游时间，每年外出旅游的次数不超过4次，每次旅游的时间不超过15天，我们根据这些约束条件建立约束函数然后采用Java程序求出每年的具体旅游行程。针对问题二问题二中题设中丰富了旅行者的出行方式，总共可分为三种。第一种是问题一中高速优先的全程自驾，第二种是先乘高铁到省会城市，然后租车的方式；最后一种先坐飞机到省会城市，然后租车到景区。考虑三种方式下旅游者在旅途过程中分别产生的旅游总费用，其中包括交通费用（包含可能产生的高铁费、机票费、租车费、高速公路的油耗加过路费及普通公路上的油耗费）住宿费用及景区门票。问题二中要求规划出费用最优、旅游体验最好的旅行路线，结合实际我们将旅行体验具体量化为旅行中在交通工具上所花费的时间最短，众所周知旅途中交通工具所占时间比重越少，比如在不考虑旅行费用的前提下，乘坐飞机固然比乘坐高铁或汽车带给旅行者的旅行体验更佳。又针对旅行费用和旅行交通工具所占时间这两个权衡指标因人而异，用层次分析法予以权衡这两个指标，来求解合适的交通方式，然后运用Java程序从而建立设计出十年内游遍所有5A级景区、费用最优、旅游体验最好的旅游路线。然后再依据问题二中具体旅游行程中的相关约定（旅游者在任一景区最长逗留时间不超过附件1给出的最少时间的两倍，高铁出行当天乘坐高铁时间不超过6小时，乘坐高铁或飞机当天至多安排半天的景区游览等）便能具体规划出并给出每一次旅行的具体行程，包括每次具体的出游方式、每一天的出发地、旅游成本、路途时间。游览景区及旅行者在每个景区的游览时间。针对问题三在问题二已有的交通方式即高速优先的全程自驾、先乘高铁到省会城市，然后租车的方式、最后一种先坐飞机到省会城市，然后租车到景区。此次旅游为常住在北京市的自驾游爱好者的十年旅游计划，考虑模型二旅游者在旅途过程中分别产生的旅游总费用，其中包括交通费用住宿费用及景区门票结合，实际在旅行中若在交通工具上所花费的时间短，旅途中交通工具所占时间比重少，我们旅行的时间就少。又针对旅行费用和旅行交通工具所占时间这两个权衡指标因人而异，用层次分析法予以权衡这两个指标，来求解合适的交通方式，再依据问题二中具体旅游行程中的相关约定（旅游者在任一景区最长逗留时间不超过附件1给出的最少时间的两倍，高铁出行当天乘坐高铁时间不超过6小时，乘坐高铁或飞机当天至多安排半天的景区游览等），然后运用Java程序从而建立设计出十年内游遍所有5A级景区、费用最优、旅游体验最好的旅游路线。便能具体规划出并给出每一次旅行的具体行程，包括每次具体的出游方式、每一天的出发地、旅游成本、路途时间。游览景区及旅行者在每个景区的游览时间。针对问题四实际上任何一个旅游景区接待游客的能力都是有限的，无限制的接待游客将导致景区的生态环境遭到严重的破坏。从旅游者来说一个景区接待的人数越多，景区的交通及公共服务能力必然会大幅下降，欣赏风景时人头攒动会耗费旅行者的时间和精力，会在很大程度上影响游客的旅行质量，游客满意度及体验感会下降，因此一个景区容纳游客的数量就该依据具体每个景区的相关配套设施及公共服务能力严加控制。正如近年来出现的黄金周旅游热，使得旅游爱好者在制定旅游规划时针对第四问要求给出更为合理的旅游规划路线，因此考虑将利用图论最大流方法和层次分析法讨论景区的流量控制时，定义才时刻景区”的人流量，产生动态的景区人流量比例函数，这个函数将一定程度上制约旅行者是否选取该景点作为下一站。对于多景点间的顺序规划的实现借助于改进后的蚁群算法。四、模型的建立问题一模型的建立和求解问题一模型的建立首先由题目中约束条件该旅游者计划在每个省会城市至少停留24小时，且由附件2知各个省会城市的交通高速网相对完善发达，故考虑将各个省会城市作为从西安市到各个省份旅游景区的中转站，将各个省划分为独立的板块，便于表述将其按附件1中的顺序编号为bi,b2,…,b31。然后将省内的各个旅游景点之间的关系转化为图论问题，建立赋权图GV,E），其中V=V,V，…,V}2 n称为G的节点集，V的每一个元素V（i=1,2,…,n）在该问题中表示景点之间。i即将每一个省内的旅游景区看着图中的一个节点，各景区景点之间的线路看成图中对应节点间的边，边上的长度表示旅游景区之间的距离，所给各旅游景区间的公路网就转化成为网络图G，要游遍该省内的各5A级景区的最佳旅游路线问题就转化为在给定的网络图中寻找从给定出发点出发，行遍所有顶点至少一次再回到定点，使得距离最小，此即改良圈算法建立的最佳旅行商问题（TSP问题）。TSP问题的本质就是从出发点出发最后回到出发点的距离最小Hamilton圈，采用改良圈算法解该问题。Hamilton圈的最邻近算法的基本思想：第一步：任意选一个点v0作起点，找一条与v0关联且权最小的边"匕的另一个端点记作v1，得到一条路v0V1；第二步：设已选出路v0v1^vi,在V（G）-40,V1,…,vi}中取一个与vi最邻近的相邻顶点vi+1得到路v0v1^vivi+1；第三步：若i+1<n-1，用i代替i+1返回步骤二，否则记v0v1^vj0，停止得到一条近似最优的Hamilton回路。用最邻近算法求得的Hamilton回路一般不是最优解，但是通过改良可以获得更短的Hamilton回路。设C=v0北…vj1是网络图G的一个Hamilton圈。对圈C中所有满足1<i+1<j<v的i,j，按照以下方法最终得到一条新的Hamilton圈C:1eE（G）且第一步：在C上检查是否有i中j，使得vvjeE（G）,vi+ivj+1攻^v^vj^+攻Iv.）<攻（vv^）+攻v.eE（G）且则构成新圈C=vv…vvv.…viv.…vv。第二步：用q代替C转到第一步，直到终止。将改良圈算法写成数学规划模型有：min工dmr，

ijiji于js.t.2nr=1,i=1,2,…,n，ijjT^j1，j=1，2,…,，i=12rj<s-1,2<s|<n-1,su』,2,…,n｝，i,jes即s为&,2,…,n｝的真子集（除起点和终点外，各边不构成圈），rjehdi，L2，…,n，i'j。4.1.2问题一模型的求解由附件1及附件2相关信息统计可得各个省（小板块）内所有旅游景区及省会城市之间的线路距离表（单位：公里）注：所有省均设其省会城市为1,其余旅游景区按附件1中给出顺序依次编号2,3,…,n；依据附件1、附件9相关信息及中国行政区域划分图，为了便于计算将河北省内的景点按邻近原则划分到北京和天津区域内，将江苏省内的景点划分部分到上海景区。表1：山西省内所有旅游景区及省会城市之间的线路距离表1234567710276803441358610722760257620411361382

38025705313222722934344620531029935132451354113222990613468636127235161032710738229332434320通过编写Lingo,求解得到结果如下（代码见附录1）求得的山西省内各旅游景区及省会城市的最短路径为1-4-5—7—6—2—3-1,最短路径长度1407公里。即山西省内各旅游景区及省会城市的最短路径为：太原市―晋城阳城县皇城相府生态文化旅游区一晋中市介休市绵山风景名胜区—晋中市平遥县平遥古城景区—晋中市乔家大院文化园区—大同云冈石窟―忻州五台山风景名胜区—太原市。如下以山西省为例验证该算法：图1：山西省内景点分布图从图1可以看出山西省内5A级景点分布零散，采用上述算法对该7个景点求最短路径后绘图如图2。图2：山西省内景点的最短路径图同样方法运行Lingo（附录1）求出其余省份的最短路径及最短路径长度见下表2：

表2：各省份最短路径及最短路径长度表省份最短路径最短路径长度北京1―3—4—7—5—6—9—10—8—2—1835天津1T7T6T4T3T2T5T1928山西1T4T5T7T6T2T3T11407内蒙古1―3—2—1543辽宁1―3—4—5—2—1981吉林1―3—4—5—2—1792黑龙江1―3—6—5—4—2—13371上海1—13—7—8—11—5-10—12—9—6—2—3—4—1318江苏1―3—2—10—8—5—11—7—6—4—9—1933浙江1-2—10—13—6—9—4—7—3—8—12—5-11—11452安徽1T8T6T4T5T9T7T2T3T11310福建1T7T2T5T4T3T6T8T9T11377江西1T2T7T6T4T5T8T3T11610山东1—10—3—7—6—5—8—4—2—9—11585河南1―7—5—4—2—8—10—3—6—9—11—11327湖北1―9—2—11—5—7—6—12—10—4—3—8—11750湖南1T6T7T4T3T8T5T2T11496广东1—11—9—7—8—5—10—3—6—4—2—11576广西1―4—2—3—5—1914海南1―5—2—3—6—4—1617重庆1T6T7T4T5T3T2T11531四川1-7—10—9—11—4—6—8—2—5—3—11789贵州1―3—2—4—5—11117云南1T4T3T7T5T6T2T12150西藏1―3—2—10陕西1T5T2T6T3T4T7T1713甘肃1―4—3—2—5—13046宁夏1―4—2—3—5—1599青海1―3—2—1404新疆1T2T8T10T7T6T4T5T9T3T12907问题一中行车路线要求采用高速优先的策略，即先通过高速公路到达与景区邻近的城市，再自驾到景区。由附件2、附件8和附件9,运用数学方法近似求得在各个省内高速公路和普通公路权重分别为0.8与0.2,又有假设自驾在高速公路上的行车平均速度为90公里/小时，在普通公路上的行车平均速度为40公里/小时，有计算式：— bm bmTm= =90*0.8+40*0.280由表2中各省内的最短路径长度及上述计算式，求出各省内（板块内）所需要游览

天数，然后由附件3能统计得出该旅行者从西安市到各个省会城市自驾行驶高速公路的里程数，又假设自驾在高速公路上的行车平均速度为90公里/小时，则从西安市出发到各个省会城市然后返回西安市所花费的旅游天数能计算得出。目标函数的建立：问题一中，在不考虑旅游费用的情况下，要求游览完201个5A级景区，使得该旅游者花费的时间最少。旅游者的时间花费由三部分组成，包括从西安市出发到各省会城市并折返回西安市的时间、花费在各个省内景区之间路程上的时间及游览景点的时间。（注：单位统一换算为天数）时间综合表注：最后折算的总时间天数的小数部分，大于0.1按1天计算；其余情况按0计算）由此总花费时间计算公式：T=2*Tm+Tm+Tm1Tmbm八=T—++Tm4 640从而计算可得Tm，当m从1取到30时，对应的省份所花费的总时间为12、11、9.5、6、10、10.5、16、13、12、14.5、13、15、13、12、13.5、14.5、12、14、10、10.5、11.5、14、9、13.5、10、6、11、6.5、6、21。由上数据发现从西安市前往新疆一次游览完所有的旅游景区需要花费21天，但题中限制该旅游爱好者每次旅游时间不超过15天。此处我们先粗略将新疆的景区按高速路G3012划分成南北两个部分，每部分近似估计游览时间为10天。由以上所建立的数学模型，对旅游线路的规划可分以下几种情况加以讨论：因每年所举行的旅行的次数不超过4次，可分为（1）若一年要4次旅行，根据题目的条件建立相应的约束函数<305<尸15通过软件求出满足条件的分类有4中即得：6+6+6+12 6+6+7+11 6+6+8+10 6+7+9+10（2）若一年要3次旅行，根据题目的条件建立相应的约束函数5<y<15,i=1,2,3，”N通过软件求出满足条件的分类有6+9+15 6+9+14 6+9+137+8+15 7+8+14 7+8+13通过软件求出满足条件的分类有6+9+15 6+9+14 6+9+137+8+15 7+8+14 7+8+136+9+12 6+9+11 6+9+107+8+12 7+8+11 7+8+106+9+97+8+9⑶若一年要2次旅行，根据题目的条件建立相应的约束函数:5<y<15,i=1,2,3，yeN通过软件求出满足条件的分类有：

15+15 15+14 15+13 15+12 15+11 15+1014+13 14+12 14+11 14+10 13+12 15+9据以上建模和其他约束条件可以推出至少需要12年时间将所有地区走完，具体路径如下：表4：模型一中十年旅行规划表旅行年数旅行次数旅行地方13青海山西河南23陕西吉林上海33内蒙古辽宁安徽43宁夏海南江苏53贵州广西甘肃63西藏新疆新疆72北京天津82黑龙江浙江92福建江西102山东湖北112湖南广东122重庆四川131云南由于地理位置的原因，游客可以自行调整旅游时间相同的地方自行旅游。由以上结果可以推出至少需要12年完成旅行，具体旅行路线与上述求得的每个省市内部旅游地点的安排有着密切的联系。下面以山西省为例给出具体的行程安排，其中包括每一天的出发地、行车时间、行车里程、游览景区及游览景区时间，其他省市类似布置每天的具体旅行行程。表5：模型一旅程具体行程安排表天数出发地行车时间行车路程游览景区景（天数）1上午西安市8720无02上午4360太原市13下午太原市4344晋城阳城县皇城相府生态文化旅0.5游区4下午晋阳市4299晋中市介休市绵山风景名胜区0.55下午介休市0.534晋中市平遥县平遥古城景区0.56上午平遥县0.532晋中市乔家大院文化园区0.56下午乔家大4361大同云冈石窟0.5院7下午大同4257忻州五台山风景区19上午忻州180太原09上午太原780西安0问题二模型的建立和求解问题二模型的建立问题二中该旅游者在出游的交通工具上有多种方式可选，考虑到附件4和附件5中提供的从旅游者所在的西安市到各省会城市的航班和高铁信息，为了简化模型，我们考虑有三种出游方式。第一种是问题一中的高速优先的全程自驾方式；第二种是先有西安市乘坐高铁到达与景区相邻的省会城市，而后采用租车的方式自驾到景区游览；第三种是是先有西安市乘坐直达航班（注：为了节约出游时间，只考虑从西安市直飞各个省会城市的情况）到达与景区相邻的省会城市，而后采用租车的方式自驾到景区游览。由问题中一中所建立的TSP问题模型中，采用改良圈算法给出了各省份内最短路径及其最短路径长度，确定了各个省份旅游景区的游览时间及具体行程安排，加上由此会产生的住宿费用及门票费用。因为三种出游方式在各个省份内部产生的交通费用，除了第一种全程自驾会多出每天300元的租车费用外，其余的交通费用都一致；交通费用产生差异最大的地方是在从西安市到各个省会城市之间的旅程中，依据不同的自驾、高铁、航班产生不同的交通费用。又依据问题二中描述，要规划出能在10年游遍5A级景区的、费用最优、旅游体验最好的旅游路线。为了更好的建立模型，将旅游体验最好这个准则层量化成为旅行中在交通工具上所花费的时间最短。对这两个准则层，在高校附近采用随机市场调查，填写问卷报告用联测法分析判断预测该地区人群对旅行中的这两个准则层的权重，加权予以权衡这两个指标，从而建立数学规划模型设计出十年内游遍所有5A级景区、费用最优、旅游体验最好的旅游路线，随后依据问题二中相关规定限制条件，规划出这十年间具体的旅游行程费用。图3：费用、时间的层次分析图问题二模型的求解对费用最优与旅游体验最好（具体量化为旅行中在交通工具上所花费的时间最短）两个准则层，利用层次分析法，通过上述调查分别取其权重为：%=%=0.3,叱=0.7权重和为:考虑第一种出行方式（全程自驾）：1考虑第一种出行方式（全程自驾）：1 _) 」)X1+DmX0.6+Pm入WXrm+Tm/考虑第二种出行方式（西安高铁到省会城市，后自驾）：TOC\o"1-5"\h\z4 \.C）3 1 《八）A=WXpmX3+、m+tm>X300+Pm与WXpm+Tm，2 1 1 1 2 2考虑第三种出行方式（西安航班到省会城市，后自驾）：/ 、, （/）…1CT）A=WXpmX3+tfm+tmX3300+Pm斗WXI-m十Tm/3 1 2 1 2 2依据附件2、3及查阅百度地图相关信息可统计出Dm,Dm的数据，由模型一的求解过程得出：表6：模型二的十年旅行规划表旅行年数旅行次数旅行地方13北京天津山西24内蒙古辽宁吉林黑龙江33上海江苏广西43浙江安徽海南53福建江西青海63山东河南陕西73湖北湖南宁夏82广东四川93重庆贵州甘肃103西藏新疆表7：模型二的旅程具体行程安排表天数出发地费用路途时间游览景区游览时间（h）1西安1546.55.5北京12天中午北京27000天坛0.53天上午北京00颐和园0.53天下午北京00恭王府景区0.54天北京701.5八达岭-慕田0.5峪4天下午北京市延庆310.5明十三陵0.5县5天上午北京市昌平区2503承德避暑山庄16天下午承德2923秦皇岛18天上午北京2293奥林匹克公园19天上午北京00故宫1注：其余省市的旅程具体行程安排表类似可知。问题三模型的建立和求解问题三模型的建立由于旅游者在出游的交通工具上有多种方式（高速优先的全程自驾方式、先由北京市乘坐高铁到达与景区相邻的省会城市再采用租车的方式自驾到景区游览、是先有北京市乘坐直达航班（为了节约出游时间，只考虑从西安市直飞各个省会城市的情况）到达与景区相邻的省会城市再采用租车的方式自驾到景区游览）可选，在问题一所建立的TSP问题模型中，采用改良圈算法给出了各省份内最短路径及其最短路径长度，确定了各个省份旅游景区的游览时间及具体行程安排，加上由此会产生的住宿费用及门票费用。因为三种出游方式在各个省份内部产生的交通费用，除了第一种全程自驾会多出每天300元的租车费用外，其余的交通费用都一致；交通费用产生差异最大的地方是在从北京市到各个省会城市之间的旅程中，依据不同的自驾、高铁、航班产生不同的交通费用。又依据模型二中描述，要规划出能在10年游遍5A级景区的、费用最优、旅游体验最好的旅游路线。为了更好的建立模型，将旅游体验最好这个准则层量化成为旅行中在交通工具上所花费的时间最短。对这两个准则层，在高校附近采用随机市场调查，填写问卷报告用联测法分析判断预测该地区人群对旅行中的这两个准则层的权重，加权予以权衡这两个指标，从而得出从北京到其他省会的最佳交通方式，然后运用Java程序设计出十年内从北京出发游遍所有5A级景区、费用最优、旅游体验最好的旅游路线，随后中相关规定限制条件，规划出这十年间具体的旅游行程费用。问题三主要模型的求解对费用最优与旅游体验最好，旅游体验最好即量化为旅行中在交通工具上所花费的时间最短两个准则层，利用层次分析法，通过上述调查分别取其权重为叱=0.3,叱=0.7。权重和1考虑第一种出行方式（全程自驾）：A=WXD^)m),A=WXD^)m义1+Dm义0.6+Pm4W*Im+Tm考虑第二种出行方式（北京高铁到省会城市，后自驾）4I。（，）。…1CT）A=WXpmX3+、m+tm4300+Pm4WXI'm+Tm，2 1 1 1 2 2TOC\o"1-5"\h\z考虑第三种出行方式（北京航班到省会城市，后自驾）/ 、\o"CurrentDocument"4 「°（）…1 '）A=w义甲m义3+¥m+tm4300+Pm4W义Pm+Tm，3 1 2 1 2 2依据附件2、3及查阅百度地图相关信息可统计出Dm,Dm的数据，利用模型二的算法求解得出常住地在北京市的自驾爱好者十年的旅游计划（见表8），此模型可推广至全国任意省会市或地区作为常住点，利用该算法求解出旅行者相应的十年旅行计划。表8：模型三的十年旅行规划表旅行年数旅行次数旅行地方14北京天津山西内蒙古24辽宁吉林黑龙江上海33江苏浙江广西44安徽福建海南西藏53江西山东湖南63河南湖北青海73广东重庆贵州83四川云南陕西93甘肃宁夏新疆4.3.3 问题三给旅游者和旅游部门的建议随着中国国民经济的不断增长，居民生活水平日益提高，旅游服务业及相关产业规模越来越完善。近年来不断兴起的“旅游热”、“自驾潮”“间隔年”，使得居民对旅游产业需求越来越大，国民的旅游消费行为也因此变得多元化，有更多倾向于个性化的过程。我国服员辽阔，国家评定的5A级旅游景区遍布全国31个省市州。再加上旅游者的不足、旅游时间不够灵活，旅游经费有限。要想在最短的时间内游遍201个5A级景点，提前做好旅游规划相当有必要，但目前我国居民对旅行缺乏具体规划观念。针对上述三个问题模型的求解分析，并针对我国旅游业发展状况给旅游爱好者和旅游相关部门提出以下建议。针对旅游爱好者的建议：.在旅行开始前，针对自己预期旅游费用、旅行时间及期望目的地，从网络查找各类有用资源进行整合，如蚂蜂窝、百度旅游、途牛旅行网等，然后自己做一份详细的旅行规划表。这能从极大程度上节约旅行成本及旅行时间。同时也能增长对旅游地人文知识的了解。.自驾旅游者应该严格控制每天自驾时间，避免疲劳驾驶，同时关注天气变化、路况、车况及路线拥堵情况的实时信息，提前标记沿途加油站及时补及汽车燃油。注意旅途中行车安全，谨记交通法规。.鉴于旅游出行方式多样化，可根据旅游者自身旅游时间及旅游预期费用，综合比较后合理选择出行方式。比如从北京到拉萨若选择自驾，按每天8小时驾驶时间计算，来回至少需要十天自驾时间，这期间将产生大笔的旅游费用（燃油费、过路费、食宿费等）。这时就可选择乘坐飞机。针对旅游相关部门的建议：.每个旅游者都有自己关于旅行天数、费用、出游方式、景区级别、目的地及景区性质的不同预期，然而市面上尚没有基于旅游爱好者个性化的旅游行程规划服务，旅游部门应该注重对旅游者个性化旅游行程规划服务产业的开发，让用户在提供以上旅行的约束条件后，能依据用户需求制定出详细的行程安排表，也即基于用户生成数据的旅游线路规划，让旅行规划个性化和实用化。.目前能提供的都是景区间的旅游规划，关于景点内部的线路选择和时间分配是个空白，需要旅游相关部门做工作加以完善，给旅游者提供更加全面的信息。.每个旅游景区都有一个最大游客容纳量，为了更好分散游客避免个别景区拥堵现象，旅游部门可利用手机GPS定位，为旅游者提供实时景点人数及景区附近地理位置图等及时反馈信息。4.4问题三模型的建立和求解问题三模型的建立用现有的蚁群算法对线路规划将使得景区的负载不均衡，若采用这种算法得到的最优路径旅游必然导致某些景点人数激增，而部分景点人数却很少。考虑改进蚁群算法，加入动态规划，将每个景区对游客的容纳量及才时刻景区的人流量加入其中，从而可以很好的实现旅游景区的负载均衡。问题四中在问题三的基础上加入了国家4A级景区，考虑旅游者的旅行时间及旅行费用均有限的情况下，要尽可能多的去游览附件1和附件7中的国家级5A和4A级风景区。即在给定时间和费用前提下，游览更多景点。因此模型的目标函数为：Maxn设a为给定的旅行时间，B为给定的旅行费用就有了约束条件。又通过对附件6、附件7的分析我们发现国家5A级景区和国家4A级景区太多，所以我们不能一次旅行完所有的景区，我们采用模型一的方法对全国各地的景区按省分块进行旅行，由于省内的景点也很多，并且旅行者受每次旅行时间的限制，不可能游完省内所有的4A和5A级景点。又因为当旅游者游览完第m个省的第i个景点后，在决策接下来是否该去第j个旅

游景点时，将受到第j个旅游景点的该时刻的旅客流量，从景点i到景点j的景区路线长度及当前剩余旅游费用的限制。所以考虑这三个影响因素对旅游者决策的影响。依据景点在/时刻游客流量及其承载量，定义以下游客量的函数关系式：Pj1Timax如果P越大，则说明景区在t时刻的游客能承载的游客流量越多，相反P越小，则1 1说明t时刻的游客流量越少。对于从景点i到景点j的景区路线长度，定义以下线路函数关系式：P2=L如果P越大则说明景点i距离景点j的旅游路线越长，相反P越小说明景点i距离景点j的旅游路线越短。对于旅游费用方面，定义了以下函数关系式:1—j)Yj如果P3越大说明前几个地点花费的费用越多，当前所剩旅游费用越少；相反P3越小则说明旅游者在这之前旅行中花费越少。由以上函数关系式知因变量和自变量成正比，由此旅行者在游览完第i个旅游景点后便能够依据以下0-1判别式来做决策是否接下来去第j个旅游景点游览:<0.5TOC\o"1-5"\h\zP+P+P-1 □ 2.<0.512 33X表示接下来是否去第j个旅游景区游览，如果x=1表示接下来去第j个旅游景区i i游览，若X,=0则表示不去。由此便可以动态的求解得出该省内哪些景区是要去的，哪些景区是不被旅行者考虑的。也即动态的产生出该省内的旅游路线的规划。然后将这31个省份看成节点，再运行模型一中编写的java语言求解出具体的旅行规划路线。举例说明动态规划过程如下：如某省内有/4，4,&四个景区，从A］景区出发，按上述改进后的蚁群算法在A，A3,A4景点中按顺序筛选出符合如何01判别式的景区A2，然后从重复筛选过程从A3,A4中筛选，直到把省内所有景区按序筛选完毕。图4：动态规划过程图五、模型的优缺点5.1模型的优点.本文正确、清楚地分析了题意的基础上，建立了合理、科学的数学模型。对旅游线路的设计进行了合理的假设，简化了一些不必要的因素，把问题转化成图论中TSP问题，利用Lingo软件，大大减少了计算过程。.在所建的模型中以旅行时间为基础，考虑了旅行中不能忽视的费用问题，考虑两者不能同时兼顾，采用层析分析法加权计算，符合实际情况。.在问题四中将建立的线路规划模型中，该算法考虑了各个景区的最大游客容纳量及/时刻景区的游客量，提出了路线的动态规划算法。考虑了与实际密切联系，并且结合实际解决问题，使得模型具有很好的广泛性和适用性。.2模型的缺点.在模型中的景区游览时间只考虑了旅游者在各个景区的最少逗留时间，以及假设交通通畅、等待交通工具的时间忽律不计，在各个省份内的旅游均考虑为从省会城市出发，这些使得我们的模型有一定的局限性。如要作为旅游规划的参考，还需进一步深入研究。.模型中线路设计时所考虑的因素还可以加入交通状况、旅游者年龄、身体状况、旅行者的心理因素及满意度等。.由于时间有限，针对问题四中5A及4A级国家风景区的规划中对多种交通方式的并行使用情况下旅游线路规划问题的思考还不是很成熟。

参考文献［1］尹华罡，基于海量时空数据的路线挖掘与检索［D］,中国科学技术大学，2013.1［2］司守奎，孙奎菁，数学建模算法与应用［M］，北京：国防工业出版社，2001.8：37-82［3］曹旭，旅游线路优化设计研究2012［D］.，西北民族大学，2013.5［4］姜启源，谢金星，叶俊，数学模型（第四版）［M］，北京：高等教育出版社，2011.1［5］王庚，王敏生，现代数学建模方法［M］，北京：科学出版社，2008：82-121［6］王徐民，方玉平，，张慧慧,，旅游线路优化设计J］，中国矿业大学，2012.8［7］佟欣，孙仲强，徐斌，黑龙江省旅游路线优化设计J］，大庆师范学院，2000.9［8］曹旭，马茜，马少仙，最短路问题在旅游线路优化中的应用J］，科技广场，2012.2［9］栗雪娟，崔尚森，张柯，最佳旅游路线选择的神经网络方法J］，长安大学［10］徐锋，基于PDA的旅游导航系统的研究与实现［D］，北京邮电大学网络，2011［11］百度地图，网站：附录山西省内最短路径Lingo运行结果如下:O口七149E1a-p3ed.B-i-ixvtimeCh±LO口七149E1a-p3ed.B-i-ixvtimeCh±L：mm：mm1Emt.c：ri-'ic：d.Solb。t-St.■二Sol^et- B-ancd—BB后三比 1407ObjB口二 14075t.ape: 0Active： □论文中的模型所用程序如下:程序1：model:sets:city/1..7/:u;!u(i)=sequenceno.ofcity;link(city,city):dist,!thedistancematrix;x;!x(i,j)=1ifweuselinki,j;endsetsdata:!distancematrix,itneednotbesymmetric;dist=027680344135861072760257620411361382802570531322272293344620531029935132413541132229906134863612723516103210738229332434320;enddata!themodel:ref.desrochers&laporte,orletters,feb.91;n=@size(city);min=@sum(link:dist*x);@for(city(k):!itmustbeentered;@sum(city(i)|i#ne#k:x(i,k))=1;!itmustbedeparted;@sum(city(j)|j#ne#k:x(k,j))=1;!weakformofthesubtourbrekingconstraints;!thesearenotverypowerfulforlargeproblems;@for(city(j)|j#gt#1#and#j#ne#k:u(j)>=u(k)+x(k,j)-(n-2)*(1-x(k,j))+(n-3)*x(j,k)));!makethex's0/1;@for(link:@bin(x));!forthefirstandlaststopweknow...;@for(city(k)|k#gt#1:u(k)<=n-1-(n-2)*x(1,k);u(k)>=1+(n-2)*x(k,1));End程序2： （java程序）packageHmath;//此程序用于实现将几个省分在一年旅行，分法必须保证每次旅行不超过15天，一年不过4次，一年总天数不超过30天publicclassarray{publicstaticvoidmain(String[]args){int[]s={8,9,8,4,5,5,0,10,10,12,11,11,10,10,13,13,10,10,6,5,10,13,6,10,3,7,9,5,4,14}；//初始化数组int[]x=newint[30];for(inti=0;i<x.length;i++){x[i]=0;}intsum=0;inty=0;for(inti=0;i<s.length;i++){System.out.println("%%%%%"+sum);if(sum<=30&&x[i]==0&&y<=3){sum=sum+s[i];y++;x[i]=1;System.out.print("#"+i+"#"+s[i]+"");}for(intj=i+1;j<s.length;j++){if(sum<=30&&y<=3&&x[j]==0){sum=sum+s[j];if(sum<=30){System.out.print("#"+j+"#"+s[j]+"");x[j]=1;y++;}else{sum=sum-s[j];}}if(j==s.length-1){System.out.println(sum+"ffff");sum=0;y=0;}}}怎样写作数学建模竞赛论文一如何建立数学模型一建立数学模型的涉骤和方法建立数学模型没有固定的模式，通常它与实际问题的性质、建模的目的等有关。当然，建模的过程也有共性，一般说来大致可以分以下几个步骤：.形成问题要建立现实问题的数学模型，首先要对所要解决的问题有一个十分明晰的提法。只有明确问题的背景，尽量弄清对象的特征，掌握有关的数据，确切地了解建立数学模型要达到的目的，才能形成一个比较明晰的“问题”。.假设和简化根据对象的特征和建模的目的，对问题进行必要的、合理的假设和简化。现实问题通常是纷繁复杂的，我们必须紧紧抓住本质的因素（起支配作用的因素），忽略次要的因素。此外，一般地说，一个现实问题不经过假设和简化，很难归结为数学问题。因此，有必要对现实问题作一些简化，有时甚至是理想化.模型的构建根据所作的假设，分析对象的因果关系，用适当的数学语言刻画对象的内在规律，构建现实问题中各个量之间的数学结构，得到相应的数学模型。这里，有一个应遵循的原则：即尽量采用简单的数学工具。.检验和评价数学模型能否反映原来的现实问题，必须经受多种途径的检验。这里包括：（1）.数学结构的正确性，即有没有逻辑上自相矛盾的地方；（2）.适合求解，即是否有多解或无解的情况出现；（3）.数学方法的可行性，即迭代方法是否收敛，以及算法的复杂性等。而更重要和最困难的问题是检验模型是否真正反映原来的现实问题。模型必须反映现实，但又不等同于现实；模型必须简化，但过分的简化则使模型远离现实，无法解决现实问题。因此，检验模型的合理性和适用性，对于建模的成败是非常重要的。评价模型的根本标准是看它能否准确地反映现实问题和解决现实问题。此外，是否容易求解也是评价模型的一个重要标准。.模型的改进模型在不断检验过程中经过不断修正，逐步趋向完善，这是建模必须遵循的重要规律。一旦在检验中发现问题，人们必须重新审视在建模时所作的假设和简化的合理性，检查是否正确刻画对象内在的量之间的相互关系和服从的客观规律。针对发现的问题作出相应的修正。然后，再次重复上述检验、修改的过程，直到获得某种程度的满意模型为止。.模型的求解经过检验，能比较好地反映原来现实问题的数学模型，最后将通过求解得到数学上的结果；再通过“翻译”回到现实问题，得到相应的结论。模型若能获得解的确切表达式固然最好，但现实中多数场合需依靠电子计算机数值求解。电子计算机技术的飞速发展，使数学模型这一有效的工具得以发扬光大。数学建模的过程是一种创造性思维的过程，对于实际工作者来说，除了需要具有想象力、洞察力、判断力这些属于形象思维、逻辑思维范畴的能力外，直觉和灵感往往不可忽视，这就是人们对新事物的敏锐的领悟、理解、推理和判断。它要求人们具有丰富的知识，实惯用不同的思维方式对问题进行艰苦探索和反复思考。这种能力的培养要依靠长期的积累。此外，用数学模型解决现际问题，还应当注意两方面的情况。一方面，对于不同的实际问题，通常会使用不同的数学模型。但是，有的时候，同一数学模型，往往可以用来解释表面上看来毫不相关的实际问题。另一方面，对于同一实际问题要求不同，则构建的数学模型可能完全不同。二写作数学建模竞赛论文应注意的问题：.论文格式论文的封面：题目 参赛队员： 指导教师：……单位： 论文的第一页是摘要，第二页开始是论文的正文，论文要有以下几方面的内容：.问题的提出.问题的分析.模型的假设.模型的建立.模型的求解.模型的检验.模型的修正.模型的评估.附录以上各部分内容应该都是要具备的，但有些步骤可以合并在一起。例如：问题的提出与问题的分析，模型的假设与模型的建立，模型的检验与模型的修正等。下面就每一步以及建模过程中应注意的几个问题作一简要介绍。2.审题：赛题一般有两道(研究生的竞赛有4道题)，我们可以从中任选一道，这就面临选哪道题合适的问题。因此，首先必需弄清题目的意义。数学建模的题目有时很长，有时很复杂。不易弄懂它的意义，一般要用几个钟头的时间才能弄清楚它的含义。因此我们要求：.深刻理解题意.弄清题目的实际背景(3)正确选择题目，根据自身的特长和优势作出决定。要注意不要被题目的繁长的叙述哧住，碰到长的题目要有耐心，要仔细的分析题目的各部分内容、条件和要求。选定题目后，接下来就应该是对题目进进一步的分析。下面的几项工作是必需要做的：.在弄清问题的背景下，说清事情的来龙去脉。.列出必要的数据，题目所给的数据往往是不够的，还要寻找题目以外的数据。.列出和题目相关的各种条件和变量，分清各变量之间的主从关系。.给出研究对象的关键信息内容。4.在分析问题的基础上，提出合理的假设模型是在假设的前提下建立起来的。对情景的说明不可能也不必要提供问题的每一个细节。由题目所提供的假设来建立数学模型还是不够的，还要补充一些假设。假设是建立数学模型很关键的一步，关系到模型的成败和优劣。所以应该仔细地分析实际问题，从大量的变量中筛选出最能表现问题本质的变量，并简化它们的关系。这部分内容就应该在论文的问题的假设部分中体现。由于假设不是实际问题直接提供的，它因人而异，所以，在撰写这部分内容时要注意以下几个方面：(1)论文中的假设要以严格、确切的数学语言来表达，使读者不致产生任何曲解。(2)所提出的假设确实是建立数学模型所必需的，与建立数学模型无关的假设只会扰乱读者的思考(3)假设应该是合理的；怎样的假设才是合理的呢？a.假设应合乎生活常识。b.假设不能与已知的科学定律相悖。c.假设必需是对建模有用的。d.尽量使用数学的语言。e.假设不要超出题目要求的范围。假设这一步是数学建模的一个难点，它关系到建模的成败和优劣，数学建模的假设就是要发挥每个人的想象力和创造力，提出适当的、合理的、有创新的见解。如果这一步成功了，那么你的整个建模过程也就成功了一半。5在假设的基础上下一步当然就是模型的建立。在建立模型之前要引进变量及其记号。每个字母所表达的确切含义。经过抽象，确切表达各变量之间的关系，用一定的数学方法，建立起方程式或归纳为其它形式的数学关系式，如图形、表格等。在建模过程中要注意以下几个问题：(1)要用分析和论证的方法，让读者清楚地了解得到建模的过程。(2)上下文之间切忌逻辑推理过程中跃度过大，影响论文的说服力。(3)需要推理和论证的地方，应该有推导过程且应该力求严谨。引用现成定理时，要先验证满足定理的条件。论文中用到的各种数学符号，必须在第一次出现时加以说明。.模型的求解把实际问题归结为一定的数学问题后，就要求解或进行分析，数学模型的求解多数是数值求解。在求解时应对计算方法有所说明。使用何种数学软件，给出计算程