陆乾杰，陈志平，张林佳，王浩南，刘纯璐

(杭州电子科技大学卓越学院，浙江 杭州 310018)



基于蚁群算法多起点多终点社区公交路径规划

陆乾杰，陈志平，张林佳，王浩南，刘纯璐

(杭州电子科技大学卓越学院，浙江 杭州 310018)

摘要：为解决大型社区的“最后一公里”难问题，提出一种根据不同乘客需求来确定行车路线的社区公交系统方案.针对系统中多乘客在不同起点去往不同终点的现象，结合蚁群算法构建了一种多起点多终点问题的路径规划算法.算法通过引入事件触发机制，解决了节点的排序问题；通过将两节点间固定网络抽象成一条最短路径，缩小了解空间的规模；通过构建解空间树，把多起点多终点问题转换成单起点单终点问题集，很好地解决了蚁群信息素混淆的问题；最后运用蚁群算法的启发性在解空间树上寻优，获得最终路径.仿真算例表明，该算法效率只与请求数线性相关，与实际网络的规模不相关，因此能很好地融入到大型社区网络中.经社区实测，验证了该路径规划算法应用于社区公交系统的可行性，有望在现代化社区中推广应用.

关键词：最后一公里；多起点多终点；路径规划；蚁群算法

0引言

随着城市化建设的推进，居民区逐渐趋向聚合，大规模的社区不断产生，然而从社区到周边交通枢纽(地铁口、公交站点等)和消费中心(医院、超市等)的距离并没有缩短.交通枢纽或者消费中心到居住区往往还有很长一段路……