B旅游线路的优化设计文档

题 目 ： 旅游线路的优化设计 摘要 本文考虑的是旅游时间（费用）不受限制的情况下，如何安排旅游路线不重复且有返回的游览完所有景点，使得费用（时间）最少，以及费用（时间）受限制或两者都受限制时，如何安排不重复且有返回的路线使得游览的景点最多。 （一）对优化模型的理解： 路线优化模型：首先我们知道本问题属于旅游路线的优化问题。为了建立模型，首先应将各景点线路转化为纯数学形式的点线集合，进行图论方面的分析。 本问题主要是解决两方面的问题：（1）、（2）两问是在时间或旅游费用不限的情况下，游完十个景点怎样才可以做到费用最省或是时间最省；（3）、（4）、（5）问是在旅游时间或是旅游费用或是两者都有约束条件的情况下，怎样才可以玩更多的地方。 根据对第一方面问题的分析可知，该问题属于旅行商问题（Traveling Salesman Problem,TSP）。对旅行商问题的理解：一位销售商从N个城市的某个城市出发，不重复的走完其余N-1个城市并回到原出发点，在所有可能路径中求出路径长度最短的一条。用图语言描述TSP：给出一个图G=（V，E），每边Ee

上有非负权值)(ew， 寻找G的Hamilton圈C，使得C的总权)()()(cEeewcW最

小。在一定程度上，各景点间的 距离与两点间的单程最省路费（单程最短时间）是成正比的，所以把两景点的最

省路（最短时间）作为权值)(ew是可行的。 第二面要解决的问题是在费用（时间）有限制或两者都有限制的情况的情况下观赏的景点近可能多，根据这种要求可从这种方案入手：建立多目标规划模型，通过适当的拟合或线性加权，把多目标转化为单目标

（二）综上所述，得到各种条件下的最优路线方案见表1.1： 表1.1 问题 结果 旅游路线 （1） 3012元

徐州青岛市崂山八达岭长城祁县乔家大院兵马俑西安市秦始皇洛阳市龙门石窟武汉市黄鹤楼市庐山九江舟山市普陀山黄山市黄山常州市恐龙园徐州 （2） 9.4天 徐州常州市恐龙园祁县乔家大院皇兵马俑西安市秦始洛阳市龙门石窟八达岭长城武汉市黄鹤楼青岛市崂山九江市庐山舟山市普陀山黄山市黄山徐州

（3） 1954元 7个景点 徐州武汉市黄鹤楼青岛市崂山八达岭长城祁县乔家大院西安市秦始皇兵马俑常州市恐龙园徐州

（4） 4.6天 5个景点 徐州常州市恐龙园西安市秦始皇兵马俑八达岭长城洛阳市龙门石窟九江市庐山徐州

（5） 1201元 4.6 天 3个景点 徐州八达岭长城西安市秦始皇兵马俑常州市恐龙园徐州



由于不同的网站公布的信息存在一定偏差，所以该结果仅依求解时提供的网站信息。

【关键词】多目标规划 旅行商问题 Hamilton圈 线性加权 最优化 一、问题重述 随着人们生活水平的提高，旅游逐渐成为最热门的户外活动之一。在旅游的过程中，我们不仅可以感受大自然之美、放松心情，而且可以领略不同地方的文化气息、拓宽视野。 旅游者在今年五月一日8点之后从江苏徐州出发，到全国一些著名景点旅游，最后回到徐州。由于跟团旅游会受到限制，旅游者打算自己背包出游。出行路途中有以下几个条件：（A）城际交通出行可以乘火车（含高铁）、长途汽车或飞机（不允许包车或包及），并且车票或机票可预定到。（B）市内交通出行可乘公交车（含专线大巴、小巴）、地铁或出租车。（C）旅游费用以网上公布为准，具体包括交通费、住宿费、景点门票（第一门票）。晚上20：:00至次日早晨7：:00之间，如果在某地停留超过6小时，必须住宿，住宿费用不超过200元/天。吃饭等其它费用60元/天。（D）假设景点的开放时间为8:00至18:00. 根据以上条件考虑到旅游者的以下需求： 1、在时间不限的情况下，游览全部景点，旅游费用最省； 2、在旅游费用不限的情况下，游览全部景点，旅游时间最短； 3、在旅游费用一定的情况下，游览尽可能多的景点； 4、在时间一定的情况下，游览尽可能多的景点； 5、在时间和旅游费用都一定的情况下，游览尽可能多的景点。 针对以上几种情况，建立相关的数学模型并为该旅行者设计详细的行程表，行程表中应包括具体的交通信息（车次、航班号、起止时间、票价等）、宾馆地点和名称，门票费用，在景点的停留时间等信息。 二、问题分析 2.1问题背景分析 对于人们生活水平不断提高，越来越多的人会选择在节假日游览一下祖国的大好河山，领略一下各地的风土人情和人文气息。在旅游的时候人们往往会想，怎样才能花最少的费用、时间游览预订的地方，怎样设计路线才能在有限的费用、时间内游览更多的地方。这就需要我们建立高效实用的数学模型来解决这些问题。 2.2对题目的理解 首先我们知道本问题属于旅游路线的优化问题。为了建立模型，首先应将各景点线路转化为纯数学形式的点线集合，进行图论方面的分析。 本问题主要是解决两方面的问题：（1）、（2）两问是在时间或旅游费用不限的情况下，游完十个景点怎样才可以做到费用最省或是时间最省；（3）、（4）、（5）问是在旅游时间或是旅游费用或是两者都有约束条件的情况下，怎样才可以玩更多的地方。 第一方面 根据对第一方面问题的分析可知，问题目的在于当时间（费用）不限的情况下求游完所有景点并回到出发地点所用的费用（时间）的最小值。该问题属于旅行商问题（Traveling Salesman Problem,TSP）。为了建立数学模型，首先应该将各个景点转化为纯数学形式的点线的集合，进行图论方面的分析。下面给出旅行商问题的定义： 旅行商问题：一位销售商从N个城市的某个城市出发，不重复的走完其余N-1个城市并回到原出发点，在所有可能路径中求出路径长度最短的一条。用数学语言描述TSP，即给定一组N个城市和它们两两之间的直达距离，寻找一条闭合的旅程，使得每个城市刚好经过一次且总的旅行距离最短。用图语言描述TSP：给出一个图G=（V，E），每边Ee上有非负权值w（e）， 寻找G的Hamilton圈C，使得C的总权)()()(cEeewcW最小。TSP问题是一个典型的组合

优化问题，其可能的搜索路径随着城市数目N的增加呈指数增长，属于NP完全问题。 了解了以上只是后，我们更加确定了该问题就是旅行商问题。只是在实际的处理中，我们把两景点的最省路费（最短时间）最为赋权值w（e），在一定程度上，各景点间的距离与两点间的单程最省路费（单程最短时间）是成正比的，所以把两景点的最省路（最短时间）作为权值w（e）是可行的。 第二方面 这一方面要解决的问题是在费用（时间）有限制或两者都有限制的情况的情况下观赏的景点近可能多，根据这种要求可从以下方案入手： 建立多目标规划模型，通过适当的拟合或线性加权，把多目标转化为单目标

三、模型假设 1、在旅游期间，天气晴朗，列车和航班没有延误并且准时到站，市内交通也没有出现长时间的堵塞 2、该旅游者是成年人，不考虑学生票的问题 3、旅游者在两地旅游来回时间和路上花的费用是相同的 四、符号约定 Xij ——路线决策变量（0—1变量） Lij ——从i地到j地的路费、路上的基本消费和需住宿时的住宿费用（单位：元） （i，j=12……11） Pi ——地区景点的第一门票费用（单位：元）（i=1，2……10） Pij ——i景点和j景点的门票费用之和（单位：元）（i=1，2……10） T ——在景点所在地区停留的时间，包括在景点的游玩时间和停留住宿等时间（单位：天）（i,j=1,2……11） A ——每天的基本消费60（单位：元） M ——旅游总共的消费（单位：元） S ——旅游总共的用时（单位：小时） Sij ——i景点和j景点的所用时间之和，（单位：小时）（i=1，2……10） Tij ——从i景点到j景点的时间，包括旅途是时间、停留等车时间、住宿时间（单位：小时）（i,j=1,2……11） Ti ——在景点i的观光时间（单位：小时）（i=1，2……10）

五、模型建立与求解 5.1 1、问题理解 在时间不受限制的情况下，可游览完所有景点，要求消费总和最低。也就是说，从徐州出发，逐一观赏各景点，不能重复，然后再回到徐州，使得这一过程中总的花费最少。这一过程中我们尽量选择便宜的交通工具。 2、模型分析 我们把各景点转化为纯数学形式的点线集合，利用图论方面的知识求解。 为了达到旅游费用最低，交通方式的费用应采用最低，并且应该尽量避免住宿，因此我们采取晚上乘火车去下一个景点。现给出旅游景点门票费用，每天基本费用（吃饭等其它费用60元），市内交通（从火车站到旅游景点的双程费用））的最低费，见表5.1.1。

表5.1.1 旅游景点 常州市恐龙园 青岛市崂山 八达岭长城 祁县乔家大院 洛阳市龙门石窟 黄山市黄山 武汉市黄鹤楼 秦始皇兵马俑 九江市庐山 舟山市普陀山

门票费用（元/人） 160 70 50 40 80 150 50 90 180 160

基本费用 60 60 60 60 60 60 60 60 60 60 市内交通 29路（4元） 304路（4元） 地铁2号线换乘直达车（20元） 81路（4元） 旅游班车（26元） 10路（4元） 306路（12元） 102路（24元） 轮船（28元）