数学建模旅游问题C4

摘要：

新疆地域广阔，旅游资源繁多，本文以节约费用或时间为目标，分别为自助游、考察

等具体情况安排了旅游线路，并为“五一旅游黄金周”设计线路，缓解景区客流顶峰及提高

接待质量。

我们采集了全疆共33个景点景区的数据，其中不乏有十分接近的，故我们按地理位置

将它们进行聚类，最终得到20大景区。接着，建立在交通费用与路线长度成正比、不同景

点的住宿费用相等、车辆行驶于公路铁路的时速恒定等假设条件下，我们先用Floyd算法

求出了景区两两间的最短路径，接着用蚁群算法估计了遍历所有景区所花费的时间总和，

为下文设计合理的线路做准备。

对第一问，通过简单计算我们发现，单位时间内游览景区的花费要小于往返景区途中

的花费，亦即：花最少的钱与游尽可能多的地方这两个目标在此题中是统一的。为此，我

们提出了一个以确定一条游览尽可能多景区的旅游线路为目标、游览总时间为约束的0-1

整数规划模型，利用LINGO软件估计了解的下限，用遗传算法求得了最优解：两人一个月

时间花费约6100元游览17个景区。

对第二问，根据蚁群算法的结果可知，只要适当安排我们便可以在2个月内完成对新

疆所有景区的游览。为此我们从两种思考的角度，建立了不同的模型来求解交通费用的最

省问题。首先我们以两次旅游的路程长度之和为适应度函数用遗传算法求出了包含所有景

区的两条路径，并使它们的路径长之和最短。接着，我们利用景点分布图固有的特点，从

简化图的角度将20个点的连通图化为一个只包含6个顶点的图，并用枚举法将可能的5种

结果逐一计算，求得最正确线路。

在处理考察任务问题时，由于考察景区所花费的时间远大于在景区间往返的时间，所

以我们首先忽略路程上的花费，将如何安排三个考察组抽象成一个线性规划问题，以最小

化三个考察小组的最长耗时为目标并用LINGO软件求解，得到一些目标函数值相同但考察

景区不同的最优解，在此根底上，我们将路程耗时纳入考虑之列，再一次使用遗传算法，

目的是求得更精确的解。

对第四问，即设计“五一黄金周”旅游线路问题，我们以错开游客顶峰、景区利用率

尽量高、同一线路的景区跨越尽可能小、线路多且丰富等条件作为安排线路的目标来设计

算法，在给出14条黄金游线路的同时，又对问题加以进一步完善，即利用剩余资源开辟了

一些5-6天的短途游线路，以充分利用旅游资源并满足不同游客的不同要求。

在模型与软件的展望局部，我们阐述了规划模型、蚁群模型与遗传算法模型等的特点

及其他应用领域，也将文章中运用的四种软件：马克威分析系统、LINGO.Excel以及

MATLAB软件的特点和扩展做了逐一的介绍。

本文的优点是充分将规划与遗传算法相结合，突出规划模型意义的同时也发挥了遗传

算法高效的特点。同时，较好的数据预处理与蚁群算法的环游估计都为解决问题做了铺垫。

另外，设计黄金周旅游线路时，我们不仅考虑了丰富多彩10日以上旅游线路，也辅之以一

些中短规模的旅游路线，为游客提供了更多的选择余地。值得一提的是，本文还综合运用

了四种软件。

关键字：

聚类、最短路、蚁群算法、遗传算法、线性规划、枚举法、

马克威分析系统、LINGO、Excel.MATLAB。

一、问题的重述:

随着近年来旅游业的不断开展，我国新疆的天池、达坂城、吐鲁番、楼兰古城、伊犁

等等的异域风情，越来越吸引着广阔的游客。在本文中，我们要完成以下几个关于旅游路

线设计的问题：

1.在科学估算旅游费用的根底上，以总本钱尽量小为目标，设计一条在一个月〔计30

天）的时间里，游尽可能多的地方的旅游路线。（吃饭费用不计）

2.以在各景点间的交通费用尽量小为目标，设计两条互不重叠的旅游路线，路线各为

期一个月，且其合集包含新疆所有景点。

3.设计三条互不重叠的旅游考察路线，在每个景点考察的时间是旅游观光时间的四倍,

用于交通的时间那么不变，要求三条考察路线各自所用时间的最大值尽可能小。

4.设计假设千条为期十二天的黄金周旅游路线，以分散游客，提高景点的接待质量，

设参加这些旅游路线的游客人数与整条路线的接待能力成比例。

5.（对题目的进一步完善）对于上面第4个问题，考虑到新疆旅游实际问题的复杂性，

除了设计一些为期12天的旅游路线外，还可以适当的设计一些短期的旅游线路，这样既可

以方便游客、给他们提供了更多的选择，又可以充分利用各景区的旅游资源，防止其闲置。

二、问题的分析

在收集新疆各个主要旅游景点之间的路程、各个景点的最正确逗留时间等信息的根底

上,我们将问题做以如下的分析和抽象：

因为新疆的旅游景点众多，所处的地理位置也不相同，从旅游路线设计的实际出发，

显然要考虑到哪些景点相距较近，可以同时游览，因而，我们需要将新疆境内的所有主要

的旅游景点按照经纬度及是否可以直接连通予以分组。所以本文中我们首先采用聚类分析

的方法，运用马克威软件将各景点归为假设干景区，以便于下一步的分析。

另外，由于路程、时间、价格三者因素之间关系错综复杂，我们希望能得到一个统一

的标准，所以，我们把路程都化为时间和价格，并寻找后两者的关系，使问题简化。

对于第一小题，这一“最值”是某一固定时间内的最小费用，景区数那么不要求遍历

而只是越多越好C为此可以建立一个考虑逗留时间和路途时间的规划问题，目标是希望遍

历的景点尽量多，而约束那么是限定一个月的时间。

而第二小题与第三小题可以说是第一小题中同时考虑逗留时间与路途时间的引申。在

第二小题中由于有要求两个暑假游览所有的景点，那么景点上的花费一定，我们只需要考

虑使路途时间最少（即交通费用最小），这样也使得总费用最小。而第三小题，由于逗留时

间远远大于路途时间，我们简化时可以只考虑逗留时间。当然，为了进一步求解更精确的

解，在只考虑逗留时间的简化模型之后，我们还应将路途时间参加。

第四小题的处理方法那么有些不同，因为增加了一些新的约束类型，考虑到景区所能

够承受的游客流量，同一时刻不能有过多的游客游览同一景点，我们所要做的就是尽量错

开游客的旅行线路，使每一时刻，各景点都接待其承受能力之内的游客，并尽可能丰富地

设计旅游线路。

总之，对于旅游线路的规划问题，我们在一定程度上都可以将其抽象成一个求最短“路”

的问题，只不过这里的路常常不单指路程，而还包括时间，费用等等方面。不同的问题，

可以通过添加不同的约束条件予以描述。将实际问题抽象成一个规划模型的方法在某种程

度上是很相似的，但是，对于抽象出的这些规划问题，具体的求解方法，那么是多种多样

的。

三、根本假设

1、为了尽量节约费用，由于飞机的价格要远高于铁路和公路，而后两者根本相同。所

以在新疆境内的交通费用，以铁路票价为主，没有开谑铁路的线路，那么以公路票价为主：

2、对于公路的收费没有明确标价的路段，以两个旅游点之间的公路里程（km）除以

平均时速（60km/h）进行估算。对于少数公路也欠兴旺的地区，那么以速度折半为30km/h

估算；

3、假设在新疆的所有景点中，对任何的A、B两个景点，从A到B所需花在路上的

时间与从B到A的相同，即忽略例如由于列车停靠站不同所造成的运行时间上的一些差异;

4、暑假的一个月为31天，考虑到往返新疆的时间，故花费在新疆境内的旅游时间以

30天计；

5、在新疆境内各旅游景区的住宿费用均为一个定值：RMB150/标准间（两人）/天；

6、设旅游途中的休息调整时间合并在每个景点的观光逗留时间之内，不再予以单独的

计算；

7.不考虑交通费用在白天和夜晚的区别，（如火车硬座与卧铺价格上的差异等）均以

最低价格即硬座票价计算。

8、对于旅行社推出的旅游线路的设计，与自助游不同，我们认为其主要目标不在于节

省费用而在于多游览美景和旅途的舒适，因此假设在新疆省内白天的时间都用来游玩，景

区间的行程那么采用飞机（时间短故可忽略）连接或在晚间乘车抵达。

9、假设铁路和公路交通费用的票价，与行驶的里程近似成线性关系，而又因为列车或

汽车时速也是一定的，这样，某一段路程需要的交通费用也与其时间呈近似的线性关系，

这样，求最小费用，也即求最短路线。

注：假设9的依据：

我们对局部景点间往返的时间和费用进行采样，并作回归分析如下页图所示：

[R平方为0.9819,F值为595.6604,说明两者呈很强的线性关系。几乎可以认为交

通费用与路程成正比。）

价

格.价格-距离采样关系图

160.0

150.0

140.0

130.0

120.0

110.0

100.0

90.0

80.0

70.0

60.0

50.0

40.0

30.0

20.0

10.0

0.0---------------------------------------------------------------------------------------------------------------------------------

0.02.04.06.08.010.012.014.016.018.020.022.0

距离

（图1：价

2塔城1

3克拉玛依0.5

4博乐4

5石河子1

6昌吉1

7乌鲁木齐1.5

8天山1

9伊犁1.5

10天鹅湖0.5

11吐鲁番1.5

12哈密2

13库车大寺1

14库尔勒1

15阿克苏1

16楼兰5

17阿图什0.75

18喀什2.25

19尼雅遗址3

20和田1

（表1：20个景区逗留时t间一览）

这20个景区的地理位置分布和相互间的道路连通情况可以如下列图所示，其中各个标

明序号的结点上方的墨绿色数字表示在该景区的逗留时间。

-----铁路

（图3：景点分布及逗留时间图）

2、用蚁群算法初步求得的遍历时间

尽管上述所示的景区道路图是连通图，但并不是任意两个景区间都存在直接连通的。

因为需要计算的是在景区内的逗留时间和路上的消耗时间，所以，我们希望得到任意两个

景区间的最短通路，这样，当需要跨越某一景区而到达相对较远的另一景区时，可以有直

接的通路，这将使问题更直观和简便。因此，我们运用Floyd算法，首先要做的是将这20

个景区之间两两的最短时间计算出来，得到一个20*20的时间矩阵如下所示。根据我们前

面的假设3,这是一个对称矩阵，矩阵元素的单位为小时。

[矩阵见附录2]

根据上述的景区间最短时间矩阵，运用带精英蚂蚁的蚁群算法⑵编制程序，我们可以

求得要遍历所有的景区，需要在路上花费的最小时间。以此，再结合各个景区的观光逗留

时间，那么可以得到遍历所有景区的总时间，根据它我们可以估算假设要游览新疆的全部

各个旅游景点，需要花费的时间是多少，为此题后面的处理做一估计。

蚁群算法的运行图示如卜.：

回

fc

金

喷

然

氐

最终可得到如下的结果：

通过2.859000秒的计算，我们得到最少环游时间：292.44小时=12.18天。与其相对应

的最短环路是：

1614II128765312

410913151718201916

而游览所有聚类后的景区总时间为一定值：33天，所以:

总时间=最短环游时间+逗留时间=12.18+33=45.18天

这个结果的意义在于，它告诉我们要想在一个月即30天内遍历所有的景区是不可能实

现的，并给出了一个十分有参考价值的数据。

因此对于第一问，我们要选择适宜的线路，从而可以游览尽量多的景区。而由于总时

间小于60天，也即我们是可以在2个月内完成对所有景区的考察，第二问也就自然会有可

行解。再注意到，如果逗留时间是33天的4倍，即132天，那么考察时间就将会是环游所

需总时间的10倍以上。这就启发我们对于第三问，可以先忽略环游时间计算一个近似最优

解，再在此根底上逐步地加以完善。

五、模型的建立与求解

模型一：

通过比拟各种交通费用，我们可以发现，在新疆境内选择飞机出游的花费要远高于铁

路和公路的费用，出于节约费用的目的，并且考虑到许多景点都是远离机场的，飞机的优

势也并不明显，为此，我们首先挨弃乘坐飞机。此外，选择铁路的性价比要略高于选择公

路，但新疆境内的铁路很有限。所以，假设两景点之间同时存在铁路和公路将它们相连通,

那么选择铁路，而假设仅有公路那么只能选择公路。

另一方面，通过计算公路交通的费用，结合公路里程、客车行驶时间和可以发现，如

果某天24小时都花费在往返假设干城市的路途上，那么两个人的花费要超过330元，但是

如果某天是停留在某个景点游玩的话，日均游玩费与住宿费之和大约只有28()元，所以从

这个角度来考虑问题的话，花最少的钱实际上去游尽可能多的景点是一致的。我们的目标

就是防止在途中过多的耽误时间，从而使游玩时间减少。

建立在总费用二住宿游览费用+路程开支的根本假设之上，我们建立了如下的线性规划

模型：

对于聚类后得到的20个景区的问题，我们引入一人20x20的矩阵X,其中的元素升为

0-1变量，当勺=1时表示我们制定的路线包含从景区i直接到景区j,否那么不包含景区，直

2020

接到九我们希望整个游览线路包含尽量多的城市，也即最大化目标函数：金川o

对于约束条件，

约束条件1：由于每个景点最多参观一次，所以，矩阵x的每行与每列之和均为()或

者1；

约束条件2：当而为了保证整条链的连通性，即使出现两条以上不相连通的链，我们

要求每行之和与每列之和相等。

约束条件3：为了满足总的时间小于一个月，还需要增加时间上约束条件。

故，完整的线性规划模型为：

20

7-i

2%=1i,j=1,2，…,心手j

+〃〃/)<=720

»=>j=i

Xy=0,1zj=l,2,...,z?

(其中id。是第j个景区的逗留时间)

我们用Lingo软件对其进行求解⑶，但是很遗憾，由于较多的变量及复杂的约束，程序

无法在短时间内完成。好在隐枚举方法给了我们启示，发现可以找到一条至少包含17个城

市的链，所以，根据这一启发，我们下面运用擅长处理NP完全问题的遗传算法来重新求

解这一问题。

算法的思想是：通过模拟自然选择和遗传中发生的复制、交叉和变异等现象，从任一

初始种群出发，通过随机选择、交叉和变异操作，产生一群更适应环境的个体，使群体进

化到搜索空间中越来越好的区域，这样一代代地不断繁衍进化，最后收敛到一群最适应环

境的个体，求得问题的最优解。

既然线性规划模型已经告诉我们，至少可以找到一条包含17个景区的链，那么我们只

需从N=17开始找一条包含N个景区的最小耗时链，假设对于某一N(N〉17),最小耗时

链的总长大于720分钟，那么一个月内最多可游览的景区即为N-lo

下面，我们对遗传算子进行设计：

定义个体：我们以一个1行20列的行向最为一个个体。其中，前N列表示一个月内

所遍历的景区的链；后20-N列表示剩卜的未遍历的景区。假设十个这样的个体组成一个种

群。

选择运算：根据适应度的上下进行优胜劣汰的选搭。在这里，遍历前N个景区道的路

上的花费时间以及停留在这N个景区的逗留时间之和越短，适应度越高。对不同适应度分

配一个被进化的概率。适应度越高，被选择进化到下一代的概率也越大。

交叉运算：交叉的方法有很多种，在这里我们对两两个体以一定概率pm(0.6-0.95)

决定是否进行交叉运算，假设进行，那么采取CX方法⑷，假设否，那么保存这两个个体。

变异运算：变异的方法也有许多种，在这里，我们分别考察每一个个体，并以一个小

概率pc(0.05〜0.15)决定是否进行变异运算，假设进行，那么采取倒位变异，假设否，那

么保存该个体。

适应度计算：以游览景区个数多少来评价适应度，游览的景区越多那么适应度越高。

模型的结果与分析：

屡W调整参四，运行遗产算咨程产，举们写到二条革历17个产区单链:

7|8|6|5|2|1|3口0|9|13口5|17|18|20|14|11|12

而另三个景区4、19、16那么不访问。

遍历这条链的总时间花费为642.5700小时，大约27天。

性能追踪

(图4：遗传算法性能追踪图)

我们再尝试N=18的情况，但是，遗传算法的结果告诉我们，无法找到一条遍历18个

景区的链，使总的时间开支小于72()小时。

所以，两个人在暑假一个月内花最少的钱最多可以游17个景区。

费用：

交通费用：717

景点住宿费用：21*150

景点游玩费用：1120*2

那么总费用：6107/两人

模型二：

2.1遗传算法的求解

根据第一小题的结果，我们发现，如果以与之前相同的出行方式显然不能在一个月之

内遍历所有的2()个景区，但是，在引言局部，我们也计算出，遍历所有景区与往返景区路

途中的总时间是45.18天，这说明分两个月完成游览是完全可以的。由于两个月之内，我

们会遍历所有的景区，所以在景区上的开支是恒定的，所以，如何安排两个月所分别游览

的景区，使交通费用最省也即是使总费用最省。

受第一小题的启发，我们依然想到运用遗传算法进行求解。

选择、交又、变异函数不变，适应度函数定义为两次游览的总交通费用的倒数，这样,

用于交通的费用越少，适应度就越高，个体就越能遗传到下一代。

由于景区总数只有2()个，所以，我们下面采用一种分类遗传的方法，这样可以使结果

更精确也可以使计算效率提高。做法是：将20个城市分为两局部，第一个暑假考察N个

景区，第二个暑假考察20-N个景区，N从3开始到17(如果N小于3的话会导致不满足

约束条件，即出现一个暑假游览所花费的时间大于30天)，同时考虑到乌鲁木齐是省会，

很多游览天山、昌吉等景区的旅行线路都是以乌鲁木齐为出发点的，所以为更切合实际，

在这里我们也要求第一个暑假从乌鲁木齐出发〔当然，这不是必要条件，我们后面采用的

方法即不需要满足此条件）。对每一个给定的N用一次遗传算法。最后将每个N对应的交

通上花费的时间作比拟，我们发现，N从7到13所花费的时间较其他更少一些，故，作

Nw[7,13]的柱状图如下：

叵

te

坂

名

乜

您

也

解

程

第一个暑假浏览的景区数N

（图5：景区数量安排与耗时关系图）

模型的结果与分析：

从上图的结果，我们可以看到：当两个月各访问10个景点，并且按照我们列出的顺序

访问，路上时间最少，而路途耗时与交通费几乎成正比，从而交通费也最省。

我们给出一组最优线路：

第一个暑假78654910132

第二个暑假12111413151718201916

遗传算法的效果和求解能力都能到达我们所期望的，但是对于这一问题固有的特性，

我们也可以直接从图的角度来建立模型：

2.2从图的角度直观求解

两次暑假遍历所有的景区，也即是将原来20个景区的连通图分割成两个子图，并找出

两条互不重叠的旅游路线。针对问题的特殊性，我们分如下儿步来处理问题：

第一步，不断地剪去图中所有度为1的顶点，即编号为：2、8、9、11、12、16、19

的点（II是因为剪去12后它成为了度为1的顶点）。

因为我们参观这类景区的时候，进出必然沿同一条线路，花费在这些路上的时间是不

可缩减的。所以，在我们的最节约时间方案中一定会包含这些路径，故寻找最短路径的时

候可以暂时将其从图上去除。

第二步，我们将度为2的顶点去除，但保存原来的路，即编号为：1、4、6、15、17、

18、20的点。

原因与第一步类似，因为对于这类顶点，一般来说，游览它们的时候，是从顶点的一

条边进入而从另一条边离开，所以，通过这类顶点的路径也是确定的，对我们所需要寻找

的最短路径不会产生影响，可以暂时将其从图上去除。

执行这两步之后，得到如下结果：

（图6：简化后的景点图）

我们发现，余下的顶点的度数都大于等于3。我们把被去除的顶点“附属于"某一个度数

大于等于3的顶点，即如果我们到达某个顶点x,我们就要遍历它的“附属”点。

要分割原先的图，并找出不重叠的两条路线就要选择如何分割这些度数大于等于3的

顶点。

模型的结果与分析：

由于数据量较少，我们用枚举的方式得出了五种较为合理的分组方式。

分组情况一情况二情况三情况四情况五

Group11—101—12、141—81—8、11、12、141—6,9、10

Group211—2013、15—209—209101315—207,8,11—20

情况一:

Groupl23178654109

Group212111413151718201916

情况二:

Groupl21391045678141112

GGrroup2113151718201916

由上面五组游览方案，我们分别计算它们的游览时间以及所需的路费，可以得到如下

表的结果：

单位（小时）情况一情况二情况三情况四情况五

Group157.37107.0345.1791.8953.41

Group2103.364.15126.5176.95130.75

总时间160.7171.18171.68168.84184.16

价格（元）―-二二四五

Group1292.3573.4220.1511.8270

Group2694.3465.9845.7541.6841.3

Sum986.61039.31065.81053.41111.3

由上表，我们发现，情况一中所消耗的时间最短，所需的费用相应也最少。因此，我

们认为，安排两个月的旅游线路最正确的分配方式由情况一的分组给出，具体的线路图可

以表示如下：

Group1231786,54109

Group212111413151718201916

（图7：最正确线路安排图）

模型三：

3.1简化的模型

由于考察分三组进行，故我们可以把整个西藏的景区分为三局部，三个考察小组各考

察一个局部，设他们考察所花费的时间分别为工、《、完成整个考察工作是指三个小组

都完成各自的考察任务，所以，尽早的完成考察也就是使三个小组完成考察时间的最大值

最小，即：minmax{7；、4、7；}。

引言中，我们已经通过蚁群算法计算出环游全部景区时，所消耗在路上的时间约12天,

现在分三组进行，花费在路上的时间更会小于12天。而现在各景区停留考察花费的时间是

原先的4倍，即33、4=132天，两者相差一个数量级。故，我们先考虑一个简化的模型，

即忽略路上所花费的时间。

现在，问题就转化为一个简单的规划问题：

20

min=max（Ec;/）/=1,2,3

'J=I

=1j=1,2,...,20

s.t.f=l

勺=0,1;=1,2,3;j=1,2,...,20

其中i=L2,3表示三组考察的线路,1=1,2,...,20表示20个景区,那么％表示第i组是

否考察第/个景区，假设考察，那么”,否那么％二°。而第一个约束条件表示每个景

20

点当且仅当被一个小组考察。目标函数中的Cj表示考察每个景区所花费的时间，目,“表

示第，组考察队伍所花费的考察时间，三组队伍的最大值表示花费的总时间，我们希望这个

值尽可能的小。

模型的结果与分析：

下面我们用LINGO软件对问题进行求解，最优解中，矩阵｛%｝的值不唯一，但是目标

函数的值是唯一的，都是44,由于总共用于所有景区的考察时间为132天，很容易得出三

个考察组在各景区所花费的时间都为44天。这与我们从直观上理解一一尽量使三个小组的

考察时间平均一一是一致的。

简化的线性规划模型的好处是不言而喻的，但是也存在着一些缺乏，从解的分布来看，

三个考察组遍历景点所花费时间都为44天的情况有许多种，尽管用于往返景区途中的时间

远小于逗留在景区内的时间，但是为了区分各组解并求得更精确的解，我们需要将路程上

的时间消耗列入考虑的范围之内。对于Ling。计算出的假设干组最优解，我们将路程时间

纳入考虑，对于其中最优的一组：

第一组231654

第二组910131517182019

第三组121114716

我们计算得，三组停留在景区与往返于景区路上所花费的总时间的最大值为1138.09

小时（47.42天）

但是，由于最优值对应的分布较多，通过Ling。屡次计算不考虑路程的最优解再将路

程消耗参加，从而比拟，这样的做法略显烦琐，也不能保证枚举到所有可能的结果。为此,

我们再一次运用遗传算法。

3.2遗传算法的求解

这一问题遗传算法的选择、交又、变异运算并没有实质的区别，但是适应度函数方面

我们做了比拟大的改良：

我们根据三个小组遍历的景区计算他们各自在景区逗留和往返景区间的时间消耗和

5&心、&H3,并将适应度取为三组完成时间的最大值的倒数

max｛7；”T、MR,这样，根据优胜劣汰的准那么，耗时最长的一组所消耗的时间越

短，那么被遗传到下一代的概率越大。以此逐代进化，最终得到最优解：

第一组18171391()42

第二组1358671112

第三组1519201416

这样，经过1120.21小时（合46.6754天），三个小组将全部完成考察任务，这比之前

所使用枚举法的1138.09小时（合47.42天）的结果要好一些，进一步说明了遗传算法处理

复杂问题的优势。

模型四：

根据20个景区各自的最正确逗留时间，我们可以算出在黄金周12天时间内每个景区

接待顾客流的数量。显然，游客在某一景区逗留的时间越短，景区可以接待游客的批次就

越多。由于各景区的接待能力大相径庭，旦同一时间每一景区接待的游客数量是有限的。

我们希望安排尽量多的游客在不同的时刻游览不同的景区，错开某一景区的人流顶峰，从

而提高旅游质量。

因此，我们的目标就是尽可能多地设计1（）天以上的旅游线路，也就是使任意时刻闲置

的景区数量尽量地少，这样整个新疆旅游区可以接待更多的游客。值得一提的是，为了使

游客花费在路上的时间尽量地节约，我们设计的线路时也考虑使访问的相临两个景区在可

能的情况下尽量地接近。然而即使如此安排，我们依然不能保证每一时候所有景区都处于

饱和状态，某些景区必然会有一定的时间出现游客数量稀少的情况。

考虑到这一情况，为了充分利用新疆的旅游资源，我们在保证长旅游线路的前提下，

对于那些无法再构成一条10天以上旅游线路的景区，尽也可能地安排它们组成了一些短程

旅游线路，这样，不仅使游客有了更多的选择空间，也可以使更多的游客浏览祖国西部的

奇山异景。

为此，以半天为一个时间单位，将12天的时间划分为24个单位。并将每一个景区以

划分成假设干区段，使每个区段包含的单位数正好等于一批游客的逗留时间。我们设计了

如下的算法：

4表示在第/个城市的逗留时间；

，表示时间轴的变化，‘£口24］；

4〃为一20x24的矩阵，表示任一单位时刻，，景区，是否已经被安排接待某批游客，假

设已经有接待任务，那么A弓二°,否那么A%"1。

第一步：

置在时刻1,我们随意选择一个空闲的景区a作为起点，…=°,'=，+方。

第二步：

从时刻'=1+1开始，列举下一时刻段没有安排接待任务的景区，从中选择与上一个城

市最近的景区为下一个访问对象，直到，＞24或者下一时间段没有可供选择的城市。

第三步，

记录遍历的景区编号和总共需要花费的时间数。置，=1重新执行前两步，直到无初始

景区可供选择。

模型的结果与分析：

由于这一算法在初始时的选择存在随机性，故每次运行的结果并不完全相同，我们运

用上述算法每次都可以得到20条不同的线路，并且在任意时候，不同线路的游客不会参观

同一景点。我们将一次结果罗列如下，其中，14条线路是10天以上几乎覆盖整个黄金周

的旅游，而另6条那么是中短途旅游线路，也可供特殊要求的游客参考：

长线：

10.5天

（一）神秘天山宗教十日游9-11-14-13-10-3-6-5-8-2

（二）冰山水域王陵十日探险1・18・2・8・10-3・12

11天

（一）玉邑丝路11日游3-10-13-14-20-17-15-9-11-7

J尼雅双湖文化之旅19-13-15-17-20-14-3-10-9

11.5天

（一）西域风土民俗游8-6-5-3-10-4-13-15-17

（二）新疆内陆景观游17-15-13-10-3-5-6-7-9-8-14

（三）火焰山千佛洞神奇之旅11-7-6-8-5-3-10-13-15-17-20

（四）尼雅博湖佛寺探秘之旅15-17-20-19-14-6-5-3-10-13

（五）疆内城市风情环游7-3-6-5-10-9-13-15-17-20-8

（六）疆内文化古迹环游5-3-10-15-17-20-18-7-6-2

（七）博乐天鹅湖周边城市游4-6-8-5-340-14-13-15

（八）天山玉邑民俗游13-10-9-15-14-20-17-8-6-11-3

（九）边疆宝藏探秘之旅10-3-8-2-7-11-12-20-14-5

12天

（一）远古文明之旅16-14-19-5-6-3

阿勒泰/哈纳斯湖/额尔齐斯河

塔城

•克鳖依

博乐/博尔塔拉/怪石沟3

・石河

本山

伊犁/苏边境的乾隆格登碑/906.

S哈密金王陵

巴音布鲁克大鹅础鲁木齐

2鲁番/火焰山

克孜尔千佛洞/库车大」.

阿克苏.13库尔给博斯腾湖.

阿图什4.•搂兰/罗浙泊

,沙图克麻扎:

•尼雅遗址

•和田

（图8：景点线路参考图）

短线：

9天

环疆山水丝路九日游20-14-8-2-3-7-15-17-10

8天

（一）西疆边境八日游18-10-9-3-1

7天

（一）疆北风情七日游2-5-3-1-13-10

6天

（一）全疆六日环游6-2-17-11-10-3

5.5天

（一）天山天鹅湖六日游12/0-3・8・2

4.5天

（一）哈密和田库尔勒五日游14-20-12

以玉邑丝路11日游为例，我们可以安排具体行程如下：

7-11-9-15-17-20-14-13-10-3

乌市、吐鲁番、伊犁、阿克苏、阿图什、和田、库乐勒、克孜乐千佛洞、天鹅湖、克拉玛

依

双飞十一日

行程安排：

第一天：乌鲁木齐市接机、入住酒店，游览城市风光，逛夜市，宿于乌鲁木齐市。

第二天：中午乘车前往吐鲁番，当日宿于吐鲁番。

第三天：从吐鲁番去火焰山，游览。晚上去伊犁，宿于伊犁。

第四天：游览伊犁景点，体验草原民俗风情。

第五天：中午飞往阿克苏。

第六天：游览阿克苏，上午去阿图什。

第七天：早上赴和田，白天游览。当晚乘飞机去库乐勒。宿于库乐勒。

第八天：游览库乐勒，当晚乘飞机去库车。宿于库车。

第九天：游览库车大寺和克孜乐千佛洞。宿于当地。

第十天：乘车去天鹅湖，游览，黄昏乘车去最近的机场，然后乘飞机去克拉玛依。

第十一天：游览克拉玛依。飞机返程。

其他均可做类似安排，不再详述。

六、模型的评价：

模型的优点：

1、本,土以规划模型为根底，以遗传算法作为求解工具，既取了规划模型的优点，即目

标函数与约束条件的意义都十分清晰，而辅之的遗传算法又克服了线性规划由于变量过多

而导致的计算效率下降等问题，从而使每一个模型根本上都能得到最优解

2、本文使用的模型和方法较为广泛，前三个问题都建立了两个模型或使用了两种方法,

这样既丰富了文章的内容，也通过模型之间的相互比拟和互相结合更好地完成了要求的任

务。

3、对于第四问，我们提出的算法思路不仅求得了多条黄金周旅游线路，同时还给出了

一些有价值的短程游路线。参加这一完善结果，可以更充分地利用各景区的旅游资源，而

且也同时满足了更多游客，让具有不同旅游需求的游客都可以领略新疆绚丽的风采，可以

说取得了一种锦上添花的效果。

4、本文综合运用了MATLAB、马克威分析系统、LINGO、EXCEL等多种软件，发挥

其各自的特长，在提高编译和求解效率的同时，也使文章图文并茂，更直观更具有可读性。

模型的缺乏及进一步探索：

1、本文的模型均建立在速度、单位行程的费用等都为恒定的根底假设之上，而实际上,

对于不同的道路，时速以及费用都会略有波动，如果在模型中能参加一些随机因素，应该

可以更接近现实生活。

2、模型处理复杂问题的求解上，根本都采用了遗传算法。但是，由于遗传算法的进化

是基于一定的概率，所以单纯的遗传算法有时并不能保证求得最优解，或者虽然能求得最

优解却要消耗相当多的时间，而这与我们的初衷是相违背的。如果能将遗传算法与模拟退

火算法、局部搜索等相结合，将会取得更好的效果。

3、在第四问中我们仅考虑了错开景点旅游顶峰，即仅从理性的角度分析筹划了旅游线

路，但没有考虑游客对各景点的偏好程度，即未参加感性的一些元素，而这些对于现实问

题还是很有影响的，因此，如果将游客的一些特定需要添加到模型的约束中，将会更符合

实际。

4、本模型第一步对景点进行了聚类，这样在为后面的分析带来了许多方便的同时，也

造成了一旦选择游览某个景区也即游览了此景区的所有景点的约束。而事实上，尤其是在

一条线路旅游的最后阶段，有可能出现时间上不允许游览某个景区，但却足够游览一两个

景点的情况。而我们的模型会直接将整个景区排除，这是我们线路设计模型的一个略有缺

乏之处。

七、模型及软件的前景展望：

1、蚁群算法模型：

本文中我们运用蚁群算法估计游遍新强境内所有景区在途中所花费的最少时间，从而

为合理安排行程做了铺垫。事实上，蚁群优化算法最初用于解决与本文问题相类似的旅行

商问题。之后又陆续渗透到诸如图的着色问题、大规模集成电路设计、通讯网络中的路由

问题以及平衡问题、车辆调度问题等其他领域中。蚁群优化算法在处理复杂优化问题，尤

其是离散优化问题方面显现出较强的优越性。对蚁群而言，在根本原理已经明确的条件下，

重要的就是开发出求解问题的算法模型，使求解问题更加切实有效。

2、遗传算法模型；

基于遗传算法的使用领域很广且算法效率高，本文多处运用遗传算法求解复杂优化问

题。这是一种模拟自然选择和遗传的随机搜索算法，它最初被应用于研究自然系统的适应

过程和设计具有自适应性能的软件。它也是一种高级最优化技术，可以用来解决函数优化、

组合优化、自动控制、图像处理、遗传编程、机器学习、数据挖掘等。遗传算法不单纯是

一种算法，也同样是一种思考问题的方式，所以它有很多代扩展的方向，如：遗传算法的

数学理论、分布并行遗传算法、分类系统、遗传神经网络、进化算法、人工生命等。

3、线性规划模型：

规划问题是运筹学中重要的分支，许多复杂问题都可以被抽象为线性、非线性、整数、

0-1规划等。本文两处运用线性规划均取得一定的进展，除此之外，它还可以处理包拈下料

问题、配料问题、选址问题、指派问题、投资问题、装箱问题、最短路问题、最小生成树

和最优连线问题等诸多看似一筹莫展的课题。

4、马克威分析系统

马克威分析系统是一款我国技术人员自行开发的软件，主要功能有：统计分析、数据

挖掘、统计图表制作。其操作十分方便，且结果显示清晰，利用马克威分析系统，可以编

制分布数列、绘制统计图、计算描述统计指标；实现区间估计、参数检验、非参数检验、

方差分析、相关与偏相关分析、回归分析、时间序列分析、聚类分析、判别分析、主成分

分析、因子分析等功能。

5、LINGO软件

LINGO语言以其简洁、易于扩展、“集合”特色等特点，在规划方面独树一帜。它既

能求解线性规划问题，也有较强的求解非线性规划问题的能力。LINGO软件不仅运行速度

快、计算能力强而且内置建模语言，提供几十个内部函数，从而能减少语句，较直观的方

式描述较大规模的优化模型。它的运用范围很广，可以用于解决各种线性、非线性规划、

多目标规划等复杂问题甚至实现非线性曲线拟合。

6、Excel软件

Excel是MicrosoftOffice套件中的电子表格软件，它的应用很广泛。Excel无需编程就

可以实现其他软件需要变成才能完成的复杂计算，能进行各种数据的统计、运算、处理和

绘制统计图形。Excel的数据功能主要有计算功能和数据分析功能两大块，前者指Excel有

强大的计算能力，它提供了300多个内部函数给用户使用，还允许自定义函数。后者指Excel

提供了“数据分析”工具包，内含方差分析、回归分析、协方差和相关系数、傅里叶分析、

t检验等分析工具。

7、MATLAB软件

MATLAB是一种高效的工程计算语言，它将计算、可视化、编程等功能集于一个易于

使用环境。其典型应用包括数学计算、算法开发、数据采集、系统建模和仿真、数据分析

和可视化、科学和工程绘图以及应用软件开发等。

MATLAB的一个重要特色就是它有一个套程序扩展系统和一组称之为工具箱的特殊

应用子程序一一工具箱，每一个工具箱都是为某一类学科专业和应用定制的，主要包括信

号处理、控制系统、神经网络、模糊逻辑、小波分析、系统仿真等方面的应用。此外，MATLAB

应用程序接口（API）支持对C、JAVA、Fortran语言的交互编写，使用户能更加自如地解

决实际的问题。

本文中的蚁群算法、遗传算法以及安排黄金周线路时都使用了MATLAB编程，其代码

简洁、可视化等特点已可见一斑。

参考文献：

11]曾五一等，统计学，北京：北京大学出版社，2006年。

⑵李士勇，蚁群算法及其应用，哈尔滨：哈尔滨工业大学出版社，2004年。

[3]雷英杰等，MATLAB遗传算法工具箱及应用，西安：西安电子科技大学出版社，2005

年。

[4]周明等，遗传算法原理及应用，北京：国防工业出版社，1999年。

[5J袁新生等,LINGO和Excel在数学建模中的应用，北京：科学出版社,2007年。

[6]求是科技，MATLAB7.0从入门至IJ精通，北京：人民邮电出版社，2006年。

17JNirwanAnsar,EdwinHou著，李军，边肇祺译，用于最优化的计算智能，北京：清华

大学出版社，1999年。

[8]国道距离信息，：〃crane88/road.asp?myid=312,2007年3月29日。

[9]公路客运，：〃china-holiday/online/skb/qhdh.asp?qhsm=®rffi,2007年3月

29日。

[10]铁路票价，：〃china-holiday/on!ine/skb/skb.asp?xs=cc&cc=P8871

/8874,2007年3月29日。

[11]经纬度查询，：〃hjqing/find/jingwei/index.asp,2007年3月29日。

[12]旅馆住宿价格查询，：〃zjxc/Iixingshe3/szlxsl86,2007年3月29日。

[13]景点逗留时间：

哈纳斯湖，://xjx.cc/kanas/jpxl/guanguang.htm

额尔齐斯河，：〃/asp/line/xianlu.hlm

阿勒泰，：〃soochina/article/articleshow.asp?ID=18257

塔城，:///Article/ShowArticle.asp?ArticleID=1758

克拉玛依，://auyou/auyou/lyxlinfo.asp?auto_id=5088

怪石沟，://bozhounews/2006-09/19Zcontent_8079338.htm

博尔塔拉，：〃bozhounews/2006-09/19/content_8079338.htm

博乐，://bozhounews/2006-09/19Zcontent_8079338.htm

石河子，：〃soochina/article/arlicleshow.asp?ID=18253

昌吉，://soochina/article/articleshow.asp?ID=18252

乌鲁木齐，://xjtstc/news/mj.asp?id=A20072l21548535693364

天山，://xjtstc/ncws/mj.asp?id=A2007281050373903767

伊犁，://gotoxj/xianl/zj3.htm

昭苏边境的乾隆格登碑，://traveL163/04/0830/17/0V25VKL900061DPB

.html

吐鲁番，://xjtstc/news/mj.asp?id=A20072121548535693364

哈密，:///travel/index.htm

巴音布鲁克天鹅湖，://uu97Zjd_2450.html

火焰山，：〃1x1/Travel」ine/20069/Travcl」ine_l300.html

回王陵，://tvtour/tour/lvj/hami/interest/08.htm

克孜尔千佛洞，：〃/lashjuku/lv/index.htni

库尔勒，：〃ylnet/travel/yllxs/ylxl3.htm

博斯腾湖，：〃ylnet/travel/yllxs/ylxl3.htm

阿克苏，：〃/Travel」ine/20069/Travel」ine_l300.html

库车大寺，：〃xjhy/line_detail.asp?id=l

罗布泊，：〃auyou/auyou/lyxlinfo.asp?auto_id=1102

楼兰，:///tanxian.htm

苏丹•沙图克麻扎，://26/kzIy/_private/kz201.htm

阿图什，://26/kzly/_privatc/kz201.htm

咯什，:///xinjiangsankcyou/kashidawakuyou.htm

香妃墓，：〃Ivyoul14/line/line_show.asp?LineID=1578

艾提布清真寺，：〃Ivyoul14/line/line_show.asp?LineID=1578

尼雅遗址，://visitxinjiang/xj/Article_Print.asp?ArticleID=3126

和田，:///plans/plan.php?id=2949,2007年3月29日。

附录：

1、新疆境内的33个旅游景点名称及其相应的观光逗留时间，经、纬度如下表所示:

序号景点名称景点观光时间经度纬度

1哈纳斯湖187.248.2

2额尔齐斯河0.586.947.8

3阿勒泰188.1547.86667

4塔城182.9666746.75

5克拉玛依0.584.7666745.6

6怪石沟18345.2

7博尔塔拉28145

8博乐182.144.93333

9石河子185.9544.26667

10昌吉187.244.2

11乌鲁木齐1.587.6833343.76667

12天山188.443.7

13伊犁181.843.9

14昭苏边境的乾隆格登碑0.58143.2

15吐鲁番189.242.9

16哈密193.442.8

17巴音布鲁克天鹅湖0.584.143.1

18火焰山0.590.243.6

19回王陵192.743.8

20克孜尔千佛洞0.582.741.8

21库尔勒0.586.0666741.68333

22博斯腾湖0.586.5333341.95

23阿克苏180.241.1

24库车大寺0.582.941.6

25罗布泊490.441.6

26楼兰688.841.6

27苏丹•沙图克麻扎0.2575.939.6

28阿图什0.7576.1166739.