黄泽斌 林焕恒 王炯鹿 邓艾岚 罗柏瑞 林贵旭
摘 要：当今，大部分人们会选择旅游进行生活娱乐，而如何规划出更好的旅游路线，对提高旅游人群的出行体验有着极大的影响。通过对蚁群算法中启发式函数的改良，变异搜索操作和随机因子及时间窗约束策略的引入，优化蚁群算法对景区的搜索，使得规划出的旅游路线更贴合实际情况。仿真结果表明，该方法具有良好的实用性和有效性。
关键词：蚁群算法;时间窗约束;路线规划;旅游
中图分类号：TP18 文献标志码：A 文章编号：2095-2945（2019）29-0028-03
Abstract： Nowadays， most people will choose to travel to enjoy life and for entertainment， and how to plan a better tourism route has a great impact on improving the travel experience of tourists. Through the improvement of heuristic function in ant colony algorithm， as well as the introduction of mutation search operation and random factor and time window constraint strategy， the ant colony algorithm is optimized to search scenic spots， so that the planned tourism route is more in line with the actual situation. The simulation results show that the method has good practicability and effectiveness.
Keywords： ant colony algorithm; time window constraint; route planning; tourism
引言
如今，国内旅游业蓬勃发展，路线规划作为旅游中至关重要的一个环节，本质上是一个TSP问题。迄今为止，已出现诸多可解决此问题的算法，譬如：蚁群算法、遗传算法、禁忌搜索算法等[1]。
蚁群算法于1992年，由米兰理学院学者M.Dorigo首次提出，算法的突出优势有信息的正反馈、支持分布计算以及启发式搜索等[2]，该算法被广泛应用于TSP问题的求解，并取得良好的结果。
在旅游路线规划中，花费在路途上的时间及游客滞留在景点上的时间对规划有着极大的影响。我们通过加入时间窗的约束和定义启发函数，将启发函数与蚁群算法相结合，使求出的解更符合现实情况。
1 蚁群算法基本原理及模型
蚁群算法通过模拟自然界蚁群的觅食行为，根据蚂蚁在路段上所留下信息素的量来寻找食物源的最短路径，蚂蚁所选择的路段与该路段上信息素的量呈正相关关系，即路段上的信息素的量越多，则该路段被蚂蚁选择的可能性越大[3]。
2.2变异搜索操作和随机因子的引入
为解决在循环多次后，出现得到的较优解小于一开始的较优解，引入变异搜索操作，通过对部分路段的信息素量进行恰当变异，扩展搜索范围以避免算法陷入局部最优状态，本文通过使用2-Opt的方法实现。使用过程中，若出现下面的运算关系：
为此，我们引入随机因子：假设某个节点的下一次选择有4个节点，通过计算可得选择这4个位置节点的概率，依次为0.1、0.2、0.3、0.4，根据传统蚁群算法会选择概率为0.4的节点。但对随机因子进行改进后，使得在0～0.15的范围内自动选择第一点，在0.25～0.39范围内选择第三节点，这样在确保大部分蚂蚁依旧按照正常的路径行走的同时又能进行全局搜索，在这过程中能降低某些路段信息素数量过大对蚂蚁的导向作用，从而大大增加了找到全局最优解的可能性。
2.3 时间窗系数的引入
时间窗在众多路径规划问题中有着广泛的讨论[5]，尤其在商旅路径规划的研究中对诸多因素有影响[6]，例如游客不愿在路途上花费过多时间时，就对路途时间提出了高要求，进而影响整体路线的规划。因此通过在蚁群算法中引入时间窗系数，使得求出的解更符合现实情况。
在时间窗启发函数的设计中[7]，定义了以下变量：wij为时间窗系数，STi为滞留在i点的时间，Tij为i点到j点所需的时间，Tik为到达i点的时刻，[ETi，LTi]为到达i点可接受的时间窗;并设计了以下的时间窗约束条件：
其中，Nc为景点的集合，K为车辆的集合，同时设计了时间窗系数与相关变量的关系如下：
3 算法的实现
3.1 参数的选择
由上述可知，参数的大小对算法得到的解有很大的影响，因此在参数选择时，需确定不同参数对算法的影响，首先确定影响较大的参数，其次再确定影响较小的参数。通过参阅相关资料[8]，启发因子？琢，期望启发因子？茁，时间窗启发式因子？兹，信息素挥发系数？籽，会对算法有着很大的影响，蚂蚁数量m和信息素强度Q对算法的影响不大。文献[8]中详细讨论了各种参数，确定信息素的强度Q=100，挥发系数ρ=0.1，蚂蚁的数量m=15;启发因子？琢=1，期望启发因子？茁=5，时间窗启发式因子θ=4，迭代次数100。
3.2 仿真实验
用以上的模拟数据进行仿真实验，算法在MATLAB R2018b中编写，并于Windows10，8.00GB等配置下进行操作。在拟定的坐标系下选取了10个坐标作为模拟起点、终点及景点，并制定相关的时间窗数据，通过10次的模拟实验得出了相关的结果数据，如图表所示。
4 结束语
随着人们对旅游规划提出更高的要求，在改进的蚁群算法加入时间窗约束，使得旅游的安排更为人性化和个性化更为贴合实际。在未来的研究上，将不断的研究及改进算法，并与人工智能等新技术相结合，使算法的性能与解更为精确。
参考文献：
[1]黄于欣，蒋洪杰.基于改进蚁群算法的旅游景区路径规划[J].河南科学，2018，36（06）：823-829.
[2]汪越，王向前，刘敏.一种基于蚁群算法的带时间窗物流运输车辆路径优化方法[J].宿州学院学报，2018，33（10）：21-24+28.
[3]徐锋，杜军平.改进蚁群算法在旅游路线规划中的应用研究[J].计算机工程与应用，2009，45（23）：193-195+226.
[4]黄于欣，蒋洪杰.基于改进蚁群算法的旅游景区路径规划[J].河南科学，2018，36（06）：823-829.
[5]李鹏飞，沈最意.基于改进蚁群算法的水产品运输车路径优化策略[J].浙江海洋大学学报（自然科学版），2017，36（05）：451-457.
[6]胡俊桥.蚁群混合算法求解带时间窗车辆路径问题[D].西安科技大学，2017.
[7]辜勇，张列，李志远，等.基于GA-ACO的带时间窗车辆路径问题研究[J].物流技术，2019，38（02）：53-60.
[8]牛悦诚.基于蚁群算法的智慧旅游路线规划研究[D].南京邮电大学，2017.
