旅游线路优化设计

《旅游线路优化设计》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、r_]王徐民方玉平张慧慧(中国矿业大学理学院，江苏徐州221008)摘要：对于旅游，选择合理的旅游路线来达到省钱省时的最佳效果是旅游者首要考虑的问题。本文通过对十个不同省市景点的具体情况，针对要求设计出了相应的旅游路线，建立了最佳旅游路线的图论模型，提出了近似求解的算法，并用MATLAB软件进行求解；从而设计出最优的旅游路线。关键词：最佳旅行商人问题；Floyd算法；最优H圈；旅游路线设计DOl：10．5969／J．issn．1671—6596．20I1．24．0160ptimalDesignofT0uristRoutes、vANGXU—min．FANGY_u．ping．ZHANGHu

2、i—hui(Collegeofscience，ChinaUniversityofMiningandTechnology，Xuzhou，liangsu221008)Abstract：Basedonthetentourismspotsindifferentprovincesdesignedfordifferenttravelitinerary．weestablishedthebesttouristroutegraphtheory，proposedalgorithm，andsolveditbyMATLABsoftware．Keywords：Besttravelingsalesmanprobl

3、em；Floydalgorithm；Optimalhamitioncircuit；Travelroutesdesignl引言比较小，可以考虑用一般方法近似求Hamilton圈就能得到随着人们生活水平的不断提高，旅游已成为提高人们比较好的结果了。生活质量的重要活动。江苏徐州有一位旅游爱好者打算在3模型准备今年的五月一日早上8点之后出发，作为背包客出游，参观3．1基本假设常州市恐龙园、青岛市崂山、八达岭长城、祁县乔家大(1)旅游费用以网上公布为准，具体包括交通费、住院、洛阳市龙门石窟、黄山市黄山、武汉市黄鹤楼、西安宿费、景点门票(第一门票)。晚上2O：o0至次日早晨7：市秦始皇兵马俑、九江

4、市庐山、舟山市普陀山十个景点，00之问。出于人道主义考虑，如果在某地停留超过6小时，在各景点的最短停留时间分别为：4、6、3、3、3、7、2、必须住宿，住宿费用不超过200元／天。吃饭等其它费用2、7、6(小时)，最后回到徐州。如果游客想将十个景点6O元／天；(2)假设景点的开放时间为8：O0至18：00；全游览完，计算出至少需要的旅游费用，并且为该旅游爱(3)汽车火车车次飞机航班等均以网上公布为准，忽略一好者设计详细的行程表，该行程表应包括具体的交通信息切等车时间；(4)天气等一切突发情况不纳入考虑范围；(车次、航班号、起止时间、票价等)、宾馆地点和名称，对于道路的拥挤程度不予考虑，

5、认为都是通畅的；(5)每门票费用，在景点的停留时间等信息。个景点严格按照最少逗留时间在景区逗留，不出现特殊情2问题分析况。分析问题得知求最少旅游费用(包括交通费用和在景3．2有关概念点游览费用)的问题实际上就是在一定的约束条件下求出恰好包含每个顶点的圈称为HamiIton圈。而所求解出费用最小值。从整体上来讲，题目实际上研究的就是图论的最短Hamiiton圈称为最优推销员回路。中的组合优化的问题。把每个景点看作图中的一个顶点，4模型的建立各个景点可以到达看作图中对应顶点间的边，各景点的费问题是解决旅游者游完以上十个景点所需的最少费用看作对应边的权值，于是形成了旅行问题的加权网络用；在不

6、考虑时间成本的情况下，旅游费用主要包括交通图。那问题就转化成了求这个简单的网络加权图的最佳推费用、食宿费用、景点门票费用；这些费用中景点门票是销员回路问题，也就是图的最优的Hamilton圈的问题固定的，为一常数；故所考虑的费用因素为交通费用和食(TSP问题)了。在加权图中求最佳推销员回路问题是一个宿费用。我们希望花最少的钱旅游完所有的旅游景点，我多局部最优的最优化问题，最简易的解决方法是通过穷举们假设任何两景点之问的距离是固定的，并且列车或汽车寻找最短路径。其算法复杂度一般取决于顶点个数，这样的车速一定；这便可以把求花费转化为求路程，即转化为将导致随着顶点的增大，复杂度成指数形式增长

7、，该方法求最小路径的问题了；也即是将景区图转化成加权网络图几乎不可能实现，目前已经证明TSP问题是NP一难的。目前G，求出最佳H圈。的解法主要有遗传算法、最小生成树、模拟退火、蚁群把每个旅游景区景点看作图中的一个节点，各景区景法、局部搜索、神经网络等。但是本文考虑的问题规模点之间的路线看作图中对应节点间的边，各条路线的长度收稿日期：2011一O6—14修回日期：2011-07-03基金项目：中央高校基本科研业务费专项基金(课题编号：2010LK