基于蚂蚁算法的公交驾驶员调度问题研究
|
摘要
公共交通在城市交通中占据主体地位,而驾驶员调度问题则是公共交通系统运营管理中的一个重要的问题,直接影响到公交公司的运营成本和服务质量。在国外,已经有比较成熟的驾驶员调度软件系统,而国内公交系统的特殊性,使得国外的研究成果和应用技术很难直接套用。因此驾驶员调度问题正在得到越来越多的国内研究者的关注。另一方面,驾驶员调度问题本身还有一些问题没有得到很好的解决,比如时间窗问题、用餐时间问题等,值得进行进一步研究。
本文研究利用蚂蚁算法来解决公共交通中公共汽车驾驶员调度的问题。蚂蚁算法是一种带有正反馈机制的启发式算法,并具有贪婪的特性,在解决路径优化、调度排班这类利用传统数学规划方法很难解决的问题上具有很大的潜力。本文对驾驶员调度问题的数学模型进行了详细分析,根据驾驶员调度问题的特点和其特殊的约束,对蚂蚁算法做了改进,包括:将驾驶员调度特有的规则加入到算法当中,为可设置的参数;采用多只蚂蚁分工进行一个解的搜索;对启发信息进行重新设置等,并通过控制蚂蚁算法中蚂蚁移动的方式解决了驾驶员调度问题的时间窗问题。同时,蚂蚁算法可以直接在行车计划的基础上进行解的搜索,实现了贪婪式的要求。最后利用C#语言实现了蚂蚁算法,并进行了仿真试验,分析了蚂蚁算法的参数对算法性能的影响,得出了经验式的参数优化设置方法,并可以在较短的时间内获得满意解。与禁忌搜索算法的对比表明,对同一原始数据可得出相似的优化结果。
Public Transport System is an indivisible part of the cities’transport, and Bus Driver Scheduling which strongly relates to the costs of operations and the quality of services is an important part of the daily operations of the public transport systems. Although there are mature bus driver scheduling software systems abroad, the differences of local public transport systems make them hard to import in. So the bus driver scheduling problem is paid more and more attention to. Meanwhile the problems of window of relief opportunity and meal time are not well solved which worth more researches.
This thesis discussed the Ant System bases bus driver scheduling. Ant system is a heuristic and greedy algorithm with a positive feedback, and it has a potential in some kinds of combinatorial optimization problems like path optimizations and scheduling problems which are hardly solved with integer linear programming. This thesis analyzed the mathematics model of bus driver scheduling problem, and improved the ant system within the special rules of this problem including adding the constraints in as the parameters, dividing ants for different works, and resetting the heuristic information. Meanwhile the window of relief opportunity problem was solved by controlling the movement of the ant. This ant system searches solutions directly from the route plan and realized a greed algorithm. This ant system is realized using C# language, and with simulation, the parameters’impacts to the performance were analyzed. Better parameters can be set from the analysis and a satisfactory solution can be got in appropriate time. In the simulation, this ant system was compared with the tabu search algorithm in a same problem from the real world showed they achieved similar results.
本文研究利用蚂蚁算法来解决公共交通中公共汽车驾驶员调度的问题。蚂蚁算法是一种带有正反馈机制的启发式算法,并具有贪婪的特性,在解决路径优化、调度排班这类利用传统数学规划方法很难解决的问题上具有很大的潜力。本文对驾驶员调度问题的数学模型进行了详细分析,根据驾驶员调度问题的特点和其特殊的约束,对蚂蚁算法做了改进,包括:将驾驶员调度特有的规则加入到算法当中,为可设置的参数;采用多只蚂蚁分工进行一个解的搜索;对启发信息进行重新设置等,并通过控制蚂蚁算法中蚂蚁移动的方式解决了驾驶员调度问题的时间窗问题。同时,蚂蚁算法可以直接在行车计划的基础上进行解的搜索,实现了贪婪式的要求。最后利用C#语言实现了蚂蚁算法,并进行了仿真试验,分析了蚂蚁算法的参数对算法性能的影响,得出了经验式的参数优化设置方法,并可以在较短的时间内获得满意解。与禁忌搜索算法的对比表明,对同一原始数据可得出相似的优化结果。
Public Transport System is an indivisible part of the cities’transport, and Bus Driver Scheduling which strongly relates to the costs of operations and the quality of services is an important part of the daily operations of the public transport systems. Although there are mature bus driver scheduling software systems abroad, the differences of local public transport systems make them hard to import in. So the bus driver scheduling problem is paid more and more attention to. Meanwhile the problems of window of relief opportunity and meal time are not well solved which worth more researches.
This thesis discussed the Ant System bases bus driver scheduling. Ant system is a heuristic and greedy algorithm with a positive feedback, and it has a potential in some kinds of combinatorial optimization problems like path optimizations and scheduling problems which are hardly solved with integer linear programming. This thesis analyzed the mathematics model of bus driver scheduling problem, and improved the ant system within the special rules of this problem including adding the constraints in as the parameters, dividing ants for different works, and resetting the heuristic information. Meanwhile the window of relief opportunity problem was solved by controlling the movement of the ant. This ant system searches solutions directly from the route plan and realized a greed algorithm. This ant system is realized using C# language, and with simulation, the parameters’impacts to the performance were analyzed. Better parameters can be set from the analysis and a satisfactory solution can be got in appropriate time. In the simulation, this ant system was compared with the tabu search algorithm in a same problem from the real world showed they achieved similar results.
引文
[1]北京市公共交通总公司,北方交通大学.城市公共交通运营调度管理.北京:中国铁道出版社, 2001.
[2]沈吟东,曾西洋.公共交通驾驶员调度的复杂性及解决方法.计算机科学. 2003, 31(9): 226-229.
[3]刘镇阳,张秀媛,徐进等.城市智能公共交通系统.北京:中国铁道出版社, 2004.
[4] Wren A. and Rousseau J. Bus Driver Scheduling-an Overview. in: the VIth International Workshop on Computer Aided Scheduling of Public Transport, Lisbon, Portugal, 1993. 1-14
[5] Smith B. M. IMPACS-a Bus Crew Scheduling System using Integer Programming. Mathematical Programming, 1988, 42(1): 181-187.
[6] Rousseau J. M., Blais J. Y. HASTUS: An Interactive System for Buses and Crew Scheduling. In: Computer Scheduling of Public Transport 2. North-Holland, 1985. 45.
[7] Daduna J. R., Mojsilovic M. Computer-Aided Vehicle and Duty Scheduling using the HOT Programme System. Computer-Aided Transit Scheduling, Lecture Notes in Economics and Mathematical Systems, 1988, 430: 133-146.
[8]沈吟东,倪郁东.基于整数规划的驾驶员调度系统-TRACSⅡ.运筹与管理, 2005, 14(003): 76-80.
[9] Fores S., Proll L. and Wren A. TRACS II: a Hybrid IP/Heuristic Driver Scheduling System for Public Transport. Operational Research Society, 2002, 53(10): 1093-1100.
[10] Wren A., Wren D. O. A Genetic Algorithm for Public Transport Driver Scheduling. Computers and Operations Research, 1995, 22(1): 101-110.
[11] Forsyth P., Wren A. An Ant System for Bus Driver Scheduling. in: the 7th International Workshop on Computer-Aided Scheduling of Public Transport. Boston, 1997. 405-421
[12] Curtis S. D., Smith B. M. and Wren A. Forming Bus Driver Schedules using Constraint Programming. in: Proceedings of the 1st International Conference on the Practical Applications of Constraint Technologies and Logic Programming. London,1999. 239-254.
[13] Zhao L., Wren A. and Kwan R. S. K. Development of a Driver Duty Estimator. The Journal of the Operational Research Society, 1995, 46(9): 1102-1110.
[14] Wren A. Heuristics Ancient and Modern: Transport Scheduling Through the Ages. Journal of Heuristics, 1998, 4(1): 87-100.
[15] SHEN Y. D., and Kwan K. R. S. Tabu Search for Driver Scheduling. in: Computer-Aided Scheduling for Public Transport 2000. Berlin, 2000. 121-135.
[16] Louren?o H. R., Paix?o J. P. and Portugal R. Multiobjective Metaheuristics for the Bus Driver Scheduling Problem. Transportation Science, 2001, 35(3): 331-343.
[17] Li J., Kwan R. S. K. A Fuzzy Genetic Algorithm for Driver Scheduling. European Journal of Operational Research, 2003, 147(2): 334-344.
[18] Kwan R. S. K., Kwan A. S. K. and Wren A. Evolutionary Driver Scheduling with Relief Chains. Evolutionary Computation, 2001, 9(4): 445-460.
[19] Li J. and Kwan R. S. K. A Meta-heuristic with Orthogonal Experiment for the Set Covering Problem. Journal of Mathematical Modelling and Algorithms, 2004, 3(3): 263-283.
[20] Li J. A Self-Adjusting Algorithm for Driver Scheduling. Journal of Heuristics, 2005, 11(4): 351-367.
[21] Laplagne I., Kwan R. and Kwan A. A Hybridised Integer Programming and Local Search Method for Robust Train Driver Schedules Planning. Practice and Theory of Automated Timetabling V, 2005: 71-85.
[22] Aickelin U., Burke E. and Li J. Improved Squeaky Wheel Optimization for Driver Scheduling. Parallel Problem Solving from Nature - PPSN IX, 2006: 182-191.
[23] Kwan R., Kwan A. Effective Search Space Control for Large and/or Complex Driver Scheduling Problems. Annals of Operations Research, 2007, 155(1): 417-435.
[24] D'Annibale G., Leone R. D. and Festa P. et al. A New Meta-heuristic for the Bus Driver Scheduling Problem: GRASP combined with Rollout. in: IEEE Symposium on Computational Intelligence in Scheduling, 2007. Hawaii, 2007. 192-197.
[25]张斐斐.公共交通驾驶员调度问题研究[硕士学位论文].北京:北方交通大学, 2007.
[26]席裕庚,柴天佑.遗传算法综述.控制理论与应用, 1996, 13(006): 697-708.
[27] Dorigo M., Maniezzo V. and Colorni A. Ant System: Optimization by a Colony of Cooperating Agents. Systems, Man, and Cybernetics, Part B: Cybernetics, Transactions on IEEE, 1996, 26(1): 29-41.
[28]李士勇,陈永強,李硏.蚁群算法及其应用.哈尔滨:哈尔滨工业大学出版社, 2004.
[29]段海滨,王道波,朱家强等.蚁群算法理论及应用研究的进展.控制与决策, 2004, 19(012): 1321-1326.
[30] Dorigo M., Gambardella L. M. Ant Colonies for the Traveling Salesman Problem. BioSystem, 1997(43): 73-81.
[31] Colorni A., Dorigo M. and Maniezzo V. et al. Ant System for Job-shop Scheduling. Belgian Journal of Operations Research, 1994, 34(1): 39-53.
[32] Kuntz P., Layzell P. and Snyers D. A Colony of Ant-like Agents for Partitioning in VLSI Technology. in: Proceedings of the Fourth European Conference on Artificial Life. Boston, 1997. 417-424.
[33] Costa D. and Hertz A. Ants can Colour Graphs. Journal of the Operational Research Society, 1997, 48(3): 295-305.
[34] Caro G. D. and Dorigo M. Mobile Agents for Adaptive Routing. in: Proceedings of the Thirty-First Hawaii International Conference on System Sciences. Hawai, 1998. 74-83.
[35] Schoonderwoerd R., Holland O. and Bruten J. Ant-like Agents for Load Balancing in Telecommunications Networks. in: Proceedings of the first international conference on Autonomous agents. California, 1997. 209-216.
[36]丁建立,陈增强,袁著祉.遗传算法与蚂蚁算法的融合.计算机研究与发展, 2003, 40(009): 1351-1356.
[37]詹士昌,徐婕和吴俊.蚁群算法中有关算法参数的最优选择.科技通报, 2003, 19(005): 381-386.
[38]叶志伟,郑肇葆.蚁群算法中参数α,β,ρ设置的研究——以TSP问题为例.武汉大学学报:信息科学版, 2004, 29(007): 597-601.
[39] Goss S., Aron S. and Deneubourg J. L. et al. Self-organized Shortcuts in the Argentine Ant. Naturwissenschaften, 1989, 76(12): 579-581.
[40] Dorigo M., Maniezzo V. and Colorni A. Positive Feedback as a Search Strategy. Technical Report, 1991: 91-016.
[41]王颖,谢剑英.一种自适应蚁群算法及其仿真研究.系统仿真学报, 2002, 14(1): 31-33.
[42] Stiitzle T., Hoos H. Improvements on the Ant-System: Introducing the MAX-MXN Ant System. in: Artificial neural nets and genetic algorithms: proceedings of the International Conference in Norwich, UK, 1997. Norwich, 1998. 245.
[43] Stützle T. and Hoos H. MAX-MIN ant system. Future Generation Computer Systems, 2000(16): 889-914.
[2]沈吟东,曾西洋.公共交通驾驶员调度的复杂性及解决方法.计算机科学. 2003, 31(9): 226-229.
[3]刘镇阳,张秀媛,徐进等.城市智能公共交通系统.北京:中国铁道出版社, 2004.
[4] Wren A. and Rousseau J. Bus Driver Scheduling-an Overview. in: the VIth International Workshop on Computer Aided Scheduling of Public Transport, Lisbon, Portugal, 1993. 1-14
[5] Smith B. M. IMPACS-a Bus Crew Scheduling System using Integer Programming. Mathematical Programming, 1988, 42(1): 181-187.
[6] Rousseau J. M., Blais J. Y. HASTUS: An Interactive System for Buses and Crew Scheduling. In: Computer Scheduling of Public Transport 2. North-Holland, 1985. 45.
[7] Daduna J. R., Mojsilovic M. Computer-Aided Vehicle and Duty Scheduling using the HOT Programme System. Computer-Aided Transit Scheduling, Lecture Notes in Economics and Mathematical Systems, 1988, 430: 133-146.
[8]沈吟东,倪郁东.基于整数规划的驾驶员调度系统-TRACSⅡ.运筹与管理, 2005, 14(003): 76-80.
[9] Fores S., Proll L. and Wren A. TRACS II: a Hybrid IP/Heuristic Driver Scheduling System for Public Transport. Operational Research Society, 2002, 53(10): 1093-1100.
[10] Wren A., Wren D. O. A Genetic Algorithm for Public Transport Driver Scheduling. Computers and Operations Research, 1995, 22(1): 101-110.
[11] Forsyth P., Wren A. An Ant System for Bus Driver Scheduling. in: the 7th International Workshop on Computer-Aided Scheduling of Public Transport. Boston, 1997. 405-421
[12] Curtis S. D., Smith B. M. and Wren A. Forming Bus Driver Schedules using Constraint Programming. in: Proceedings of the 1st International Conference on the Practical Applications of Constraint Technologies and Logic Programming. London,1999. 239-254.
[13] Zhao L., Wren A. and Kwan R. S. K. Development of a Driver Duty Estimator. The Journal of the Operational Research Society, 1995, 46(9): 1102-1110.
[14] Wren A. Heuristics Ancient and Modern: Transport Scheduling Through the Ages. Journal of Heuristics, 1998, 4(1): 87-100.
[15] SHEN Y. D., and Kwan K. R. S. Tabu Search for Driver Scheduling. in: Computer-Aided Scheduling for Public Transport 2000. Berlin, 2000. 121-135.
[16] Louren?o H. R., Paix?o J. P. and Portugal R. Multiobjective Metaheuristics for the Bus Driver Scheduling Problem. Transportation Science, 2001, 35(3): 331-343.
[17] Li J., Kwan R. S. K. A Fuzzy Genetic Algorithm for Driver Scheduling. European Journal of Operational Research, 2003, 147(2): 334-344.
[18] Kwan R. S. K., Kwan A. S. K. and Wren A. Evolutionary Driver Scheduling with Relief Chains. Evolutionary Computation, 2001, 9(4): 445-460.
[19] Li J. and Kwan R. S. K. A Meta-heuristic with Orthogonal Experiment for the Set Covering Problem. Journal of Mathematical Modelling and Algorithms, 2004, 3(3): 263-283.
[20] Li J. A Self-Adjusting Algorithm for Driver Scheduling. Journal of Heuristics, 2005, 11(4): 351-367.
[21] Laplagne I., Kwan R. and Kwan A. A Hybridised Integer Programming and Local Search Method for Robust Train Driver Schedules Planning. Practice and Theory of Automated Timetabling V, 2005: 71-85.
[22] Aickelin U., Burke E. and Li J. Improved Squeaky Wheel Optimization for Driver Scheduling. Parallel Problem Solving from Nature - PPSN IX, 2006: 182-191.
[23] Kwan R., Kwan A. Effective Search Space Control for Large and/or Complex Driver Scheduling Problems. Annals of Operations Research, 2007, 155(1): 417-435.
[24] D'Annibale G., Leone R. D. and Festa P. et al. A New Meta-heuristic for the Bus Driver Scheduling Problem: GRASP combined with Rollout. in: IEEE Symposium on Computational Intelligence in Scheduling, 2007. Hawaii, 2007. 192-197.
[25]张斐斐.公共交通驾驶员调度问题研究[硕士学位论文].北京:北方交通大学, 2007.
[26]席裕庚,柴天佑.遗传算法综述.控制理论与应用, 1996, 13(006): 697-708.
[27] Dorigo M., Maniezzo V. and Colorni A. Ant System: Optimization by a Colony of Cooperating Agents. Systems, Man, and Cybernetics, Part B: Cybernetics, Transactions on IEEE, 1996, 26(1): 29-41.
[28]李士勇,陈永強,李硏.蚁群算法及其应用.哈尔滨:哈尔滨工业大学出版社, 2004.
[29]段海滨,王道波,朱家强等.蚁群算法理论及应用研究的进展.控制与决策, 2004, 19(012): 1321-1326.
[30] Dorigo M., Gambardella L. M. Ant Colonies for the Traveling Salesman Problem. BioSystem, 1997(43): 73-81.
[31] Colorni A., Dorigo M. and Maniezzo V. et al. Ant System for Job-shop Scheduling. Belgian Journal of Operations Research, 1994, 34(1): 39-53.
[32] Kuntz P., Layzell P. and Snyers D. A Colony of Ant-like Agents for Partitioning in VLSI Technology. in: Proceedings of the Fourth European Conference on Artificial Life. Boston, 1997. 417-424.
[33] Costa D. and Hertz A. Ants can Colour Graphs. Journal of the Operational Research Society, 1997, 48(3): 295-305.
[34] Caro G. D. and Dorigo M. Mobile Agents for Adaptive Routing. in: Proceedings of the Thirty-First Hawaii International Conference on System Sciences. Hawai, 1998. 74-83.
[35] Schoonderwoerd R., Holland O. and Bruten J. Ant-like Agents for Load Balancing in Telecommunications Networks. in: Proceedings of the first international conference on Autonomous agents. California, 1997. 209-216.
[36]丁建立,陈增强,袁著祉.遗传算法与蚂蚁算法的融合.计算机研究与发展, 2003, 40(009): 1351-1356.
[37]詹士昌,徐婕和吴俊.蚁群算法中有关算法参数的最优选择.科技通报, 2003, 19(005): 381-386.
[38]叶志伟,郑肇葆.蚁群算法中参数α,β,ρ设置的研究——以TSP问题为例.武汉大学学报:信息科学版, 2004, 29(007): 597-601.
[39] Goss S., Aron S. and Deneubourg J. L. et al. Self-organized Shortcuts in the Argentine Ant. Naturwissenschaften, 1989, 76(12): 579-581.
[40] Dorigo M., Maniezzo V. and Colorni A. Positive Feedback as a Search Strategy. Technical Report, 1991: 91-016.
[41]王颖,谢剑英.一种自适应蚁群算法及其仿真研究.系统仿真学报, 2002, 14(1): 31-33.
[42] Stiitzle T., Hoos H. Improvements on the Ant-System: Introducing the MAX-MXN Ant System. in: Artificial neural nets and genetic algorithms: proceedings of the International Conference in Norwich, UK, 1997. Norwich, 1998. 245.
[43] Stützle T. and Hoos H. MAX-MIN ant system. Future Generation Computer Systems, 2000(16): 889-914.