最佳旅行路线设计(值得细读),图论

《最佳旅行路线设计(值得细读),图论》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、302006最佳旅行线路设计摘要：新疆地域广阔，旅游资源繁多，本文以节约费用或时间为目标，分别为自助游、考察等具体情况安排了旅游线路，并为“五一旅游黄金周”设计线路，缓解景区客流高峰及提高接待质量。我们采集了全疆共33个景点景区的数据，其中不乏有十分接近的，故我们按地理位置将它们进行聚类，最终得到20大景区。接着，建立在交通费用与路线长度成正比、不同景点的住宿费用相等、车辆行驶于公路铁路的时速恒定等假设条件下，我们先用Floyd算法求出了景区两两间的最短路径，接着用蚁群算法估计了遍历所有景区所花费的时间总和，为下文设计合理的线路

2、做准备。对第一问，通过简单计算我们发现，单位时间内游览景区的花费要小于往返景区途中的花费，亦即：花最少的钱与游尽可能多的地方这两个目标在本题中是统一的。为此，我们提出了一个以确定一条游览尽可能多景区的旅游线路为目标、游览总时间为约束的0-1整数规划模型，利用LINGO软件估计了解的下限，用遗传算法求得了最优解：两人一个月时间花费约6100元游览17个景区。对第二问，根据蚁群算法的结果可知，只要适当安排我们便可以在2个月内完成对新疆所有景区的游览。为此我们从两种思考的角度，建立了不同的模型来求解交通费用的最省问题。首先我们以两次旅

3、游的路程长度之和为适应度函数用遗传算法求出了包含所有景区的两条路径，并使它们的路径长之和最短。接着，我们利用景点分布图固有的特点，从简化图的角度将20个点的连通图化为一个只包含6个顶点的图，并用枚举法将可能的5种结果逐一计算，求得最佳线路。在处理考察任务问题时，由于考察景区所花费的时间远大于在景区间往返的时间，所以我们首先忽略路程上的花费，将如何安排三个考察组抽象成一个线性规划问题，以最小化三个考察小组的最长耗时为目标并用LINGO软件求解，得到一些目标函数值相同但考察景区不同的最优解，在此基础上，我们将路程耗时纳入考虑之列，再

4、一次使用遗传算法，目的是求得更精确的解。对第四问，即设计“五一黄金周”旅游线路问题，我们以错开游客高峰、景区利用率尽量高、同一线路的景区跨越尽可能小、线路多且丰富等条件作为安排线路的目标来设计算法，在给出14条黄金游线路的同时，又对问题加以进一步完善，即利用剩余资源开辟了一些5-6天的短途游线路，以充分利用旅游资源并满足不同游客的不同要求。在模型与软件的展望部分，我们阐述了规划模型、蚁群模型与遗传算法模型等的特点及其他应用领域，也将文章中运用的四种软件：马克威分析系统、LINGO、Excel以及MATLAB软件的特点和扩展做了逐

5、一的介绍。本文的优点是充分将规划与遗传算法相结合，突出规划模型意义的同时也发挥了遗传算法高效的特点。同时，较好的数据预处理与蚁群算法的环游估计都为解决问题做了铺垫。另外，设计黄金周旅游线路时，我们不仅考虑了丰富多彩10日以上旅游线路，也辅之以一些中短规模的旅游路线，为游客提供了更多的选择余地。值得一提的是，本文还综合运用了四种软件。关键字：聚类、最短路、蚁群算法、遗传算法、线性规划、枚举法、马克威分析系统、LINGO、Excel、MATLAB。34最佳旅游路线设计302006一、问题的重述：随着近年来旅游业的不断发展，我国新疆的

6、天池、达坂城、吐鲁番、楼兰古城、伊犁等等的异域风情，越来越吸引着广大的游客。在本文中，我们要完成以下几个关于旅游路线设计的问题：1．在科学估算旅游费用的基础上，以总成本尽量小为目标，设计一条在一个月（计30天）的时间里，游尽可能多的地方的旅游路线。（吃饭费用不计）2．以在各景点间的交通费用尽量小为目标，设计两条互不重叠的旅游路线，路线各为期一个月，且其合集包含新疆所有景点。3．设计三条互不重叠的旅游考察路线，在每个景点考察的时间是旅游观光时间的四倍，用于交通的时间则不变，要求三条考察路线各自所用时间的最大值尽可能小。4．设计若干

7、条为期十二天的黄金周旅游路线，以分散游客，提高景点的接待质量，设参加这些旅游路线的游客人数与整条路线的接待能力成比例。5.（对题目的进一步完善）对于上面第4个问题，考虑到新疆旅游实际问题的复杂性，除了设计一些为期12天的旅游路线外，还可以适当的设计一些短期的旅游线路，这样既可以方便游客、给他们提供了更多的选择，又可以充分利用各景区的旅游资源，避免其闲置。二、问题的分析在收集新疆各个主要旅游景点之间的路程、各个景点的最佳逗留时间等信息的基础上，我们将问题做以如下的分析和抽象：因为新疆的旅游景点众多，所处的地理位置也不相同，从旅游路

8、线设计的实际出发，显然要考虑到哪些景点相距较近，可以同时游览，因而，我们需要将新疆境内的所有主要的旅游景点按照经纬度及是否可以直接连通予以分组。所以本文中我们首先采用聚类分析的方法，运用马克威软件将各景点归为若干景区，以便于下一步的分析。另外，由于路程、时间、价