浅谈旅游线路的优化设计.docx

旅游线路的优化设计摘要在基本假设和符号说明的基础上，建立了最优线路Rm与时间T、花费S的函数F(S,T).对于第一问本文以十一个城市的经纬度坐标算得城市之间的距离，构造成完备图,进而用TSP算法,使用蚁群算法程序解得最优路径和最少费用为3394元并设计出行程表.第二问以完全城市之间距离的最短时间为权重，运用01变量来控制住宿等不确定因素，使用lingo算法确定最优路径和最短时间为185小时.第三问和第四问是建立在第一和第二问的基础上，添加约束条件S2000元T120小时，使用排除法得到最终结果：第三问的最少费用为1998元，游览城市8个，第四问的最短时间为107小时，游览城市7个；第五小问是第三和第四小问的有机整合，同时考虑时间和花费的约束，联系实际情况，得到最终结果为；最少费用1848元，对应的最短时间为103小时，游览城市为5个。最后，给出模型的优点和缺点的说明。 关键字：完备图 蚁群算法 01规划 约束条件 一、问题重述江苏徐州有一位旅游爱好者打算现在的今年的五月一日早上8点之后出发，到全国一些著名景点旅游，最后回到徐州。由于跟团旅游会受到若干限制，他(她)打算自己作为背包客出游。他预选了十个省市旅游景点，如表所示：现假设： 省市景点名称在景点的最短停留时间江苏常州市恐龙园4小时山东青岛市崂山风景区6小时北京八达岭长城3小时山西祁县乔家大院3小时河南洛阳市龙门石窟3小时安徽黄山市黄山7小时湖北武汉市黄鹤楼2小时陕西西安市秦始皇兵马俑2小时江西九江市庐山7小时浙江舟山市普陀山6小时(A) 城际交通出行可以乘火车(含高铁)、长途汽车或飞机（不允许包车或包机），并且车票或机票可预订到。(B) 市内交通出行可乘公交车(含专线大巴、小巴)、地铁或出租车。(C) 旅游费用以网上公布为准，具体包括交通费、住宿费、景点门票(第一门票)。晚上20：00至次日早晨7：00之间，如果在某地停留超过6小时，必须住宿，住宿费用不超过200元/天。吃饭等其它费用60元/天。(D) 假设景点的开放时间为8:00至18:00。根据以上要求，针对如下的几种情况，为该旅游爱好者设计详细的行程表，该行程表应包括具体的交通信息(车次、航班号、起止时间、票价等)、宾馆地点和名称，门票费用，在景点的停留时间等信息。(1) 如果时间不限，游客将十个景点全游览完，至少需要多少旅游费用？请建立相关数学模型并设计旅游行程表。(2) 如果旅游费用不限，游客将十个景点全游览完，至少需要多少时间？请建立相关数学模型并设计旅游行程表。(3) 如果这位游客准备2000元旅游费用，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。(4) 如果这位游客只有5天的时间，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。(5) 如果这位游客只有5天的时间和2000元的旅游费用，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。二、问题分析旅游最优路线问题已成为现今人们所感兴趣的话题之一。本题通过给定相关资料和数据，要求为旅游爱好者设计最优路线，建立具体优化模型，最后求解最优行程表。本题类似于旅行商问题（TSP问题），求解TSP问题的关键在于设计合适的优化算法【1】，主要包括分支定界法、改良回路法、贪婪算法、MST算法、插入法，蚁群算法、遗传算法，在算法的选取上，应该讲求合适便捷的准则。基于本题的实际情况，可以按以下的求解过程实现：首先，建立以十一个城市为顶点的完全图。对于第一问，题目要求遍历所有城市使得话费最小，为了解题方便，我们可以选取城市之间的距离作为相应点与点之间的权重，最后通过合适的算法求解最优路线并设计出最优行程表；对于第二问，题目要求遍历所有城市使得时间最小，通过改变第一问的权重（把距离改成完成这段距离的最短时间）即可实现；然后，第三问和第四问分别是在第一问和第二问的基础上，通过添加约束条件，即费用和时间的约束，即可求得最优线路，进而设计最优行程表；最后，第五问是建立在第三和第四小问基础上的有机组合，实现的方法是：在第三问所求得的结果的基础上，把第四问的约束条件添加进去，最后解得最优线路并设计最有行程表。三、模型假设1、不考虑班车和航班的推迟或取消，忽略天气影响或不可预测的事故； 2、把经纬度看成是平面坐标的两簇相互垂直的平行线； 3、旅馆处于非满客状态，即总可预订到房间； 4、在时间的认识上，把当天早上八点到次日的早上八点定义为一天； 5、不考虑实际生活中出现的堵车等车等不可知现象。四、符号说明城市i与城市j的图上距离 旅游总费用 第i个城市到第j个城市的交通费 第i个城市到第j个城市是否需要通车 第个城市到第个城市的时间表示最优线路五、模型建立根据以上假设，把最优线路问题看成是时间和花费的函数，而时间和花费又是相互联系的，通过建立以下（01）变量，构造模型的目标函数、旅游费用函数 。六、模型求解第一问求解：根据以上模型，本小问即是求解函数F使得S取得最小值（设为），转化为TSP问题，目标函数就是： min根据相关资料得到各个城市的经纬度，以经度为横坐标，纬度为纵坐标，建立（经度纬度）坐标图像（图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.84745.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.54161084718.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.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.5796 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.3710 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.710594.65857.51849.77695.18890.721224.43846.73701.16北京634.36977394594.650857.51849.771096.31069.851008.151136.461257.97祁县620.331019.41857.51514.360715.71006.78791.23497.51935.471324.68洛阳507.3826.64849.77715.7297.110784.59506.59375.22670.21156.69黄山462.82266.66695.181096.31006.78784.590470.991078.11235.64430.58武汉518.9620.72890.721069.85791.23506.59407.990709.48198.47838.37西安877.611205.611224.431008.15497.51375.221078.11709.480905.661484.54九江523.41486.39846.731136.46935.47670.2235.64198.47905.660660.46舟山707.31305.56701.161257.971324.681156.69430.58838.371484.54660.460 表3得到最优线路的总路程为： min=4448.680km根据以上最优路线，并通过查阅大量相关资料，得到以下行程表：日期时间行程价格（元）5月1日7；5012：36乘坐列车T114（徐州常州）7012：4013：40乘坐公交29路到常州恐龙园113：4018：00游玩常州恐龙园19018：0020：00游玩常州020：007：00住宿于常州蓝色快舟营销认连锁店1205月2日7：0010：51游玩常州010：5115：08乘坐列车D5431（常州宁波东）7315：0817：38乘坐728W公交到白峰码头乘坐船到普陀区1617：3920：00游玩普陀区020：007：00住宿于普陀山金沙小院905月3日7：008：00乘坐公交到普陀山风景区48：0014：00游玩普陀山风景区20014：0015：41返回宁波东站1615：4122：16乘坐列车K8500（宁波东宣城）6322：1601：33候车05月4日01：3305：07乘坐列车K161（宣城黄山）2905：077：00休息07：008：00乘坐公交到黄山风景区158：0015：00游玩黄山23015：0016：00乘公交返回黄山站1516：0018：28游玩黄山市018：2823：29乘坐列车K70（黄山鹰潭）5123：2900：22候车05月5日00：2203：47乘坐列车K253（鹰潭九江）4206：477：00休息07：008：00乘坐公交到庐山风景区28：0015：00游玩庐山风景区18015：0016：00乘公交返回九江站716：0020：24游玩九江市020：2422：22乘列车K752（九江南昌）2222：2200：22候车05月6日01：426：28乘坐列车1586（南昌武昌）466：287：30休息07：308：00乘坐432W公交到黄鹤楼28：0010：00游玩黄鹤楼8010：0010：30乘坐43W公交返回武昌站210：3020：40游玩武昌市020：4006：27乘坐列车K896（武昌洛阳）925月7日6：277：30休息07：308：30乘坐81W公交到龙门石窟28：3011：30游玩龙门石窟12011：3012：30乘坐43W返回洛阳站212：3015：00游玩洛阳市015：0019：54乘坐列车K388(洛阳西安)5519：5421：00乘坐306W公交车到秦始皇兵马俑221：008：00住宿于西安美宝宾馆后辛门点1385月8日8：0010：00游玩秦始皇兵马俑15010：0011：00乘坐306W公交车返回西安站211：0020：46游玩西安020：4606：19乘坐列车2670（西安祁县）395月9日06：1907：30休息007：3008：30乘坐公交到乔家大院208：3012：30游玩乔家大院4012：3013：29乘坐公交返回祁县站213：2904：00乘坐列车2604（祁县北京）945月10日04：0007：00休息007:00-8:00乘坐地铁2号线和919公交车到八达岭长城148:0011：00游玩八达岭长城4511：0012：00乘坐地铁2号线和919公交车返回北京站1412;0019：28游玩北京019：2826：08乘坐列车T215(北京德州)5423：0800：45候车05月11日00：455：59乘坐列车2244（德州蓝村）575：5907：00休息007：0008：00乘坐公交到崂山风景区2008：0014：00游玩崂山风景区13014：0014：15乘坐311W公交车到青岛站714：1515：22游玩青岛市015:2201:25乘坐列车1112（青岛徐州087吃饭等其他费用660总旅游费用3394总时间（单位：小时）257.58第二问求解：类似的，本小问即是求解函数使得T取得最小值（设为），根据问题分析，只需把第一问完全图的权重改为时间，目标函数即是： min确定城市之间到达的最短时间矩阵:通过网上的相关资料，我们得到各个城市之间到达的最短时间矩阵为：0 322 320 70 660 280 602 562 521 528 724 322 0 944 85 1140 735 583 250 110 840 272 320 944 0 75 100 914 1395 115 110 1015 90 70 85 75 0 75 105 120 110 105 135 130 660 1140 100 75 0 701 994 80 65 731 960 280 735 914 105 701 0 1750 423 270 696 1320 602 583 1395 120 994 1750 0 467 1300 484 490 562 250 115 110 80 423 467 0 70 215 75 521 110 110 105 65 270 1300 70 0 967 170 528 840 1015 135 731 696 484 215 967 0 828 724 272 90 130 960 1320 490 75 170 828 0 求解最优遍历路线:由于每个城市去且仅去一次，最终肯定是形成一个圈的结构，这就导致了这十一个城市其中有的两个城市是直接相连的，另外也有两个城市是不连接的。这就可以考虑设0-1变量，如果两个城市紧接着去旅游的则为1，否则为0。因为每个城市只去一次，所以其中任何一个城市的必有且仅有一条进入路线和一条出的路线。我们引入0-1变量，若通过两城市之间的路径，则赋值为1；若不通过两城市之间的路径，则赋值为0。对于无向图的最短时间路径问题，可以这样理解，从点到点和点到点的边，看成有向弧，其他各条边均看成有不同方向的双弧。使用lingo设计算法（代码5），得到最优解为（截取有通路部分）： Variable Value Reduced Cost X12 1.000000 322.0000 X16 1.000000 280.0000 X29 1.000000 110.0000 X35 1.000000 100.0000 X311 1.000000 90.00000 X46 1.000000 105.0000 X47 1.000000 120.0000 X59 1.000000 65.00000 X710 1.000000 484.0000 X810 1.000000 215.0000 X811 1.000000 75.00000 即最优路线是: 11 8 10 7 4 6 1 2 9 5 3 即（图3）：舟山武汉九江黄山北京洛阳徐州常州西安祁县青岛得 min=1966min 图 3计时间最短的行程表:根据以上线路，结合实际情况，设计出以下线路表，时间最短为：184小时日期时间行程价格（元）5月1日07：3512：26乘坐列车T54（徐州常州）7012：2613：30乘坐出租车到常州恐龙公园4013：3017：30游玩常州恐龙公园19017：3018：60乘坐出租车到常州奔牛机场4018：3021：10休息021：1023：00乘坐飞机MU5638(常州西安)62323：0024：00乘坐出租车到秦始皇兵马俑405月2日00:008：00住宿于西安美宝宾馆后辛门店1388；0010：00游玩秦始皇兵马俑15010：0011：00乘坐出租车西安咸阳飞机场4011：0011：35游玩西安市011：3512：50乘坐飞机GS4612（西安太原）41312：5014：00乘坐公交车到乔家大院4014：0017：00游玩乔家大院4017：0018：00乘坐出租车到西安咸阳飞机场4018：0018：35游玩太原018：3519：55乘坐飞机SC4612（太原青岛）63119：5521：00乘坐出租车到崂山风景取4021：008：00住宿于青岛新天桥宾馆885月3日8：0014:00游玩崂山风景区13014:0015:00乘公交车返回青岛流亭机场4015：0017：30游玩青岛017：3018：55乘坐飞机HU7842（青岛宁波）74318：5520：00乘坐出租车到普陀山风景区4020：0008：00住宿于舟山华融大酒店1585月4日8：0014：00游玩普陀山风景区20014：0015：00乘坐出租车返回宁波栎社飞机场4015：0020：40游玩宁波市020：4022：00乘坐飞机MU2532（宁波武汉）53622：0023：00乘坐出租车到黄鹤楼4023：0008：00住宿于武汉鄂钢大酒店895月5日08：0010：00游玩黄鹤楼8010：0011：00乘坐出租车到武汉天河国际场4011：0013：08游玩武汉市013：0814：52乘坐列车D3241（武汉庐山）11814：5216：00乘坐出租车到庐山风景区18016：0020：00游玩九江市4020：0008：00住宿于九江悠然快捷酒店425月6日08：0015：00游玩庐山风景区18015：0016：15乘出租车到九江4016：1520：04乘坐列车K1187（九江鹰潭）4220：0422：29候车022：2903：47乘坐列车（鹰潭黄山）515月7日03：4707：00休息007：0008：00承租出租车到黄山风景区4008：0015：00游玩黄山23015：0016：00乘出租车到黄山机场4016：0021：35游玩黄山市021：3523：35乘坐飞机CA1552（黄山北京）86523：3507;00住宿于北京佳号宾馆1685月8日07:0008：00乘坐出租车到八达岭长城4008：0011：00游玩八达岭长城4511：0012：00乘坐出租车返回北京首都机场012：0012：55游玩北京012：5514：40乘坐飞机MU5695（北京洛阳075614：4015：00乘坐出租车到龙门石窟4015：0018：00游玩龙门石窟12018：0018：32乘坐出租车返回洛阳站4018：3201：02乘坐列车K1132（洛阳徐州）70吃饭等其他费用480总旅游费8272总时间（单位：小时）185第三问求解：在第一问的求解结果的基础上，我们添加以下约束，旅游总经费：并且把旅游景点的个数调整为动态的。首先，确定第一小问各个景点的总花费（如表4）和城际交通费用（如表5），列出下表：城市1234567891011花费（元）0311214734414428984292253326 表4城市1-22-1111-77-1010-88-66-99-55-44-33-1花费（元）7073635146925539945487 表5根据第一小问的总费用为3394，运用排除法，基本步骤是： 1、把最大花费的城市剔除，删去相关车费，并添加与该城市相连的两点间的车费； 2、确定路线设计最优行程表，把所得最少经费与2000对比； 重复以上步骤直至最少经费大于2000跳出。 根据相关数据，我们得到最优路线（如图4）是： 图4=6 9 5 4 3 1 7 10 8 即：洛阳西安祁县北京青岛徐州黄山九江武汉具体行程表如下：日期时间行程价格（元）5月1日21：3807：08乘坐列车K614（徐州九江）875月2日7：088：00乘坐公交到庐山风景区28：0015：00游玩庐山风景区18015：0016：00乘坐公交返回九江站216：0020：24游玩九江市020：2422：22乘坐列车K752（九江南昌）2222：2201：42候车001：426：28乘坐列车1586（南昌武昌）466：287：30休息05月3日7：308：00乘坐43W公交到黄鹤楼28：0010：00游玩黄鹤楼8010：0010：30乘坐43W公交返回武昌站210：3020：40游玩武昌市020：4006：27乘坐列车K896（武昌洛阳）926：277：30休息05月4日7：308：30乘坐81W公交到龙门石窟28：3011：30游玩龙门石窟12011：3012：30乘坐43W返回洛阳站212：3017：15游玩洛阳市017：1522：47乘坐列车K388（洛阳西安）3222：4700：00乘坐306W公交车到秦始皇兵马俑200：008：00住宿于西安美宝宾馆后辛门店1385月5日8：0010：00游玩秦始皇兵马俑15010：0011：00乘坐306W公交返回西安站211：0020：46游玩西安020：4606：19乘坐列车2670（西安祁县）3906：1907：30休息007：3008：30乘坐公交到乔家大院208：3012：30游玩乔家大院405月6日12：3013：29乘公交返回祁县站213：2904：00乘坐列车2604（祁县北京09404：0007：00休息007：0008:00乘坐地铁2号线和919公交到八达岭长城1408:0011:00游玩八达岭4511：0012：00乘坐地铁2号线和919公交返回北京站145月7日12：0019：28游玩北京019：2823：08乘坐列车T215（北京德州）5423：0800：45候车000：455：59乘坐列车2244（德州蓝村）575：5907：00休息007：0008：30乘坐公交到崂山2008：3014：00游玩崂山13014：0014：15乘坐311W公交车到青岛站714：1515：22游玩青岛0015：2201：25乘坐列车1112（青岛徐州）87吃饭等其他费用420总费用1988总时间（单位：分钟）10307由于第一天都在徐州，直到21：38才出发，故第一天的其他费用不计，求得最后最少费用为1998元。第四问求解：同样类似于第三问，基于第二问的求解结果，添加时间上的约束（7200分钟）, 并且把旅游景点的个数调整为动态的。首先，确定第一小问各个景点的总花费时间（如表6）和城际交通时间（如表7），列出下表： 城市1234567891011时间(min)052412957603452281072788147518231545表6城市1-22-99-55-33-1111-88-1010-77-44-66-1时间（min）29111065808580102318120105280 表7先把停留时间最长的四个城市剔除，即西安、九江、舟山、青岛，将剩下的城市计算得到最短花费时间为4593min（不包括到达中断城市的车程），远远小与7200min。把四个城市分别添加进去，通过计算，发现添加青岛进去时，结果较好。考虑到祁县的交通问题，把西安添加进去，再计算总时间，结果不符合要求，最后，把黄山剔除，得到的结果符合要求。即得到最优路线：8 4 6 1 2 9 5 3 即：武汉北京洛阳徐州常州西安祁县青岛具体行程表如下：日期时间行程价格（元）5月1日07：3512：26乘坐列车T54（徐州常州）7012;2613:30乘坐出租车到常州恐龙园4013：3017：30游玩常州恐龙园19017：3018：30乘坐出租车到常州奔牛机场4018：3021：10休息021：1023：00乘坐飞机MU5638（常州西安）62323：0024：00车出租车到秦始皇兵马俑0405月2日00：0008：00住宿于西安美宝宾馆后辛门店13808：0010：00游玩秦始皇兵马俑15010：0011：00乘坐出租到西安咸阳飞机场4011：0011：35游玩西安市011：3512：50乘飞机GS7582（西安太原）41312：5014：00乘坐公交到乔家大院4014：0017：00游玩乔家大院4017：0018：00乘坐出租车返回安咸阳机场4018：0018：35游玩太原018：3519：55乘坐飞机SC4612（太原青岛）63119：5521：00乘出租车到崂山4021：008：00住宿于青岛亲天桥宾馆885月3日8：0014：00游玩崂山13014：0015：00乘公交返回青岛流亭机场4015：0020：00游玩青岛020：0021：55乘飞机HU9960（青岛武汉0144521：5523：00乘出租车到黄鹤楼4023：0008：00住宿于武汉鄂钢大酒店895月4日08：0010：00游玩黄鹤楼8010：0010：40乘出租车到武汉天河国际机场4010：4012：35乘坐飞机CA1334（武汉北京）94112：3513;35乘出租到八达岭长城4013:3516:35游玩八达岭长城4516:3517：35乘出租返回北京首都机场4017：3519