旅游线路的设计.docx

2012年安徽省建模竞赛题目：旅游线路的优化设计摘要本文考虑的是旅游时间费用）不受限制的情况下，如何安排旅游路线不重复且有返 同的游览完所有景点，使得费用时间）最少，以及费用时间）受限制或两者都受限制 时，如何安排不重复且有返回的路线使得游览的景点最多。（一）对优化模型的理解：路线优化模型：首先我们知道本问题属于旅游路线的优化问题。为了建立模型，首先 应将各景点线路转化为纯数学形式的点线集合，进行图论方面的分析。本问题主要是解决两方面的问题：1）、2）两问是在时间或旅游费用不限的情况下， 游完十个景点怎样才可以做到费用最省或是时间最省；3）、4）、5）问是在旅游时间或 是旅游费用或是两者都有约束条件的情况下，怎样才可以玩更多的地方。根据对第一方面问题的分析可知，该问题属于旅行商问题f Traveling Salesman PrObIem,TSP）。对旅行商问题的理解：一位销售商从N个城市的某个城市出发，不重复的 走完其余N-I个城市并回到原出发点，在所有可能路径中求出路径长度最短的一条。用图 语言描述TSP：给出一个图G=V, E）,每边e E上有非负权值w（e）,寻找G的Hamilton 圈C,使得C的总权W（C）= Z¼<e）最小。在一定程度上，各景点间的e=E（c）距离与两点间的单程最省路费单程最短时间）是成正比的，所以把两景点的最省路最 短时间）作为权值w（e）是可行的。第二面要解决的问题是在费用时间）有限制或两者都有限制的情况的情况下欣赏的 景点近可能多，根据这种要求可从这种方案入手：建立多目标规划模型，通过适当的拟合 或线性加权，把多目标转化为单目标问题结果旅游路线11)3012 元徐州常州市恐龙园黄山市黄山舟山市普陀山九江 市庐山武汉市黄鹤楼洛阳市龙门石窟西安市秦始皇 兵马俑祁县乔家大院八达岭长城青岛市崂山徐州12)徐州黄山市黄山舟山市普陀山九江市庐山青岛市崂山 武汉市黄鹤楼八达岭长城洛阳市龙门石窟西安市秦始 室兵马俑祁县乔家大院常州市恐龙园徐州13)1954 元7个景点徐州常州市恐龙园西安市秦始皇兵马俑祁县乔家大院 八达岭长城青岛市崂山武汉市黄鹤楼徐州14)5个景点徐州九江市庐山洛阳市龙门石窟八达岭长城 西安市秦始皇兵马俑常州市恐龙园徐州1201 元4. 6天3个景点徐州常州市恐龙园西安市秦始皇兵马俑 八达岭长城徐州由于不同的网站公布的信息存在一定偏差，所以该结果仅依求解时提供的网站信息。【关键词】多目标规划 旅行商问题 HamiltOn圈线性加权 最优化一、问题重述随着人们生活水平的提高，旅游逐渐成为最热门的户外活动之一。在旅游的过程中， 我们不仅可以感受大自然之美、放松心情，而且可以领略不同地方的文化气息、拓宽视野。旅游者在今年五月一日8点之后从江苏徐州出发，到全国一些著名景点旅游，最后回 到徐州。由于跟团旅游会受到限制，旅游者打算自己背包出游。出行路途中有以下几个条 件：A）城际交通出行可以乘火车含高铁）、长途汽车或飞机不允许包车或包及），并 且车票或机票可预定到。B）市内交通出行可乘公交车含专线大巴、小巴）、地铁或出租 车。C）旅游费用以网上公布为准，具体包括交通费、住宿费、景点门票第一门票）。晚 上20： :00至次日早晨7： :00之间，如果在某地停留超过6小时，必须住宿，住宿费用不 超过200元/天。吃饭等其它费用60元/天。D假设景点的开放时间为8:00至18:00.根据以上条件考虑到旅游者的以下需求：1、在时间不限的情况下，游览全部景点，旅游费用最省；2、在旅游费用不限的情况下，游览全部景点，旅游时间最短；3、在旅游费用一定的情况下，游览尽可能多的景点；4、在时间一定的情况下，游览尽可能多的景点；5、在时间和旅游费用都一定的情况下，游览尽可能多的景点。针对以上几种情况，建立相关的数学模型并为该旅行者设计详细的行程表，行程表中 应包括具体的交通信息车次、航班号、起止时间、票价等）、宾馆地点和名称，门票费用， 在景点的停留时间等信息。二、问题分析对于人们生活水平不断提高，越来越多的人会选择在节假日游览一下祖国的大好河山， 领略一下各地的风土人情和人文气息。在旅游的时候人们往往会想，怎样才能花最少的费 用、时间游览预订的地方，怎样设计路线才能在有限的费用、时间内游览更多的地方。这 就需要我们建立高效实用的数学模型来解决这些问题。题目的理解首先我们知道本问题属于旅游路线的优化问题。为了建立模型，首先应将各景点线路 转化为纯数学形式的点线集合，进行图论方面的分析。本问题主要是解决两方面的问题：1）、2）两问是在时间或旅游费用不限的情况下， 游完十个景点怎样才可以做到费用最省或是时间最省；3）、4）、5）问是在旅游时间或 是旅游费用或是两者都有约束条件的情况下，怎样才可以玩更多的地方。第一方面根据对第一方面问题的分析可知，问题目的在于当时间费用）不限的情况下求游完 所有景点并回到出发地点所用的费用时间）的最小值。该问题属于旅行商问题Traveling Salesman Problem9TSPh为了建立数学模型，首先应该将各个景点转化为纯数学形式的点 线的集合，进行图论方面的分析。下面给出旅行商问题的定义：旅行商问题：一位销售商从N个城市的某个城市出发，不重复的走完其余N-I个城市 并回到原出发点，在所有可能路径中求出路径长度最短的一条。用数学语言描述TSP,即 给定一组N个城市和它们两两之间的直达距离，寻找一条闭合的旅程，使得每个城市刚好 经过一次且总的旅行距离最短。用图语言描述TSP：给出一个图G=V, E）,每边e石上 有非负权值We）, 寻找G的HamiltOn圈C,使得C的总权W（C）=2似最小。TSP e=E（c）问题是一个典型的组合优化问题，其可能的搜索路径随着城市数目N的增加呈指数增长， 属于NP完全问题。了解了以上只是后，我们更加确定了该问题就是旅行商问题。只是在实际的处理中， 我们把两景点的最省路费最短时间）最为赋权值w S）,在一定程度上，各景点间的距 离与两点间的单程最省路费单程最短时间）是成正比的，所以把两景点的最省路最短 时间）作为权值W S）是可行的。第二方面这一方面要解决的问题是在费用时间）有限制或两者都有限制的情况的情况下欣赏 的景点近可能多，根据这种要求可从以下方案入手：建立多目标规划模型，通过适当的拟合或线性加权，把多目标转化为单目标三、模型假设1、在旅游期间，天气晴朗，列车和航班没有延误并且准时到站，市内交通也没有出现 长时间的堵塞2、该旅游者是成年人，不考虑学生票的问题3、旅游者在两地旅游来回时间和路上花的费用是相同的四、符号约定Xij路线决策变量01变量）Lij 从i地到j地的路费、路上的根本消费和需住宿时的住宿费用单位：元）（i, j=1211）Pi 地区景点的第一门票费用单位:元）（i=l, 210）Piji景点和j景点的门票费用之和单位：元）i=l, 2.10）T 在景点所在地区停留的时间，包括在景点的游玩时间和停留住宿等时间单位: 天）（i,j=l,211）A 每天的根本消费60单位：元）M 旅游总共的消费单位：元）s 旅游总共的用时单位：小时）Siji景点和j景点的所用时间之和，单位:小时）G=L 2.10）Tij 从i景点到j景点的时间，包括旅途是时间、停留等车时间、住宿时间单位: 小时）（i,j=l,2.）Ti在景点i的观光时间单位：小时Ii=L 2.10）五、模型建立与求解1 问言时间不受限制的情况下，可游览完所有景点，要求消费总和最低。也就是说，从徐 州出发，逐一欣赏各景点，不能重复，然后再回到徐州，使得这一过程中总的花费最少。 这一过程中我们尽量选择廉价的交通工具。2、模型分析我们把各景点转化为纯数学形式的点线集合，利用图论方面的知识求解。为了到达旅游费用最低，交通方式的费用应采用最低，并且应该尽量防止住宿，因此 我们采取晚上乘火车去下一个景点。现给出旅游景点门票费用，每天根本费用吃饭等其 它费用60元），市内交通从火车站到旅游景点的双程费用）的最低费，见表。表.1旅游景常州青岛八达祁县洛阳黄山武汉秦始九江舟山点市恐市崂岭长乔家市龙市黄市黄皇兵市庐市普龙园山城大院门石山鹤楼马俑山陀山门票费 用元/ 人）160705040801505090180160根本费 用60606060606060606060市内交29路304地铁直达81路旅游10路306102轮船通14路42号车4班车4路路28元）元）线换20元）26元）1224元）乘元）元）元）元）919快车30元）一天总224134140120144236114162264248计费用元元元元元元元元元元已经分析，该问题属于旅行商问题，这一过程中费用最省就是求最小路途费用的 HamiltOn圈。我们把两景点的最省路费最为赋权值W S）,在一定程度上，各景点间的距 离与两点间的单程最省路费是成正比的，所以把两景点的最省路费作为权值W S）是可行 的。影响消费的因素:目标函数确实定：用Lij表示i景点到j景点的途中花费，并引入路线决策变量Xijf 1 经过i到j的路段Xij= <O 不经过i到j的路段用Pj表示j地区景点的第一门票费用，T表示在景点所在地区停留的时间 那么总费用，那么目标函数为：11 1110M=X" + R+ATz=l 7=1z=l约束条件确实定：由于每个景点只能有一条边出去，所以对j景点Xij之和影等于1,既:11EXij = 11=1,211J=I同理，每个景点只能有一条边进去，所以对i景点Xij之和也应等于1,既:11ERi=I1=1,211J=I应该注意的是，除了起点和终点都是徐州）以外，各边不构成Hamilton圈。3、模型建立综上分析，建立HamiItOn圈的线性规划模型：11 1110minM = Z Z XV + Z Pi +AT1 1111EXij=Is.t<Li=l,21111EXji=Ij=i4、模型求解注：上网查阅列车时刻表 ：Shike尽量保证车次是晚间发车并且到达下一 个景点时不耽误游玩，上网）找到了满足条件的宾馆。我们得到了从一个景点到另一个 景点所需的最低费用火车费用，在火车上行驶一天吃饭的费用和遇到需要住宿时的住宿 费