一种改进蚁群算法的区域景点单程路线多目标规划方法

摘要

本发明实施例公开了一种改进蚁群算法的区域景点单程路线多目标规划方法，其特征在于使用基于移动损失的蚁群算法对区域旅游路线进行优化，得到多条从出发点到目标点的旅游路线，其步骤为：(1)收集区域景点数据；(2)区域内设置一个出发点和目标点，并设置算法的相关参数；(3)对旅游路线的三个优化目标进行数学建模；(4)使用基于移动损失的蚁群算法进行迭代优化，得到Pareto解。本发明的优点在于快速得到多条旅游路线，省去游客选择景点和路线规划的时间；三个优化目标满足不同游客的需要；使用移动损失改善算法的优化效果。

说明书

技术领域

本发明涉及进化优化领域，涉及一种基于移动损失的蚁群算法的区域旅游景点单程路线多目标优化方法，该方法针对旅游业，从多个角度出发，为自驾游的游客规划旅游路线。

背景技术

随着社会生产力的提高，人们有更多的精力用于休闲娱乐。目前，自驾游成为众多人们休闲、度假的一种主要方式。然而，在自驾游的过程中，游客经常会遇到两个难题，一是如何在出发点和目标点之间选择自己喜欢的旅游景点，二是如何规划旅游路线才能更加经济和快捷。解决以上这两个问题已经是一个值得旅游业研究的方向。

目前许多旅游服务产品多是采用基于协调过滤的推荐算法，为游客推荐旅游景点，但是这个技术的缺点是推荐的是单个景点而非一整条旅游路线，推荐的景点也缺乏一种方向性，即没有出发点到目标点的方向性，游客常常在选择旅游景点时还要边考虑如何做路线的规划，因此该技术具有一定的不便利性。

蚂蚁算法是一种经常用来做路径规划的进化算法，但是在给游客推荐旅游路线的问题中，蚂蚁从出发点出发，最后到达目标点，蚂蚁应该具有从出发点向目标点移动的趋势，否则如果区域内的景点多，蚂蚁算法的收敛速度会慢，最后的性能效果也会不理想，因此需要对传统的蚁群算法做改进。

发明内容

本发明实施例所要解决的技术问题在于，提供一种基于移动损失的蚁群算法的单程旅游路线多目标优化方法。可针对旅游业，从多个角度出发，为自驾游的游客规划旅游路线。

为了解决上述技术问题，本发明实施例提供了一种基于移动损失的蚁群算法的区域旅游景点单程路线多目标优化方法，其特征在于，包括以下步骤：

S1：收集目标区域的旅游景点数据；

S2：在所述目标区域内设置一个目标点、优化权重、旅行时间、景点类型喜好，并设置蚁群数量和迭代轮数；

S3：确立旅游路线的目标费用函数f

S4：利用基于移动损失的蚂蚁算法来求解该优化问题，得到一组帕累托最优解。

其中，所述步骤S3包括以下步骤：

S31：建立旅游路线的优化目标费用函数：

上式中n表示路线中包含的景点个数，p

S32：建立旅游路线的优化目标满意度函数：

上式中s

S33：建立目标行程函数：f

S34：将三个目标函数f

min[f

maxf

s.t.

上式表示模型要最小化路线的费用和行程，最大化路线的满意度，tw

其中，所述步骤S4包括以下步骤：

S41：以节点0表示出发点，节点1到N分别表示N个景点，节点N+1表示目标点，根据节点的经纬度信息计算邻接矩阵d(i,j)，公式如下：

d(i,j)＝R*arccos(cos(Y(i))*cos(Y(j))*cos(X(i)-X(j))+sin(Y(i))

*sin(Y(j)))

上式中d(i,j)表示节点i到节点j的距离，X(i)表示节点i的经度，Y(i)表示节点i的纬度，R是地球半径；

S42：根据所述邻接矩阵计算节点的移动损失，公式如下：

Δd(i,j)＝d(i,N+1)-d(i,j)-d(j,N+1)

上式中Δd(i,j)表示节点i到节点j的移动损失；

S43：根据所述移动损失计算路径L(i，j)的接受概率PA(i，j)，公式如下：

PA(i，j)＝exp(Δd(i，j)/30)

S44：初始化路径信息素，所有路径L(i,j)上的信息素τ(i,j)均为1；初始化精英蚁群，此时精英蚁群中的蚂蚁数量为0；初始化路径启发信息η(i,j)，公式如下：

S45：初始化蚁群数量为50的蚁群；将蚂蚁都放置在节点0，即出发点；初始化所有蚂蚁的禁忌表，禁忌表为一个长度为N+1的向量，向量中元素的编号从0开始记，即0到N，元素编号对应节点的编号，禁忌表的元素为0或1，0表示对应编号的节点不可选，1表示可选，初始化禁忌表时，编号为0的元素为0，其他元素均为1；

S46：蚂蚁在转移到另一个节点前都需要计算一次路径选择概率PS(i,j)，计算公式如下：

上式中PS(i，j)表示路径L(i,j)被选择的概率；τ(i,j)表示路径L(i，j)上的信息素；η(i,j)表示路径L(i,j)上的启发信息；pathable(j)表示禁忌表的第j个元素；α是信息素重要因子；β是启发信息重要因子；

S47：根据所述接受概率、路径选择概率再计算路径转移概率P(i，j)，公式如下：

S48：蚂蚁根据所述路径转移概率，从当前节点转移到另外一个节点，记录下一个节点的编号，并将对应编号的禁忌表元素置为0；

S49：蚂蚁每移动到另一个节点都检测当前花费时间是否超过旅行时间，如果未超过，则重复步骤S46至S48；如果超过，蚂蚁移动到节点N+1，完成一条旅游路线的生成；

S410：根据S46至S49的内容，完成蚁群中所有蚂蚁的移动；

S411：使用快速非支配排序法确定蚁群中所有蚂蚁的支配级；

S42：蚁群中支配级为1的蚂蚁加入精英蚁群，精英蚁群中去除旅游路线完全相同的蚂蚁，即去重，然后再进行一次快速非支配排序，精英蚁群中支配级为1的蚂蚁组成新的精英蚁群；

S413：精英蚁群中的蚂蚁参与路径信息素的更新；

S414：按设置好的迭代轮数重复步骤S45到S413若干次，最后得到的精英蚁群为帕累托最优解。

其中，所述步骤S413包括以下步骤：

S4131：对蚂蚁的费用f

上式中f′

S4132：对蚂蚁的满意度f

上式中f′

S4133：对蚂蚁的行程f

上式中f′

S4134：蚂蚁对路径信息素进行更新，更新公式如下：

上式中

实施本发明实施例，具有如下有益效果：1)直接生成旅游路线，既推荐了景点又作了路径规划；2)从费用，满意度和行程三个角度出发，满足不同游客要求；3)利用基于移动损失的蚁群算法进行优化，使蚂蚁具有从出发点向目标点移动的趋势，加快算法的收敛，改善最终的优化结果。

附图说明

图1是本发明的主流程图；

图2是步骤103的流程图；

图3是步骤104的流程图；

图4是步骤313的流程图；

图5是仿真实验中景点分布图；

图6是仿真实验中节点分布图；

图7是路线1描绘图；

图8是路线2描绘图；

图9是路线3描绘图；

图10是路线4描绘图；

图11是路线5描绘图；

图12是蚁群费用平均值随迭代轮数的变化曲线；

图13是蚁群满意度平均值随迭代轮数的变化曲线；

图14是蚁群行程平均值随迭代轮数的变化曲线；

图15是表1，是仿真实验中Pareto解的三个目标函数值；

图16是表2，是路线1中各景点的详细信息；

图17是表3，是路线2中各景点的详细信息；

图18是表4，是路线3中各景点的详细信息；

图19是表5，是路线4中各景点的详细信息；

图20是表6，是路线5中各景点的详细信息。

具体实施方式

为使本发明的目的、技术方案和优点更加清楚，下面将结合附图对本发明作进一步地详细描述。

如图1所示，

主流程图的步骤特征如下：

步骤101：收集某一个区域的旅游景点数据，数据属性包括景点的门票，经度，纬度，游览时间和类型；

步骤102：在区域内设置一个出发点和一个目标点，优化权重，旅行时间，景点类型喜好(可选且只影响旅游路线的满意度)；设置蚁群数量n_ant＝50和迭代轮数n_turn＝30；

步骤103：确立旅游路线的三个目标函数f

步骤104：利用基于移动损失的蚂蚁算法来求解该优化问题，得到一组Pareto最优解，其中每一个解是一条旅游路线，游客可以在其中选择一条作为自己的旅游路线。

如图2所示，

所述的步骤103，包括如下步骤：

步骤201：建立旅游路线的优化目标费用，它的目标函数f

上式中f

步骤202：建立旅游路线的优化目标满意度，它的目标函数f

上式中f

步骤203：建立旅游路线的优化目标行程，它的目标函数f

f

上式中f

步骤204：将三个目标函数f

min[f

maxf

s.t.

上式表示模型要最小化路线的费用和行程，最大化路线的满意度，tw

如图3所示，

所述的步骤104，包括如下步骤：

步骤301：区域内的景点、出发点和目标点统称为节点，节点0表示出发点，节点1到N分别表示N个景点，节点N+1表示目标点，根据节点的经纬度信息计算邻接矩阵d(i,j)，公式如下：

d(i,j)＝R*arccos(cos(Y(i))*cos(Y(j))*cos(X(i)-X(j))+sin(Y(i))

*sin(Y(j)))

上式中d(i,j)表示节点i到节点j的距离，X(i)表示节点i的经度，Y(i)表示节点i的纬度，R是地球半径，取R＝6371km；

步骤302：根据步骤301得到的邻接矩阵，计算节点的移动损失，公式如下：

Δd(i,j)＝d(i,N+1)-d(i,j)-d(j,N+1)

上式中Δd(i,j)表示节点i到节点j的的移动损失；

步骤303：根据步骤302得到的节点之间的移动损失，计算路径L(i,j)(节点i到节点j的线段)的接受概率PA(i,j)，公式如下：

PA(i,j)＝exp(Δd(i,j)/30)

步骤304：初始化路径信息素，所有路径L(i,j)上的信息素τ(i,j)均为1；初始化精英蚁群，此时精英蚁群中的蚂蚁数量为0；初始化路径启发信息η(i,j)，公式如下：

步骤305：初始化蚁群数量为50的蚁群；将蚂蚁都放置在节点0，即出发点；初始化所有蚂蚁的禁忌表，禁忌表为一个长度为N+1的向量，向量中元素的编号从0开始记，即0到N，元素编号对应节点的编号，禁忌表的元素为0或1，0表示对应编号的节点不可选，1表示可选，初始化禁忌表时，编号为0的元素为0，其他元素均为1；

步骤306：蚂蚁在转移到另一个节点前都需要计算一次路径选择概率PS(i,j)，计算公式如下：

上式中PS(i,j)表示路径L(i,j)被选择的概率；τ(i,j)表示路径L(i,j)上的信息素；η(i,j)表示路径L(i,j)上的启发信息；pathable(j)表示禁忌表的第j个元素；α是信息素重要因子，取α＝1；β是启发信息重要因子，取β＝1；

步骤307：根据步骤303和306得到的接受概率和选择概率，再计算路径转移概率P(i,j)，公式如下：

步骤308：蚂蚁根据步骤307得到的路径转移概率，从当前节点转移到另外一个节点，记录下一个节点的编号，并将对应编号的禁忌表元素置为0；

步骤309：蚂蚁每移动到另一个节点都检测当前花费时间是否超过旅行时间，如果未超过，则重复步骤306至308；如果超过，蚂蚁移动到节点N+1，即移动到目标点，完成一条旅游路线的生成；

步骤310：根据306至309的内容，完成蚁群中所有蚂蚁的移动；

步骤311：使用快速非支配排序法确定蚁群中所有蚂蚁的支配级；

步骤312：蚁群中支配级为1的蚂蚁加入精英蚁群，精英蚁群中去除旅游路线完全相同的蚂蚁，即去重，然后再进行一次快速非支配排序，精英蚁群中支配级为1的蚂蚁组成新的精英蚁群；

步骤313：精英蚁群中的蚂蚁参与路径信息素的更新；

步骤314：按设置好的迭代轮数重复步骤305到313共30次，最后得到的精英蚁群便是Pareto最优解。

如图4所示，

所述的步骤313中包括如下步骤：

步骤401：对蚂蚁的费用f

上式中f′

步骤402：对蚂蚁的满意度f

上式中f′

步骤403：对蚂蚁的行程f

上式中f′

步骤404：蚂蚁对路径信息素进行更新，更新公式如下：

上式中

本发明的效果可以通过仿真实验进一步说明

仿真条件

本实验是在Intel(R)Celeron(R)CPU N 3450 1.10GHz 7.83G内存Windows 10系统下，Jupyter Notebook运行平台上完成的。

仿真内容

按照步骤101收集广州与深圳之间的景点，共103个，景点数据的名称，门票，地址，评分，类型来自于去哪儿网站(https：//piao.qunar.com)，景点数据的经纬度由地址在百度地图上获取，景点数据的游玩时间是根据景点类型估算的，景点的位置如图5所示。

按照步骤102在区域内设置一个出发点和目标点，出发点为广州番禺区，目标点为深圳南山区，如图6所示，其中红点是出发点，黄点是目标点。设置三个优化权重为

再按照步骤103和步骤104进行迭代优化，得到Pareto最优解。

仿真结果和分析

得到的Pareto解共有5个，图7到图11描绘了各条路线。表1展示了各条路线的三个目标函数值，表2至表6分别展示各条路线中景点的详细信息，从图7至图11可见，规划出的路线是合理的；从表2至表6中的景点可见，路线中的景点大多是门票便宜评分高，类型也倾向于符合喜好。

图12至图14分别描绘了蚁群三个优化目标的平均值随迭代轮数的变化曲线，图12中费用平均值随着迭代轮数的增加呈下降趋势，图13中满意度平均值随迭代轮数的增加呈上升趋势，图14中行程平均值随迭代轮数的增加呈下降趋势，符合最小化费用和行程，最大化满意度的优化期望。

综上所述，本发明有效地优化了旅游路线的三个目标函数，可以应用于推荐旅游路线，节省游客选择景点和路线规划的时间。

以上所揭露的仅为本发明一种较佳实施例而已，当然不能以此来限定本发明之权利范围，因此依本发明权利要求所作的等同变化，仍属本发明所涵盖的范围。