基于改进蚁群算法的通勤车智慧路线研究

魏雁天

（三门峡职业技术学院，河南三门峡 472000）

近年来，国家对职业教育支持力度的加大，较多城市建设了职教园区，但园区距离市区较远，原本居住在市区的教工们的日常通勤问题凸显，有效减少通勤车数量、降低不必要成本、提高通勤车服务质量和效率、减少教师出行时间，可以改善新园区的位置偏远给教师的工作和生活带来不便，降低通勤车接送成本，提高园区建设智能化。本文研究实际情况约束条件下的班车路线优化，以期获得最优通勤车路线方案。

1 方案分析

1.1 问题描述

通勤车路线规划：在某些时间段，通勤车经过停靠点，接载分布在相应站点的所有教师到职教园区；在另外一些时间段，通勤车负责将教师从职教园区送回相应的站点。

通勤车路线规划的智慧化程度决定了通勤车数量、运营次数、运营时间以及教师出行时间。

1.2 数据采集

选取三门峡市职教园区两所大学为例，搜集两所大学教工数据，整理成一张二维表，字段为本校教师的职工号、乘通勤车意愿和家庭住址，如表1所示。

表1 数据收集格式

在优化通勤车路线方案之前，设定一些通勤车运行规则：每辆通勤车的限载30人；以0.5 km标准作为教师从家出发抵达站点的距离，选停靠点接教师上通勤车；平衡站点的负载，舍弃一些明显距离较远的站点，将此站的教师合并到合适的停靠点，保证教师的正常出行时间；通勤车满时，直接开往职教园区，不再途经其他站点；尽量避开人流密集的地方，如大型百货量贩、需要家长接送孩子的幼儿园和小学门前的道路。

1.3 挑选候选停靠点

根据教师的家庭住址数据和道路数据筛选通勤车站点。由于教师家庭住址较为分散，放弃一些距离较远的，保证教师的正常上下班时间，设置0.5 km标准作为教师抵达站点的距离，并平衡好站点的密集程度，通勤车行驶路线上共设置30个停车点。

通过百度地图生成事先统计好的各个停靠点经纬度坐标，各个站点的距离相较于偌大的区块划分，距离很近导致在地图上各点的经纬度相近，为了更直观使用MATLAB的绘图功能显示仿真结果，对各个停靠点的经纬度进行处理。

去掉停靠点经度的整数部分，保留经度小数点后的3、4、5、6位，生成千位数字横坐标；去掉停靠点纬度的整数部分，保留纬度的小数点后的2、3、4、5位生成千位数字纵坐标。使用MATLAB编程前，将30个停靠点在百度地图上的经纬度坐标，使用上述方法加大坐标的辨识度，转换成如下标注（X，Y）坐标的数据，导入MATLAB，为通勤车路线方案优化提供基础数据。

通勤车路径上停靠点坐标如表2所示。

表2 通勤车路径上停靠点坐标

1.4 数学建模

在进行算法设计之前，需要针对通勤车路线优化进行数学建模，先期量化部分参数指标，设置ant为50个，通勤车停靠点的数量为30个，把前期能够确定的参数映射到蚁群算法中。

2 算法设计

2.1 改进的蚁群算法实现

基于改进的蚁群算法相较于基本蚁群算法的突出特征是，对蚁群的启发参数采用混合参数，即每只蚂蚁的启发参数均不同，以期更好地发挥蚁群算法的优势。

（1）在MATLAB中初始化已优化蚁群算法的参数，如设置ant的个数为50个，通勤车停靠点的数量为30个，每一只ant随机挑选30个停靠点中的任一地点作为出发地。

（2）使用迭代构建此次项目停靠点的次序，在这一项目中每个ant可随机选择一个停靠点作为其遍历所有车站的出发点，并时刻更新一张路径记忆列表，用以存放该ant当前时刻之前依次经过的停靠点，以免重复访问。ant在构建路径的每一步中，按照(t)值的大小选择下一个要到达的停靠点。(t)是在t时刻antk从通勤路线上的停靠点i移动到下一停靠点j的随机概率。

转移概率的Matlab的实现过程如图1所示。

图1 转移概率计算的Matlab的实现过程

（3）在循环内通过函数求解每只ant经过的所有停靠点之间的路径长度，在设置的变量里保存当前最短路径。

（4）每一轮过后更新路径上信息值，一轮过后本项目中的所有路径上的信息值通过程序设定都会相应自动减少，所有的ant根据自己构建的路径，在本轮经过的路径上释放信息增加该值。

（5）程序判断迭代次数，本项目中设定可迭代的次数是150次，通过循环变量计数，达到次数即认为达到终止条件，若满足条件，则转到下一步，反之重复。

（6）输出当前最优路径。

2.2 蚁群算法效果测试

根据针对蚁群算法运行参数的设定，借助MATLAB软件对教师通勤车路线进行仿真实试验，得到的串联两所高校的校通勤车优化路线。

设定职教园区2号站为校车的终到站，不设置通勤班车的出发点，根据提前设置好的交通规则和总路径长度最短的目的。

设置蚂蚁数量为50个，这样每次迭代都会产生50种不同的路径分配计划，程序设定一次迭代完成后，通过比较都会挑选出一个当前最优路径向量方案，通过程序设定增加该方案的信息值，以确保下一次迭代中，其他蚂蚁选择该路径走向方案的概率较高。并且还使用一定比例的蚂蚁采用随机分配策略来寻找更好的解决方案。

优化路线结果如图2所示。

图2 优化路线的结果

经过大约30次迭代后，出现了全局最优路径长度变化曲线，如图3所示。

图3 路径长度变化曲线

3 结语

选取三门峡市职教园区两所高校通勤车路线案例，使用百度地图转换停靠点的地理坐标，采用改进的蚁群算法结合MATLAB根据设置的交通规则和实际情况模拟真实的通勤车路线，进行最短路线计算，使用蚁群算法解决通勤车路线优化问题实用、高效。