《B旅游线路的优化设计》由会员分享，可在线阅读，更多相关《B旅游线路的优化设计（30页珍藏版）》请在金锄头文库上搜索。
1、2011 年南京邮电大学数学建模竞赛题 目 ： 旅游线路的优化设计摘要本文考虑的是旅游时间（费用）不受限制的情况下，如何安排旅游路线不重复且有返回的游览完所有景点，使得费用（时间）最少，以及费用（时间）受限制或两者都受限制时，如何安排不重复且有返回的路线使得游览的景点最多。（一）对优化模型的理解：路线优化模型：首先我们知道本问题属于旅游路线的优化问题。为了建立模型，首先应将各景点线路转化为纯数学形式的点线集合，进行图论方面的分析。本问题主要是解决两方面的问题：（1） 、 （2）两问是在时间或旅游费用不限的情况下，游完十个景点怎样才可以做到费用最省或是时间最省；（3） 、 （4） 、（5）问是在
2、旅游时间或是旅游费用或是两者都有约束条件的情况下，怎样才可以玩更多的地方。根据对第一方面问题的分析可知，该问题属于旅行商问题（Traveling Salesman Problem,TSP） 。对旅行商问题的理解：一位销售商从 N 个城市的某个城市出发，不重复的走完其余 N-1 个城市并回到原出发点，在所有可能路径中求出路径长度最短的一条。用图语言描述 TSP：给出一个图 G=（V，E） ，每边上有非负权值 ， 寻找 G 的 Hamilton 圈 C，使得 C 的总权Ee)(ew最小。在一定程度上，各景点间的)(ceW距离与两点间的单程最省路费（单程最短时间）是成正比的，所以把两景点的最省路（最
3、短时间）作为权值 是可行的。)(e第二面要解决的问题是在费用（时间）有限制或两者都有限制的情况的情况下观赏的景点近可能多，根据这种要求可从这种方案入手：建立多目标规划模型，通过适当的拟合或线性加权，把多目标转化为单目标（二）综上所述，得到各种条件下的最优路线方案见表 1.1：表 1.1问题 结果 旅游路线1（1） 3012 元 徐 州青 岛 市 崂 山八 达 岭 长 城祁 县 乔 家 大 院兵 马 俑 西 安 市 秦 始 皇洛 阳 市 龙 门 石 窟武 汉 市 黄 鹤 楼市 庐 山 九 江舟 山 市 普 陀 山黄 山 市 黄 山常 州 市 恐 龙 园徐 州 （2） 9.4 天 徐 州常 州 市
4、 恐 龙 园祁 县 乔 家 大 院皇 兵 马 俑 西 安 市 秦 始洛 阳 市 龙 门 石 窟八 达 岭 长 城武 汉 市 黄 鹤 楼 青 岛 市 崂 山九 江 市 庐 山舟 山 市 普 陀 山黄 山 市 黄 山徐 州（3） 1954 元7 个景点 徐 州武 汉 市 黄 鹤 楼青 岛 市 崂 山八 达 岭 长 城祁 县 乔 家 大 院西 安 市 秦 始 皇 兵 马 俑常 州 市 恐 龙 园徐 州 （4） 4.6 天5 个景点 徐 州常 州 市 恐 龙 园西 安 市 秦 始 皇 兵 马 俑八 达 岭 长 城洛 阳 市 龙 门 石 窟九 江 市 庐 山徐 州（5） 1201 元4.6 天3 个景点
5、徐 州八 达 岭 长 城 西 安 市 秦 始 皇 兵 马 俑常 州 市 恐 龙 园徐 州由于不同的网站公布的信息存在一定偏差，所以该结果仅依求解时提供的网站信息。【关键词】多目标规划 旅行商问题 Hamilton 圈 线性加权 最优化一、问题重述随着人们生活水平的提高，旅游逐渐成为最热门的户外活动之一。在旅游的过程中，我们不仅可以感受大自然之美、放松心情，而且可以领略不同地方的文化气息、拓宽视野。旅游者在今年五月一日 8 点之后从江苏徐州出发，到全国一些著名景点旅游，最后回到徐州。由于跟团旅游会受到限制，旅游者打算自己背包出游。出行路途中有以下几个条件：（A）城际交通出行可以乘火车（含高铁）
6、、长途汽车或飞机（不允许包车或包及） ，并且车票或机票可预定到。 （B）市内交通出行可乘公交车（含专线大巴、小巴） 、地铁或出租车。 （C）旅游费用以网上公布为准，具体包括交通费、住宿费、景点门票（第一门票） 。晚上 20：:00 至次日早晨 7：:00 之间，如果在某地停留超过 6 小时，必须住宿，住宿费用不超过200 元/天。吃饭等其它费用 60 元/天。 （D）假设景点的开放时间为 8:00 至18:00.根据以上条件考虑到旅游者的以下需求：1、在时间不限的情况下，游览全部景点，旅游费用最省；2、在旅游费用不限的情况下，游览全部景点，旅游时间最短；3、在旅游费用一定的情况下，游览尽可能多
7、的景点；24、在时间一定的情况下，游览尽可能多的景点；5、在时间和旅游费用都一定的情况下，游览尽可能多的景点。针对以上几种情况，建立相关的数学模型并为该旅行者设计详细的行程表，行程表中应包括具体的交通信息（车次、航班号、起止时间、票价等） 、宾馆地点和名称，门票费用，在景点的停留时间等信息。二、问题分析2.1 问题背景分析对于人们生活水平不断提高，越来越多的人会选择在节假日游览一下祖国的大好河山，领略一下各地的风土人情和人文气息。在旅游的时候人们往往会想，怎样才能花最少的费用、时间游览预订的地方，怎样设计路线才能在有限的费用、时间内游览更多的地方。这就需要我们建立高效实用的数学模型来解决这些问
8、题。2.2 对题目的理解首先我们知道本问题属于旅游路线的优化问题。为了建立模型，首先应将各景点线路转化为纯数学形式的点线集合，进行图论方面的分析。本问题主要是解决两方面的问题：（1） 、 （2）两问是在时间或旅游费用不限的情况下，游完十个景点怎样才可以做到费用最省或是时间最省；（3） 、 （4） 、（5）问是在旅游时间或是旅游费用或是两者都有约束条件的情况下，怎样才可以玩更多的地方。第一方面根据对第一方面问题的分析可知，问题目的在于当时间（费用）不限的情况下求游完所有景点并回到出发地点所用的费用（时间）的最小值。该问题属于旅行商问题（Traveling Salesman Problem,TSP
9、） 。为了建立数学模型，首先应该将各个景点转化为纯数学形式的点线的集合，进行图论方面的分析。下面给出旅行商问题的定义：旅行商问题：一位销售商从 N 个城市的某个城市出发，不重复的走完其余N-1 个城市并回到原出发点，在所有可能路径中求出路径长度最短的一条。用数学语言描述 TSP，即给定一组 N 个城市和它们两两之间的直达距离，寻找一条闭合的旅程，使得每个城市刚好经过一次且总的旅行距离最短。用图语言描述 TSP：给出一个图 G=（V，E） ，每边 上有非负权值 w（e ） ， 寻找 GEe的 Hamilton 圈 C，使得 C 的总权 最小。TSP 问题是一个典型的)(cW组合优化问题，其可能的
10、搜索路径随着城市数目 N 的增加呈指数增长，属于NP 完全问题。了解了以上只是后，我们更加确定了该问题就是旅行商问题。只是在实际的处理中，我们把两景点的最省路费（最短时间）最为赋权值 w（e ） ，在一定程度上，各景点间的距离与两点间的单程最省路费（单程最短时间）是成正比的，所以把两景点的最省路（最短时间）作为权值 w（e ）是可行的。第二方面这一方面要解决的问题是在费用（时间）有限制或两者都有限制的情况的情况下观赏的景点近可能多，根据这种要求可从以下方案入手：建立多目标规划模型，通过适当的拟合或线性加权，把多目标转化为单目标3三、模型假设1、在旅游期间，天气晴朗，列车和航班没有延误并且准时到
11、站，市内交通也没有出现长时间的堵塞2、该旅游者是成年人，不考虑学生票的问题3、旅游者在两地旅游来回时间和路上花的费用是相同的四、符号约定Xij 路线决策变量（01 变量）Lij 从 i 地到 j 地的路费、路上的基本消费和需住宿时的住宿费用（单位：元） （i，j=1211）Pi 地区景点的第一门票费用（单位：元） （i=1，210）Pij i 景点和 j 景点的门票费用之和（单位：元） （i=1，210）T 在景点所在地区停留的时间，包括在景点的游玩时间和停留住宿等时间（单位：天） （i,j=1,211）A 每天的基本消费 60（单位：元）M 旅游总共的消费（单位：元）S 旅游总共的用时（单位
12、：小时）Sij i 景点和 j 景点的所用时间之和， （单位：小时） （i=1，210）Tij 从 i 景点到 j 景点的时间，包括旅途是时间、停留等车时间、住宿时间（单位：小时） （i,j=1,211）Ti 在景点 i 的观光时间（单位：小时） （i=1，210）五、模型建立与求解5.11、问题理解在时间不受限制的情况下，可游览完所有景点，要求消费总和最低。也就是说，从徐州出发，逐一观赏各景点，不能重复，然后再回到徐州，使得这一过程中总的花费最少。这一过程中我们尽量选择便宜的交通工具。2、模型分析我们把各景点转化为纯数学形式的点线集合，利用图论方面的知识求解。为了达到旅游费用最低，交通方式的
13、费用应采用最低，并且应该尽量避免住宿，因此我们采取晚上乘火车去下一个景点。现给出旅游景点门票费用，每4天基本费用（吃饭等其它费用 60 元） ，市内交通（从火车站到旅游景点的双程费用） ）的最低费，见表 5.1.1。表 5.1.1旅游景点常州市恐龙园青岛市崂山八达岭长城祁县乔家大院洛阳市龙门石窟黄山市黄山武汉市黄鹤楼秦始皇兵马俑九江市庐山舟山市普陀山门票费用（元/人）160 70 50 40 80 150 50 90 180 160基本费用60 60 60 60 60 60 60 60 60 60市内交通29 路（4元）304路（4元）地铁2 号线换乘919快车（30元）直达车（20元）81
14、路（4元）旅游班车（26元）10 路（4元）306路（12元）102路（24元）轮船（28元）一天总计费用224元134元140元120元144元236元114元162元264元248元已经分析，该问题属于旅行商问题，这一过程中费用最省就是求最小路途费用的 Hamilton 圈。我们把两景点的最省路费最为赋权值 w（e ） ，在一定程度上，各景点间的距离与两点间的单程最省路费是成正比的，所以把两景点的最省路费作为权值 w（e ）是可行的。 影响消费的因素：路费住宿费基本消费门票费总费用5目标函数的确定：用 Lij 表示 i 景点到 j 景点的途中花费，并引入路线决策变量 XijXij=用 Pj
15、 表示 j 地区景点的第一门票费用，T 表示在景点所在地区停留的时间则总费用，则目标函数为：ATPiXijMij110约束条件的确定:由于每个景点只能有一条边出去，所以对 j 景点 Xij 之和影等于 1，既：i=1,2.111jXi同理，每个景点只能有一条边进去，所以对 i 景点 Xij 之和也应等于 1，既:i=1,2111jXi应该注意的是，除了起点和终点（都是徐州）以外，各边不构成 Hamilton圈。3、模型建立综上分析，建立 Hamilton 圈的线性规划模型：min ATPiXijM110i=1,2.111.jjXiits4、模型求解（注：上网查阅列车时刻表（http:/ ，尽量保证车次是晚间发车并且到达下一个景点时不耽误游玩，上网1 经过 i 到 j 的路段0 不经过 i 到 j 的路段6（http:/ ，见表 5.1.2。表 5.1.2费用(元)徐州 常州 青岛 北京 祁县 洛阳 黄山 武汉 西安 九江 舟山徐州 0 62 130 154 179 122 159 158 159 118 176常州 62 0 150 140 180 125 73 361 165 120 193青岛 130 150 0 116 120 245 360 373 363 371 42
