基于蚁群算法的农村公共交通线路研究

刘合伟，罗璟

（650504 云南省 昆明市 昆明理工大学 机电工程学院）

随着社会经济的不断发展，道路交通相关问题成为广大学者的研究热点。研究城市交通的相关学术文献不断增多，学术成果不断被应用。相比而言，农村交通方面的研究明显不足。目前，农村交通方面的文献大多是交通安全方面的，对于农村交通的研究广度不够。随着近年来我国农村的不断发展与新农村改造建设不断推进，农村生活在各方面朝着城市靠近。一个地方良好的社会经济状况往往可以从交通方面体现。城市经过多年建设与发展，交通等各方面得以完善，人们出行更加便捷。农村发展相对滞后，交通落后于城市。随着近几年新农村建设，农村的变化日新月异。由于农村的经济情况与私人交通工具的限制，人们的出行远没有城市方便，农村对公共交通的需求更加迫切，农村公共交通建设的线路规划与研究是一个亟待探讨的课题。

农村公共交通线路的规划与研究远没有城市相关的研究充分，对城市公共交通相关的线路研究与农村独特的环境背景相结合进行农村公共交通线路的研究也许会取得不错的成果。对于交通线路路径与线路的相关理论方法有广度优先算法、狄克斯特拉算法、蚁群算法等，这些算法在相关研究上都取得了不错的成果。潘星[1]对层次策略和广度优先算法进行改进，使其更加贴合多模式公共交通路径的研究；
狄克斯特拉算法在路径相关的研究，如AGV 路径研究、最短线路问题研究等都取得相关成果[2-3]。而蚁群算法在路径与线路相关的问题上，由于其智能性，使得其研究更加广泛。例如物流配送路径的优化研究上[4-5]，车间物料配送路径上[6]，还有交通线路相关的问题上[7-8]等等。上述路径相关的算法及其改进使得对于路径与线路相关的问题得以解决。

公共交通线路问题是一个复杂的非线性的规划问题，其求解需要将现代路径研究方法与计算机相结合。蚁群算法是模拟蚁群觅食机制的智能算法，因其在解决路径规划问题中具备的优异性能而被广泛应用[9-10]。但传统的蚁群算法由于正反馈、单一搜索能力等原因，容易陷入局部最优解、收敛速度慢等情况[11]，且相关问题由于其独特的环境背景使得传统的蚁群算法不能完全适应。本文在结合农村公共交通建设相关的环境背景下，对传统的蚁群算法进行改进，使其能对农村公共交通线路的研究进行更好的匹配。

蚁群算法（AG）是一种模拟蚂蚁觅食行为的模拟优化算法，它是由意大利学者Dorigo 等于1991 年首先提出，并首先使用在解决TSP（旅行商问题）上[12]。经过多年的发展，其已经陆续渗透到其他领域中，比如图着色问题[13-14]、集成电路问题[15-16]、通讯网络中的问题[17]等。其算法基本流程如图1 所示。

图1 蚁群算法流程图Fig.1 Flow chart of ant colony algorithm

在蚁群算法中常用参数：蚂蚁数量m，信息素常量Q，迭代次数t，信息素因子α，启发函数因子，β，信息素挥发因子ρ。

在图1 中需要计算状态概率，以选择下一节点，计算状态概率公式一般为：

图1 中信息素浓度更新为

式中：τij（t+1）——第t+1 次迭代后i 到j 节点上的信息素量；
（1-ρ）——信息素残留系数。

式中：Lk——第k 只蚂蚁一次循环的总路径，当迭代次数达到要求迭代次数时停止，输出最终最优解。

2.1 问题描述

由于交通线路的复杂性，将开通农村公共交通线路问题在图上用相应的节点及线段表示，构建一个简单的图用以说明，如图2 所示。

图2 农村线路模拟图Fig.2 Rural route mimic map

图2 中，A 为公共交通起始点，B、C、D、E、F 为村庄，G 为终点。车辆需从A 经过多个村庄到达终点G。线段上数字为各节点之间距离，节点上字母后面数字为该村庄人流量单位数。一般公共交通线路其需要遵守线路覆盖主要客流走廊的原则，线路长度适中原则。由于农村的特殊环境背景，使得建筑与人流量不像城市那么密集，通常以一个村庄为聚集点，在同等距离的情况下，人口多的村庄应比人口少的村庄优先选择。由于线路需要遵守长度适中原则，在线路长度保证一定大于最高要求标准线路时，线路长度越短越好。即要使得从A 到G 线路长度最短，且尽量经过人口多的村庄。本文假设从A 到G 的任意路径其长度都大于最高要求线路长度标准。

2.2 改进蚁群算法求解

由于线路的研究涉及距离与客流量，单纯的蚁群算法求最短路径不能够完全满足公共交通线路需遵守的原则，应在求最短路径时加入客流量这个变量，即要满足路径较短的情况下经过客流量尽量大的地区。由于路径与流量是2 个不同的变量，将人口流量与路径长度相关联，使其转化为可以比较的变量。例如可以假设20 个单位的人口流量为1 个单位的长度，40 个单位的人口流量为2 个单位长度等，人口越多其长度越大，在此称其为流量长度。再将路径长度与流量长度按照不同的权重来进行路线的规划。优化后的目标函数为

式中：H——从起始节点到目标节点所经过的路径总数；
dij——端点i，j 之间的路径长度；
gij——i，j 两点间的流量长度；
h——两端所连接节点之间最短路径；
μ和v——路径长度和流量长度的权重系数，其满足关系μ+v=1。

传统蚁群算法在解决TSP（旅行商问题）上通常以路径长度最短为最优目标，本文所提农村公共交通路径的优化其以路径与人口流量关联后的最小值为目标，其目标值如式（4）所示。为了使蚁群算法能够按既定的目标进行优化搜索，需要根据优化后的目标值对信息启发因子的计算方法进行改进，其计算方法改进后如式（5）所示：

另外，在一般蚁群算法中，挥发因子ρ的取值对信息素浓度的大小有十分重大的影响。在信息素浓度更新过程中，若挥发因子ρ的取值过大，将导致还未被选取过的路径上的信息素浓度快速减小到0，容易导致较优路径被排除，这样就较大程度地限制了蚁群算法的全局搜索能力；
若挥发因子ρ的取值过小，将会使得各路径上信息素含量差别较小，导致算法的收敛速度降低[5]。因此，本文在蚁群算法迭代计算过程中动态调整挥发因子大小，使其尽量减小挥发因子过大或者过小造成的问题。在对信息素浓度进行动态改进后，其更新方法如式（6）、式（7）：

在式（6）与式（7）中，φ（t）为关于迭代次数t 的正比例函数，φ（t）的值伴随着迭代次数t 的增加而增加。

2.3 最优路径MATLAB 实现

对于农村公交线路问题的模拟图2 进行求解，在只考虑路径的情况下，排除人流量的影响后，对图2 进行蚁群算法求解。使用MATLAB 进行程序运行后，可以得到最优路径为A-B-E-G，或者A-D-E-G，或者A-D-F-G，这3条路径其长度相同，总路径为25 个单位。在进行蚁群算法的多次迭代后可以得到迭代次数与目标值的迭代关系图，如图3 所示。

图3 蚁群算法迭代图Fig.3 Ant colony algorithm iteration graph

从图3 可以看到目标值随迭代次数的变化情况，最后目标值稳定在25。

在考虑人流量后，将人流量参数加入蚁群算法求解。根据实际情况将人口流量转化为流量长度，再根据式（4）—式（7）对原蚁群算法进行优化。根据对路径长度与流量的重视程度，可以分别对这2 个变量进行权重赋值。本文假设路径与人口流量的权重分别为0.8 与0.2。在通过计算后，将得到的参数与值代入蚂蚁算法中，然后在MATLAB 上对路径进行求解，可以得到最优路径为A-D-E-G。在进行蚁群算法的多次迭代后，可以得到迭代次数与目标值的迭代关系图，如图4 所示。

图4 引入人流量的蚁群算法迭代图Fig.4 Ant colony algorithm iterative diagram introducing human traffic

从图4 中可以看到，在引入流量路径后，其目标值稳定在19 个单位。在加入人口流量优化后的蚁群算法后，其与优化前相比，其最优路径从3条变为1 条。将优化后的路径A-D-E-G 与优化前的路径A-B-E-G 和A-D-F-G 进行对比可以发现，尽管这3 条路径其长度一样，但优化后求得的路径A-D-E-G 其经过的节点人流明显高于另外2 条。从以上分析中可以看出，在传统蚁群算法中引入人流参数可以在某种程度上对线路的规划研究发挥一定的作用。

本文以一简单网图模拟农村公共交通线路为例，针对公共交通线路需遵守的人流量原则，在原蚁群算法的基础上引入人流量参数对农村公共交通线路进行研究。从中可以看到，在结合人流量后，最优路径发生改变，说明引入人流量的蚁群算法对于农村公共交通线路的研究非常必要。然而由于农村公共交通的建设涉及多线路、多班次，以及人口流量的复杂化等问题，如何合理地将多线路、多班次及人口流量相结合以对农村公共交通问题进行优化，仍有待进一步研究。

猜你喜欢 蚁群人流量公共交通 游戏社会：狼、猞猁和蚁群现代装饰(2020年8期)2020-08-24自动门人流量检测系统设计科学与信息化(2020年18期)2020-08-03蚂蚁：比人类更有组织性的动物创新作文(3-4年级)(2019年5期)2019-11-22复杂复印机故障信号的检测与提取现代电子技术(2018年22期)2018-11-13提高高职院校图书馆现刊阅览室人流量的策略研究文理导航(2018年9期)2018-08-16基于NB-IOT技术的公共交通显示牌设计智能城市(2018年7期)2018-07-10在未来，我们不需要路大科技·百科新说(2018年2期)2018-03-19三级客运汽车站服务能力影响因素分析现代经济信息(2016年34期)2017-08-12基于计算实验的公共交通需求预测方法自动化学报(2017年1期)2017-03-11公共交通一卡通TSM平台研究中国交通信息化(2016年3期)2016-06-05

推荐访问:算法 农村 交通线路