最佳旅游路线设计

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

1、姓名：李忻玮学号：07111044题目：D最佳旅游路线设计摘要本论文主要考虑通过合理的假设将问题简化为图论问题，使用floyed算法得到任意两点间的最短路径后，带入各景点间的距离、时间、门票等信息后，视为0-1线性规划模型用lingo进行求解。问题一给出了一个月的时间要求，同时需要考虑到最少的花费和前往最多的景点两个规划目标，是一个0-1多目标的线性规划问题。我们通过将其中一个规划目标：“最多的景点”划入约束条件，将多目标问题变成“在前往N（N>=12)个景点的条件下，最少花费”的0-1线性单目标规划问题。使用lingo后求出结果如下：乌鲁木齐—哈密—库尔勒—楼兰—阿克苏—千佛洞—天鹅湖

2、—伊犁—石河子—博乐—克拉玛依—阿勒泰—天池—乌鲁木齐。问题二要求用两年暑假游遍新疆的所有假期，即使用两个除乌鲁木齐外不想交的圈遍历全图，并使两条线路的总费用最小。显然可得，将所有的顶点以乌鲁木齐为界划分出南北两块，每个区块使用一个圈进行遍历将能节省费用。我们以行驶路程为规划目标，用相应的约束条件建立0-1线性规划模型，使用lingo求解两个区块的的最佳旅行路线。再分析均衡度后调整区块的分布，以求得最佳均衡度的分组。求解得最佳路线规划如下：问题三与问题二的解答方法相同，根据各景点之间的最短路径画出以乌鲁木齐为根的树形图，然后将地理上在一个区域的景点分为三块。将模型二中的目标函数替换为考察

3、时间最小后，可使用lingo计算出每组的最佳路线，在参考均衡度对分组进行调整后可得到近似的最佳分组和每组的最佳路线。结果如下：问题四中，通过合理假设，我们认为每个景点只应该出现在一条线路上。据此，我们根据假期时间限制以及游遍所有景点所需时间最少，求得至少要提供4条旅游路线才能满足题意。根据分析，我们发现无法找到这样4条路线均满足要求，因此，我们将所有景点分为5组，通过多次求解调整，最终我们为旅行社提供了5种路线。具体结果在正文中给出。最后，本文对模型进行了分析与评价。关键词最短距离均衡度0-1线性规划最佳路线一、问题的重述王先生夫妇是华东某高校的年轻教师，打算暑假中到新疆旅游。受文学作品

4、的影响，天池、达坂城、吐鲁番、楼兰古城、伊犁都是他们十分向往的地方，新疆的其他地方对他们也有很大的吸引力。1．请你们为他们设计合适的旅游路线，使他们在今年暑假一个月的时间里花最少的钱游尽可能多的地方，并估算除吃饭之外的费用。[12]姓名：李忻玮学号：07111044题目：D2．如果他们打算今、明两年暑假完成对新疆的旅游，请你们为他们设计合适的旅游路线，使在新疆境内的交通费用尽量地节省。3．如果华东某高校的少数民族研究所组织对新疆文化考察，考察分三组进行，用于交通的时间和前两种情况相同，但考察时间是旅游观光时间的四倍，请你们为他们设计合适的考察路线，以便尽早完成考察任务。4．新疆自治区旅游

5、部门为迎接“五一旅游黄金周”（考虑到远途旅游，自治区内游程延长为十二天）准备为自治区外的游客组织多条旅游路线以分散游客，提高接待的质量。在假设参加你们设计的各条路线的游客人数与整条路线的接待能力成比例的条件下，请你们为新疆自治区旅游部门设计合适的、准备向游客推介的全部旅游路线。下图是新疆主要景点分布图，各旅游点之间的路程、每个景点的最佳逗留时间等信息可以登陆新疆旅游网对题。你也可以目做进一步的完善。二、问题的分析由简单的分析可以得出，问题的实质都是要求得出一条满足某一约束条件的旅游路线。我们将景区进行编号，并通过网络查找到各个景点之间的距离，我们就可以将实际地图简化为赋权无向图，所以问题

6、就变成了图论问题。另外我们还需补充路费、最佳逗留时间以及门票费用等其他信息。[12]姓名：李忻玮学号：07111044题目：D问题一的目标是找到一条能在一个月内实现的最佳旅游路线，要求花费最少，景点最多，这是一个多目标线性规划问题。我们可以使用floyd算法求得各个顶点（景区）之间的最短路径，然后我们以花费最少为规划目标，将“景点最多”这一目标放入限制条件中，要求走过的景点数为N（N>=12)。然后再建立时间、景点路线为要求的约束条件，将多目标规划问题转变成单目标0-1规划问题。使用lingo求解可得最佳旅游路线。问题二需要两条旅游线路，这两条旅游线路可以覆盖新疆的全部景点。同时这两条线

7、路都从乌鲁木齐出发再回到乌鲁木齐，彼此之间无重复的景点，这两组线路所需时间都在一月之内。我们很容易想到，将全部的景点以乌鲁木齐为界分为南北两组比较容易求出满足要求的路线。我们将景点进行分组，并计算均衡度后利用0-1规划求解得到的最佳路线及所需时间，再根据均衡度进行调整，选取均衡度最佳的一组。问题三是多旅行商问题。解法同问题二，我们将所有景点分为3组，使各组的考察时间尽量相等。由问题一中已经画出的各景点间的最短路径，求出以乌鲁木齐为起