B旅游线路的优化设计.doc

《B旅游线路的优化设计.doc》由会员分享，可在线阅读，更多相关《B旅游线路的优化设计.doc（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、【精品文档】如有侵权，请联系网站删除，仅供学习与交流B旅游线路的优化设计.精品文档.2011年南京邮电大学数学建模竞赛题 目 ： 旅游线路的优化设计摘要本文考虑的是旅游时间（费用）不受限制的情况下，如何安排旅游路线不重复且有返回的游览完所有景点，使得费用（时间）最少，以及费用（时间）受限制或两者都受限制时，如何安排不重复且有返回的路线使得游览的景点最多。（一）对优化模型的理解：路线优化模型：首先我们知道本问题属于旅游路线的优化问题。为了建立模型，首先应将各景点线路转化为纯数学形式的点线集合，进行图论方面的分析。本问题主要是解决两方面的问题：（1）、（2）两问是在时间或旅游费用不限的情况下，游完

2、十个景点怎样才可以做到费用最省或是时间最省；（3）、（4）、（5）问是在旅游时间或是旅游费用或是两者都有约束条件的情况下，怎样才可以玩更多的地方。根据对第一方面问题的分析可知，该问题属于旅行商问题（Traveling Salesman Problem,TSP）。对旅行商问题的理解：一位销售商从N个城市的某个城市出发，不重复的走完其余N-1个城市并回到原出发点，在所有可能路径中求出路径长度最短的一条。用图语言描述TSP：给出一个图G=（V，E），每边上有非负权值， 寻找G的Hamilton圈C，使得C的总权最小。在一定程度上，各景点间的距离与两点间的单程最省路费（单程最短时间）是成正比的，所以把

3、两景点的最省路（最短时间）作为权值是可行的。第二面要解决的问题是在费用（时间）有限制或两者都有限制的情况的情况下观赏的景点近可能多，根据这种要求可从这种方案入手：建立多目标规划模型，通过适当的拟合或线性加权，把多目标转化为单目标（二）综上所述，得到各种条件下的最优路线方案见表1.1： 表1.1问题结果旅游路线（1）3012元（2）9.4天（3）1954元7个景点（4）4.6天5个景点（5）1201元4.6 天3个景点 由于不同的网站公布的信息存在一定偏差，所以该结果仅依求解时提供的网站信息。【关键词】多目标规划 旅行商问题 Hamilton圈 线性加权 最优化一、问题重述随着人们生活水平的提高

4、，旅游逐渐成为最热门的户外活动之一。在旅游的过程中，我们不仅可以感受大自然之美、放松心情，而且可以领略不同地方的文化气息、拓宽视野。旅游者在今年五月一日8点之后从江苏徐州出发，到全国一些著名景点旅游，最后回到徐州。由于跟团旅游会受到限制，旅游者打算自己背包出游。出行路途中有以下几个条件：（A）城际交通出行可以乘火车（含高铁）、长途汽车或飞机（不允许包车或包及），并且车票或机票可预定到。（B）市内交通出行可乘公交车（含专线大巴、小巴）、地铁或出租车。（C）旅游费用以网上公布为准，具体包括交通费、住宿费、景点门票（第一门票）。晚上20：:00至次日早晨7：:00之间，如果在某地停留超过6小时，必须

5、住宿，住宿费用不超过200元/天。吃饭等其它费用60元/天。（D）假设景点的开放时间为8:00至18:00.根据以上条件考虑到旅游者的以下需求：1、在时间不限的情况下，游览全部景点，旅游费用最省；2、在旅游费用不限的情况下，游览全部景点，旅游时间最短；3、在旅游费用一定的情况下，游览尽可能多的景点；4、在时间一定的情况下，游览尽可能多的景点；5、在时间和旅游费用都一定的情况下，游览尽可能多的景点。针对以上几种情况，建立相关的数学模型并为该旅行者设计详细的行程表，行程表中应包括具体的交通信息（车次、航班号、起止时间、票价等）、宾馆地点和名称，门票费用，在景点的停留时间等信息。二、问题分析2.1问

6、题背景分析对于人们生活水平不断提高，越来越多的人会选择在节假日游览一下祖国的大好河山，领略一下各地的风土人情和人文气息。在旅游的时候人们往往会想，怎样才能花最少的费用、时间游览预订的地方，怎样设计路线才能在有限的费用、时间内游览更多的地方。这就需要我们建立高效实用的数学模型来解决这些问题。2.2对题目的理解首先我们知道本问题属于旅游路线的优化问题。为了建立模型，首先应将各景点线路转化为纯数学形式的点线集合，进行图论方面的分析。本问题主要是解决两方面的问题：（1）、（2）两问是在时间或旅游费用不限的情况下，游完十个景点怎样才可以做到费用最省或是时间最省；（3）、（4）、（5）问是在旅游时间或是旅

7、游费用或是两者都有约束条件的情况下，怎样才可以玩更多的地方。第一方面根据对第一方面问题的分析可知，问题目的在于当时间（费用）不限的情况下求游完所有景点并回到出发地点所用的费用（时间）的最小值。该问题属于旅行商问题（Traveling Salesman Problem,TSP）。为了建立数学模型，首先应该将各个景点转化为纯数学形式的点线的集合，进行图论方面的分析。下面给出旅行商问题的定义：旅行商问题：一位销售商从N个城市的某个城市出发，不重复的走完其余N-1个城市并回到原出发点，在所有可能路径中求出路径长度最短的一条。用数学语言描述TSP，即给定一组N个城市和它们两两之间的直达距离，寻找一条闭合

8、的旅程，使得每个城市刚好经过一次且总的旅行距离最短。用图语言描述TSP：给出一个图G=（V，E），每边上有非负权值w（e）， 寻找G的Hamilton圈C，使得C的总权最小。TSP问题是一个典型的组合优化问题，其可能的搜索路径随着城市数目N的增加呈指数增长，属于NP完全问题。了解了以上只是后，我们更加确定了该问题就是旅行商问题。只是在实际的处理中，我们把两景点的最省路费（最短时间）最为赋权值w（e），在一定程度上，各景点间的距离与两点间的单程最省路费（单程最短时间）是成正比的，所以把两景点的最省路（最短时间）作为权值w（e）是可行的。第二方面这一方面要解决的问题是在费用（时间）有限制或两者都有

9、限制的情况的情况下观赏的景点近可能多，根据这种要求可从以下方案入手：建立多目标规划模型，通过适当的拟合或线性加权，把多目标转化为单目标三、模型假设1、在旅游期间，天气晴朗，列车和航班没有延误并且准时到站，市内交通也没有出现长时间的堵塞2、该旅游者是成年人，不考虑学生票的问题3、旅游者在两地旅游来回时间和路上花的费用是相同的四、符号约定Xij 路线决策变量（01变量）Lij 从i地到j地的路费、路上的基本消费和需住宿时的住宿费用（单位：元） （i，j=1211）Pi 地区景点的第一门票费用（单位：元）（i=1，210）Pij i景点和j景点的门票费用之和（单位：元）（i=1，210）T 在景点所

10、在地区停留的时间，包括在景点的游玩时间和停留住宿等时间（单位：天）（i,j=1,211）A 每天的基本消费60（单位：元）M 旅游总共的消费（单位：元）S 旅游总共的用时（单位：小时）Sij i景点和j景点的所用时间之和，（单位：小时）（i=1，210）Tij 从i景点到j景点的时间，包括旅途是时间、停留等车时间、住宿时间（单位：小时）（i,j=1,211）Ti 在景点i的观光时间（单位：小时）（i=1，210） 五、模型建立与求解5.1 1、问题理解在时间不受限制的情况下，可游览完所有景点，要求消费总和最低。也就是说，从徐州出发，逐一观赏各景点，不能重复，然后再回到徐州，使得这一过程中总的花

11、费最少。这一过程中我们尽量选择便宜的交通工具。2、模型分析我们把各景点转化为纯数学形式的点线集合，利用图论方面的知识求解。为了达到旅游费用最低，交通方式的费用应采用最低，并且应该尽量避免住宿，因此我们采取晚上乘火车去下一个景点。现给出旅游景点门票费用，每天基本费用（吃饭等其它费用60元），市内交通（从火车站到旅游景点的双程费用）的最低费，见表5.1.1。表5.1.1旅游景点常州市恐龙园青岛市崂山八达岭长城祁县乔家大院洛阳市龙门石窟黄山市黄山武汉市黄鹤楼秦始皇兵马俑九江市庐山舟山市普陀山门票费用（元/人）160705040801505090180160基本费用606060606060606060

12、60市内交通29路（4元）304路（4元）地铁2号线换乘919快车（30元）直达车（20元）81路（4元）旅游班车（26元）10路（4元）306路（12元）102路（24元）轮船（28元）一天总计费用224元134元140元120元144元236元114元162元264元248元已经分析，该问题属于旅行商问题，这一过程中费用最省就是求最小路途费用的Hamilton圈。我们把两景点的最省路费最为赋权值w（e），在一定程度上，各景点间的距离与两点间的单程最省路费是成正比的，所以把两景点的最省路费作为权值w（e）是可行的。 影响消费的因素：路费住宿费基本消费门票费总费用目标函数的确定：用Lij表示i

13、景点到j景点的途中花费，并引入路线决策变量Xij1 经过i到j的路段0 不经过i到j的路段Xij=用Pj表示j地区景点的第一门票费用，T表示在景点所在地区停留的时间则总费用，则目标函数为：约束条件的确定: 由于每个景点只能有一条边出去，所以对j景点Xij之和影等于1，既： i=1,2.11 同理，每个景点只能有一条边进去，所以对i景点Xij之和也应等于1，既: i=1,211应该注意的是，除了起点和终点（都是徐州）以外，各边不构成Hamilton圈。3、模型建立综上分析，建立Hamilton圈的线性规划模型： min i=1,2.11 4、模型求解（注：上网查阅列车时刻表（ 表5.1.2费用(

14、元)徐州常州青岛北京祁县洛阳黄山武汉西安九江舟山徐州062130154179122159158159118176常州62015014018012573361165120193青岛1301500116120245360373363371422北京154140116094106182210210225493祁县179180120940184248379109337569洛阳12212524510618402878733125546黄山159733601822482870205206120200武汉158361373210379872050267177674西安1591653632101093320

15、62670207313九江1181203712253371251201772070169舟山1761934224935692462006743131690根据建立的模型，我们利用LINGO软件编程得到全局最优解为3012元，最佳的旅游路线如下：徐州常州市恐龙园黄山市黄山舟山市普陀山九江市庐山武汉市黄鹤楼洛阳市龙门石窟西安市秦始皇兵马俑祁县乔家大院八达岭长城青岛市崂山据此，我们为该旅游爱好者设计了详细的行程表，见表5.1.3：表5.1.3起止地点列车车次列车起止时间列车票价游览行程徐州常州13485月1日 21:4303:3462元乘29路至常州市恐龙园，门票120元，在恐龙园大约停留9个小时常

16、州黄山K84185月2日20:025月3日06:5573元乘旅游班车至黄山，门票150元，在黄山大约停留10个小时黄山鹰潭22395月3日20:565月4日03:3130元乘船至舟山市，转乘27路公交车到达，门票160元，在普陀山大约停留7个小时鹰潭宁波东K4745月4日23:045月5日06:4077元宁波舟山乘船5月5日上午33元舟山宁波乘船5月5日下午15:0033元乘102路至庐山，门票180元，在庐山大约停留9个小时宁波杭州D31085月5日16:1517:4246元杭州九江K2535月5日18:035月6日03:4790元九江十堰K10785月6日19:155月7日05:4353元

17、乘10路车到武汉黄鹤楼，门票50元，大约停留5个小时十堰武汉T2585月7日23:455月8日06:0664元武汉洛阳K8625月9日00:3009:2687元乘81路车至龙门石窟，门票80元，大约停留5个小时洛阳西安10455月9日22:335月10日03:5733元乘306旅游专线至秦始皇兵马俑，门票90元，大约停留6个小时西安太原T425月10日18:205月11日03:3486元乘直达车至祁县乔家大院，门票40元，大约停留4个小时太原祁县24625月11日05:0006:0823元祁县北京26045月11日13:335月12日04:0094元乘地铁2号线，再转乘919快车，门票50元，

18、大约停留6个小时北京青岛T255月12日22:485月13日07:38116元乘304路至崂山，门票70元，在崂山内大约停留7个小时青岛徐州K705月13日19:105月14日05:06130元到家（注：该行程的设置使得夜间的住宿均在火车上）5.21、问题理解在费用不受限制的情况下，可游览完所有景点，要求所用的时间最短。也就是说，从徐州出发，逐一观赏各景点，不能重复，然后再回到徐州，使得这一过程中所用时间最少。这一过程中我们尽量选择高速的交通工，并且将在旅游景点停留的时间设为最短的符合要求的时间。2、模型分析我们把各景点转化为纯数学形式的点线集合，利用图论方面的知识求解。已经分析，该问题属于旅

19、行商问题，这一过程中时间最省就是求最省时间路线的Hamilton圈。我们把两景点的最短时间（包括旅途中的时间和停留、住宿的时间）作为赋权值w（e），在此，我们把两景点间的时间类比于旅行商问题中的路程，所以把两景点的最短时间作为权值w（e）是可行的。影响总时间的因素： 旅途时间住宿时间停留观光时间总时间目标函数的确定：用Tij表示从i景点到j景点的时间，包括旅途是时间、停留等车时间、住宿时间（单位：小时）（i,j=1,211）Ti表示在景点i的观光时间（i=1，210）则总时间，既目标函数为：约束条件的确定 由于每个景点只能有一条边出去，所以对j景点Xij之和影等于1，既： i=1,2.11 同

20、理，每个景点只能有一条边进去，所以对i景点Xij之和也应等于1，既: i=1,211应该注意的是，除了起点和终点（都是徐州）以外，各边不构成Hamilton圈。3、模型建立综上分析，建立Hamilton圈的线性规划模型： i=1,2.11 4、模型求解 根据网上查阅列车时刻表（），航班时刻表（表5.2.1时间（h）徐州常州恐龙园崂山八达岭长城乔家大院龙门石窟黄山黄鹤楼秦始皇兵马俑庐山普陀山徐州024242429.6825.752424242424常州恐龙园24017.317.317.317.317.317.310.8317.7315.5崂山2417.3016.31719.2516.31.751

21、6.2513.0814.25八达岭长城2417.316.3018.581.7513.422.172.8312.7522.83乔家大院29.6817.31718.5803842.2539.43143838.3龙门石窟25.7517.319.251.753806219.214.67178717黄山2417.316.313.4242.4540.7015.6716.173814.3黄鹤楼2417.31.752.1739.4319.215.67016.31414.3秦始皇兵马俑2410.8316.252.831414.6716.1716.303814.3庐山2417.7313.0812.753817.8

22、7381438014.67普陀山2415.514.2522.8338.31714.314.314.314.670 根据建立的模型，我们利用LINGO软件编程得到全局最优解为7.7天（其中在景点停留的时间按最短时间计算）。据分析，该游客在无车离开时可以在景点停留更多的时间，因此此结果偏小。可以通过开往下一景点的车次时刻表，计算出该游客在景点区或车站（包括机场）停留的时间。所以通过车次（航班）时刻表查询可得出的最短天数为9.4天。最佳的旅游路线如下：徐州常州恐龙园祁县乔家大院秦始皇兵马俑洛阳市龙门石窟八达岭长城黄山市黄山舟山市普陀山九江市庐山青岛市崂山武汉市黄鹤楼据此，我们为该旅游爱好者设计的详细

23、行程表，见表5.2.2：表5.2.2起止地点列车车次（或航班号或汽车）起止时间票价游览行程住宿情况徐州黄山K1745月1日10：5213:4599元乘旅游班车到达黄山，门票150元，在景点大约停留了9小时住在黄山假日酒店（黄山市屯溪区浣江中路4号）118元黄山上海FM92685月2日22:30-23:30580元乘27路至普陀山，门票160元，在景点大约停留6小时5月2日晚住在上海吉泰连锁酒店（闸北区中心北路1038号）108元上海舟山MU56435月3日07：2508:20740元舟山上海FM94265月3日15:4016:25740元乘102路至九江，门票180元，在景点大约停留8小时5月

24、3日晚住在九江格林豪泰连锁酒店（九江市长虹大道280号）130元上海九江FM92715月3日19:3020:50710元九江上海FM92305月4日17：4519:05740元乘304路至崂山，门票70元，在景点大约停留6个半小时5月4日晚住在青岛人湶宾馆（青岛市南区湖南路64号）120元上海青岛FM92715月4日19:3020:50710元青岛武汉C236325月5日15:5518:001000元乘10路至武汉，在景点大约停留2小时5月5日晚住在武汉天都时尚宾馆（武汉市汉口沿江大道17码头门楼）138元武汉北京CA13345月6日10:4012:351080元乘地铁2号线换乘919快车到达

25、，大约停留4小时无北京洛阳MU52275月6日19:2021:05860元乘81路至洛阳，在景点大约停留3小时5月6日晚住在洛阳易家国际青年旅舍（洛阳市中井东路329号）120元洛阳西安长途汽车5月7日12：2016:4069元乘306路到达，在景点大约停留2小时5月7日晚住在西安美宝宾馆后宰门店（西安市新城区后宰门3号）138元西安北京MU56965月8日10:2511:45860元乘直达车到达乔家大院，在景点大约停留3小时5月8日晚住在平遥程家老院民俗宾馆（山西晋中市平遥县城内北大街125号）108元北京太原MU52965月8日13:2514:25590元太原祁县10955月8日19:14

26、20:277元祁县太原10965月9日12:2913:478元乘29路至恐龙园，在景点大约停留4小时5月9日晚住在动车上太原北京MU52955月9日15:3016:40590元北京常州D3095月9日21:1606:00290元常州徐州K5165月10日13:3119:3370元到家5.31、问题理解在游客准备了2000元旅行费的情况下，想尽可能多的游览景点，要求游览的景点数最多。也就是说，从徐州出发，尽量观赏多个景点，不能重复，然后再回到徐州，使得这一过程中所的费用不超过2000元。在这一过程中我们不仅要考虑到景点所用的车费，还要考虑景点的门票费用，使得这两者相加起来尽可能的少。在去景点的过

27、程中要尽量选择火车作为的交通工具。2、模型分析我们把各景点转化为纯数学形式的点线集合，利用图论方面的知识求解。已经分析该题是已知费用的最大限度求最佳路径问题，因此要选择到下一景点总的最低费用作为去下一景点的前提条件且剩余费用要足够回到徐州。如前面模型，我们把两景点的最省路费作为赋权值，在一定程度上，各景点间的距离与两点间的单程最省路费是成正比的，因此把两景点的最短路费作为权值是可行的。影响景点数的因素： 旅途坐车费用住宿、基本费用门票费用不多于2000元的费用费用 目标函数的确定：假设总费用未知，但满足条件（常州13485月1日21:435月2日03:3462元乘29路至常州市恐龙园，门票12

28、0元，在恐龙园大约停留9个小时在火车上住宿常州西安T525月2日20:535月3日12:24165元乘 306路到达，门票90元，在景点大约停留4小时在火车上住宿西安太原T425月3日18:205月4日03:3486元乘直达车到达，门票40元，在景点大约停留4小时在车上住宿太原祁县24625月4日05:0006：0823元祁县北京26045月4日13:335月5日04:0094元乘地铁2号线，再换乘919快车，门票50元，在景点大约停留8小时在车上住宿北京青岛T255月5日22:485月6日07:38116元乘304路到达，门票70元，在景点大约停留7小时在车上住宿青岛郑州K2085月6日16

29、:155月7日05:40140元乘10路车去黄鹤楼，门票50元，在景点大约停留7小时5月7日晚住在武汉天都时尚宾馆（武汉市汉口沿江大道17马头门楼）105元郑州武汉D1235月7日14:4818:3468元武汉邯郸K5225月8日16:2001:52103元到家邯郸徐州K2335月8日15:3622:4982元经计算，此路线的总费用为1954元（小于2000元），共玩了六个景点。5.4 1、问题理解在游客只有五天可以旅游的情况下，想尽可能多的游览景点。也就是说，从徐州出发，在仅有的时间内尽量观赏多个景点，不能重复，然后再回到徐州，使得这一过程中所到的景点数最多。在这一过程中我们不仅要考虑到坐车

30、、等车行程中所用的时间，还要考虑到在景点停留的时间，要使得这两者相加起来尽可能的少。因此再在去景点的过程中要尽量选择飞机作为交通工具，且尽量减少转机（转车）次数。2、模型分析我们把各景点转化为纯数学形式的点线集合，利用图论方面的知识求解相应问题。已经分析该题是已知确定的时间限制求解最佳路径问题，因此要考虑到在时间最充分利用的前提下五天之内回到徐州。如前面模型，我们把两景点的最省时间作为赋权值w（e），在一定程度上，各景点间的距离与两点间的单程最省路费是成正比的，因此把两景点的最短时间作为权值w（e）是可行的。影响景点数的因素：坐车（飞机）、转车（转机）时间旅馆住宿时间旅游景点观赏停留时间不多于

31、五天的时间费用目标函数的确定：假设游玩的天数未知，用S表示，但满足条件（九江K6145月1日21:065月2日07:0758元乘102路到达庐山，在景点大约停留8小时在车上住宿九江南昌D63775月2日17:1818:1342元乘81路到龙门石窟，在景点大约停留4小时在车上住宿南昌洛阳K7905月2日19:075月3日09:26130元洛阳北京K2705月3日19：285月4日05:57106元乘地铁2号线，再转乘919快车，在景点大约停留3小时在车上住宿北京西安CA12235月4日12:3014:251050元乘306旅游专线到达，在景点大约停留2小时无住宿西安常州K3785月4日17:20

32、5月5日11:39165元乘29路车到达恐龙园，在景点大约停留5小时在车上住宿常州徐州T1385月5日17:3922:1370元到家从图中可知该旅客5月5日24时之前已经到家，总共玩了五处景点。5.51、问题理解基于对三、四问题的分析下，在游客只有五天时间和2000元费用可以旅游的情况下，想尽可能多的游览景点。也就是说，从徐州出发，在仅有的时间和有限的经费内尽量观赏多个景点，不能重复，然后再回到徐州，使得这一过程中所到的景点数最多。在这一过程中我们不仅要考虑到坐车、等车行程中所用的时间和费用，还要考虑到在景点停留的时间和门票费，要使得这两者相加起来尽可能的少。因此要综合考虑三、四两种情况。 2

33、、模型分析我们把各景点转化为纯数学形式的点线集合，利用图论方面的知识求解相应问题。已经分析该题是已知时间限制和费用制约的前提下求解最佳路径问题，因此要考虑到能充分利用五天时间和2000元费用回到徐州。在时间和费用都有约束的条件下，选择一个作为约束条件，减少目标规划。目标函数的确定： 假设总费用未知，用M表示，但满足条件（=2000元）假设游玩的天数未知，用S表示，但满足条件（常州12305月2日10:0915:57160元乘29路至常州市恐龙园，门票120元，在恐龙园大约停留6个小时5月1日晚住在常州蓝色快舟营销人连锁店（常州市 博爱路50号）120元常州西安K3605月3日14:2509:2

34、090元乘 306路到达，门票90元，在景点大约停留4小时无住宿西安北京T425月4日18:2009:02150元乘地铁2号线，再换乘919快车，门票50元，在景点大约停留8小时在车上住宿北京徐州T315月5日15：3923:05106元到家由表格可知总共用时4.6天，共花费金额为1201元。六、模型评价 （1） 问题一、二建立了单目标的优化模型，将各景点的路线转化为纯数学形式的点线集合，进行了图论方面的分析，同时经过适当的线性加权，还将各景点的门票、每天的基本费用和市内交通费用考虑在内，增加了模型的实用性。 （2） 问题三、四和五则有了条件的约束，在问题一、二模型的基础上，增加了该旅游者对旅游路线意向的考虑，变成不目标优化问题，求解比较复杂，所以模型中通过拟合或先行加权把多目标优化转化为较简单的单目标优化，求得了合适的旅游路线，比问题一、二的模型更能适用于实际生活。 （3）在建立费用最少模型时，我们把两景点间的交通费用、住宿费用、每天的基本费用和门票费用作为边