《浅谈旅游线路的优化设计》由会员分享，可在线阅读，更多相关《浅谈旅游线路的优化设计（25页珍藏版）》请在金锄头文库上搜索。
1、旅游线路的优化设计摘要在基本假设和符号说明的基础上，建立了最优线路Rm与时间T、花费S的函数F(S,T).对于第一问本文以十一个城市的经纬度坐标算得城市之间的距离，构造成完备图,进而用TSP算法,使用蚁群算法程序解得最优路径和最少费用为3394元并设计出行程表.第二问以完全城市之间距离的最短时间为权重，运用01变量来控制住宿等不确定因素，使用lingo算法确定最优路径和最短时间为185小时.第三问和第四问是建立在第一和第二问的基础上，添加约束条件S2000元T120小时，使用排除法得到最终结果：第三问的最少费用为1998元，游览城市8个，第四问的最短时间为107小时，游览城市7个；第五小问是第
2、三和第四小问的有机整合，同时考虑时间和花费的约束，联系实际情况，得到最终结果为；最少费用1848元，对应的最短时间为103小时，游览城市为5个。最后，给出模型的优点和缺点的说明。 关键字：完备图 蚁群算法 01规划 约束条件 一、问题重述江苏徐州有一位旅游爱好者打算现在的今年的五月一日早上8点之后出发，到全国一些著名景点旅游，最后回到徐州。由于跟团旅游会受到若干限制，他(她)打算自己作为背包客出游。他预选了十个省市旅游景点，如表所示：现假设： 省市景点名称在景点的最短停留时间江苏常州市恐龙园4小时山东青岛市崂山风景区6小时北京八达岭长城3小时山西祁县乔家大院3小时河南洛阳市龙门石窟3小时安徽黄
3、山市黄山7小时湖北武汉市黄鹤楼2小时陕西西安市秦始皇兵马俑2小时江西九江市庐山7小时浙江舟山市普陀山6小时(A) 城际交通出行可以乘火车(含高铁)、长途汽车或飞机（不允许包车或包机），并且车票或机票可预订到。(B) 市内交通出行可乘公交车(含专线大巴、小巴)、地铁或出租车。(C) 旅游费用以网上公布为准，具体包括交通费、住宿费、景点门票(第一门票)。晚上20：00至次日早晨7：00之间，如果在某地停留超过6小时，必须住宿，住宿费用不超过200元/天。吃饭等其它费用60元/天。(D) 假设景点的开放时间为8:00至18:00。根据以上要求，针对如下的几种情况，为该旅游爱好者设计详细的行程表，该行
4、程表应包括具体的交通信息(车次、航班号、起止时间、票价等)、宾馆地点和名称，门票费用，在景点的停留时间等信息。(1) 如果时间不限，游客将十个景点全游览完，至少需要多少旅游费用？请建立相关数学模型并设计旅游行程表。(2) 如果旅游费用不限，游客将十个景点全游览完，至少需要多少时间？请建立相关数学模型并设计旅游行程表。(3) 如果这位游客准备2000元旅游费用，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。(4) 如果这位游客只有5天的时间，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。(5) 如果这位游客只有5天的时间和2000元的旅游费用，想尽可能多游览景点，请建立相关数
5、学模型并设计旅游行程表。二、问题分析旅游最优路线问题已成为现今人们所感兴趣的话题之一。本题通过给定相关资料和数据，要求为旅游爱好者设计最优路线，建立具体优化模型，最后求解最优行程表。本题类似于旅行商问题（TSP问题），求解TSP问题的关键在于设计合适的优化算法【1】，主要包括分支定界法、改良回路法、贪婪算法、MST算法、插入法，蚁群算法、遗传算法，在算法的选取上，应该讲求合适便捷的准则。基于本题的实际情况，可以按以下的求解过程实现：首先，建立以十一个城市为顶点的完全图。对于第一问，题目要求遍历所有城市使得话费最小，为了解题方便，我们可以选取城市之间的距离作为相应点与点之间的权重，最后通过合适的
6、算法求解最优路线并设计出最优行程表；对于第二问，题目要求遍历所有城市使得时间最小，通过改变第一问的权重（把距离改成完成这段距离的最短时间）即可实现；然后，第三问和第四问分别是在第一问和第二问的基础上，通过添加约束条件，即费用和时间的约束，即可求得最优线路，进而设计最优行程表；最后，第五问是建立在第三和第四小问基础上的有机组合，实现的方法是：在第三问所求得的结果的基础上，把第四问的约束条件添加进去，最后解得最优线路并设计最有行程表。三、模型假设1、不考虑班车和航班的推迟或取消，忽略天气影响或不可预测的事故； 2、把经纬度看成是平面坐标的两簇相互垂直的平行线； 3、旅馆处于非满客状态，即总可预订到
7、房间； 4、在时间的认识上，把当天早上八点到次日的早上八点定义为一天； 5、不考虑实际生活中出现的堵车等车等不可知现象。四、符号说明城市i与城市j的图上距离 旅游总费用 第i个城市到第j个城市的交通费 第i个城市到第j个城市是否需要通车 第个城市到第个城市的时间表示最优线路五、模型建立根据以上假设，把最优线路问题看成是时间和花费的函数，而时间和花费又是相互联系的，通过建立以下（01）变量，构造模型的目标函数、旅游费用函数 。六、模型求解第一问求解：根据以上模型，本小问即是求解函数F使得S取得最小值（设为），转化为TSP问题，目标函数就是： min根据相关资料得到各个城市的经纬度，以经度为横坐标
8、，纬度为纵坐标，建立（经度纬度）坐标图像（图1）(见代码1)：图1再运用欧拉距离公式： 算得任意两点间的图上距离（表1）（代码2）：单位：CM徐州常州青岛北京祁县洛阳黄山武汉西安九江舟山徐州03.69643.61575.70825.77294.78034.17714.72658.25004.71336.6644常州3.696404.029688.84749.43878.05412.41585.781211.2 7614.49 072.97 24青岛3.61574.296805.45898.10338.00816.27468.188011.52157.71106.4102北京5.70828.84
9、745.458904.85916.58859.87409.64279.398010.221811.5372祁县5.77299.43878.10334.859102.66239.22854.57968.14 1812.4 024.78 03洛阳8.05548.00816.58852.66233.662307.26844.57923.51646.115410.9358黄山4.7712.41586.27469.87409.22857.268403.844210.05502.22254.1658武汉4.72655.78128.18809.64277.12084.57923.844206.5416108
10、4718.0089西安8.250011.276111.52159.3.9804.57963.516410.05506.541608.371014.0254九江4.71334.49077.711010.22188.47186.11242.22251.84718.371006.3353舟山6.66442.97246.410211.537212.410210.93584.16588.008914.02546.33530 表1并使用Floyd算法（见代码3）算得任意两点间的最短距离，构造以下图上最近距离矩阵为： 0 3.6964 3.6157 5.7082 5.7729 4.7803 4.1771 4
11、.7265 8.2500 4.7133 6.6644 3.6964 0 4.2968 8.8474 9.4387 8.0541 2.4158 5.7812 11.2761 4.4907 2.9724 3.6157 4.2968 0 5.4589 8.1033 8.0081 6.2746 8.1880 11.5215 7.7110 6.4102 5.7082 8.8474 5.4589 0 4.8591 6.5885 9.8740 9.6427 9.3980 10.2218 11.5372 5.7729 9.4387 8.1033 4.8591 0 2.6623 9.2285 1208 4.57
12、96 8.4718 12.4102 4.7803 8.0541 8.0081 6.5885 2.6623 0 7.2684 4.5792 3.5164 6.1124 10.9358 4.1771 2.4158 6.2746 9.8740 9.2285 7.2684 0 3.8442 10.0550 2.2225 4.1658 4.7265 5.7812 8.1880 9.6427 7.1208 4.5792 3.8442 0 6.5416 1.8471 8.0089 8.2500 11.2761 11.5215 9.3980 4.5796 3.5164 10.0550 6.5416 0 8.3
13、710 14.0254 4.7133 4.4907 7.7110 10.2218 8.4718 6.1124 2.2225 1.8471 8.3710 0 6.3353 6.6644 2.9724 6.4102 11.5372 12.4102 10.9358 4.1658 8.0089 14.0254 6.3353 0 并对各个城市进行编号如下（表2）： 城市徐州常州青岛北京祁县洛阳黄山武汉西安九江舟山编号1234567891011 表2根据以上图上最近距离矩阵，设计蚁群算法（见代码4），得到最优路线为（如图2所示）：到最优路线为： Rm=6 9 5 4 3 1 2 11 7 10 8 即：洛阳西安祁县北京青岛徐州常州舟山黄山九江武汉 图2根据各个城市之间的实际距离（表3）: 单位: km徐州常州青岛北京祁县洛阳黄山武汉西安九江舟山徐州0401.9388.2634.36620.33507.3462.82518.9877.61523.41707.31常州401.90476.71977.941019.41862.64266.66620.721205.61486.39305.56青岛388.2476.7105
