一种基于景区路径的优化方案研究

魏玮　吴梦月

摘 要：该文介绍了一种基于景区路径的优化方案，采用旅行商问题求解来破解旅游线路的拥堵问题，并对遗传算法进行了约束求解。相对于传统的静态求解方法，基于北京市旅游線路的复杂特征，通过引入堵车系数来进行动态求解优化方案，对求解的实际路线进行算法性能分析，实验结果证明该算法能够快速有效地求得问题的最优解。

关键词：旅行商问题 堵车系数 优化方案

中图分类号：TP391 文献标识码：A 文章编号：1674-098X（2017）01（b）-0014-03

随着旅游业的高速发展，交通拥堵问题已成为制约旅游业发展的瓶颈问题。如何破解交通拥堵这一问题，近年来引起了许多学者的广泛关注。旅行商问题（简称TSP问题）为我们解决该问题提供了一种数学方法。从数学上讲，TSP问题就是一种遍历各个景点的最短路径求解。近年来，遗传算法在求解旅行商问题中显示了其优越性。它将旅行商问题的解集看作一个种群，通过群的操作最终求解。但传统的算法存在速度慢的缺陷，笔者根据北京交通的复杂性，结合旅行商问题求解的算法，对已有的算法进行了改进，为求解最优旅游路线方案提供了一种新的研究思路。

1 解决方案

遗传算法是目前最常用的解决TSP问题的算法[1]，其优势在于算法可以进行全局空间搜索，但也存在需要改进的不足，如算法速度较慢。笔者针对北京城区旅游线路的不同特征，有针对性地对遗传算法进行改进[2]，主要工作如下。

（1）调研了多条北京景区旅游线路，根据不同线路特征，设计了不同权重的堵车参数。

（2）对参数表达函数进行了改进，使之有利于问题求解。

（3）采用了改进的贪婪交叉算子和启发式倒位变异算子，提高了求解效率。

根据北京交通的历史数据分析，最短旅行路线未必是时间最优的旅行路线，而影响时间因素的最大因子是堵车，因此，笔者在方案设计中加入了堵车参数，通过对历史数据的统计分析，来求解堵车系数。通过堵车系数，可以最大程度地衡量旅游路线的优化程度。

2 算法设计与实现

2.1 拥堵数据分析

为了确定最优的堵车系数，笔者结合网上数据抽样调研景区路线的拥堵情况，调查范围主要包括北京城六区，得出了北京交通通畅程度最差的7片区域[3]，如图1所示，分别为：（1）环故宫区域，包括前门、天安门、故宫、什刹海、西单、王府井等，记为区域A；（2）双井、劲松、南磨房、王四营等地区，记为区域B；（3）亚运村地区、北苑、天通苑等地区，记为区域C；（4）中关村地区，以及五环外的回龙观地区，记为区域D；（5）香山、植物园等地区，记为区域E；（6）黄村地区，记为区域F；（7）通州区，记为区域G。

区域A的拥堵主要是由于古典名胜的存在导致大量外来游客的涌入，人流过多导致交通不畅通。区域B的拥堵是由于住宅区和商业区的集中造成。区域C和区域D主要是由于高新技术IT产业和房地产商的不断扩张导致人流过于集中。区域E交通拥堵的主要原因是城区老化所致。区域F和区域G则由于交通工具数量较少不方便，导致行车不畅。

2.2 堵车系数区间

根据北京交通发展研究中心发布的北京交通拥堵指数，笔者给出了堵车系数设置区间，如表1所示。

通过上述分析，该求解方案的堵车系数设置如下：

2.3 实例求解

笔者以古韵京城精品旅游线路为实例，其景点及编号：1——八达岭长城、2——故宫、3——天坛、4——颐和园、5——明十三陵、6——周口店北京人遗址、7——王府井、8——天安门、9——雍和宫、10——恭王府，对应距离矩阵如表2所示。

上述景点对应的堵车类别及堵车系数如表3所示。

由表2和表3中数据计算得到的堵车系数矩阵和距离权矩阵分别为：

程序运行结果：用改进的遗传算法求得的最优旅行路径为（1，4，9，10，2，7，8，3，6，5）；总距离为287 km；以市内平均时速50km/h为标准，同时加入堵车时间，求得路程所用最短时间为6.405 h；算法迭代时间为1.02 s。程序运行结果界面如图2所示。

2.4 性能分析

该文对算法的改进，最重要的是针对北京市交通特点，给出了合理的堵车参数，通过节省时间来综合求解旅游线路的最优方案。笔者以实例古韵京城精品旅游线路为例，对比加入堵车参数和未加入堵车参数的遗传算法求解结果，如表4所示。

从上述结果中，我们可以看出，加入堵车参数之后，求得的最优路径不一定是该线路的最短旅游路径，但是所用时间却最短，这更适合北京城区的旅游线路优化。

3 结语

利用遗传算法求解北京城区旅游景点优化问题，为北京市内旅游提供相应的优化方案和理论依据，对推动北京市旅游业发展具有十分重要的意义。本文将路径优化问题映射为数学研究中的旅行商问题，通过改进算法对其求解，可以提供一种旅游线路的最优方案。希望该文介绍的方法为提升旅游出行提供有益参考。

参考文献

[1] 王化宇.最小生成树算法及其应用[J].内蒙古科技与经济，2011（6）：72-73.

[2] 惠燕，潘煜.骑士游历问题算法的研究[J].电子设计工程，2011，19（11）：112-114.

[3] 高晓路，季珏，张文忠.北京市交通出行环境的空间评价[J].地理科学，2009，29（6）：817-824.