基于遗传混合蚁群算法的公共自行车调度研究

PDF(1394 KB)

交通运输研究 ›› 2019, Vol. 5 ›› Issue (2) : 17-27.

专题

基于遗传混合蚁群算法的公共自行车调度研究

崔元洋,邢晓红,陈思尧,文凯,秦显辉,娄勃凯

作者信息 +

Public Bicycle Scheduling Based on Genetic Hybrid Ant Colony System Algorithm

CUI Yuan-yang, XING Xiao-hong, CHEN Si-yao, WEN Kai, QIN Xian-hui and LOU Bo-kai

Author information +

文章历史 +

摘要

为了提高公共自行车的使用效率和用户满意度水平，保证国内公共交通服务的合理运行与发展，根据公共自行车用车峰时和谷时的不同调度目标，建立两时期车辆调度模型。用车谷时以调度车路径最短为优化目标，用车峰时以用户满意度最高为优化目标。融合遗传算法（Genetic Algorithm, GA）和蚁群算法（Ant Colony System, ACS），形成遗传混合蚁群算法（Genetic Hybrid Ant Colony System Algorithm, GA-ACS），并将融合后的算法应用于调度模型中，以提升获得优化的车辆调度方案的求解速度和质量。群智能算法在不同数据集上的性能比较结果表明，与传统蚁群算法相比，遗传混合蚁群算法在求解速度和求解质量上都有更好的表现，在较短的时间内至少可以缩短10%的调度路程，因此该算法模型可以用于解决实际的公共自行车调度问题。

Abstract

To improve the service efficiency and customer satisfaction degree of public bicycle and ensure the rational operation and development of domestic public transportation services, two-stage bicycle scheduling model was established. The aim of this model was to get the shortest length of the bicycle carrier during valley period and to maximize customer satisfaction degree during peak period. GA(Genetic Algorithm) and ACS (Ant Colony System) were merged together, which was called Genetic Hybrid Ant Colony System Algorithm (GA-ACS). The merged algorithm was applied to the scheduling model to improve the solving speed and quality of bicycle scheduling solution. Through comparing the performance of different algorithms on different datasets, the results indicate that GA-ACS has better performance in solving speed and quality than ACS, and it shortens at least 10% of the scheduling distance in a short period. It is concluded that GA-ACS could be used to solve practical public bicycle scheduling problem.

导出引用

崔元洋,邢晓红,陈思尧,文凯,秦显辉,娄勃凯. 基于遗传混合蚁群算法的公共自行车调度研究[J]. 交通运输研究. 2019, 5(2): 17-27

CUI Yuan-yang, XING Xiao-hong, CHEN Si-yao, WEN Kai, QIN Xian-hui and LOU Bo-kai. Public Bicycle Scheduling Based on Genetic Hybrid Ant Colony System Algorithm[J]. Transport Research. 2019, 5(2): 17-27

参考文献

[1] ZUO X Q, CHEN C, TAN W, et al. Vehicle Scheduling of an Urban Bus Line via an Improved Multiobjective Genetic Algorithm[J]. IEEE Transactions on Intelligent Transportation Systems, 2014, 16(2): 1030-1041.
[2] GONG Y C, HUANG R G, YANG X R, et al. Improved Ant Colony Algorithm for Vehicle Scheduling Problems of Military Logistics Distribution[C]// 2010 International Conference on Logistics Systems and Intelligent Management. Harbin: IEEE, 2010: 669-673.
[3] MINOCHA B, TRIPATHI S, MOHAN C. Solving Vehicle Routing and Scheduling Problems Using Hybrid GeneticAlgorithm[C]// 2011 3rd International Conference on Electronics Computer Technology. Kanyakumari: IEEE, 2011.
[4] SHUI X G, ZUO X Q, CHEN C, et al. A Clonal Selection Algorithm for Urban Bus Vehicle Scheduling[J]. Applied Soft Computing, 2015, 36: 36-44.
[5] TARANTILIS C D, ZACHARIADIS E E, KIRANOUDIS C T. A Hybrid Metaheuristic Algorithm for the Integrated Vehicle Routing and Three-Dimensional Container-Loading Problem[J]. IEEE Transactions on Intelligent Transportation Systems, 2009, 10(2): 255-271.
[6] LI J P, KWAN R S K. A Fuzzy Genetic Algorithm for Driver Scheduling[J]. European Journal of Operational Research, 2003, 147(2): 334-344.
[7] STEINZEN I, BECKER M, SUHL L. A Hybrid Evolutionary Algorithm for the Vehicle and Crew Scheduling Problem in Public Transit[C]// 2007 IEEE Congress on Evolutionary Computation. Singapore: IEEE, 2007.
[8] JOZEFOWIEZ N, SEMET F, TALBI E G. An Evolutionary Algorithm for the Vehicle Routing Problem with Route Balancing[J]. European Journal of Operational Research, 2009, 195(3): 761-769.
[9] FAIZ T I, VOGIATZIS C, NOOR-E-ALAM M, et al. A Column G Algorithm for Vehicle Scheduling and Routing Problems[J]. Computers and Industrial Engineering, 2019, 130: 222-236.
[10] BOYER V, IBARRA-ROJAS O J, R1OS-SOLOLV Y A, et al. Vehicle and Crew Scheduling for Flexible Bus Transportation Systems[J]. Transportation Research Part B: Methodological, 2018, 112: 216-229.
[11] HE F, YANG J, LI M. Vehicle Scheduling under Stochastic Trip Times: An Approximate Dynamic Programming Approach[J]. Transportation Research Part C: Emerging Technologies, 2018, 96:144-159.
[12] KLIEWER N, MELLOULI T, SUHL L. A Time-Space Network Based Exact Optimization Model for Multi-Depot Bus Scheduling[J]. European Journal of Operational Research, 2006, 175(3): 1616-1627.
[13] 成先镜，吕亚楠，翁小勇，等. 基于两阶段调度策略下的公共自行车调度模型与优化方法[J]. 遵义师范学院学报，2018，20（1）：115-119.
[14] ZHENG L J, DONG D C, WANG D Y. A Hybrid Intelligent Algorithm for the Vehicle Scheduling Problems with Time Windows[C]// 17th IEEE International Conference on Intelligent Transportation Systems. Qingdao: IEEE, 2014.
[15] DORIGO M, GAMBARDELLA L M. Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem[J]. IEEE Transactions on Evolutionary Computation, 1997, 1(1): 53-66.
[16] 刘冉，戴冀峰，林建新，等. 城市公共自行车调度优化方法研究[J]. 交通工程，2017（2）：3-7，28.
[17] 武交峰. 应用遗传算法提高蚁群算法性能的研究[D]. 太原：太原理工大学，2007.