利用Floyd 算法优化设计旅游路线——以苏州市为例

赵 强，沈正平，史春云，叶 青

（1. 江苏师范大学地理测绘与城乡规划学院，江苏 徐州 221000；2. 闽江学院海洋学院，福建 福州 350000）

随着社会的发展，人们生活水平和经济能力不断提高，促使旅游需求不断增加。旅游活动属于消费活动，其目的是消遣、追求享受，因此应对旅行体验加以关注。交通成本是旅行成本中最具优化价值的成本因素之一，科学的路线规划可大大减少通行成本，从而提高旅行过程中的游行比，即游览过程成本与旅游全程成本之比[1]。近年来，关于旅游路线规划的研究热度持续攀升，分析知网中相关文献发现，针对旅游路线规划的研究自2006年开始逐渐兴起，并呈螺旋式上升、波浪式前进，2019年研究热度出现了高峰；新冠疫情的影响导致旅游活动热情减退，旅游路线的研究减少，但随着疫情在我国甚至世界范围内得到相应控制，对旅游活动的热情将会恢复，旅游需求会更加旺盛，因此关于旅游路线的研究必不可少。然而，利用科学模型对旅游路线进行规划的研究较少，在知网的相关文献中能将科学数理模型与研究主题相结合的文献寥寥无几，虽然部分旅游路线规划研究采用了Dijkstra算法或蚁群算法，但在实际案例应用中，其推演过程与结果有时并不理想[2-4]。因此，选择一个适合的、科学的数理模型并将其应用于实际案例中是旅游路线规划研究领域需要关注的重点。

1 Floyd算法及其推演过程

1.1 算法简介

路径规划的经典算法为Dijkstra 算法、Ford 算法、Floyd 算法和蚁群算法。Dijkstra 算法又称贪心算法，其不足在于无法解决负权边问题、规划过程不具有动态性和推演过程中路径结果不可回溯；蚁群算法则面临计算量大、推算时间长、演算过程不可回溯等问题；Ford算法可以解决负权边问题；Floyd算法不仅可解决负权边问题，而且推演过程具有动态性，可在推演过程中不断更新优化路径结果，且推算过程简便[5-6]。

Floyd 算法又称插点法，产生于20 世纪60 年代，2000年开始得到发展，并呈逐年攀升的态势，2017年是其研究发展的高峰。该算法常被应用于移动机器人路径规划、紧急疏散线路设计、轨道交通路网设计、物资配送等领域[7-11]。将Floyd 算法应用于旅游路线规划方面的研究较少，如杨柳[12]等以出发地为中心，在全国范围内划分分支线，再以省会为中心，在省内构建游览路线的哈密顿圈，即闭合的回路；但其研究尺度较宏观，不注重微观线路的优化设计，且线路边权值仅考虑空间距离，未考虑时间距离与经济距离。本文旨在利用Floyd 算法研究苏州市旅游路线规划，并从地理学角度对Floyd 算法的数据选取提出改进建议，即并非单纯指空间距离数据，而是空间、时间、经济综合计算的结果。

1.2 Floyd算法推演

1.2.1 插点更新路径推演

该算法的主要思想为：在起点到终点的路径中插入一个中转点，并计算从起点经中转点再到终点的路径距离；若该距离小于直接从起点到终点的距离，则以插入中转点的路径取代原本路径，从而达到更新优化路径的目的。具体演算步骤为：①确定从A点出发直接到达B点的路径，并计算路径距离，记为x；②在A、B 点之间插入C 点，确定从A 点出发经C 点再到B点的路径，并计算路径距离，记为y=a+b，a为A点到C 点的距离，b为C 点到B 点的距离；③若y＜x，则以新路径取代原本路径，并输出取代后的路径，若x＜y，则保留原本路径，并将该路径输出。

1.2.2 路径循环更新推演

在插点更新路径推演中，插入C点后，在该路径中A 点到C 点也构成了一条路径，因此同样可对A 点到C 点的路径进行更新优化，具体步骤为：①记录A点到C 点的路径距离a；②在A、C 点之间插入D 点，确定从A 点出发经D 点再到C 点的路径，并计算路径距离，记为w；③若w＜a，则以新路径取代原本路径，并输出取代后的路径，实现迭代更新，若a＜w，则保留原本路径并输出，路径优化结束（图1）。同理，C点到B点的路径也可利用该方法实现循环更新迭代。

图1 Floyd算法路径迭代优化图解

2 苏州市旅游路线优选方案

由于Floyd 算法采用的数据基础是单纯的空间距离，而在旅游线路规划过程中，所需考虑的因素不只是实际空间距离，若将空间距离数据直接套用Floyd算法，其规划的路径将不尽完善[13]。因此，需对算法中数据选取进行改进。数据计算公式为：

式中，Dij、Lij分别为i点到j点的路径边权值和实际路程距离，Dij越小表明路径花费的成本越小，路径越优；T为路程中花费的时间；C为路程中的费用。

2.1 景点间路径的确定

苏州是一座美丽的城市，自古便有“上有天堂、下有苏杭”的美誉，闻名前来旅游的游客络绎不绝。苏州市位于江苏省南部，与上海市接壤。丰厚的江南文化底蕴和独特的江南景观特征决定了苏州市适合旅游业发展。如今旅游业发展正是繁荣时期，利用科学的算法模型，在苏州市范围内进行旅游路线优化设计是有必要的。

苏州市旅游资源众多，据统计大小景点约有54个，但人们不可能游玩每个景点，只能选择较典型或具有代表性的景点进行游历，以了解这座城市并感受其中文化。因此，本文以苏州市范围内5A 级及以上景区为研究对象，利用Floyd 算法对其进行旅游路线规划设计，并对算法机制提出优化建议。本文对选取的5A级景区进行编号，即拙政园、留园、虎丘山风景名胜区、金鸡湖景区、太湖景区、同里古镇、周庄古镇、尚湖风景区依次为1～8，各景区区位分布见图2。

图2 苏州市5A景区分布图

驾车出行是目前旅游过程中较便捷的选择，因此本文定义出行方式为驾车通行。根据式（1）计算各景点之间两两通达的路径边权值，数据均依据驾车标准获取；并将所得数据记录到矩阵中。矩阵的行和列分别代表起点和终点，矩阵的行数和列数分别代表景点编号数[14]，如第三行第四列的数据代表从3 号景点出发到4 号景点的路径边权值，即从虎丘山风景名胜区出发到金鸡湖景区的路径边权值。本文选取了8 个景点研究对象，因此需设置一个8 点的矩阵来装载算法推演过程中所得出的路径边权值数据。

2.2 景点间路径距离更新迭代

由于在两个景点之间插入一个中转点后，通行所花费的实际距离、时间和费用都有可能发生变化，因此此时的路径边权值也可能发生变化，需要对矩阵进行更新迭代，即在插入中转点后得到新路径，根据公式推算新路径的路径边权值，若新的路径边权值比原值小，则将新数据取代矩阵中相应的旧数据；反之，则保留矩阵中的旧数据[15]。将各景点的路径边权值数据汇总整合到Floyd 矩阵，并不断进行更新优化迭代，其路径边权值矩阵结果见图3，其中∞表示两地之间无法直接通达，必须中转才可到达；0 表示两地之间通达距离为0，即未发生位移。

图3 路径边权值矩阵结果

2.3 最优方案选择

旅游路线规划的最终目标是形成哈密顿圈，即闭合回路。由于已得到更新迭代后的城市间路径边权值矩阵，只需科学选取和排列矩阵中的数据即可得出完整的路线规划。数据处理时应满足的原则为：①不选取对角线上的数据，矩阵对角线代表起点和终点相同，数据无意义；②选取的数据行数、列数各不相同，线路规划中每个地方只经历一次，不可能出现一个地方作为起点对应多个终点或终点对应多个起点的情况；③不可出现行数、列数互为相反的情况，该情况意味着在两地间往返，无法到达其他景点，而陷入死循环路径，这在旅行过程中是不现实的；④排列数据时，前一个数据的列数与后一个数据的行数应相同，旅游路线中的每个地方均是前一个地方的终点和后一个地方的起点，并以此不断循环往复进行。

Python 是一门应用场景广泛的编程语言，具有开源、灵活等特点，拥有庞大的第三方库，常被用于数据运算处理，在矩阵数据运算方面具有很大优势。利用Python 程序的第三方库可实现上述数据处理原则，将利用Floyd 算法处理好的矩阵数据导入程序的第三方库中，便可在程序内部自行实施运算并输出最终结果（具体路线和路径边权值）见表1。

表1 路径输出结果

根据结果选出边权值最小的路径，得到路线规划最优方案，即拙政园→留园→虎丘山风景名胜区→金鸡湖景区→同里古镇→周庄古镇→太湖景区→尚湖风景区→拙政园，全程路径边权值为382（图4）。

图4 最优路线哈密顿圈

3 结 语

Floyd 算法是经典的路径规划算法，部分学者将其应用于路径规划研究中，并提供了精确的编程代码，但缺少关于路径边权值矩阵数据的处理方法。

1）本文将Floyd 算法与旅游路线规划研究相结合，路线规划方案利用具体算法模型求得，因此结论具备一定的科学性和可行性。路线规划过程中得出的旅游路线是一个哈密顿圈，即闭合回路，旅游者可从任何方位进入该旅游区域开始其旅游行程，这为旅游活动带来了许多便利。

2）本文提出了优化路径边权值数据的思想。从地理学的角度来看，距离包括空间距离、时间距离和经济距离。随着科学技术和交通水平的提高，空间距离在人们出行中的限制力度大大减弱，人们出行时更加倾向于关注便捷程度，因此出行时人们更多的是考虑时间距离和经济距离的影响。传统Floyd 算法边权值数据只考虑空间距离，这在本文中得到了改进。该算法的优化不仅限于地理学旅游路线规划领域的研究，还可根据需要，对数据进行科学地调整，将其推广应用于其他领域的研究。

3）本文提供了路径边权值矩阵数据的处理方法。本文在前人研究的基础上提出了对边权值矩阵中数据进行选取和编排的规则方法，并应用于计算机自动化运算。目前自动化运算研究还不完全成熟，仍存在不足，如在处理边权值矩阵数据时，由于编程解释器生成的随机数是“伪随机数”而非“真随机数”，导致在利用该方法进行自动化运算时一次只能生成一条路径，要得出最佳路径只能人工计算其路径边权值，不能做到完全自动化。后续电子信息技术领域中编程解释器“随机数”机制的完善或编程运算的优化，可使解决该问题成为可能，这也是今后研究中努力突破的方向。