单车场非对称双向多线路车辆调度系统
|
摘要
随着城市化建设步伐的加快,大力发展公交事业成为解决公共交通问题的重点。发展公交事业,不能够一味靠加大投资,还需要加强公交企业的运营管理效率。加强公交车辆的调度效率是加强公交企业运营管理效率的重要途径,本文分析了公交企业的车辆调度工作的业务流程、根据其业务自身的内容和需求设计解决企业车辆调度问题的车辆调度系统,并设计了编制车辆调度计划的调度算法。最终实现了系统。
本系统满足公交企业车辆调度业务的需求,能够对车辆调度工作涉及的各种基础数据进行管理和维护,其中包括线路、站点、停车场的数据管理维护,还包括对站点间地理信息的管理维护和发车任务的管理维护。
发车任务由公司通过系统下达到车辆调度人员,车辆调度人员选择需要编制车辆调度计划的线路进行编制,系统自动读取所需的数据,使用调度算法编制出车辆调度计划。
该系统解决的是单车场多线路双向非对称的车辆调度问题,适合编制多条线路公用停车场和车辆资源的实际情况。车辆能够跨线行驶以平衡不同线路的高低峰客流。文章对车辆调度问题进行数学建模,并使用时-空二维网络图算法、2-OPT算法和模拟退火算法共同解决车辆调度问题:通过时-空二维网络图算法构造初始可行班次,2-OPT算法和模拟退火算法对初始班次进行进一步优化。
通过实际检验,系统工作正常,编制车辆调度计划的调度算法中时-空二维网络图算法和2-OPT算法能够快速有效计算车辆班次并优化,模拟退火算法的效果还不理想,其参数设置还需要进一步进行研究。
As the step of urbanization speeds up, developing bus undertaking comes to the point of resolving the problems in public transport. Developing bus undertaking, can not rely on increased investment but also increased efficiency in operation.
To increase the efficiency in the bus vehicle scheduling is the key to increase the efficiency in operation the bus company. This paper analyses the business process of the bus scheduling, designed a vehicle scheduling system and scheduling algorithm to resolve the bus scheduling process according to its needs, and then eventually implemented the system.
This system meets the need in bus scheduling as it manage and maintains all data that refer to the bus scheduling business, including bus lines data, bus station data, bus depot data and the data of geographic relation between stations and the data of dispatching plan as well.
The company makes the dispatching plan then gives the appointment to the bus scheduling worker through the system. The bus scheduling worker chooses the bus line to make bus schedule and the system automatically reads the needed data and build bus schedule using an algorithm.
The system is designed to resolve a Single Depot Asymmetric Bi-direction Multi-line bus scheduling problem, it fits the case that several bus lines shares one depot. Buses cross the lines when needed to balance the passenger flow between different lines.
This paper gives the mathematic model of the bus vehicle scheduling problem ,then resolve it using Time-space Network Graphic Algorithm,2-OPT algorithm and Simulating Annealing algorithm: the Time-space Network Graphic Algorithm is aiming at build initial feasible shifts, 2-OPT algorithm and Simulating Annealing are aiming at improve the shifts.
As practical tests showed, the system works normally .The Time-space Network Graphic Algorithm and the 2-OPT algorithm are fast and in effect, but the Simulating Annealing algorithm still need to be improved as the parameters is difficult to choose.
本系统满足公交企业车辆调度业务的需求,能够对车辆调度工作涉及的各种基础数据进行管理和维护,其中包括线路、站点、停车场的数据管理维护,还包括对站点间地理信息的管理维护和发车任务的管理维护。
发车任务由公司通过系统下达到车辆调度人员,车辆调度人员选择需要编制车辆调度计划的线路进行编制,系统自动读取所需的数据,使用调度算法编制出车辆调度计划。
该系统解决的是单车场多线路双向非对称的车辆调度问题,适合编制多条线路公用停车场和车辆资源的实际情况。车辆能够跨线行驶以平衡不同线路的高低峰客流。文章对车辆调度问题进行数学建模,并使用时-空二维网络图算法、2-OPT算法和模拟退火算法共同解决车辆调度问题:通过时-空二维网络图算法构造初始可行班次,2-OPT算法和模拟退火算法对初始班次进行进一步优化。
通过实际检验,系统工作正常,编制车辆调度计划的调度算法中时-空二维网络图算法和2-OPT算法能够快速有效计算车辆班次并优化,模拟退火算法的效果还不理想,其参数设置还需要进一步进行研究。
As the step of urbanization speeds up, developing bus undertaking comes to the point of resolving the problems in public transport. Developing bus undertaking, can not rely on increased investment but also increased efficiency in operation.
To increase the efficiency in the bus vehicle scheduling is the key to increase the efficiency in operation the bus company. This paper analyses the business process of the bus scheduling, designed a vehicle scheduling system and scheduling algorithm to resolve the bus scheduling process according to its needs, and then eventually implemented the system.
This system meets the need in bus scheduling as it manage and maintains all data that refer to the bus scheduling business, including bus lines data, bus station data, bus depot data and the data of geographic relation between stations and the data of dispatching plan as well.
The company makes the dispatching plan then gives the appointment to the bus scheduling worker through the system. The bus scheduling worker chooses the bus line to make bus schedule and the system automatically reads the needed data and build bus schedule using an algorithm.
The system is designed to resolve a Single Depot Asymmetric Bi-direction Multi-line bus scheduling problem, it fits the case that several bus lines shares one depot. Buses cross the lines when needed to balance the passenger flow between different lines.
This paper gives the mathematic model of the bus vehicle scheduling problem ,then resolve it using Time-space Network Graphic Algorithm,2-OPT algorithm and Simulating Annealing algorithm: the Time-space Network Graphic Algorithm is aiming at build initial feasible shifts, 2-OPT algorithm and Simulating Annealing are aiming at improve the shifts.
As practical tests showed, the system works normally .The Time-space Network Graphic Algorithm and the 2-OPT algorithm are fast and in effect, but the Simulating Annealing algorithm still need to be improved as the parameters is difficult to choose.
引文
[1] Wren A. Heuristics Ancient and Modern : Transport Scheduling Through the Ages. Journal of Heuristics, 1998, 4(1): 87～100.
[2] Yan S, Chi C J, Tang C H. Inter-city bus routing and timetable setting under stochastic demands. Transportation Research Part A: Policy and Practice, 2006, 40(7): 572～586.
[3] Xu K, Wang Y, Teng W, et al. Design and Implementation of Intelligent Vehicle Monitoring and Management System Based on the Multi-Net. IEEE Computer Society, 2006.
[4] Kliewer N, Mellouli T, Suhl L. A time-space network based exact optimization model for multi-depot bus scheduling. European Journal of Operational Research, 2006, 175(3): 1616～1627.
[5] Chardaire P, Mckeown G P, Verity-harrison S A, et al. Solving a Time-Space Network Formulation for the Convoy Movement Problem. OPERATIONS RESEARCH Operations Research, 2005, 53(2): 219～230.
[6] Desaulniers G, Lavigne J, Soumis F. Multi-depot vehicle scheduling problems with time windows and waiting costs. European Journal of Operational Research, 1998, 111(3): 479～494.
[7] Karuno Y, Nagamochi H. An approximability result of the multi-vehicle scheduling problem on a path with release and handling times. Theoretical Computer Science, 2004, 312(2-3): 267～280.
[8] Karuno Y, Nagamochi H. 2-Approximation algorithms for the multi-vehicle scheduling problem on a path with release and handling times. Discrete Applied Mathematics, 2003, 129(2-3): 433～447.
[9] Haghani A, Banihashemi M, Kun-hung C. A comparative analysis of bus transit vehicle scheduling models. Transportation Research, Part B (Methodological), 2003, 37B(4): 301～322.
[10] Cornillier F, Boctor F F, Laporte G, et al. A heuristic for the multi-period petrol station replenishment problem. European Journal of Operational Research, 2008, 191(2): 295～305.
[11] Wang H, Shen J. Heuristic approaches for solving transit vehicle scheduling problem with route and fueling time constraints. Applied Mathematics and Computation, 2007, 190(2): 1237～1249.
[12] Dondo R, Cerd J. A cluster-based optimization approach for the multi-depot heterogeneous fleet vehicle routing problem with time windows. European Journal of Operational Research, 2007, 176(3): 1478～1507.
[13] Mesquita M, Paias A. Set partitioning/covering-based approaches for the integrated vehicle and crew scheduling problem. Computers and Operations Research, 2008, 35(5): 1562～1575.
[14] Oukil A, Amor H B, Desrosiers J, et al. Stabilized column generation for highly degenerate multiple-depot vehicle scheduling problems. Computers & Operations Research, 2007, 34(3): 817～834.
[15] Freling R, Huisman D, M A P. Models and Algorithms for Integration of Vehicle and Crew Scheduling. Journal of Scheduling, 2003, 6(1): 63～85.
[16] Steinzen I, Becker M, Suhl L. A hybrid evolutionary algorithm for the vehicle and crew scheduling problem in public transit. Singapore, Singapore: IEEE, 2007.
[17] Walker C G, Snowdon J N, Ryan D M. Simultaneous disruption recovery of a train timetable and crew roster in real time. Computers and Operations Research, 2005, 32(8): 2077～2094.
[18] Naor J S, Shachnai H, Tamir T. Real-Time Scheduling with a Budget. Algorithmica, 2007, 47(3): 343～364.
[19] Li J Q, Mirchandani P B, Borenstein D. The vehicle rescheduling problem: Model and algorithms. Networks, 2007, 50(3): 211～229.
[20]蒋光震,何显慈.公共交通线路组合调度模型.系统工程, 1985, (02).
[21]马庆国徐一勤,王文莲.城市公交行车计划模型.系统工程, 1987, (04).
[22]王大勇,王海星.城市公交区域运营模式及其关键技术.综合运输, 2008, (03).
[23]曲大义,张晓靖,王殿海.智能化公交调度系统结构及功能设计.交通与计算机, 2008, (01).
[24]张南平,刘思津.基于.NET Remoting框架的分布式车辆调度系统.计算机技术与发展, 2008, (04).
[25]邹迎.公交区域调度行车计划编制方法研究.交通运输系统工程与信息, 2007, (03).
[26]刘志刚,申金升.区域公交时刻表及车辆调度双层规划模型.系统工程理论与实践, 2007, (11).
[27]刘志刚,申金升,杨威.基于禁忌搜索的公交区域调度配车模型研究.交通运输工程与信息学报, 2007, (04).
[28]丰伟,李雪芹.基于粒子群算法的多目标车辆调度模型求解.系统工程, 2007, (04).
[29]范秋生,潘纹.遗传算法在智能交通系统车辆调度中的应用研究.计算机与数字工程, 2007, (05).
[30]娄山佐,史忠科.有限车辆调度问题的模型和改进遗传算法.计算机应用研究, 2006, (04).
[31]张海刚,吴燕翔,顾幸生.基于免疫遗传算法的双向车辆调度问题实现.系统工程学报, 2007, (06).
[32]张海刚,顾幸生.基于混合免疫遗传算法的车辆调度问题.微电子学与计算机, 2007, (01).
[33]韩印,刘闯. BP神经网络在公交智能化调度中的应用研究.交通与计算机, 2007, (06).
[34]钟石泉,贺国光.多车场有时间窗的多车型车辆调度及其禁忌算法研究.运筹学学报, 2005, (04).
[35]钟石泉,贺国光.有时间窗约束车辆调度优化的一种禁忌算法.系统工程理论方法应用, 2005, (06).
[36]钟石泉贺国光.单车场复杂情况下的车辆调度.系统工程, 2005, (05).
[37]贾永基谷寒雨,席裕庚.动态车辆调度系统的滚动时域调度算法. Journal of Southeast University, 2005, (01).
[38]谢优平,张莉.一种多级静动态车辆调度模型的设计及实现.地理空间信息, 2007, (01).
[39] Lubbecke M E, Desrosiers J. Selected Topics in Column Generation. Operations Research, 2005, 53(6): 1007～1023.
[40] Mourgaya M, Vanderbeck F. Column generation based heuristic for tactical planning in multi-period vehicle routing. European Journal of Operational Research, 2007, 183(3): 1028～1041.
[41] Nagamochi H, Ohnishi T. Approximating a vehicle scheduling problem with time windows and handling times. Theoretical Computer Science, 2008, 393(1-3): 133～146.
[42]姜昌华,戴树贵,胡幼华.求解车辆路径问题的混合遗传算法.计算机集成制造系统, 2007, (10).
[43] Mavroidis I, Papaefstathiou I, Pnevmatikatos D. A fast FPGA-based 2-Opt solver for small-scale Euclidean traveling salesman problem. Napa, CA, USA: IEEE, 2007.
[44] Ling W, Da-zhong Z. An effective hybrid optimization strategy for job-shop scheduling problems. Computers & Operations Research, 2001, 28(6): 585～596.
[45] Ling W, Da-zhong Z. A modified evolutionary programming for flow shop scheduling. International Journal of Advanced Manufacturing Technology, 2003, 22(7-8): 522～527.
[2] Yan S, Chi C J, Tang C H. Inter-city bus routing and timetable setting under stochastic demands. Transportation Research Part A: Policy and Practice, 2006, 40(7): 572～586.
[3] Xu K, Wang Y, Teng W, et al. Design and Implementation of Intelligent Vehicle Monitoring and Management System Based on the Multi-Net. IEEE Computer Society, 2006.
[4] Kliewer N, Mellouli T, Suhl L. A time-space network based exact optimization model for multi-depot bus scheduling. European Journal of Operational Research, 2006, 175(3): 1616～1627.
[5] Chardaire P, Mckeown G P, Verity-harrison S A, et al. Solving a Time-Space Network Formulation for the Convoy Movement Problem. OPERATIONS RESEARCH Operations Research, 2005, 53(2): 219～230.
[6] Desaulniers G, Lavigne J, Soumis F. Multi-depot vehicle scheduling problems with time windows and waiting costs. European Journal of Operational Research, 1998, 111(3): 479～494.
[7] Karuno Y, Nagamochi H. An approximability result of the multi-vehicle scheduling problem on a path with release and handling times. Theoretical Computer Science, 2004, 312(2-3): 267～280.
[8] Karuno Y, Nagamochi H. 2-Approximation algorithms for the multi-vehicle scheduling problem on a path with release and handling times. Discrete Applied Mathematics, 2003, 129(2-3): 433～447.
[9] Haghani A, Banihashemi M, Kun-hung C. A comparative analysis of bus transit vehicle scheduling models. Transportation Research, Part B (Methodological), 2003, 37B(4): 301～322.
[10] Cornillier F, Boctor F F, Laporte G, et al. A heuristic for the multi-period petrol station replenishment problem. European Journal of Operational Research, 2008, 191(2): 295～305.
[11] Wang H, Shen J. Heuristic approaches for solving transit vehicle scheduling problem with route and fueling time constraints. Applied Mathematics and Computation, 2007, 190(2): 1237～1249.
[12] Dondo R, Cerd J. A cluster-based optimization approach for the multi-depot heterogeneous fleet vehicle routing problem with time windows. European Journal of Operational Research, 2007, 176(3): 1478～1507.
[13] Mesquita M, Paias A. Set partitioning/covering-based approaches for the integrated vehicle and crew scheduling problem. Computers and Operations Research, 2008, 35(5): 1562～1575.
[14] Oukil A, Amor H B, Desrosiers J, et al. Stabilized column generation for highly degenerate multiple-depot vehicle scheduling problems. Computers & Operations Research, 2007, 34(3): 817～834.
[15] Freling R, Huisman D, M A P. Models and Algorithms for Integration of Vehicle and Crew Scheduling. Journal of Scheduling, 2003, 6(1): 63～85.
[16] Steinzen I, Becker M, Suhl L. A hybrid evolutionary algorithm for the vehicle and crew scheduling problem in public transit. Singapore, Singapore: IEEE, 2007.
[17] Walker C G, Snowdon J N, Ryan D M. Simultaneous disruption recovery of a train timetable and crew roster in real time. Computers and Operations Research, 2005, 32(8): 2077～2094.
[18] Naor J S, Shachnai H, Tamir T. Real-Time Scheduling with a Budget. Algorithmica, 2007, 47(3): 343～364.
[19] Li J Q, Mirchandani P B, Borenstein D. The vehicle rescheduling problem: Model and algorithms. Networks, 2007, 50(3): 211～229.
[20]蒋光震,何显慈.公共交通线路组合调度模型.系统工程, 1985, (02).
[21]马庆国徐一勤,王文莲.城市公交行车计划模型.系统工程, 1987, (04).
[22]王大勇,王海星.城市公交区域运营模式及其关键技术.综合运输, 2008, (03).
[23]曲大义,张晓靖,王殿海.智能化公交调度系统结构及功能设计.交通与计算机, 2008, (01).
[24]张南平,刘思津.基于.NET Remoting框架的分布式车辆调度系统.计算机技术与发展, 2008, (04).
[25]邹迎.公交区域调度行车计划编制方法研究.交通运输系统工程与信息, 2007, (03).
[26]刘志刚,申金升.区域公交时刻表及车辆调度双层规划模型.系统工程理论与实践, 2007, (11).
[27]刘志刚,申金升,杨威.基于禁忌搜索的公交区域调度配车模型研究.交通运输工程与信息学报, 2007, (04).
[28]丰伟,李雪芹.基于粒子群算法的多目标车辆调度模型求解.系统工程, 2007, (04).
[29]范秋生,潘纹.遗传算法在智能交通系统车辆调度中的应用研究.计算机与数字工程, 2007, (05).
[30]娄山佐,史忠科.有限车辆调度问题的模型和改进遗传算法.计算机应用研究, 2006, (04).
[31]张海刚,吴燕翔,顾幸生.基于免疫遗传算法的双向车辆调度问题实现.系统工程学报, 2007, (06).
[32]张海刚,顾幸生.基于混合免疫遗传算法的车辆调度问题.微电子学与计算机, 2007, (01).
[33]韩印,刘闯. BP神经网络在公交智能化调度中的应用研究.交通与计算机, 2007, (06).
[34]钟石泉,贺国光.多车场有时间窗的多车型车辆调度及其禁忌算法研究.运筹学学报, 2005, (04).
[35]钟石泉,贺国光.有时间窗约束车辆调度优化的一种禁忌算法.系统工程理论方法应用, 2005, (06).
[36]钟石泉贺国光.单车场复杂情况下的车辆调度.系统工程, 2005, (05).
[37]贾永基谷寒雨,席裕庚.动态车辆调度系统的滚动时域调度算法. Journal of Southeast University, 2005, (01).
[38]谢优平,张莉.一种多级静动态车辆调度模型的设计及实现.地理空间信息, 2007, (01).
[39] Lubbecke M E, Desrosiers J. Selected Topics in Column Generation. Operations Research, 2005, 53(6): 1007～1023.
[40] Mourgaya M, Vanderbeck F. Column generation based heuristic for tactical planning in multi-period vehicle routing. European Journal of Operational Research, 2007, 183(3): 1028～1041.
[41] Nagamochi H, Ohnishi T. Approximating a vehicle scheduling problem with time windows and handling times. Theoretical Computer Science, 2008, 393(1-3): 133～146.
[42]姜昌华,戴树贵,胡幼华.求解车辆路径问题的混合遗传算法.计算机集成制造系统, 2007, (10).
[43] Mavroidis I, Papaefstathiou I, Pnevmatikatos D. A fast FPGA-based 2-Opt solver for small-scale Euclidean traveling salesman problem. Napa, CA, USA: IEEE, 2007.
[44] Ling W, Da-zhong Z. An effective hybrid optimization strategy for job-shop scheduling problems. Computers & Operations Research, 2001, 28(6): 585～596.
[45] Ling W, Da-zhong Z. A modified evolutionary programming for flow shop scheduling. International Journal of Advanced Manufacturing Technology, 2003, 22(7-8): 522～527.