数学建模旅游问题C2

【摘要】

旅游的最佳线路的选择会直接决定旅行者的旅行时间和金钱的花费，设计合理可行的旅游线路则使这一费用的唯一标准，由于实际纷繁复杂的景点，交通，时间等对方面因素的综合影响和相互作用下，通过“点线图”将复杂的现实景点和路线表示在便于处理的简单的只有点和线组成的图中，便于我们运用一定的数学工具进行最优化处理。

通过综合各方面的信息、资源，并对其进行相应的处理整合如“点线图”，在保证合理，准确，有效，详实的同时，将抽象的，复杂的实际概念和数据量，转化为有价值的，精确的时间和费用值。这样“点线图”中每一个点就对应地包含其最佳停留时间和花费情况，其中为了合理的表示花费，构造“城市分”的概念来表示。而每一条线也都对应地包含所花费的时间和费用，这些数量通过表格给出，在求取最优解时视为相应点或线的特性。为了难保证这种转化的实际意义和有效性，准确性，通过多方数据的综合分析、平均，共同得到的综合得到。

在“点线图”的基础上，做出必要假设和的基础上，将图形做进一步的简化分区，将一个图形分成若干个子图，对图进行处理，把问题拆减。利用已经比较成熟的Dijstra算法，找到其它城市距离中心城市（这里使乌鲁木齐）的最小距离，然后利用避图法找到最小树，这样在路线周围，结合图形特点，围绕近似路线周围作局部搜索，在大大减少数据运算的情况下，得到相对最优解。对得到的最优解进行检验，验证其确实是比较优的线路。即基本处理过程为：

抽象图形 分解图 找到近似算法 子图中在近似算法得到路径周围搜索 调整边界 检验路线

分析建模、解模的整个过程，合理地分析可以得到，方法可以被推广到其它更加复杂的环境。

【关键词】 ： 点线图 城市分 旅行推销员问题 哈密顿 Dijkstra算法，

避图法

301015

1．问题

随着我国经济的不断增长，节假日外出旅游已经成为当今时代的热点和亮点，而伴随者出游人数的不断增多，产生了一系列的与旅游线路安排，设计，选择的有关的问题，旅游地旅游部门，旅行社，随团游客，自助游者都希望可以构建一个和谐的旅游线路和行程，使所有的人达到最大的满足。

旅游部门希望多条旅游线路合理安排时间，以分散游客，提高接待效率;旅行社希望合理安排人员和旅游线路，以取得最大得收益和利润；随团游客希望选择自己最合适的旅游线路，以达到最大的满足；自助游者希望合理的安排自己的时间和线路，以用尽可能少的时间和花费游览更多的景点??

各方出发点不同，目的不同，但是问题的关键都集中到了旅游路线的设计和选择上。这样，如何选择一条或多条合理，和谐的旅游线路成为问题所在.如何在特定的已有的复杂实际环境计算出最佳的出游或考察路线，如何合理的预算出游的花费和时间？

确实有不少出游者遇到了出游路线的设计问题：华东某高校的年轻教师王先生夫妇打算假期中到新疆旅游.他们对新疆的天池，达坂城，吐鲁番，楼兰故城，伊犁等地有特别感兴趣，而其它地方对他们也有一定的吸引力。他们如何安排合适的旅游线路可以在一个月的时间里最少的钱有尽可能多的地方？相应的路线和旅游情况下？他们的花费应该在多少呢？如果他们今，明两年的暑假完成新疆游呢？线路会有变化吗？又应该重新设计怎样的线路呢？

不仅出游者需要来考虑到处有线路的设计问题，一些类似的活动也需要有合理的安排路线来实现一定的目的：华东某高校少数民族所组织新疆文化考察，考察对分三组分别进行，其中交通费有与旅游情况相同，但是考察时间是旅游观光时间的四倍，这种情况下他们的线路又该如何设计和选择，尽早完成考察任务呢？

与以上问题类似，“五一”黄金周即将到来，如果新疆自治区旅游部门准备为自治区外的游客组织多条旅游路线以分散游客，提高接待的质量（考虑到远途旅游，自治区内游程延长为十二天）。在参加你们设计的各条路线的游客人数与整条路线的接待能力成比例的条件下，新疆自治区旅游部门又该如何设计合适的准备向游客推介的全部旅游路线？

2. 问题处理的现状

对于旅游线路设计的问题，已经受到的各方的关注和重视，也有许多相关的书籍和论文，但基本上都以管理学的理论，市场需求，旅游管理等人文，管理观点为出发点，考虑旅游者心理，资源导向，市场细分，效益，安全等旅游中的人文问题和企业景点的管理问题。几乎完全没有涉及到数学中的最优问题求解的思想和方法，甚至没有把相关的问题规划入数学的计算和处理中，只是停留在表面的“以人为本”的解决思路上。也看到了一些应用数学方法的设计问题，并并没有很量化和很实际准确的处理和案例，只是笼统的思想和方法。

这样在解决问题前，先通过已有的一些书籍和论文对这个倍受关注的旅游线路设计问题的现状作一个简单的介绍和说明，在此基础上提出我们的解决的具体思路和具体方法。

最佳旅游线路的设计

1

301015

2．1 相关出版物列举

2．1．1 《关于旅游线路设计的思考》

《关于旅游线路设计的思考》一书，作为高职高专的旅游专业课程教材，运用现代管理学的理论叙述旅游线路设计的概念、类型、原则和方法，配合一定数量的图表，使旅游线路设计更符合实际，并结合典型的案例帮助学生加深理解和掌握。内容主要涉及旅游线路设计概述，旅游线路类型，旅游线路设计原则，旅游线路市场调研，旅游线路设计方法，旅游线路设计实例。

2．1．2 《旅游线路设计——全国旅游专业系列教材》

《旅游线路设计——全国旅游专业系列教材》一书将提高旅游组织者工作效率、降低旅游企业成本及增强竞争能力，作为实现多数旅游者舒适度不受影响或体力许可前提下，能花较少的费用和较短的时间尽可能旅览更多的风景名胜的关键所在，以此为基础，寻求更好的旅游线路的设计方法，以满足旅游企业与旅游者双方的共同要求。此书的总体编写理论性实践性相结合，体例清晰、严谨，内容简洁、新颖、运用直观形象的图、表等，图文并茂。内容主要涉及：旅游线路设计的理论基础，旅游者消费行为，旅游餐饮，旅游住宿，旅游交通，旅游景区，旅游购物， 旅游娱乐， 旅游线路设计实务。

可以看到相关的书籍只涉及到了人文的管理问题，有很大的局限性，很难用以实际问题的处理上来。

2．2 相关论文列举

与旅游线路的设计问题相关的论文数量很大，但内容是比较集中的，也是比较明显的。这里只拿出两篇比较典型的相关度比较高的论文。 2．2．1《关于旅游线路设计的思考》

《关于旅游线路设计的思考》通过旅游线路要素分析，针对旅游线路现状问题，提出旅游线路设计与经营应更注意市场需求，从消费心理角度注重旅游线路的层次性，旅游线路的设计应体现旅游产品特色，旅游部门应加强旅游连路经营管理。

2．2．2 《旅游线路设计与优化中的运筹学问题》

《旅游线路设计与优化中的运筹学问题》虽然把运筹学的方法引入旅游研究，探讨旅游线路的优化设计问题，基于定量分析和定性分析相结合，重点展示了运筹学和图论方法的运用潜力，但没有着力具体的技术细节。文章同样以旅游学相关的人文学原理，概念为主，并没有具体的提出解决办法和计算过程，更没有运用在实际的问题中。

2．3 现状总结

正如前面指出，收集到的大量的资料表明：已有的关于旅游线路的设计问题的解决完全处在一个“人文”的范畴中，问题的出发点在如何更好地满足各方的需求，如何合理的利用资源，而没有就花费，时间的最小化，最优化进行分析和定量的处理，这个明显的局限性是不可容忍的。

在这样的研究和处理现状下，要想对问题有更进一步的分析，解决，得到更加准确，合理的解决，必须运用相关的数学思想和方法，在一个特定的实际情况基础上，通过转化，计算，处理，作出准确，详实，实际，可行的设计方案，达到经济和时间的最优化。

最佳旅游线路的设计

2

301015

3.假设

3．1 将隶属于同一县，市的不同景点划归到这一城市，由其对应的城市统一代

表，即认为到达某一城市游览，就是对其下属下的部分景区，景点的游览，将全部景点就可以等效的假设为数量较小的城市，但没有缩小游览和考察的地方；

3．2 按城市的位置将各城市，地区设为独立的点，点与点之间的线就是城市之

间的交通路线，即可以通过某种交通往返的城市之间由相应的线段连接，这样把整个旅游的目的地，新疆，假设为一系列点和线组成。整个旅游过程也可被视为在点线图上的移动和停留；

3．3 各点，即各城市应其经济状况，区域，景点数量，质量等多方面因素的影

响，以及在某处的停留时间（包括这住宿），也由该地的景点数量，质量，住宿，交通情况决定，假设这个在某地的花费和停留时间是由城市的各项情况综合确定的 ；

3．4 结束了一点的游览可立即通过相应的交通，即相应的线到达下个点，这里

假设点与点间的转移只花费路上的交通时间。新疆境内整个道路情况相同，车速一定，单位路程所需要的费用一定。而这个一样的车速由整个新疆境内的铁路，公路基本速度，价格情况综合等效得出；

3．5 为简单表述，定义上面的“点和线所表示的新疆”为：点线图，每一点为

其对应的旅游和考察城市，包含需要游览和考察的多个景点，景区，以及相关最佳停留时间和所花费用；每一线为其相对应的路线，包含所花费的时间和路费。

4．建立模型

由基本问题和基本假设出发，对问题的处理应该建立在新疆总体点线图的基础上，而这个点线图应该以新疆的各项实际情况为基础，是一个可以合理的，实际的，体现真是情况，有多项实际意义和指标的基本情况图。这个基本情况应该尽可能的实际，客观，真实。任何的数据失真都会对最终的选择造成影响和变化，这就要在大量的实际数据上抽象出相应时间，费用情况。

在综合点线图情况已知的情况下，可以将问题 4．1建立点线图

由假设，首先将所要的游览（或考察）的目的地（新疆）合理 ，客观地转化相应地点线图，根据假设3.5可知，这里的点线图是包含大量信息的，这就要在实际数据的基础上，分别予以概念。

4．1．1 城市到点的转化 1．最佳时间

由假设3.1根据新疆的实际情况：景区的分布和其隶属情况以及已有的一些比较热的旅游目的地，从中提取出由旅游价值的18个主要的城市，它们按照具

最佳旅游线路的设计

3

301015

体景区的隶属情况，分别包括各自的大部分景点，景区，尽统计，这18个主要的城市包含了95％以上的新疆旅游点，全部的重要的，有意义的游览景点，而在当地所的最佳停留时间应由它所拥有的资源决定：景点，景区的规模，数量，距离城市的距离，即到达所需的时间，都会影响和决定最佳停留时间。所以通过选择提取各地的主要景点，分析其游览所要花费的时间，便可求和求得某地得最佳逗留时间。

这样，根据景点的情况可以按照一定的标准将景点分为A,B,C,D四个等级，评分的标准见表4－1。

表4－1 景区分档标准 评定标准 A B C D 市内及近郊的小市内大型景点,型景点（小型寺，距城市30公里庙等） 内的小型景点（公园等） 1/4天 1/2天 30－100公里范100公里以外的围的重大星型景大型景点（大的点（分景区等） 旅游区等） 1天 2天 所需时间 注：以上时间中已经等效地包含了休息及睡眠时间及按休息、睡眠时间是等比例

于游览时间地，将游览和休息地总时间平均到各景点，所以每一景点地时间都是被加长的，这样就避免游和睡的时间混合计算带来的麻烦。

这样，在以上分档标准的基础，收集、选取各地的主要景点，将其划分在不同的景点，以通过此得到在点的最佳逗留时间，见表4－2。

表4－2 主要景区分级 编城号 市 1 1/4天景点 1/2天景点 红山公园, 二道桥巴扎,新疆民街, 人民公园, 水磨沟,猛进水库, 乌拉泊古城遗址 铁门关, 沙依东园艺场, 艾肯大坂, 蒙古王府旧址 1天景点 南山牧场,西白杨沟,菊花台,东白杨沟,照壁山,苗儿沟, 柴窝堡湖,盐湖, 达坂城 2天景点 天山天池,一号冰川, 乌自治区博物馆,鲁文庙, 塔塔尔木寺, 陕西大寺,齐 南大寺, 汗腾格里清真寺,新疆人民会堂 库大清真寺,巴仑尔台黄庙 勒 2 博斯腾湖, 焉耆县七个星千佛洞, 四十里堡故城遗址 巴音布鲁克草原,天鹅湖, 巩乃斯林场, 阿尔先沟温泉 3 吐鲁番 叶吐鲁番地区博物馆 火焰山,葡萄沟,丰库, 交河故城, 苏公塔, 坎儿井,五道林, 红柳河园艺艾丁湖,高昌故城, 哈拉和卓古墓群, 帕孜克里克千佛洞 最佳旅游线路的设计 4

301015

5 6 7 8 9 10 11 13 14 15 16 17 18 哈密 阿勒泰 塔城 博乐 伊宁 库车 石河子 昌吉 阿克苏 阿图什 喀什 和田 若羌 1 2 1 1 4 2 5 3 3 3 4 1 1 1 12 克拉玛依 64.28 汽 火 77.93 61.42 汽 飞 75.86 60.00 汽 飞 75.86 汽 71.72 61.90 67.14 汽 飞 75.86 60.00 汽 火 飞 80.69 62.85 汽 火 77.93 60.00 汽 飞 75.86 汽 71.72 63.33 62.85 汽 火 77.93 60.00 汽 火 77.93 64.28 汽 火 飞 80.69 60.95 汽 飞 75.86 汽 71.72 60.00 71.10 68.64 67.93 66.81 71.50 70.34 70.39 67.93 67.52 70.39 68.96 72.48 68.40 65.86 注：根据查找得到的信息，这里交通情况基本评分原则为：

（1）. 汽车可以到其它任意地点；

（2）. 火车可以前往火车开通的其它任意地方；

（3）. 飞机只有在乌鲁木齐与有机场的令一城市的航班；

（4）. 通过火车、汽车到另一的记1分，经计算飞机价格大约时火车、汽

车的4倍，这样，记程飞机到另一地记4分。

（5）. 按以上方法加和得到交通分，然后转化为60－100的分数。

表4－7 城市景点数量统计表 编号 城市 景点数量 1/4天景点 1/2天景点 (市内) (市郊) 1 2 3 4 5 6 7 8 9 10 11 13 14 乌鲁木齐 库尔勒 吐鲁番 鄯善 哈密 阿勒泰 塔城 博乐 伊宁 库车 石河子 昌吉 阿克苏 8 2 1 1 2 1 6 2 2 8 4 8 4 5 7 4 1 4 6 2 3 1 1天景点 (30-100公里) 9 5 4 6 4 3 6 10 1 2 1 7 2 2天景点 (100公里外) 2 2 1 1 2 综合 得分 时间 得分 19 11.5 8.25 2 8.75 10 5.25 8.5 13.5 4.5 3.5 2.5 7.5 6 12 克拉马依 100.0 84.21 77.36 64.21 78.42 81.05 71.05 77.89 88.42 69.47 67.36 65.26 75.78 72.63 10

最佳旅游线路的设计

301015

15 16 17 18 阿图什 喀什 和田 若羌 1 4 2 2 6 4 3 1 5 3 2 4.25 5 8.5 7 68.94 70.52 77.89 74.73 表4－8 国家级景点数量表 编号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 城市 A 乌鲁木齐 库尔勒 吐鲁番 鄯善 哈密 阿勒泰 塔城 博乐 伊宁 库车 石河子 克拉马依 昌吉 阿克苏 阿图什 喀什 和田 若羌 3 1 5 2 2 5 3 4 AA 8 2 3 6 2 1 4 5 4 1 3 1 2 国家级景点 AAA 3 4 7 3 4 2 3 3 AAAA 2 1 AAAAA 1 1 1 总A数 分数 41 16 26 0 16 34 12 4 21 0 10 8 16 9 2 8 0 0 100.00 75.60 85.36 60.00 75.60 93.17 71.70 63.90 80.48 60.00 69.75 67.80 75.60 68.78 61.95 67.80 60.00 60.00 表4－9 城市分记算表 编号 1 2 3 4 5 6 7 8 9 10 11 12 13 城市 乌鲁木齐 库尔勒 吐鲁番 鄯善 哈密 阿勒泰 塔城 博乐 伊宁 库车 石河子 克拉马依 昌吉 基础情况 百度指数 住宿出行 72.82 68.31 67.30 71.70 68.13 70.14 62.83 62.25 63.36 64.71 64.97 74.89 63.70 100.00 77.60 82.34 60.00 72.85 68.90 65.99 66.07 70.95 60.00 73.41 78.11 70.20 72.24 70.11 68.96 71.10 68.64 67.93 66.81 71.50 70.34 70.39 67.93 67.52 景点情况 84.21 77.36 64.21 78.42 81.05 71.05 77.89 88.42 69.47 67.36 65.26 75.78 97.28 76.75 77.90 64.01 74.10 78.07 68.75 68.24 77.05 64.90 69.53 69.96 71.75 11

综合得分 100.00 100.00 100.00 75.60 85.36 60.00 75.60 93.17 71.70 63.90 80.48 60.00 69.75 67.80 75.60 最佳旅游线路的设计

301015

14 15 16 17 18 阿克苏 阿图什 喀什 和田 若羌 64.94 62.11 81.86 80.51 75.28 77.26 63.11 78.37 79.19 60.00 70.39 68.96 72.48 68.40 65.86 72.63 68.94 70.52 77.89 74.73 68.78 61.95 67.80 60.00 60.00 71.37 65.34 72.93 72.04 66.38 由表4－9最终给出了18个城市的城市分，将以上数据表示在一张折线图中，以直观的比较，分析所得到的城市分的数字的准确性，见图4－1。

100959085807570656097.2877.976.7578.0774.177.0572.9372.0471.7571.3769.9669.5366.3865.3464.968.7568.2464.01 表4－1 城市，城市分对应表

城市分数据分析：

（1）. 由于数据是由多组不同的量综合得来的，所以对于每一个量来说，都比

较好地反映了一个城市地单位消费情况，可以说做到了客观，真是，准确；

（2）. 可以看到乌鲁木齐的城市分与远远高出其它地区，这以点时可以得到解

释的：纵观各项数据，不难看出，乌鲁木齐都有着比较明显的优势，作为自治区的首府和窗口，得到这样的数据时正常的；

（3）. 整体看来其它城市基本在65－80的范围内，这就表明了：通过多组数据

的选取，作到了城市分核算的准确性，数据基本集中在这个比较小的范围内；

（4）. 从几个比较下地在65分左右地地区，即城市分较低的地方：鄯善、库车

县、若羌，不难看出，都时一些比较小的，欠发达的，旅游资源较贫乏的地区，这与数据时完全吻合的；

（5）. 除乌鲁木齐外，值比较大的几个地区：吐鲁番、阿勒泰、伊宁，都在新

疆比较由地位和有实力的地区，其基本条件，旅游资源也都是相对丰富的。

不难从最终的城市分的结果看看到，通过大量数据综合得到的这些数据是完

全可以反映单位时间在新疆的花费的，只要在城市分前都乘上统一的比例系数，即可表示出想对应的在各点的消费情况。

最佳旅游线路的设计

12

乌鲁木齐库尔勒吐鲁番鄯善哈密阿勒泰塔城博乐伊宁库车石河克子拉马依昌吉阿克苏阿图什喀什和田若羌301015

这样，在得到了最佳时间和城市分这以表示花费的后，也就完成了城市到点的转化过程，综合以上的到的数据，得到最后的表4－10：“点－值表”即从城市转化而来的点以及它们想对应的两个量。

表4－10 点－值对应表 编号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 城市 乌鲁木齐 库尔勒 吐鲁番 鄯善 哈密 阿勒泰 塔城 博乐 伊宁 库车 石河子 克拉马依 昌吉 阿克苏 阿图什 喀什 和田 若羌 时 间 19 11.5 8.25 2 8.75 10 5.25 8.5 13.5 4.5 3.5 2.5 7.5 6 4.25 5 8.5 7 综合得分 97.28 76.75 77.90 64.01 74.10 78.07 68.75 68.24 77.05 64.90 69.53 69.96 71.75 71.37 65.34 72.93 72.04 66.38

4．1．2 路到线的转化

由假设3.4：新疆境内整个道路情况相同，车速一定，单位路程所需要的费用一定。而这个一样的车速由整个新疆境内的铁路，公路基本速度，价格情况综合等效得出，这就要求由一个比较真是，综合的，合理的速度和时间值，这就要在对新疆境内交通情况调查，由一定了解的情况下，求得一个有效的值。

1． 新疆境内基本交通情况的调查

总体来开，大体可以将交通方式划分为三种情况：汽车，火车、飞机，在表4－6：城市住宿、出行情况分计算表中，已经给出了各地区和城市的交通情况，结合实际的汽车客运、火车列次、机场航班情况，不难得到新疆境内，要考察的18各地区的基本交通情况为：

(1). 汽车是最便利的交通方式，在选取的18各点中，虽然不难满足任意两点见

都可以由最短、最直接的汽车客运，但通过其它定完全可以达到的任意两点的相互联系；

(2). 在选取的18各点中，有火车站的点是10个， (3). 在选取的18个点中，有机场的是9个地区或城市，它们之间只有乌鲁木齐

最佳旅游线路的设计

13

301015

与其它8个地方的往返航班，其余8个点中都没有相互之间的航班，而且也只有乌鲁木齐与外省市有航班；

(4). 综合三种交通工具的各项情况，可以看到，新疆境内的交通并不是特别便

利，不过还是可以通过汽车客运的方式到达任何的一点，这保证了道路选择的任意性。

2． 基本速度、基本价格的求取

要在选取交通工具不确定的情况下得到一个整体环境下的平均速度和平均时间，这样才可以保证在整个路程计算的结果最好地与实际相吻合，使得到最终计算的结果产生最下的偏差。这样，就需要在研究调查各种交通工具的情况下，进行综合分析， 1）．公路情况：

选取一部分关键的数据点，其中乌鲁木齐作为交通中心和唯一可能的起始，终止点，我们都选择与乌鲁木齐作为起始点，选择相离较远的点为终止点，通过这些点之间的平均的求解得到整体情况下的平均，由于选取的路线中基本已经包括了全部的其间的大多数路线，所以虽然理论数为

18*1718*17?153?153

22的总线路数，由于大多线路不存在，加之很大一部分是重合的，所以只要选取一部分就可一了，如表4－11所示。

表4－11 新疆主要汽车时、路、速情况 始发站 终点站 时间（h） 距离（km） 速度（km/h） 和田 24 1731 72．13 乌 阿勒泰 10 703 70．30 鲁 伊宁 9 692 76．89 木 喀什 26 1588 61．08 齐 和田（北线） 24 1977 82．38 总和 93 6691 71.95 90速度（km/h）80706050和田阿勒泰72.1370.382.3876.8971.9561.08终止站和田（北线）平均伊宁喀什 图4－2 各线速度及平均速度分布图

最佳旅游线路的设计

14

301015

通过上表及其分布图我们可以看出，在新疆境内平均车速集中在60—80km/h之间，上述五线的平均速度为：

V=71.95km/h

由于新疆境内多为长途客车，如果考虑途中吃饭放风和车辆维修，意外事件等情况所浪费的，平均速度将有所下降，也为了计算和处理的方便，这里对这一平均速度进行一定的修正，即近似地取平均速度为：

V=70.00km/h

从而确定了在点线图中的汽车平均速度。

在计算平均费用时，调查得到的各车站大体都拥有低、中、高档三种车型，而这三档车的发车比例约为：1：2：2，从而到车站乘坐三种车的概率分别为0.20、0.40、0.40。

在确定了基本的乘车概率后，就可以在已有数据的基础上获得平均基本价格了，由于实际中乘车的价格状况要复杂于其速度（受距离长短的影响比较大，而由不直接正比于路程），所以选择更多的求值终点以保证数据更加接近平均价格的真值。

表4-12 部分线路低、中、高档汽车车票票价 始发站 终点站 低档票价(元) 中档票价(元) 高档票价(元) 路程（元） 塔城 52.00 84.00 97.00 633 博乐 45.00 60.00 70.00 528 克拉马依 33.00 49.00 54.00 342 乌 哈密 45.00 55.00 65.00 626 鲁 伊宁 56.00 90.00 100.00 692 木 阿克苏 70.40 94.40 107.40 1004 齐 喀什 90.40 139.40 158.40 1470 阿图什 90.40 135.40 154.40 1427 吐鲁番 19.20 26.60 30.40 187 哈密 62.40 83.40 95.40 626 库尔勒 45.40 60.40 70.40 464 库车 53.40 73.40 84.40 751 总和 626.60 951.00 1086.80 8750 在表4－12的基础上，以及三档车的票价，可以得到，单位路程的价格可以是：

662.60*0.2?951.00*0.4?1086.30*0.4P??0.108元/千米

8750即得到的P可以用来表示单位距离的汽车的平均费用。

在得到了平均速度和单位距离的平均车费后，设某段路程为s，则可以很容易的表示出：

S?T??V ???Q?S*P最佳旅游线路的设计

15

301015

同时可以得到汽车时间与费用的关系系数，则

QP*Sb＝＝?P*V＝7.56元/小时

STV 2）．铁路情况：

对于铁路同样使用与上类似的方法，可以得到选择铁路情况下得P、V、b即可。

这里，铁路列车在新疆内以直达车为主（乌鲁木齐至哈密除外），只考直达车得情况，和硬座，硬卧两种车价得情况下，硬座，硬卧的比例约为3：1时，可以认为其买到硬座，硬卧概率分别为0.75和0.25。具体的数据见表4－13。

表4－13 直达铁路时间、票价、路程情况 始发站 终点站 时间(h) 硬座票价 硬卧票价 路程 奎屯 4.18 23 50 242 乌 阿克苏 18.28 70 153 1126 鲁 喀什 29.73 93 199 1588 木 哈密 12.74 70 140 553 齐 阿拉山口 11.82 34 78 477 库尔勒 11.75 41 93 600 求和 88.5 331 713 4586 则通过与公路计算完全相同的方法可以的到:

v=52.34千米/小时 a=0.058元/千米 b=4.86元/小时

3)．航线情况

由于整个新疆境内航班不是特别的便利，加上航班的价格比较高，作为旅游，并不适合选择飞机这一交通工具，所以不做具体计算和考察，这里只在表4－14中列出。

表4－14 航班时间价格表 始发站 终点站 票价低（￥） 时间（h） 折后 喀什 1230 1．50 4折-490 和田 1250 1．67 4.5折-560 乌 鲁 伊宁 740 1．00 4折-300 木 阿勒泰 500 2．00 4折-200 齐 库尔勒 340 0．92 6 折-200 库车 590 最佳旅游线路的设计

1．38 6折-350 16

301015

3．综合结论：

通过以上对交通情况的调查，可以看到，汽车有着明显的优势，在速度，价格方面，这样，可以确定，在具体的点线中，线上的花费和时间是完全一汽车得到的数据为标准的，即：

V=70.00km/h

P=0.108元/千米 B=7.56元/小时

注：由于空间问题，点点距离不便放在文中，这里略取 4．2 制作点线图

在得到表4－10“点－值对应表”的基础上，以基本的新疆地图为基础，点代表城市，线代表城市间的路程，得到了经过转化的“点线图”，大体绘制出相应地“点线图”，见图4－3。

IHGJs D t LBA CE MN F

K O P R Q A 乌鲁木齐 B 昌吉 C 吐鲁番 D 石河子 E 鄯善 F 哈密 G 克拉玛依 H 塔城 I 阿拉泰 J 博乐 K 伊宁 L 库尔勒 M 库车 N阿克苏 O 阿图什 P 喀什 Q 和田 R 若羌 s,t 道路交叉点

图4－3 新疆旅游点线图

最佳旅游线路的设计

17

301015

这样图上的点A－R分别代表城市及其所包含的景点，而表4－10和表4－14分别给出了对应的停留时间，花费的比例基数和线路之间的时间、费用。从而实现了将实际的旅游设计线路的问题转化到一个点线图中求最小值的问题。

4．3 处理电线图

通观所出现的几个问题，在通过4.1以及4.2的转化后，问题相当类似于经典的旅行推销问题，但又不完全相同，在我们处理过后的点线图中，涉及到更多的变量，情况更加复杂。但即便是旅行推销员问题，目前也无统一算法，必须借助一定的搜索方法。利用与之相关的几个算法：Dijlestra算法，避圈法生成最小树以及利用Hamiton环等做局部搜索。虽然它们并不能完全解决问题，但我们有理由相信围绕着这些路径，是会找到原问题的近似最优解。下面就就1.问题中所提到的

5． 解决问题

5．1 30天的最佳线路

通过我们上述表格的分析，在旅行地点逗留时间远大于路上所用时间。而在我们计算一个月旅游时间时引入了紧张系数J，它的意义是在不同的约束时间，选择不同的旅游时间，也就是说旅游是不完全的，那么我们就有理由假设，当这对夫妇重复在某地旅游时，他们会重复旅游这个城市（终点除外）。其假设如下：

只乘汽车一种交通工具，若到旅游地点不能跳过，暑假时每月31天。夫妇二人在一起旅游，到所在地点想走即走，即不计算等车时间。由于时间和花费有一定的正相关关系，所以我们只计算时间。

这里在某地的停留时间系数选择0.35，即原全部最佳时间前乘以0.35,得到现有的时间。

根据假设旅游时间比路上花费的时间大的多，我们尽可能一次性（即不重复游完所有地点）。下面我们选择一个Hamiton环（如无法找到就选择近似图形），选择方法如下：

（1） 先从局部开始

有图的特征，先将原图分成两个子图：

L M N O P R

Q 最佳旅游线路的设计

18

301015

I H G Js BA D K t CF

E L 这样就将复杂的图简化，便于找出近似Hamiton环，如上图。 将这两幅图拼接在一起：

I

H G

Js

BA D K t CF

E

L M N

O P R Q

A 乌鲁木齐 B 昌吉 C 吐鲁番 D 石河子 E 鄯善 F 哈密 G 克拉玛依 H 塔城 I 阿拉泰 J 博乐 K 伊宁 L 库尔勒 M 库车 N阿克苏 O 阿图什 P 喀什 Q 和田 R 若羌 s,t 道路交叉点

进行局部调整，原则：将漏掉的线补进图中，尽量避免线的重复，让重复的路尽量少。调整完如图：

最佳旅游线路的设计

19

301015

IHGJK s D t LBA CE MF

N O P R

Q

这样时间为：51.45天。

下面进行局部调整：其中若羌（包括楼兰）、吐鲁番、乌鲁木齐（包括天山）和伊宁（包括伊犁）根据题目要求，是最好尽可能去旅游的点，不宜去掉。

以这样的原则，得到如下路线：(综合各方面因素，我们决定精确到小数点后一位)

a：乌鲁木齐→t→伊宁→t→库车→阿克苏→阿图什→喀什→和田→若羌→库尔勒→乌鲁木齐 用时：30.2天 10个城市

b：乌鲁木齐→t→伊宁→t→库车→和田→若羌→库尔勒→吐鲁番→乌鲁木齐 用时：27.8天 8个城市

c：乌鲁木齐→哈密→鄯善→吐鲁番→库尔勒→若羌→和田→t→乌鲁木齐用时：27.2 9个城市

d：乌鲁木齐→昌吉→石河子→s→克拉玛依→塔城→阿拉泰→哈密→鄯善→吐鲁番→库尔勒→乌鲁木齐 用时：30.6 10个城市

a路线虽然最多，但缺少吐鲁番；

b路线虽然不是很多，但是题目中向往的城市均有； c路线缺少伊宁；

d路线缺少伊宁和若羌，但却游玩了北部地区。 根据每个城市的消费：“城市分”和时间，算出总的花费：

a=8697+444＝9141 ￥ b=8097+463＝8560 ￥ c=6618+483＝7101 ￥ d=8569+459＝9028 ￥

5.2 60天分两次完成

因为题要求是在两年之内游完新疆，那么我们有理由相信，时间是充裕的，

最佳旅游线路的设计

20

301015

而实际要求成为消费最小。

不难知道，求出路上的时间最少，而且又是分两次走，这类似于多个推销员问题，而这类问题在目前也是不可解决的。我们知道，求最小路径和最小树是在一定程度上对这类问题近似。所以，我们围绕这两种“最优”路线做局部搜索，从而算出近似最优解。

首先，用Dijkstra算法与乌鲁木齐到各点的最小时间为： 昌吉：0.02 石河子：0.09 克拉玛依：0.19 塔城：0.38 阿拉泰：0.42 哈密：0.31 鄯善：0.14 吐鲁番：0.14 库尔勒：0.27 若羌：0.55 和田：0.97 喀什：0.68 阿图什：0.66 阿克苏：0.42 库车：0.28 伊犁：0.35 博乐：0.32

由图可知：可将原图分成两个子图，供游客两次游玩，然后调整边界，使结果相

I对最优。

H

G

J s BA D K t F C

E

L M

N O P R

Q

对下面的子图，可以看出，到和田的最短路径，几乎将下图所有城市连接起来，所以围绕它作局部搜索，可得路线：

乌鲁木齐→昌吉→石河子→s→t→库车→阿克苏→阿图什→喀什→和田→若羌→库尔勒→吐鲁番→乌鲁木齐（2. 13天）

P=at

=2.46*7.56*24

=386￥ （a为单位时间所需费用，如上定义）

虽然无法证明其为最优，但通过再搜索几条路线验证以及刚才围绕最短路径搜索的方法，我们有理由相信，它即使不是最优，也会是一个最优解。其路上费

最佳旅游线路的设计

21

301015

用。

对上方子图的处理有所不同，因为各个城市的最短路径与乌鲁木齐成辐射式分布，所以不能再围绕最短路径找，下面我们尝试围绕最小树做局部搜索。 利用避圈法做出最小树为： I

H

G

J s BA D K

t CF E

经过最小树附近几次搜索可得路径

乌鲁木齐→石河子→昌吉→石河子→s→t→伊市→博乐→B→克拉玛依→塔城→克拉玛依→阿勒泰→哈密→鄯善→吐鲁番→乌鲁木齐 时间为2.46天消费

P=at

=2.46*7.56*24 =446￥

5．3 分三组对新疆进行考察

在某种程度上是第二问的一个变形,我们沿袭了解决了第二个问题的思想解决了问题3;但又不完全一样,因为问题3所要达到的目的函数和问题2不一样. 我们首先作出这样的假设:1.队伍如果分成三组,则不会再分组或重新组合.2,考察队一起来到乌鲁木齐,并一起离开.3,不考虑等车时间.4,只乘汽车一种交通工具.5,由于考察比较彻底,去过的地方则不再考察.6,定义标准旅游时间t。考察时间4t。具体考察时间如下:

乌鲁木齐 19.0 昌吉 7.5 克拉玛依2.5 塔城5.25

阿勒泰10.0 哈密8.75 鄯善2 .0 吐鲁番8.25 伊宁13.5 博乐8.5 库车4.5 库尔勒11.5 阿图什4.25 喀什5.0 和田8.5 若羌7.0 石河子3.5

根据木桶效应,我们要实现的目标为考察最后到达的队伍考察所用的时间最短,即要求min{maxh(最后)};我们亦不希望看到一个队早早考察完,而另一个队还有很繁重的任务,即我们还要求min{h(最后)-h(最先)}为了简化问题,我们把第一个目标看作主要目标 (不太可能满足两个目标)做出分析.

先将地图分成3个子图,将复杂问题简单化,然后对每个子图用Dijkstra法或破圈求最小树求出近似路程最优解,然后调整边界,列出路线. 具体划分如下

最佳旅游线路的设计

22

301015

搜索结果如下(综合各方面因素，我们决定精确到小数点后一位):乌鲁木齐→昌吉(不考察) →石河子→s→博乐→伊宁→t→s→石河子(不考察) →乌鲁木齐(不考察) 45.4天

乌鲁木齐(不考察) →昌吉→克拉玛依→塔城→克拉玛依(不考察) →阿勒泰→哈密→鄯善→吐鲁番→乌鲁木齐(不考察) 46.1天

乌鲁木齐(不考察) →昌吉(不考察) →石河子(不考察) →s→t→库车→阿克苏→阿图什→喀什→和田→若羌→库尔勒→乌鲁木齐(不考察) 48.9天

结果分析:将路程忽略,把考察天数相加/3得平均考察天数为45.2天,而我们得到的结果和这个偏差不大,说明走的重复路线不多,而h(最后)-h(最先) =48.9-45.4=3.5天也是可以接受的,所以我们可以认为我们得到了近似得最优解.

5．4 “五一”线路设计问题

本题目与其他三个题目不同的地方在于要求缓解交通压力和城市旅游压力.为了完成这个目的,我们查阅了其他交通方式,最后我们发现只有在喀什,伊宁和乌鲁木齐飞往华东地区的飞机,我们不妨把喀什,伊宁和乌鲁木齐作为游客集散地.通过对城市情况的分析,我们可以看到乌鲁木齐地位远高于其他城市,所以我们假设游客来新疆必然首先来到乌鲁木齐,根据旅游世间的长短,利用我们定义的紧张系数J,求出每天在旅游景点的停留时间如下:

乌鲁木齐:3.96 昌吉1.56克拉玛依0.52 塔城1.10 阿勒泰2.08 哈密1.82 鄯善

最佳旅游线路的设计

23

301015

0.42吐鲁番1.72 石河子0.72 博乐1.78 伊宁2.82 库车0.94 阿克苏 1.26 阿图什0.88 喀什1.04 和田1.78 若羌1.46 库尔勒2.40

由于时间紧张,我们假设旅游过此地若再经过便不再旅游. 现在按照集散地将图形分区:

现在考虑的问题时,在各个区域中,怎样走才能使游客在12天的旅游中看到景区较多并浪费在路上的时间最短.在以喀什和伊宁为离开地点的线路,可看成路径最短问题,当然可以考虑利用Dijkstra算法,而以乌鲁木齐为离开地点的路线,我们可以沿用上面三问的思想.

这样我们可得路线:（综合各方面因素，我们决定精确到小数点后一位）

1. 乌鲁木齐→昌吉→石河子→s→t→库车→阿克苏→阿图什→喀什: (11.0天) 2. 乌鲁木齐→库尔勒→库车→和田→喀什 (11.6天)

3. 乌鲁木齐→吐鲁番→库尔勒→若羌→和田→喀什 (13.9)(取消) 4. 乌鲁木齐→库尔勒→若羌→和田→喀什(12.1)(取消) 5. 乌鲁木齐→吐鲁番→库尔勒→和田→喀什(12.3)(取消)

6. 乌鲁木齐→哈密→鄯善→吐鲁番→库尔勒→乌鲁木齐(11.4) 7. 乌鲁木齐→昌吉→石河子→s→博乐→伊宁(11.3)

8. 乌鲁木齐→昌吉→克拉玛依→塔城→克拉玛依→阿勒泰→哈密→乌鲁木齐(12.9)(取消)

9. 乌鲁木齐→昌吉→克拉玛依→阿勒泰→哈密→乌鲁木齐(11.4)

10. 乌鲁木齐→昌吉→克拉玛依→塔城→克拉玛依→阿勒泰→乌鲁木齐(10.5)

最佳旅游线路的设计

24

301015

6．模型分析

6．1 方法有效性分析

问题类似于旅游推销员问题，而旅游推销员问题属于NP—完全类，结合新疆繁多、复杂的实际景点状况，使解决的问题在一个相当大的范围内。这样，要得到真正的最优路线使不现实，也是不可能的，决算通过不断地群举得到最优解，也不具备推广的意义，所以在建立模型的基础上，针对具体问题的不同，应该采取不同的方法：具体问题具体分析。

模型的建立过程是将实际复杂情况合理，准确，有效，详实地表现在点线图中，将抽象的，复杂的实际概念和数据量，转化为有价值的，精确的时间和费用值，所建立的模型简单，实际，操作性强。同时，由于实际量的复杂性，很难保证这种转化的实际意义和有效性，准确性。所以通过多方数据的综合分析、平均，共同得到的综合城市分和道路情况，已经很大限度的排除了数据的不合理性，可以说，它们比较准确的表现了所要表示的量和值，保证了解决模型时求最优，花费，时间的准确性。

模型的解决过程中，借助整和得到的数据和路线，对问题和状况作了全面得了解，根据图形得特点，做出必要假设和的基础上，将图形做进一步的简化分区，将一个图形分成若干个子图，对图进行处理，把问题拆减。这使问题在很大程度上得到了简化和优化，在不影响最终结果的情况下，很好地将计算和求解简单化，很值得在更加复杂，多变的情况下的推广和应用，甚至在这个思想基础上，可以就全国，全球的情况进行处理，即将全图合理地分解为若干子图，在子图地基础上处理，将处理地最终结果回归到总图上。由于时间和数据量的关系，这个问题暂不做处理，但是可以肯定的使，越是复杂的情况，这种分解解决问题的方法越是可以有效的应用使问题简化的。

在考虑算法问题上，解决模型中并不用计算机进行搜索，而针对问题与短路径问题和最小数问题相似，利用已经比较成熟的Dijstra算法，找到其它城市距离中心城市（这里使乌鲁木齐）的最小距离，然后利用避图法找到最小树，这样在路线周围，结合图形特点，围绕近似路线周围作局部搜索，在大大减少数据运算的情况下，得到相对最优解。

由于采用了“围绕近似路线周围搜索”的方法，这种算法会随着图形复杂程度的增加，粗糙程度可能会有所增加，但在处理对数据精确度要求不是特别高的实际问题中，确实大有用处，在使用这种算法找到近似最优解后，也进行了较大规模的检验，结果表明这种算法得到的结果是让人相当满意的。

6．2 方法推广性分析

可以推广得到，在“6.1”的几个基本过程的指导下，当问题需要推广使，当遇到大规模问题时，可以仿照这一思想方法进行求解，即：

抽象图形 分解图 找到近似算法 子图中在近似算法得到路径周围搜索 调整边界 检验路线

方法可以在问题的复杂度和相关问题中得到要推广。

6．2．1 复杂推广可能性的说明

可以看到，整个模型建立、解决过程中，并没有因为问题的复杂而过分的简化，而是在尊重现实的基础上，合理的将复杂的情况作了统一（建立点时，将景

最佳旅游线路的设计

25

301015

点统一）和分解（解决模型时，将全图分解为若干个子图），相反，在题目情况相当复杂的情况下，得到了比较优越、简单的解决方法，这可以说明，这以方法时可以被推广到其它更加复杂的情况下的，情况复杂了，统一和分解的过程将更加重要，只要合理的统一和分解，完全可以在更加复杂的情况下应用。

6．2．2 相关问题推广的可能性说明

整个解决模型的过程是以点线图为基础的，而并不涉及到具体的新疆的实际情况如何，因为各方面的因素已经通过模型建立的数据整合得到了规划和整理，可以通过点－数，点－线的一一对应得到全部相关信息，这就意味着：只要将数据，情况整合成相应的点线图，只要有希望最优的对象和其对应的点、线得到确定，就可以通过解决模型中的方法进行处理。也就时说，只要可以将实际转化到点线图，这一方法完全可以推广到其它任一相关问题的解决中

7． 结论

通过了以上一系列的转化，求解，分析，处理，完成了待处理的问题，不仅

设计出了不同情况下的旅游，考察线路，得到的结果是合理的；而且分析可以看出这方法在解决此类问题时是值得、可以推广的，可以比较方便的用来处理相关的问题。

[1] 玫影，新疆之旅，广州:广东旅游出版社，2005

[2] 陈启跃， 旅游线路设计，上海：上海交通大学出版社，2005； [3] 吴国清，旅游线路设计——全国旅游专业系列教材，北京：旅游教育出版社，

2006

[4] 蔡锁章，数学建模：原理与方法，北京：海洋出版社，2000； [5] 孙麟平，运筹学，北京:科学出版社，2005. [6] 王树和，图论，北京:科学出版社，2004.

[7] Fred·Buckley，Marty·Lewinter，图论简明教程，北京:清华大学出版社，

2005.

[8] 徐光烣，运筹学基础，北京：科学出版社，2005.

[9] 王昕，关于旅游线路设计的思考，重庆师范学院学报（自然科学版），17（增刊），34-36，2000；

[10] 吴凯，旅游线路设计与优化中的运筹学问题，旅游科学，18（1），41-44，

2004

[11] 段禅伦，斯勤夫，关于旅行推销员问题的一个算法， 内蒙古大学学报（自

然科学版)，32（6），695-696，2001；

[12] 潘玉奇，王潍，康健，王永燕，货郎问题求解算法分析，济南大学学报（自

然科学版)，16（4），336-340，2002；

最佳旅游线路的设计

26

301015

[13] 马良，旅游推销员问题的算法综述，数学的实践与认识，30（2），157-165，

2000；

[14] 中国旅游局信息中心，宾馆饭店，www.cnta.com/lyml/hotel.asp，

2007.3.30.

[15] 中国旅游局信息中心，旅游景区，www.cnta.com/lyml/travel.asp，

2007.3.30；

[16] 百度公司，百度指数，index.http://www.njliaohua.com/，2007.3.29。

最佳旅游线路的设计 27

本文来源：https://www.bwwdw.com/article/q19g.html