基于蚁群算法的多约束动态旅游路线规划

Multi-Constraint Dynamic Tourism Route Planning Based on Ant Colony Algorithm

摘要: 现有的路线规划算法大多仅关注性能的改进，而常常忽略了多约束条件的影响，并且当前研究的约束条件往往比较固定，在动态多约束条件下进行路线评价和规划的研究十分必要。为顺应疫情放开后攀升的旅游需求，本文设计并实现基于蚁群算法的多约束条件下的旅游路线规划方案，立足于时间、费用两个固定约束条件和激励收入动态约束条件，探究变化的多约束条件对旅游路线规划的影响。该方案成功规划旅游产业集聚的长三角地区旅游路线，避免旅游路线相似和同质化问题，提供高质量游玩体验，促进长三角地区旅游业发展。

Abstract: Most of the existing path planning algorithms only focus on the improvement of performance, and often ignore the influence of multiple constraints, and the constraints of the current research are often relatively fixed, and it is necessary to conduct path evaluation and planning under dy-namic multi-constraint conditions. In order to meet the rising tourism demand after the epidemic liberalization, this paper designs and implements a tourism route planning scheme under dynamic constraints based on ant colony algorithm, based on the two fixed constraints of time and cost and the dynamic constraints of incentive income, and explores the impact of changing multiple constraints on tourism route planning. The plan successfully plans the tourism routes in the Yangtze River Delta region where the tourism industry is clustered, avoids the problem of similarity and homogeneity of tourist routes, provides high-quality play experience, and promotes the development of tourism in the Yangtze River Delta region.

1. 引言

随着国民生活水平的提高，我国旅游业热度攀升，2022年国内旅游总人次25.30亿，旅游收入2.04万亿元，疫情管控全面放开后，游客的出行需求旺盛，异地消费较去年同期增长76% [1] 。作为热门旅游地区的长三角，旅游产业集聚发展，具有良好的区域旅游环境承载力 [2] 。但游客往往存在费用、时间等多方面考虑，而大多旅游产品缺乏灵活的规划机制，存在路线相似、同质化严重等问题 [3] ，导致高峰期景区的拥挤和游客体验雷同。因此，旅游服务商需要结合游客需求和约束条件的变化，基于蚁群算法规划旅游路线，提供高质量的旅游服务，让游客在最佳游览时间内实现舒适度较高且花费较低的旅游体验，推进旅游产业的健康发展 [4] 。

本文立足于时间、费用两个固定约束条件，考虑旅游Vlog激励收入的动态约束条件，分析日视频收益和当天旅游城市客流量、粉丝数量之间的关系，实时放宽约束条件，在传统约束条件下旅游规划的研究基础上，探究约束条件不断变化时，蚁群算法在长三角地区旅游路线规划问题上的应用，设计一条满意度最佳的旅游路径。

2. 研究现状

国内外对全局路径规划的研究主要分为传统路径规划算法和智能仿生学路径规划算法两类 [5] 。

在传统路径规划算法领域，崔海洋等人 [6] 建立了一种动态分析模型，基于广度优先算法规划出港路径；汤伟等人 [7] 基于Dijkstra优化算法，建立自动机模型进行复杂大规模迷宫路径规划；葛文雅等人 [8] 优化A-Star算法 [9] ，进行高质量的移动机器人路径规划。

在智能仿生学路径规划领域，为优化蚁群算法的收敛速度和局部最优问题，马小陆等人 [10] 提出了一种基于万有引力搜索策略的蚁群算法 [11] ；任云晖等人 [12] 提出了基于配对双向新型蚁群算法的路径规划方法，在栅格环境下效果优越；为解决遗传算法效率低、局部搜索能力差等问题，谢冲冲等人 [13] 融合遗传算法和鲸鱼算法，提升了算法的优化准确率和收敛度。

旅游路径规划是基于经典组合优化的TSP问题(Traveling Saleman Problem)演化而来 [14] 。为实现更好的景点规划，黄腾 [15] 采用遗传算法对5A景区进行无约束条件下的旅游路线规划，然后运用蚁群算法进行有费用约束条件下的旅游路径规划。万慧云等人 [14] 基于时间最短、费用最少、路线最短、舒适度最高四个目标函数，运用蚁群算法对全国5A景区进行旅游路线规划和设计。汤可宗等人 [16] 提出了一种基于权重扰动机制的模拟退火遗传算法，针对景德镇陶瓷文化景区进行高精度、低时间复杂度的旅游路径规划。林晓玲等人 [17] 指出，现有的路径规划算法大多仅关注性能的改进，而常常忽略了多约束条件的影响，阐明了对多约束条件下进行路径评价和规划的研究十分必要。

3. 蚁群算法

3.1. 蚁群算法原理

TSP商旅问题规定只有单一的旅行者，从某一特定起点出发，经过所有给定的点后，最后仍然回到原点，得出最小的路径成本。常见算法有：暴力枚举法(解往往是多维的、多局部极值的、趋于无穷大的复杂解)、模拟退火算法以及蚁群算法等。

蚁群算法是一种应用于组合优化问题的启发式搜索算法和用来寻找优化路径的概率性算法，在解决离散组合优化方面具有良好的性能。作为仿自然体算法，每只蚂蚁在其经过的支路上都留下信息素，蚂蚁选择城市的概率与城市之间的距离和当前里连接支路上所包含的信息素余量有关。

蚁群算法的原理在于：蚂蚁在路径上释放信息素，碰到还没走过的路口，就随机挑选一条路走。同时，蚂蚁释放与路径长度有关的信息素，信息素浓度与路径长度成反比。后来的蚂蚁再次碰到该路口时，就选择信息素浓度较高的路径，从而达到路径长度越来越短的效果。当蚁群的数量达到一定程度时，可以得到最短路径的近似最优解。

3.2. 蚁群算法步骤

蚁群算法有两个基本过程：状态转移和信息素更新。步骤可总结为：

1) 对各个计算参数进行初始化；

2) 并随机在各个地点放上蚂蚁；

3) 蚂蚁自由选择地点；

4) 若有地点可选择，就再次进行步骤3)，直到没有地点可供选择，此时更新信息素表；

5) 计算叠加次数，如果叠加次数没有达到极限值，就重新进行步骤2)，直到叠加次数到达限制，此时得到蚁群算法的最优路径。

4. 数据收集与处理

城市景点分析与评估

本文以长三角地区为例，基于蚁群算法对地区内的旅游景点进行多约束条件下的旅游路线规划。

长三角地区地图如图1所示。在查阅长三角地区旅游景点的相关资料后，本文根据交通便利程度、城市景点数、景点知名度、景点花费等因素，对大量的数据进行了一定的分析和筛选，除出发城市杭州外，最终确定8个待选的游览城市以及其中的特色景点。待选城市及经纬度数据如表1所示。

Table 1. Selected city and latitude and longitude data table

表1. 待选城市及经纬度数据表

Figure 1. Map of the Yangtze River delta region

图1. 长三角地区地图

借助Matlab工具，画出各个城市经纬度相对坐标图，如图2所示。

城市及景点数据来源于多个平台：在中国旅游局官网、大众点评、美团和小红书四个平台上收集到了长三角旅游城市、各个城市的知名旅游景点、景点特色、游客满意度、游玩花费及周边住宿费用，在中国铁路12306网站上收集城市之间交通时间、费用，在腾讯地图、高德地图APP上收集景点和酒店之间的通勤方式、费用和时间。

Figure 2. Relative coordinates of latitude and longitude of each city

图2. 各个城市经纬度相对坐标图

记每个城市为一个节点，每组数据包含每个节点的城市名称、经纬度坐标、城市之间通勤时间和费用、2~4个热门游玩景点的相关信息、经济型和高档型的住宿费用、停留天数等。其中，热门游玩景点的相关信息包含景点名字、门票费用、逗留时间、客流量、满意度等数据。

城市景点客流量指数计算方法为当前城市客流量除以所有景点的最大客流量，将各个城市的著名景点客流总量进行标准化评估，标准化公式为：

$\partial =\frac{x_i-\min }{\max -\min }$

城市之间的通勤时间和费用如表2和表3所示。以南京为例，各热门景点部分数据如表4所示。考虑到哔哩哔哩平台播放收益，南京客流量和播放量之间的数据记录如表5所示。

Table 2. Commute time between cities data sheet

表2. 城市之间通勤时间数据表

Table 3. Data table of commuter costs between cities

表3. 城市之间通勤费用数据表

Table 4. Data table of popular attractions in Nanjing

表4. 南京热门景点数据表

Table 5. Nanjing video creation playback data table

表5. 南京视频创作播放量相关数据表

5. 模型建立

对收集到的数据进行预处理后，需要建立数学模型，并设立时间和费用的约束条件，然后通过编程实现蚁群算法来求得相对最优的解，规划出可行的旅游路线。

5.1. 模型假设

本模型作出如下假设：

1) 所给的每个城市可以全部参观，也可以参观其一，但是选定的城市的每个景点，都要进行参观，并且景点之间的通勤主要考虑乘坐公共交通工具进行费用和时间的计算，地铁的优先级高于公交车。旅游的步骤约束为：旅游者选择一个想要旅行的城市，再从公共交通站点依次前往所有的景点游玩，最后再从同样的公共交通站点前往下一个城市；

2) 交通费用和时间以及门票价格等保持稳定，不会随着时间的变化而上下波动；

3) 其中往返于各个旅游景点，其交通费用、在景点的花费、在景点的逗留时间根据互联网数据搜集取合理平均值等数据处理手段，经当地物价、客运部门及旅行社以及旅游当事人进行参照得出；

4) 假设在旅游过程中不会重复游历和走回头路，并且城市与城市之间只通过两个固定的交通站，即城市之间的通勤时间和费用不变；

5) 从杭州出发，在有限的时间或者费用内，时间约束为14天，费用约束为5000元，旅游者最终要返回杭州，并且从杭州所在地到达交通站点的相关影响因素不在路线规划考虑之内，模型选取的出发点为杭州东高铁站；

6) 旅游的总费用不仅包括饮食和住宿等相对固定的必需支出，还必须考虑交通费用和在景点游玩时的门票等额外消费；旅游的总时间则包括在城市与城市之间、景点与景点之间的通勤时间，游玩景点的时间，夜间休息及处理各种琐事的时间。假设旅游的路途和游玩时间只在白天的12个小时内进行，用餐、休息和购买特产以及处理其他琐事在另外12个小时内完成；

7) 一个城市(景点)到达下一个城市(景点)指的是，途中经过的其他所有城市(景点)都只是一个中转地，并不进行游览活动；

8) 假设除舟山(高铁和大巴的交通方式相结合)之外，全部通过高铁的方式从一个城市到另一个城市，通过地铁和公交结合的方式从一个景点到另一个景点；

9) 假设一个城市的满意度根据这个城市中游览的所有景点的客流量均值排名来评估；

10) 假设一位正常成年人在旅游途中一天的餐饮费和购买纪念品等零碎支出为100元。

11) 旅游者会在旅行过程中，同步在哔哩哔哩平台上每日发布旅游Vlog，收入实时补充为在旅行中的经济预算，费用约束不定量放宽。假设旅游者的粉丝数为52.5万，单个视频基础播放量为10万，收入仅限于视频激励收益。根据哔哩哔哩平台创作激励计划规则，视频激励收益是由稿件本身内容价值，包括用户喜爱度、内容流行度和内容垂直度等多维度指数综合计算得出，在每1万播放量收入30元的基础奖励上，综合播放量 + 点赞数 + 投币 + 收藏行为带来的流量变现。其中用户喜爱度是基于点赞等互动行为综合计算的，为收益计算的首要衡量指标。本文日收益与当天的具体旅游景点密切相关，并且报酬按日结算。具体计算方法为：根据城市景点客流量指数确定视频播放量指数，日收益为景点客流量指数、基础播放量、视频播放量指数和基础播放奖励的乘积。

5.2. 建立目标函数

在旅行过程中，规定旅行的范围为长三角地区。旅行者从指定起始城市杭州开始旅游行程，最终回到杭州。在数据的预处理阶段，根据搜集到的长三角地区各个景点的分布图和客流量图，考虑到旅行成本和时间问题，本文以城市为基本单位，在9个城市间进行路线的规划。

i，j：第i个或者第j个城市 $\left(i,j=1,2,\cdots ,9\right)$ ，分别表示杭州、上海、合肥、舟山、苏州、扬州、南京、无锡、嘉兴。 $t_i$ ：在第i个城市旅行的时间； $c_i$ ：在第i个城市所需要的总费用； $t_{ij}$ ：从第i个城市到第j个城市路途中需要的时间； $c_{ij}$ 从第i个城市到第j个城市所需要的交通费用； $r_{ij}=0$ 代表旅行者不直接从i城到j城， $r_{ij}=1$ 代表旅行者直接从i城到j城。在旅行过程中，目标为让旅行者满足约束下旅行更多的地方，所以可得目标函数：

$\max {\displaystyle \underset{i=1}{\overset{9}{\sum }}{\displaystyle \underset{j=1}{\overset{9}{\sum }}{r}_{ij}}}$

5.3. 约束条件分析

1) 0-1约束

由于旅行者最终要回到杭州，即整个旅游路线是环形的，每个景点作为环形上的一个点。对于每个点来说，只允许最多一条边进入，同样只允许最多一条边出来，并且只要有一条边进入就要有一条边出去。因此可得约束：

${\displaystyle \underset{i=1}{\sum }{r}_{ij}}={\displaystyle \underset{j=1}{\sum }{r}_{ij}}\le 1,\left(i,j=1,2,\cdots ,9\right)$

当 $i=1$ 时，因为杭州是出发点，所以： ${\displaystyle {\sum }_{j=1}{r}_{ij}}=1$ ；

当 $j=1$ 时，因为最终要回到杭州，所以： ${\displaystyle {\sum }_{i=1}{r}_{ij}}=1$ ；

同样，当 $i,j\ge 2$ 时，根据题意不可能出现 $r_{ij}=r_{ji}=1$ ，即不可能出现在两地间往返旅游，因为这样显然不满足游览景点尽量多的原则。因此可得约束：

$r_{ij}\times r_{ji}=0\left(i,j=1,2,\cdots ,9\right)$

2) 时间约束

旅游的总时间由2部分组成，分别为两个城市之间交通时间和在每个城市游玩的时间。因此本文定义：n旅行者旅游的城市数，t旅行者旅游的总时间， $t_1$ 旅行者交通的时间， $t_2$ 旅行者在城市游玩的时间。

旅游的总时间 = 交通的时间 + 游玩的时间，由于模型假设中规定白天12个小时用于路途和游玩，总时间约束为14天。所以，时间约束：

$t=t_1+t_2\le 12\times 14$

其中，

$t_1={\displaystyle \underset{i=1}{\overset{9}{\sum }}{\displaystyle \underset{j=1}{\overset{9}{\sum }}{r}_{ij}}}\times t_{ij}$ , $t_2=\frac{1}{2}{\displaystyle \underset{i=1}{\overset{9}{\sum }}{\displaystyle \underset{j=1}{\overset{9}{\sum }}{r}_{ij}}}\times \left(t_i+t_j\right)$

3) 动态经济约束

在模型定义中，先考虑旅行过程中的交通费用、住宿费和每日消费等这些固定消费，再考虑旅行者每日拍制视频带来的收益补贴，收益补贴是动态的，因此，总的经济约束也是动态的。

定义c为旅游总花费， $c_1$ 小李的交通总费用， $c_2$ 小李的旅游城市的花费。

交通住宿总花费：因为 $m_{ij}$ 表示从第i个城市到第j个城市所需的交通费用，而 $r_{ij}$ 是判断小李是否从第i个城市直接到第j个景点的0-1变量，因此得到交通总费用为：

$c_1={\displaystyle \underset{i=1}{\overset{9}{\sum }}{\displaystyle \underset{j=1}{\overset{9}{\sum }}{r}_{ij}}}\times c_{ij}$

旅游景点的花费：因为 $m_i$ 表示小李在i个城市的总消费， $r_{ij}$ 也可以表示出小李是否到达过第i个和第j个城市，而整个旅游路线又是一个环形，因此 ${\displaystyle \underset{i=1}{\sum }{\displaystyle \underset{j=1}{\sum }{r}_{ij}}}\times \left(m_i+m_j\right)$ 实际上将小李在所有城市的花费计

算了两遍，从而得到旅游城市的花费为：

$c_2=\frac{\text{1}}{\text{2}}{\displaystyle \underset{i=1}{\overset{9}{\sum }}{\displaystyle \underset{j=1}{\overset{9}{\sum }}{r}_{ij}}}\times \left(c_i+c_j\right)$

收益计算：旅行者利用新媒体技术在旅行过程中同时进行拍摄Vlog，在哔哩哔哩平台流量变现，从而实时补充在旅行中的经济预算，进一步影响旅行路径的规划。哔哩哔哩平台的流量转变报酬的比例与当天游览城市与博主的粉丝数量有关，旅行者的粉丝数达52.5万，只需考虑游览城市对播放量(以及投币、点赞收藏的)影响。

设旅行者在第i天的收入为 $e_i$ ，可知小李在开始旅行后至第d天的累积收入为

$c_d=-{\displaystyle \underset{i=1}{\overset{d}{\sum }}{e}_i}$

旅游总花费：通过上面得分析，我们可以计算得到旅行过程中得总消费约束为：

$c=c_1+c_2-c_d={\displaystyle \underset{i=1}{\sum }{\displaystyle \underset{j=1}{\sum }\left(r_{ij}\times c_{ij}\right)}}+\frac{1}{2}{\displaystyle \underset{i=1}{\sum }{\displaystyle \underset{j=1}{\sum }\left[r_{ij}\times \left(c_i+c_j\right)\right]}}-{\displaystyle \underset{i=1}{\overset{14}{\sum }}{e}_i}\le 5000$

综上所述，我们将目标函数和约束条件总结如下：

$\max {\displaystyle \underset{i=1}{\overset{9}{\sum }}{\displaystyle \underset{j=1}{\overset{9}{\sum }}{r}_{ij}}}$

s.t.

$c=c_1+c_2-c_d\le 5000$

$t=t_1+t_2\le 12\times 14$

$r_{ij}\times r_{ji}=0\left(i,j=1,2,\cdots ,9\right)$

${\displaystyle \underset{j=1}{\sum }{r}_{ij}}={\displaystyle \underset{i=1}{\sum }{r}_{ij}}=1;$

${\displaystyle \underset{i=1}{\sum }{r}_{ij}}={\displaystyle \underset{j=1}{\sum }{r}_{ij}}\le 1,\left(i,j=1,2,\cdots ,9\right)$

6. 模型求解分析

6.1. 动态约束下的模型求解

此问题与常规的TSP问题处理稍有不同，需要满足费用和时间两个约束，并且费用会在旅游的过程中放宽限制，还要保证旅游的地点尽可能多。本文使用Matlab按照约束和求解目标，编写改进的蚁群算法进行模型求解。

在求解蚁群算法前，我们需要先进行启发函数的构造，在一般的求解最短路径的旅行商问题中，启发函数构造为距离的倒数，随着技术的发展，人们旅行借助现代的交通工具，距离已经变得不那么重要，因此启发函数的设计也需要重新思考，根据约束和要求，评估在本次研究中的几个与以往的距离类似的因素以及其对旅行选择重要程度分别为：城市距离(0.1)、交通时间(0.3)、交通费用和消费收益(0.4)、城市客流指数(0.2)，综合四种因素构成综合启发函数，提高蚁群在决策中的效率。

改进型的蚁群算法求解步骤如下：

Step1：(初始化)蚁群规模Ant设置为20，蚁群规模适当的大于城市的数量可以加速信息素积累，更快求出最优解，但是也不能过多，过多会导致，迭代过程中，每条路上的信息素都很多，容易陷入局部解，影响求解结果；信息素重要程度 $\alpha$ ：影响信息素积累对蚁群搜寻的决策，设置为0.8；信息素衰减指数 $\rho$ ：表明迭代过程中信息素自然挥发的快慢，设置为0.2；启发式因子重要程度 $\beta$ ：启发函数是距离的倒数，该因子越大启发函数的影响也越大，设置为0.3，蚂蚁需要游览城市数n：根据我们选取的9个城市设置为9；迭代次数 $N_c$ ：初始先设置为800次，可以多次运行尝试合适的值；

Step2：开始迭代；

Step3：初始蚂蚁种群的位置，产生1 − n的随机数，并随机分配给每只蚂蚁，确定蚂蚁的初始位置，并保存到禁忌表中，保证蚂蚁不会再次访问这些城市；

Step4：根据 $p_{ij}^k\left(t\right)=\{\begin{array}{l}\frac{{\left[{\tau }_{ij}\left(t\right)\right]}^{\alpha }{\left[{\eta }_{ij}\right]}^{\beta }}{{{\displaystyle \sum }}_{k\in allowed}{\left[{\tau }_{ik}\left(t\right)\right]}^{\alpha }{\left[{\eta }_{ik}\right]}^{\beta }},j\in allowed\\ 0,\text{else}\end{array}$ 计算蚂蚁的转移概率，并产生随机的转移概率阈值，选择转移概率大于阈值的第一个城市进行转移；

Step5：更新蚂蚁走过路径的信息素，然后根据 ${\tau }_{ij}\left(t\right)=\left(1-\rho \right){\tau }_{ij}+{\displaystyle {\sum }_{k=1}^n\Delta {\tau }_{ij}^k}$ 更新全局信息素，为取得全局最优解，提高算法的求解效率我们在模型中使用蚁周系统计算信息素增量 $\Delta {\tau }_{ij}^k$ ，计算方式为：

$\Delta {\tau }_{ij}^k=\{\begin{array}{l}\frac{Q}{L_k},若蚂蚁k在本次周游中经过路径为l_{ij}\\ 0,否则\end{array}$

Step6：判断当前路线是否满足时间约束和动态经济约束，若不满足，将求解标志位置为“失败”；若满足，将求解标志位置为“成功”。记录地图信息素和蚁群分布状态，准备下一次迭代。

Step7：判断是否到达迭代次数。若到达了迭代次数，返回Step3结束；反之，根据求解标志位输出结果：求解标志位置为“失败”，输出最后迭代的路线，以及其对应的旅游时间和花费；求解标志位置为“成功”，输出求解的路线，以及其对应的最短旅游时间和花费。

6.2. 结果分析

对Matlab程序进行求解多次迭代后，如图3和图4所示，得到模型在实时更新过程中的迭代曲线图及旅游路线图。

通过图3中的迭代曲线，可以看出迭代次数达到约100次后，蚁群搜素的路径基本不变，说明达到了最优解。同时，对结果路径中城市包含的景点信息进行分析，这几座城市的景点美食较多，著名景点集中，能够在多约束条件下，优化旅行者的旅游体验。图4展示了旅行的求解路径结果：14356271，即杭州→嘉兴→上海→苏州→扬州→南京→合肥→杭州，旅游总时间：164个小时，164/12 = 13.67 < 14，满足时间约束；旅游总消费：4856.37 (城市花销) + 495 (交通费用) − 1170 (收益) = 4181.37 < 5000，满足经济约束。

Figure 3. Model iteration graph

图3. 模型迭代曲线图

图4. 旅游路线规划结果

7. 总结与展望

本文以传统路径规划算法、智能仿生学路径规划算法这两种全局路径规划算法的研究现状作为研究基础，阐明了旅游路径规划算法在多约束条件下的不足和研究的必要性，然后经过数据收集与处理、模型建立、模型求解分析三个步骤，实现基于蚁群算法的多约束条件下的动态旅游路线规划。模型建立和求解的过程中受到时间和费用两个条件的约束，同时还需要考虑旅游Vlog激励收入对费用约束的影响；模型求解的过程经过100次左右的迭代，达到稳定状态，得到最优解：杭州→嘉兴→上海→苏州→扬州→南京→合肥→杭州，总用时为164个小时，总费用为4181元，满足模型约束条件。该方法提供高质量和灵活性强的旅游规划服务，让游客在最佳游览时间内实现舒适度较高且花费较低的旅游体验，推进长三角地区旅游产业的健康发展，对其它地区也有一定的借鉴意义。

基金项目

浙江理工大学2021年高等教育科学研究课题、浙江省一流课程建设项目。

NOTES

^*通讯作者。