《论文旅游路线优化设计》由会员分享，可在线阅读，更多相关《论文旅游路线优化设计（21页珍藏版）》请在金锄头文库上搜索。
1、1 旅游路线的优化设计摘要 本文主要研究最佳旅游路线的设计问题。其实际就是一个路线优化的问题。题目要求旅客从徐州出发到各个省市的十个旅游景点，要在满足相关的约束条件之下，选择设计合理的旅游线路，达到省时经济的最佳效果是本文的目标。基于对此的研究，建立数学模型，设计出最佳旅游线路。问题一，要在时间不限费用最少的情况下将十个景点全游览完。通过地图，我们得到 10 个景点大致位置，根据费用最小原则，利用蚁群算法，得出最佳回路，由于飞机票和汽车票的费用都远大于火车票，所以我们用火车价格来计算车费，得出最省钱的路径和最小费用。路线徐州-常州- 舟山 -黄山- 九江-武汉-洛阳-西安-祁县 -北京- 青岛
2、- 徐州；耗时 11 天，总费用 2962 元。问题二，要在费用不限用时最少的情况下将十个景点全游览完。而总耗时包括交通时间，景点逗留时间以及住宿时间。所以同问题一相似，只不过此题考虑的是时间而非费用。由于飞机要比火车以及汽车快的多，在没有飞机的城市，我们选择最快的动车来代替。利用 lingo 软件求出旅游线路。路线为徐州-北京-祁县-西安-洛阳-武汉 -九江 -黄山-舟山 -常州-青岛-徐州。问题三，在问题一的基础上，将费用缩小在 2000 的范围内，而要游览尽可能多的城市，所以，我们先排除车费和门票都较贵的 4 个景点，得出费用 1401 元，还有很多结余，完全可以再游览其他城市。再综合比
3、较，得出游览七个城市，分别为徐州- 九江-武汉- 洛阳-西安-祁县- 北京-青岛-徐州，总共花费 1737 元。问题四，显然是在问题二的基础上进行优化，由于时间限制在了 5 天。所以利用排除法，排除逗留时间长和距离较远的景点，以此来缩小路线网，然后再对剩下的景点寻找最优路线，如此重复，直到满足 5 天的时间限制。最后得出最多游览7 个景点。问题五，结合了问题三、四的条件，在他们的基础上，再次对路线网进行压缩，在满足问题三的路线中排除逗留时间长和距离远的，而在问题四的路线中排除门票和车费高的景点，最后得出最佳路线方案。5 天游览 7 个城市，最小花费 2092元。2 1.问题重述1.背景随着社会
4、的发展，人们物质生活的提高，人们对物质生活的追求，已逐渐转化为精神生活的追求，相应的旅游业也逐渐发展壮大起来。人们对外界事物的好奇与追求也越来越热，而旅游，不仅满足了人们的好奇与心理需求，还能让人忙里偷闲，放松自己，从而也加强自己的见识与认知。旅游已成为提高人们生活质量的重要活动。2.问题此题讲诉江苏徐州有一位旅游爱好者打算现在的今年的十月一日早上 8 点之后出发，到全国一些著名景点旅游，最后回到徐州。由于跟团旅游会受到若干限制，他(她)打算自己作为背包客出游。他预选了十个省市旅游景点，如表 1 所示。表 1. 预选的十个省市旅游景点省市 景点名称 在景点的最短停留时间江苏 常州市恐龙园 4
5、小时山东 青岛市崂山 6 小时北京 八达岭长城 3 小时山西 祁县乔家大院 3 小时河南 洛阳市龙门石窟 3 小时安徽 黄山市黄山 7 小时湖北 武汉市黄鹤楼 2 小时陕西 西安市秦始皇兵马俑 2 小时江西 九江市庐山 7 小时浙江 舟山市普陀山 6 小时问题：根据以上要求，针对如下的几种情况，为该旅游爱好者设计详细的行程表，该行程表应包括具体的交通信息(车次、航班号、起止时间、票价等)、宾馆地点和名称，门票费用，在景点的停留时间等信息。(1) 时间不限，游览完十个景点所需费用最少(2) 费用不限，游览完十个景点所需时间最短(3) 2000 元旅游费用，时间不限，游览的景点最多(4)5 天旅游
6、时间，费用不限，游览的景点最多(5) 5 天的时间和 2000 元的旅游费用，游览的景点最多3 2.问题分析问题 1、问题 2对这两个问题，都是一个优化问题：一个在时间不限的情况下，要游览完所有景点，并且所花费用要最少；一个是在费用不限的情况下，所花时间最小。所以我们利用各城市之间的相对位置做出散点图，分别利用蚁群算法，和商旅问题的算法，根据花费最小和时间最少，得出旅游的最短回路。第一问要求时间不限，用最少的旅游费用游览全部景点，而考虑到不同交通工具的速度和票价都不相同，各个旅馆的住宿费用也不相同，所以我们对其行程进行详细的安排，尽量减少其在交通和住宿上的费用，减少不必要的花费。最后得出一个最
7、少旅游费用的旅游行程表。第二问要求费用不限，时间最短，交通工具就尽量考虑直达飞机，然后再对其行程进行详细的安排，尽量避免不必要的时间。最后得出一个最短时间的旅游行程表。问题 3、问题 4这两题是在前两题的基础上，对路径网的进一步调整，逐步排除最浪费时间和花销最大的景点，以缩小旅游线路网，利用 lingo 软件求出满足条件的最少费用和最短时间。问题 5对地 5 个问，题目给出了两个限制条件，旅游费用不超过 2000 元，并且旅游时间在 5 天以内。只用 5 天和 2000 元游览完 10 个景点是不可能的，所以我们对其进行优化。由于飞机价格非常高，所以我们基于第三问，并且结合第四问的数据对其进行
8、优化。然后，对旅游行程进行优化计算，为了简化运算，我们假设交通线路上花费的时间和费用只是简单相加。通过除去旅游景点计算出 2000 元以下和 5 天以内的时间最优解。最后得出一个最优旅游行程表。3.模型假设（1）城际交通出行可以乘火车(含高铁)、长途汽车或飞机（不允许包车或包机） ，并且车票或机票可预订到；(2) 市内交通出行可乘公交车(含专线大巴、小巴) 、地铁或出租车；(3) 旅游费用以网上公布为准，具体包括交通费、住宿费、景点门票(第一门票)。晚上 20：00 至次日早晨 7：00 之间，如果在某地停留超过 6 小时，必须住宿，住宿费用不超过 200 元/天。吃饭等其它费用 60 元/天
9、；(4) 假设景点的开放时间为 8:00 至 18:00；4 （5）不论选择什么交通工具，都不存在堵车或者晚点或航班取消的情况；（6）忽略乘坐出租车时经过收费路段所交的费用；（7）为简化运算，并且忽略从旅馆到火车站或景点的时间；（8）为简化模型，我们仅画出每个省的省会坐标点；（9） 忽略吃饭时间；（10） 为简化运算，我们假定公交上车均为 2 元，计算费用时，只是简单的加和；（11）在外出游期间，天气状况良好，符合出行条件。4.符号说明ij路径上的信息量ijn启发函数信息启发式因子期望启发式因子kijpt蚂蚁 k在 t时刻由 i城市转向 j城市的转移概率kabu第 只蚂蚁的禁忌搜索表信息素挥发
10、系数kijtt时刻 k蚂蚁在路径 ij上留下的信息素量L短到目前为止所找到的全局最短路径长度Q蚂蚁携带的信息素量k本次循环中第 k只蚂蚁所走的路程长度m蚂蚁的总数量蚂蚁的编号dij i,j 两地的距离xij 0-1 变量： 0 表示不从 i 到 j，1 表示从 i 到 j5 5.模型建立与求解5.1 模型一5.1.1 建立蚁群算法1的数学模型(1)状态转移规则因为蚂蚁 k不能重复经过一个城市，所以建立禁忌表 (1,2.)ktabum来记录蚂蚁走过的城市，禁忌表随着时间做动态变化。建立蚂蚁 由 i城市转移到 j城市的状态转移概率如下：() ()() 0 kijikkkisisijstabu kt
11、jtabupt jt（1）上式中 为信息启发式因子，表示路径的相对重要性，是对所积累的信息素影响作用的一个加权值； 为期望启发式因子，表示能见度的相对重要性；每只蚂蚁必须依据以城市距离和连接边上信息素的数量为变量的概率函数，决定选择下一个城市的概率。每只蚂蚁必须根据禁忌表和概率函数寻找下一个城市，以保证该蚂蚁从起点出发经过所有城市有且只有一次，并且最终返回到起点。(2)信息素的全局更新规则当 m只蚂蚁成功的完成一次寻径过程之后，将选出目标函数值最小的路径，用以完成全局信息素的更新，使得较优解保留下来，对后继蚂蚁产生影响，加快收敛到最优解的速度。设 i， j为两个相连接点，则有： (,)1,ij
12、 ij ij （2）其中，变量 ij是在 t时刻，节点 ,之间路上信息素的增加量1,(),0ij fijglobaestourLthrwi短是位于0,1 上的“激素”挥发因子； L短 为到目前为止所找到全局最短路径长度。(3)信息素的局部更新6 对于第 k只蚂蚁，在建立一个解得过程中也同时进行激素迹的更新，如果节点,ij是它所选择路径上的两个相邻节点，规则如下： ()1ij ijijttt 否则，不更新。其中， 0 1， 0()ij， 是各条路上的信息素的初始值，通常取同一值，表示同一环境。信息素的更新策略有很多种方法，每种更新策略的主要差别体现在 kijt的求法上。我们规定蚂蚁在完成一个循环
13、后更新所有路径上的信息素，其方程式为： ki,j0 kijQLt蚂 蚁 本 次 循 环 经 过 （ ）否 则（3）上式中 表示蚂蚁携带信息素的量，其值的大小影响算法的收敛速度； kL表示第k只蚂蚁在本次循环中所走的路程总长度。由于常州和徐州都在一个省里，因此将其合为一个点来简化计算。5.1.2 模型一的求解根据散点位大致位置，计算出个城市之间的而相对坐标位置，并根据坐标对市行编号（附录 I） 。再利用蚁群算法，通过编程得到最短回路（图 1）： 图 1 游览城市回路图对回路图进行处理，得到旅游最佳路线为：徐州-常州 -舟山-黄山-九江-武汉- 洛阳-西安-祁县-北京-青岛- 徐州7 根据最佳路线
14、，为是费用最小，我们查阅了各时刻火车票价，车次，各景点门票以及旅店名称费用等信息。在花费最少的情况下，设计如下旅游线路（表 2）：日期 时间 行程 费用10:05-15:48 乘坐 1230/1227（徐州-常州） 6216:00-17:00 常州火车站乘 29 路公交到恐龙园 417:30-21:00 游览常州市 010.121：00-7:00 住宿于常州蓝色快舟营销人连锁旅店 1128:00-12:00 进园游览 16013：00-16:00 回到常州火车站候车 416:49-00:03 乘 k75 前往宁波 7310.200:20-5:40 在火车站休息一下 05:40-8:40 由宁波
15、乘汽车到沈家门 358:50-9:10 坐轮船由沈家门到普陀山 149:20-15:20 游览普陀山 16015:10-18:40 返回宁波火车站 4919:30-21：00 火车站候车 010.321:07-02:41 乘 k8564 到达宣城 6302:50-4:10 候车室候车 04:21-7:35 乘 k45 到黄山 297:35-9:30 乘坐班车至黄山脚下 159:30-16:30 黄山一日游 23017:00-18:00 返回黄山火车站 1510.418:28-23:29 乘 K70 到鹰潭 510:22-3:47 乘 K253 到九江 427:00-8:30 乘 101 公交到汽车站再到庐山 1408:30-15:30 爬庐山 18010.516:00-18:00 回九江火车站候车 142:01-7：02 乘 K921 到汉口 517:20-8:00 乘 10 路公交至黄鹤楼 28:00-10:00 游玩
