城市公交线路的布设受到诸多影响因素的作用,单纯的追求线路单一指标的"最优"在实际公交线路优化时往往难以取得满意的效果。首先针对传统公交线路优化算法在求解线路优化问题中存在的不足,基于蚁群优化算法的寻优特性,结合Dijkstra算法在局部路径寻优中的优点,提出了Dijkstra蚁群混合优化算法。其次对于线路优化所得到的可行备选方案集,基于分层聚类主成分分析评价法进行优化效能评价。最后以合肥市一环内公交线路优化为实例进行验证。结果表明, 本文提出的方法在兼顾客流密度最大、出行路径最短的同时给出了有效公交线路备选方案,优化结果也符合合肥市的实际情况。同时,该方法对我国大中城市公交线网优化问题的研究具有一定的借鉴意义。
The city bus line layout is influenced by many factors. The simple pursuit of the best single indicator line in the actual bus route optimization is often difficult to obtain satisfactory results. Due to shortcoming of traditional bus route optimization algorithm for solving optimization problems that exist in the line, the paper analyzes the ant colony optimization algorithm optimization features. Combined with the advantages of the local path Dijkstra algorithm optimization, Dijkstra hybrid ant colony optimization algorithm is proposed. Secondly, for the optimization of the resulting line, a hierarchical clustering method of principal component analysis and evaluation to optimize the performance evaluation is proposed. Finally, the case study of bus lines optimization in Hefei is proposed as an example to verify the proposed algorithm. The results show that the proposed algorithm could take into account traffic density and maximum travel the shortest path, and gives an effective alternative. The optimization results are consistent with the actual situation in Hefei. The achievement of this paper has practical and realistic significance to the large urban public transportation network optimization in China.
[1] Mandl C E. Evaluation and optimization of urban public transportation networks[J]. European Journal of Operational Research, 1980,5(6):396-404.
[2] Szeto W Y, Wu Yongzhong. A simultaneous bus route design and frequency setting problem for Tin Shui Wai, Hong Kong[J]. European Journal of Operational Research, 2011, 209(2):141-155.
[3] Biellia M, Caramiab M, Carotenuto P. Genetic algorithms in bus network optimization[J]. Transportation Research Part C: Emerging Technologies, 2002, 10(1):19-34.
[4] 高明霞. 基于双层规划的交通疏散中车辆出发与交通控制综合优化[J].中国管理科学, 2014,22(12):65-71.
[5] 葛显龙, 许茂增, 王伟鑫. 多车型车辆路径问题的量子遗传算法研究[J].中国管理科学, 2013,21(1):125-133.
[6] Nikoli? M, Teodorovi? D. Transit network design by Bee Colony Optimization[J]. Expert Systems with Applications, 2013,40(15):5945-5955.
[7] MirHassani S A, Abolghasemi N. A particle swarm optimization algorithm for open vehicle routing problem[J]. Expert Systems with Applications, 2011,38(9):11547-11551.
[8] Yu Bin, Yang Zhongzhen, Jin Penghuan, et al. Transit route network design-maximizing direct and transfer demand density[J]. Transportation Research Part C: Emerging Technologies, 2012, 22:58-75.
[9] 唐炉亮, 常晓猛,李清泉,等.基于蚁群优化算法与出租车GPS 数据的公众出行路径优化[J].中国公路学报, 2011,24(2):89-95.
[10] 李志威, 张旭梅. 基于动态扫描和蚂蚁算法的物流配送网络优化研究[J].管理工程学报, 2006, 20(4):9-12.
[11] 曹庆奎, 赵斐. 基于遗传蚁群算法的港口集卡路径优化[J].系统工程理论与实践,2013,33(7):1820-1828.
[12] 刘心报, 叶强,刘林,等. 分支蚁群动态扰动算法求解TSP问题[J].中国管理科学,2005,13(6):57-63.
[13] 马溪骏, 凌海峰,刘业政,等. 基于蚁群算法的群体用户兴趣导航路径发现[J].中国管理科学,2006,14(3):56-59.
[14] 刘志硕, 申金升, 关伟. 车辆路径问题的混合蚁群算法设计与实现[J].管理科学学报, 2007,10(3):15-22.
[15] 王佳, 符卓. 综合客运枢纽接运公交线路优化设计[J].系统工程,2012,30(5):101-106.
[16] 郭孜政, 姜梅. 点-域匹配的公交主干线网规划方法[J].交通运输工程学报,2008, 8(6): 77-81.
[17] 吴庆洪, 张纪会, 徐心和. 具有变异特征的蚁群算法[J].计算机研究与发展, 1999, 36(10):1240-1245.
[18] 吴斌, 史忠植. 一种基于蚁群算法的TSP问题分段求解算法[J].计算机学报, 2001,24(12): 1328-1333.
[19] 马溪骏,潘若愚,杨善林.基于信息素递减的蚁群算法[J].系统仿真学报.2006,18(11):3297-3300.
[20] 马溪骏,贺尔蓉,潘若愚.基于主成分聚类的我国沿海钢铁产业基地布局研究[J].经济问题探索, 2011,7:58-62.