旅游线路设计和对比

旅游线路设计和对比

朱晓斌韦哲丁俊飞唐超

摘要

本文首先运用主成分分析法对景点品质进行分析，选取主成分，并把主成分得分按照方差的贡献率进行加权求和，得出每一个景点的综合评价指数，进而对各景点进行排序，发现排序与知名度和门票价正相关。

通过对旅游设计六个原则进行分析，确定进行路线设计分两步走，一是先综合考虑各旅游城市的景点资源和各城市间的距离对旅游路线的干道进行设计；二是运用蒙特卡罗改进的模拟退火算法，以最短路径，最少花费为目标对各个旅游城市进行局部的旅游路线进行优化设计。

对于问题三，为了更好地对两条线路进行相似性比对评估，本文从空间距离、运行路线、时间安排、线路总体相似度、总体差异度、特色饱和度等方面采用了层次分析法进行分析，进行定量与定性的比对性评估，得知A线路与B线路比较相似，其中通过模型二设计的路线得分为0.508，A线路的综合得分为0.253，B线路的综合得分为0.292。

关键字：主成分分析法旅游路线设计模拟退火算法最短路径层次分析法

现在，旅游越来越成为消费时尚，旅游者外出旅游大多是为了游览名山大川、名胜古迹，轻松、娱乐、增长见识是他们的主要需求。作为旅游行业，开发出更好的旅游产品是很重要的，而设计好旅游线路是其中的一个重要环节。设计者应根据不同的游客需求设计出各具特色的线路。比如不少商人洽谈生意之余也需要到处旅行,他们的旅行多是出于商务方面的动机，商务旅游的特点是消费较高，喜欢入住高级酒店，为业务交往需要经常在餐厅宴请宾客，而且来去匆匆；而针对退休老年人的旅游线路就应该轻松、休闲、节奏稍慢，费用适中等等。旅游市场发展日新月异，游客的需求与品位也在不断地变化和提高。为了满足游客的需要，旅行社应及时把握旅游市场动态，注重新产品、新线路的开发，并根据市场情况及时推出新的有特色的旅游线路。一条具有特色的旅游线路，有时能为旅行社带来惊人的经济收入与社会效益。

现在某旅行社为了进一步开发旅游市场，比如以海南省旅游为例，想对旅游线路进行重新整合，合理设计。一般考虑旅游线路，从经营方或者供给方出发，会涉及下面的五个方面：一是空间距离；二是运动路线；三是组织形式；四是旅游目的；五是各类旅游线路之间的关系。主要设计原则有：一是资源导向原则，如注意旅游地的主题特色；二是以游客旅游需求和目的为主的原则；三是市场细分区位原则；四是供给全面原则；五是时效优先效益兼顾原则，如注意冷热景点搭配、注意向新开发景点引导；六是安全第一原则。设计出来的旅游线路必须重视作为旅游活动主体的心理和生理需求，给旅游活动带来方便，提高旅游者的满意度和出游积极性，进而促进旅游地的可持续发展。

旅游线路的设计关键是适应市场需求，具体而言，它必须最大限度地满足旅游者的需求，如成本最小，日程最方便等等。对于旅行社来讲，又要尽可能在满足旅游者需要的前提下降低运营成本，提高效益。在设计时充分考虑景点资源、交通条件、时间效率、旅游者的满意程度等因素的限制，一般的设计思路为：第一步资源分析；第二步市场定位分析；第三步典型线路设计。下面请你以武汉到海南五日游（双飞）为对象，运用上述原理完成下面的问题，为简化设计，我们规定往返的飞机票在800－850元/人之间，全程空调旅游车的车费按约1元/（公里*人）计算。

需要研究的问题有：

1、运用你所学方法对海南主要景点进行品质综合评价；

2、参考以上原理设计几条特色旅游路线，如：文化历史游，生活享受游，风景游等等，要求至少保证3到6个高品质景点，为保证旅游者的需要，建议在你的路线中保留一些传统的知名景点；

3、为了保证线路质量，旅行社要求每条线路都要进行比对评估，试建立模型从空间距离、运行路线、时间安排、线路总体相似度、总体差异度、特色饱和度等方面进行线路相似性比对评估；如选择下面线路A与线路B（参考附件2），并与你上面设计的一条线路进行总体比对，并给出具体定量化结果；

4、参考附件2，给武汉的三组旅游者设计不同的旅游线路和价格（五日四晚游双飞），并对其进行比较。

旅游路线的设计最主要是适应市场的要求，给旅游活动带来方便，提高旅游者的满意度和出游积极性，进而促进旅游地的可持续发展。

对于问题一，很明显这是一个综合评价问题，在对海南主要景点进行品质评价时，最关键的是确定评价品质的评价指标。根据附表1可知，景点品质最主要与其所在城市、景点的门票价格、景点离市中心的距离、景点的知名度、景点的类型、景点的规模及景点的开发时间有关。所在城市越繁华越有名，景点就越被人知晓；景点的门票价格也从另外一个角度反映出了该景点的质量；景点离市中心越近，去观赏景点的人就越多；景点的开发时间越近，对旅游者越有好奇感和新鲜感。而且通过分析这几个评价指标，发现他们之间有很明显的相关性。因此为了能够更好的、客观、准确的对景点品质做出评价，可以先对这几个指标进行量化，然后采用主成分分析消除各评价指标之间的相关性，使得所反映信息重叠的变量被某一主成分代替，减少变量的个数，从而降低系统评价的复杂性。再以方差贡献率作为每一个主成分的权重，由每一个主成分的得分加权即可完成对景点品质的综合评价。

问题二，我们为了简化问题的求解，只选取了三种类型的旅游作为代表进行研究，即文化历史游、生活享受游和风景游。根据题意可知，本问要在考虑六个原则的条件下设计出最佳的旅游路线，很明显这是一个多目标问题。资源向导原则即旅游地要有主要特色，也就是说文化历史游路线要以文化历史为主要特色，生活享受游路线要以自然为主要特色，风景游路线要以风景为主要特色；因此，可以在海南主要旅游景点中按照各风景类型进行分类，在从每一个分类中找出相应的最佳旅游路线。设计旅游路线最关键的是最大限度地满足旅游者的需求，给旅游活动带来方便，提高旅游者的满意度，即要满足第二个设计原则。通过查阅有关资料，与旅游者满意度相关的指标最主要有旅游价格、导游、住宿、餐饮、购物、交通、旅游资源、娱乐、目的地居民态度等，因为本题没有提供相关的数据，所以在本文里我们只考虑旅游价格、交通和旅游资源三个主要指标来确定旅游者的满意度。同时我们在满足其他的设计原则的条件下，尽量提高旅游者的满意度。如：考虑到一整天参观文化历史类的景观可能会产生欣赏疲劳，因此设计旅游路线时要尽量冷热景点搭配及向新开发的景点引导。所以我们建立一个三目标的优化模型，分别以旅游价格最小、路程最短及旅游资源最多为目标函数，对问题进行求解。对于旅游时间问题我们不给与太多的考虑，当旅游时间结束时我们就停止旅游。

问题三，这是一个综合比对问题，我们可以根据空间距离、运行路线、时间安排、线路总体相似度、总体差异度、特色饱和度等准则建立一个层次分析模型，对每一条线路进行综合比较，最后得出各条路线的综合打分，根据综合打分来判断各条路线的相似程度。

三、模型假设

1、假设景点的评价因素只考虑附件1中给出的，其他的影响因素不予考虑；2、假设景点品质与景点的类型无直接联系；

3、假设从武汉到海南花费的时间不计入旅游时间，即武汉到海南是一瞬间完成的；

4、假设在海南省内旅游时一律只坐空调旅游汽车；

5、假设在旅游过程当中不走回头路，并且游玩了一个旅游城市后必须回到市里再去下一个旅游城市；

6、假设旅游只在白天的十二个小时内进行，而且在一个城市游玩的时间不能够超过三天；

四、符号说明

Z

W景点品质的综合评价值各旅游城市的评价值城市含所有景点数城市含知名景点数景点i去景点j的旅游花费

sizih(i,j)

五、模型的建立与求解

5.1、景点品质综合评价模型

主成分分析(PrincipalComponentsAnalysis，PCA)也称为主分量分析，是一种通过降维来简化数据结构的方法：如何把多个变量（指标）化为少数几个综合变量（综合指标），而这几个综合变量可以反映原来多个变量的大部分信息。为了使这些综合变量所含的信息互不重叠，应要求它们之间互不相关。主成份分析的目的是从原始的多个变量取若干线性组合，能尽可能多地保留原始变量中的信息。从原始变量到新变量是一个正交变换（坐标变换）。设有

X=(X1,X2, Xp)是一个p维随机变量且有二阶矩，记µ=E(X)，

'

∑=Var(X)。考虑它的线性变换：

Y1=L1'X=l11X1+ +lp1Xp

Y=L'X=lX+ +lX

p1p1ppp p

（1）

易见

Var(Yi)=Li∑Li

'

Cov(Yi,Yj)=Li∑Lj

'

i,j=1,2, ,p

（2）

如果要用Y1尽可能多地保留原始的X的信息，经典的办法是使Y1的方差尽可能大，这需要对线性变换的系数L1加限制，一般要求它是单位向量，即

L1'L1=1。其它的各Yi也希望尽可能多地保留X的信息，但前面的Y1,Y2, ,Yi 1已保留的信息就不再保留，即要求Cov(Yi,Yj)=0,j=1,2, ,i 1，同时对Li也有

Li'Li=1的要求，在这样的条件下使Var(Yi)最大。设协方差阵

∑

的特征值为

λ1≥λ2≥ ≥λp≥0，相应的单位特征向量分别为a1,a2, ,ap（当特征根有重根时单位特征向量不唯一）。这时X的第i个主成分为Yi=ai'X,i=1,2, ,p，且

Var(Yi)=λi。记A=(a1,a2, ap)。

λ1 Λ=

λp

p

p

（3）

Y=(Y1,Y2, Yp)，则A为正交阵，Y=AX，Var(Y)=Λ，且∑λi=∑σii，其

'

1

1

中σii为

∑

的主对角线元素。

主成份Yk与原始变量Xi的相关系数ρ(Yk,Xi)称为因子负荷量

(factor

p

ii

loading)，可以证明ρ(Yk,Xi)=λkaik

2

ii,i,k=1,2, ,p，

p

∑σρ(Y,X)

k

i

1

=λk，

∑ρ(Y

1

p

k

,Xi)=∑λkaik2λkaik2ii=1。

2

k=1

为了减少变量的个数，希望前几个Yi就可以代表X的大部分信息。定义

λk

∑λ

i=1

p

i

为主成份Yk的贡献率，称∑λi

i=1

m

∑λ

i=1

p

i

为主成份Y1,Y2, ,Ym的累计贡献

率。一般取m使得累计贡献率达到70% 80%以上。累计贡献率表示m个主成份从X1,X2, Xp中提取了多少信息，但没有表达用它来恢复每一个Xi能恢复多少，为此定义m个主成份Y1,Y2, ,Ym对原始变量Xi的贡献率νi，νi为Xi对

2

Y1,Y2, ,Ym的复相关系数平方，可以用公式νi=∑λkaikii计算（注意m=p

p

k=1

时νi=1）。前m个主成份Y(m)=(Y1,Y2, Ym)'在X的m个线性组合中能对X最好地线性逼近。

对于本问题，由于没有明确的数据，所以我们首先要查阅相关资料得到各指标的值和对各个指标进行量化。景点所在城市以城市的前年旅游收入进行赋值；景点地址以到城市的距离进行赋值；景点规模根据小中大等级分别赋值为1,2,3；同样，景点开发时间也以开发时间的新老等级进行分别进行赋值3,2,1。然后根据主成分分析的方法，分析海南省近一百多个景点的七个品质评价指标值。步骤如下：

Step1：为了消除不同变量的量纲的影响，首先需要对变量进行标准化，设要评价的景点数为n个，指标共p个，分别设为X1,X2, Xp，

xij(i=1, n;j=1, p)为第个景点的第个指标的值。做变换

Yj=

Xj E(Xj)(j=1, p)(Xj)

（4）

得到标准化的数据矩阵Y；

Step2：在标准化数据矩阵Y的基础上计算p个原始指标相关系数矩阵R=(rij)，

其中：

rij=

∑(x

k=1nk=1

n

ki

i)(xkj j)

n

22

()(x )x ∑kii∑kjj

(i=1,2, n;j=1,2, ,p)

（5）

k=1

Step3：求相关系数矩阵R的特征值并排序λ1≥λ2≥ ≥λp，再求出R的特征值的相应的正规化单位特征向量li=l1i,l2i, lpi，则第i个主成分表示各个指标

()

Xk的线性组合Zi=∑lkiXk。

k=1

p

Step4:确定主成分数目。本文中取累计贡献率为95%。

Step5：计算综合得分。首先计算得到的第i个景点中第k个主成分的得分，然后再以每一个主成分的方差贡献率为权重，求出第i个景点的综合得分。

Step6：根据每一个景点的综合得分进行排序。调用Matlab中的主成分分析工具箱即可求得结果。统计结果如下：

六个评价指标的相关系数矩阵为:

-0.088146-0.230580.11421-0.219470.10483 1

10.207620.329250.506150.37672 -0.088146

-0.230580.2076210.0579330.26334-0.033186

R=

0.329250.05793310.369640.014597 0.11421

-0.21947 0.506150.263340.369641-0.0025187 0.104830.37672-0.0331860.014597-0.00251871

各个主成分的特征值、贡献率及累计贡献率如下表1：

表1各主成分的贡献率表特征值

0.48840.22040.19850.05580.0322

贡献率49.070%22.142%19.942%5.611%3.235%

累计贡献率49.070%71.272%91.214%96.825%100%

第一主成分第二主成分第三主成分第四主成分第五主成分

分析上表可知,各个主成分的贡献率没有特别大的情况，说明各个指标不存在尺寸问题。而且前四个主成分的累积贡献率已经达到96.8%，很明显大于我们规定的95%，所以我们取前四个主成分去评价景点品质。

根据相关系数矩阵R的特征值的相应的正则化的单位特征向量，前四个主成分关于指标的线性组合为：

y1= 0.62x1+0.32x2+0.42x3+0.14x4+0.5x5 0.18x6y2= 0.26x1+0.37x2 0.07x3 0.41x4 0.11x5+0.78x6y3=0.09x1+0.36x2 0.67x3+0.55x4+0.30x5+0.13x6y4= 0.30x1 0.14x2+0.24x3+0.67x4 0.55x5+0.27x6

（6）

由上述的线性表达式可以看出,y1最主要与x1,x3的联系比较密切；y2最主要反应的是x4,x6的指标特性；y3是除x1指标外的线性组合；y4跟x4,x5分别成正相关、反相关的关系。

以各个主成分的贡献率为权重可得出各个景点的综合评价值Z为：

Z=0.497y1+0.221y2+0.199y3+0.056y4

部分结果如下表2（其余的见附表1）：

表2各主成分及综合的得分

景点蜈支洲岛天涯海角亚龙湾中心广场大东海南山文化旅游区西岛

第一成分6031.36516.211440123471840.31360.3

第二成分-17315-18739-32918-35398-5279.6-3942.8表3

景点蜈支洲岛天涯海角亚龙湾中心广场大东海南山文化旅游区西岛

城市57.8657.8657.8657.8657.8657.86

第三成分231022495643832472137081.15265.8

第四成分2806930365533425740785606376.8

综合得分398403698929631217842105919479

（7）

排名123456

排名前六景点的六个指标值

距离市心的距离23.220.114.44.931.815.7

知名度854347936963592467914519141790

景点规模321123

开发时间212121

门票价1606555065100

分析上表2和原始指标数据表3可知，当景点的门票价和知名度越高时，景点的综合得分也越靠前，说明景点品质的好坏与门票价和知名度呈正相关的关系。

5.2旅游路线设计模型

5.2.1文化历史游的路线设计

对于旅游路线设计问题，最关键的是要考虑整个旅游的旅游花费、路程最短和景点资源等问题。通过问卷调查，旅游者最关心的是旅游花费和时间问题，对景点资源只要是大体上符合自己的要求就比较满意。因此我们在设计旅游路线时采取分两步走的思想：一是先根据旅游路线的特色，从附件1中手工的挑出满足该特色所有的旅游景点，并对这些景点按城市进行分类，同时也对海南省的所有的景点按城市进行统计分类，然后综合这两种分类，从中选取出含旅游景点和特色旅游景点都相对比较多的城市，并对他们进行排名，把排名第一的城市作为旅游路线的起始点，最后综合各城市的景点品质和各旅游城市间的相对位置用求出旅游路线的下一个旅游城市，得到一个整体的旅游路线干线城市图；二是根据旅游城市图对每一个城市的景点进行旅游路线设计，在设计的过程中要保证旅游路线最短和旅游花费最少，为了能同时考虑这两个目标，我们把路径最短问题也转化为旅游花费最少问题，即把双目标问题转化成为单目标问题，用蒙特卡罗改进的模拟退火算法对其进行求解。

由于景点资源关系到很多的方面，而且它也是一个很模糊的概念，因此我们对它进行具体化，在保证每一条路线至少有3至6个高质量的景点的基础上，旅游时要尽量安排冷热景点搭配和向新开发的景点引导，把那些景点品质高的景点尽量安排进去，并在有限的时间内玩尽可能多的景点；对于交通条件，应使旅游的设计路线越短越好，这样才能保证路费最少，也能减少旅客的疲劳度；在整个的旅游过程中旅游花费最主要包括住宿、餐饮、娱乐及路费等，本文只考虑路费和门票费的情况，花费越少，旅客越能接受，而且也越能吸取更多的旅游者。

5.2.1.1旅游城市之间旅游干线的设计

根据海南省主要旅游景点信息一览表可得出几个含景点数比较多的旅游城市，统计数据如下表4：

表4

城市景点数

三亚22

海南最主要旅游城市所含的景点数

万宁11

琼山7

文昌6

琼海7

儋州9

海口10

通过分析附件1可得到所有属于文化历史类的景点及它们所在的城市，具体统计结果如下表5：

表5

城市三亚

文化历史游的景点分布

屯昌

海口万宁琼山乐东保亭文昌博鳌琼海澄迈

景点14数城市安定

6421122261

儋州五指临高

山3

3

1

3数

从上表中可看出，其中三亚含文化历史类型的景点数最多，海口和琼海次之，再其次是万宁、安定、儋州和五指山。

由上表4和上表5综合考虑可得，其中三亚含景点数最多，含文化历史类型的景点数也最多，而且由模型一得出的景点品质综合得分也可看出三亚含高品质的景点也是最多的，因此文化历史游旅游路线的起始点可确定为三亚。

根据题目的要求，要求每一条旅游路线上至少应包含3至6个高品质的景点，因此我们可从表5中选出三亚、海口、琼海、万宁、安定、儋州和五指山作为旅游干线的可选对象。干线城市选择的结构示意图如下：

图16干线设计结构图

首先把三亚A0作为旅游路线的起始点，然后从A1, A6中选出一个城市作为干线的第二个旅游城市，依次下去、、、、、、直到所有的城市都被选完，即可得到文化历史游的干线。

在确定旅游干线的城市时，既不能就单纯的只考虑给城市之间的距离，也不能单纯的只考虑各旅游城市的景点品质。我们要考虑的应该是他们两者的综合。为了能够更好的量化各个旅游城市的值，我们定义了一个城市评价值W，它是城市距离和城市景点品质二者的加权。由于城市到城市的距离跟各旅游城市的景点品质的量纲不一样，因此在确定城市评价值时应先对这两个指标进行标准化，

本文采用极差标准化，假设有n个城市可供选择，则由干线初始城市到下一城市距离xi为：

xi=

xi min(xi)

,i=1,2, n 1

maxxi minxi（8）

在确定各个可选旅游城市的景点品质时，依据该城市含所有景点数si和含知名景点数zi进行确定。根据模型一可在确定好文化历史类景点的综合指数，然后进行排序，我们规定排名前十的景点为知名景点。所旅游景点品质Yi为它们两的线性组合：

Yi=λ1si+λ2zi,i=1,2, n

（9）

通过对游客们的问卷调查可知,λ1约为0.4，λ2约为0.6。然后也用极差标准化对Yi进行标准化得到yi，所以城市的评价指标知w为：

w=α1x1+α2y2

（10）

其中α1,α2为权重系数。同样根据游客们的反馈信息可确定α1,α2分别为-0.2，0.8。不过在具体解决问题时，可以根据旅游者自己的意愿进行赋值。本文采用

α1= 0.2,α2=0.8。

根据我们查出来的三亚与各可选城市之间的距离经过（8）式标准化之后的数据如下表6：

表6各城市的xi值

景点

海口1

琼海0.584

万宁0.325

安定0.792

儋州0.527

五指山0

xi

由上表5可以知道该城市含所有景点数si和含知名景点数zi，经过（9）式计算后进行标准化得yi为：

表7各城市的yi值

景点

海口0.297

琼海0.203

万宁0.188

安定0

儋州0.125

五指山0.017

yi

以上表6、表7的数据，代入到低（10）式得到各个城市的w值为：表8各个城市的w值景点

w

海口0.0374琼海0.0456万宁0.0850安定-0.1584儋州-0.0054五指山0.0125

从上表8中可以很明显看出万宁的w值最大，因此我们把万宁市作为整个文化历史游旅游路线的第二个城市,根据上述原理经过六次这样的运算后可以很简单的把旅游线路的主干线给确定出来：

图2文化历史游线路的旅游干线

5.2.1.2各个旅游城市旅游路线的设计

在旅游路线干线确定好后，只要在各个旅游城市里设计好旅游路线就能解决问题。由于不考虑时间的约束，即旅游者游完五日之后就结束，因此我们只要考虑旅游路线最短和旅游花费最少两个目标即可。旅游线路越短，在线路上花费的时间也越少，因此可以保证在有限的时间内游玩更多的景点；对于旅游花费最主要包括住宿、餐饮、购物及娱乐等方面，但是在本文我们只研究景点的门票费和路费。旅游花费越低，旅游者的积极性就越高，也能为更多的旅游者所接受。考虑到本问题是一个双目标规划问题，但是如果直接对旅游路线和旅游花费进行双目标规划求解，因为很难找到约束条件，而且计算的复杂性，所以很难求出问题的准确解。通过进一步分析目标函数，发现路径最短问题可以直接转化为旅游路费最少问题，由于在前文已经假设了在海南省内旅游只坐空调旅游车，而做空调旅游车的车费按约1元/（公里*人）计算，因此只要把路程S乘以空调旅游车单位距离的车费就可得到路费。综上所述，我们可以把去某个景点的要花的路费和景点的门票价加起来作为该景点的旅游花费。然后用蒙特卡罗改进的模拟退火算法对问题进行求解。

模拟退火的基本思想：

模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据

Metropolis准则，粒子在温度T时趋于平衡的概率为exp( EkT)),其中E为温度T时的内能， E为其改变量，k为Boltzmann常数。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是一种启发式随机搜索过程。退火过程由冷却进度表(CoolingSchedule)控制，包括控制参数的初值t及其衰减因子 t、每个

t值时的迭代次数L和停止条件S。

模拟退火算法可以分解为解空间、目标函数和初始解三部分。

由一个产生函数从当前解产生一个位于解空间的新解；为便于后续的计算和接受，减少算法耗时，通常选择由当前新解经过简单地变换即可产生新解的方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产生新解的变换方法决定了当前新解的邻域结构，因而对冷却进度表的选取有一定的影响。

计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算。事实表明，对大多数应用而言，这是计算目标函数差的最快方法。

判断新解是否被接受,判断的依据是一个接受准则，最常用的接受准则是

Metropolis准则。

当新解被确定接受时，用新解代替当前解，这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正目标函数值即可。此时，当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时，则在原当前解的基础上继续下一轮试验。

模拟退火算法与初始值无关，算法求得的解与初始解状态S(是算法迭代的起点)无关；模拟退火算法具有渐近收敛性，已在理论上被证明是一种以概率l收敛于全局最优解的全局优化算法；

设某个旅游城市下有

个景点，用数码1

,2, n代表。在进行路线设计时，

3

所示：图3景点路线结构的拓扑图

设景点i和景点j之间的边为去景点j的旅游花费h(i,j),i,j=1,2, n。旅游景点路线设计问题是要找遍访每个景点恰好一次的一条回路，且要求这条路径上的总旅游花费为最少.。

求解旅游景点路线设计问题的模拟退火算法最主要的步骤如下：

确定解空间：解空间S是遍访每个景点恰好一次的所有回路，是(1,2, ,n)的所有循环排列的集合，S中的成员记为(w1,w2, ,wn)，并记wn+1=w1。初始解可选为(1,2, ,n)。

目标函数此时的目标函数即为访问所有景点的旅游花费C(S)；我们要求此目标函数的最小值。

新解的产生随机产生1和n之间的两相异数k和m，若k<m，则将

(w1,w2, ,wk,wk+1, ,wm, ,wn)变为：(w1,w2, ,wm,wm 1, ,wk 1,wk, ,wn)

如果是k>m，则将

(w1,w2, ,wk,wk+1, ,wm, ,wn)

变为：

(wm1,wm 1, ,w1,wm+1, ,wk 1,wn,wn 1, ,wk)

上述变换方法可简单说成是“逆转中间或者逆转两端”。当然也可以采用其他的变换方法，本文就采用上述的变换方法。

代价函数差设将(w1,w2, ,wn)变换为(u1,u2, ,un)后,则代价函数差为：

C(S') C(S);

模拟退火算法的具体步骤如下：

Step1：初始化：初始温度T(充分大)，初始解状态S(是算法迭代的起点)，每个T值的迭代次数L；

Step2：对k=1,2, ,L做第Step3至第Step6步；Step3：产生新解S'；

Step4：计算增量 t'=C(S') C(S)，其中C(S)为评价函数；

Step5：若 t'<0则接受S'作为新的当前解，否则以概率exp( t')接受S'作为新的当前解；

Step6：如果满足终止条件则输出当前解作为最优解，结束程序。终止条件

通常取为连续若干个新解都没有被接受时终止算法。

Step7：T逐渐减少，T(t+1)=kT(t)且T→0，k为正的略小于1.00的常数，t为降温的次数，然后转第Step2步。

对于原本含人文历史类景点比较少的城市我们直接用模拟退火算法进行求解即可，但对于那些含人文历史类景点比较多的城市在进行旅游路线设计时，我们没必要把所有的人文历史类景点全部游完，我们只要选去其中一部分景点进行游玩，因此，我们用蒙特卡罗改进的模拟退火的算法对其求解，保证旅游路线是最短路径和花费最少。

本方法可以根据旅游者的具体情况进行旅游路线的设计，具有很强的应用广泛性，即只要旅游者给出自己要在某个旅游城市的游玩景点数，就可以找出相对应的最短路径和最少旅游花费的路线。

通过计算机编程可对每一个旅游城市进行最佳旅游路线设计，其中对三亚这个大型旅游城市含的景点数很多，不可能全部游完，所以在此只选了满足条件的十个旅游景点，其文化历史游的主要路线如下表所示：

表9文化历史游的路线安排

三亚

西岛

兴隆温泉

↓

琼海

南山文化旅游区

↓

万泉河

↓

美丽之冠丽景温泉鱼疗

↓

万泉湖旅游度假区

↓

三亚爱心大世界

↓

官塘温泉

↓

三亚田原温泉鱼疗

↓

红色娘子军纪念园

↓

三亚泰象表演馆

↓

琼海红色娘子军塑像

↓

古崖州城

↓

水世界“罗马剧场”

↓

亚龙湾蝴蝶谷

↓

海口滨海公园

↓

南田温泉（神州第一泉）

↓

秀英古炮台

↓

万宁

东南亚风情园

↓

丘浚墓

↓

东山岭

↓

海瑞墓

↓

石梅湾潜水加井岛

↓

海口人民公园

↓

注：本路线中由于在同一个旅游城市不能超过三天，所以在三亚只选了10个旅游景点。除此之外，该路线没有规定几日游，因此，对于有时间限制的旅行只能是按照路线的安排顺序往下游玩，一直游玩到时间结束。

至于风景游和生活享受游的设计方案模型同文化历史游一样，其结果件附录。

5.3旅游路线的比对模型

设某层有n个因素，要比较它们对上一层某一准则（或目标）的影响程度，确定在该层中相对于某一准则所占的比重。（即把n个因素对上层某一目标的影响程度排序）上述比较是两两因素之间进行的比较，比较时取1 9尺度。用aij表示第i个因素相对于第j个因素的比较结果，则

aij=

1aji

A=(aij)n×n

a11 a21= a n1a12 a1n

a22 a2n

an2 ann

A则称为成对比较矩阵。

若成对比较矩阵是一致阵，则我们自然会取对应于最大特征根的归一化特征向量.

若成对比较矩阵不是一致阵，Satty等人建议用其最大特征根对应的归一化特征向量作为权向量.

由于特征值连续的依赖于n，则特征值比n大的越多,不一致性越严重。用最大特征值对应的特征向量作为被比较因素对上层某因素影响程度的权向量，其不一致程度越大，引起的判断误差越大。因而可以用与数值的大小来衡量

λ nCI=

n 1随机一致性指标RI的数值：n1234567891011RI000.580.901.121.241.321.411.451.491.51

CICR=<0.1，不一致程度在容许范围之内，可用其归一化一般，当一致性比率RI

特征向量作为权向量，否则要重新构造成对比较矩阵，对A加以调整。在本问题中，决策层为最优路线，准则层为：空间距离、运行路线、时间安排、特色。

第一层的比较阵

11/21/41/9 211/21/4

A=

4211/2

21 94

最大特征值λ=4.085，特征向量ω={0.0688,0.1306,0.2612,0.5393}。一致性检验

CR<0.1各对象对各准则的比较阵空间距离 11/21/9

A1= 211/4

941 最大特征值λ=3.0015，对应特征向量ω1={0.0852,0.1773,0.7275}。

路线质量

195 A2= 1/911/2

1/521

,0.0816,0.1576)。最大特征值λ=3.0012，对应特征向量ω2=(0.7608

11/31/5 A3= 311/2

521

时间安排

,0.3090,0.5815)最大特征值λ=3.0037，对应特征向量ω2=(0.1094

25 1 A4= 1/212

1/51/21

特色

最大特征值λ=3.0055，对应特征向量ω2=(0.5954,0.2764,0.1283)得出各路线的综合打分为：(0.508,0.252,0.292)

六、模型的评价和改进

主成分分析模型具有如下的主要特点：（1）指标的综合性，它将多个有相关

性的指标综合成几个主成分，使之更能体现各个指标的特性，简化了模型的求解；（2）建模思想比较简单，不需要太复杂的理论知识，能被大部分人所理解；（3）建模精度较高，可保持原系统的特征，能较好的反映系统的实际状况。

蒙特卡罗改进的模拟退火模型的特点有：（1）具有很广泛的应用性，因为用的是蒙特卡罗的方法，可以在城市内随机的选取景点数，所以应用很广；（2）具有全局最优性，模拟退火算法具有渐近收敛性，是一种以概率l收敛于全局最优解的全局优化算法。

层次分析法具有的特点为：（1）能对定性的问题给与相对准确的定量分析；（2）具有结构层次性，思路清晰明了。

对于模型一，题中没有给出一个明确的指标体系来评价景点的品质，为了建立模型简便，我们没有再增加其他影响景点品质的因素，只是根据附件1中给出的几个指标，把它进行简单的量化之后就做为景点的评价指标，所以，如果在模型中再增加其他的评价因素可能会得到更好的结果；对于模型二，题中明确要求要在六个原则下进行旅游路线的设计，但是由于六个原则太多，而且也不好把六个原则目标进行加权，因此本文只考虑了其中最重要的三个因素：景点资源、路

程和旅游花费，并在设计时采用了两步走的思想，先考虑了主干道的设计，然后再考虑局部的路线设计，虽然设计的结果还比较理想，但是这大大的缩减了题目对路线设计的要求。因此在景点设计时如果能把冷热景点搭配和向新景点引导设为一个新的目标，在对问题进行求解，可能会把旅游路线设计的更加完美。而且用蒙特卡罗改进的模拟退火算法具有随机性，求解的路线有可能不是精确解。在问题三之中，虽然我们用了层次分析法对每一条旅游线路进行了定量与定性的分析，但是在量化的过程之中，由于指标的抽象性，导致人的主观因素太大，最后造成模型的结果有很大的误差。

参考文献

[1]

曾建军李世航等，MATLAB语言与数学建模，合肥，安徽大学出版社，2005甘应爱田丰等，运筹学，北京，清华大学出版社，2005.6阮晓青周义仓等，数学建模引论，北京，高等教育出版社，2005.7汪定伟王俊伟等，智能优化方法，北京，高等教育出版社，2007.4

[2][3]

[4]

附录：

生活享受游的路线

日期

游览城市：海口

第1天

行程安排：金牛岭公园→西海岸带状公园→热带海洋世界琼山

第2天

行程安排：东寨港红树林保护区→海南鹿场游览城市：琼中、兴隆

第3天

行程安排：黎母山森林公园→兴隆热带植物园→

兴隆热带花园→东南亚风情园游览城市：陵水、三亚

第4天

行程安排：南湾猴岛→吊罗山国家森林公园→南田温泉三亚

第5天

行程安排：亚龙湾蝴蝶谷→龙虎园→天涯海角

无三亚兴隆琼山海口

行程安排

住宿

风景游的路线

日期

游览城市：海口

第1天

行程安排：各主要景点游览城市：琼海、兴隆

第2天

行程安排：红色娘子军塑像→万泉河漂流→玉带滩→博鳌水城

琼山海口

行程安排

住宿

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