基于时空网络的城市常规公交多车场车辆调度问题研究
|
摘要
随着城市化进程的加快,城市交通问题日益严重,城市常规公交由于其建设成本低、机动性好的优点在解决交通拥堵问题上发挥了巨大的作用。常规公交企业通过采用多车场车辆调度模式可以调配多条线路的车辆、人员等资源,以提高车辆的使用效率,实现资源的优化配置。在考虑到我国城市常规公交运营的实际情况的基础上,本文着重研究了基于时空网络的城市常规公交多车场车辆调度问题。
首先,阐述了城市常规公交多车场车辆调度问题的概念,分析了城市常规公交多车场车辆调度问题与单车场车辆调度问题之间的关系,说明了城市常规公交多车场车辆调度问题的复杂性。
其次,研究了城市常规公交多车场车辆调度问题的网络描述,分别给出了连接网络与时空网络这两种网络的结构、简化方法以及相应的数学模型,并且给出了时空网络的构建步骤。同时,对连接网络与时空网络在任务表示方法、接续关系表示方法和网络规模上进行了比较。
再次,在分析了城市常规公交多车场车辆调度问题的基础上,基于时空网络建立了考虑公交车辆离场时间约束的城市常规公交多车场车辆调度问题的集分割模型,并且设计了基于分枝定价的大规模邻域搜索算法。
最后,通过算例对基于时空网络建立的考虑公交离场时间约束的城市常规公交多车场车辆调度模型及其算法进行了验证,结果说明了设计的基于分枝定价的大规模邻域搜索算法的可行性和有效性。
With the acceleration of urbanization, urban traffic problems, are becoming increasingly serious. As a result, urban bus system has played an important role in solving traffic congestion for its low construction cost and flexibility. By applying multiple depot vehicle scheduling mode, urban bus system enterprise can dispatch vehicles and crew on different bus lines so as to improve the vehicle efficiency and eventually achieve the optimal allocation of resources. Considering the actual situation of urban bus system in our country, the multiple depot vehicle scheduling problem of urban bus system based on a time-space network is studied.
Firstly, the concept of multiple depot vehicle scheduling problem of urban bus system is elaborated and its complexity is also analyzed. The relationship between multiple depot vehicle scheduling problem and single depot vehicle scheduling problem is analyzed.
Secondly, the network used to depict the multiple depot vehicle scheduling problem of urban bus system is studied and the structure, simplifying method and the corresponding mathematical model of connection-based network and time-space network are demonstrated. The construction steps of a time-space network model are given. Meanwhile, the task-depicting method, connection-depicting method and network scale of the two different models are compared.
Thirdly, after analyzing the multiple depot vehicle scheduling problem of urban bus system, the set partitioning model which has taken the departure-duration constraint of buses into consideration is built up based on a time-space network. To solve the model, a branch-and-price-based large neighborhood search algorithm is also designed.
Finally, the set partitioning model and the algorithm are verified by an case. Thé result shows that the branch-and-price-based large neighborhood search algorithm is feasible and effective.
首先,阐述了城市常规公交多车场车辆调度问题的概念,分析了城市常规公交多车场车辆调度问题与单车场车辆调度问题之间的关系,说明了城市常规公交多车场车辆调度问题的复杂性。
其次,研究了城市常规公交多车场车辆调度问题的网络描述,分别给出了连接网络与时空网络这两种网络的结构、简化方法以及相应的数学模型,并且给出了时空网络的构建步骤。同时,对连接网络与时空网络在任务表示方法、接续关系表示方法和网络规模上进行了比较。
再次,在分析了城市常规公交多车场车辆调度问题的基础上,基于时空网络建立了考虑公交车辆离场时间约束的城市常规公交多车场车辆调度问题的集分割模型,并且设计了基于分枝定价的大规模邻域搜索算法。
最后,通过算例对基于时空网络建立的考虑公交离场时间约束的城市常规公交多车场车辆调度模型及其算法进行了验证,结果说明了设计的基于分枝定价的大规模邻域搜索算法的可行性和有效性。
With the acceleration of urbanization, urban traffic problems, are becoming increasingly serious. As a result, urban bus system has played an important role in solving traffic congestion for its low construction cost and flexibility. By applying multiple depot vehicle scheduling mode, urban bus system enterprise can dispatch vehicles and crew on different bus lines so as to improve the vehicle efficiency and eventually achieve the optimal allocation of resources. Considering the actual situation of urban bus system in our country, the multiple depot vehicle scheduling problem of urban bus system based on a time-space network is studied.
Firstly, the concept of multiple depot vehicle scheduling problem of urban bus system is elaborated and its complexity is also analyzed. The relationship between multiple depot vehicle scheduling problem and single depot vehicle scheduling problem is analyzed.
Secondly, the network used to depict the multiple depot vehicle scheduling problem of urban bus system is studied and the structure, simplifying method and the corresponding mathematical model of connection-based network and time-space network are demonstrated. The construction steps of a time-space network model are given. Meanwhile, the task-depicting method, connection-depicting method and network scale of the two different models are compared.
Thirdly, after analyzing the multiple depot vehicle scheduling problem of urban bus system, the set partitioning model which has taken the departure-duration constraint of buses into consideration is built up based on a time-space network. To solve the model, a branch-and-price-based large neighborhood search algorithm is also designed.
Finally, the set partitioning model and the algorithm are verified by an case. Thé result shows that the branch-and-price-based large neighborhood search algorithm is feasible and effective.
引文
[1]Bodin L, Golden B, Assad A, Ball M. Routing and scheduling of vehicles and crews: The state of the art[J]. Computers and Operations Research, 1983,10(2):63-211.
[2]Bertossi A.A., Carraresi P., Gallo G.. On Some Matching Problems Arising in Vehicle Scheduling Models[J]. Networks, 1987, 17(3):271-281.
[3]Celso C. Ribeiro, Francois Soumis. A Column Generation Approach to the Multiple-depot Vehicle Scheduling Problem[J]. Operations Research, 1994, 42(1):41-52.
[4]Lobel A. Vehicle scheduling in public transit and lagrangean pricing[J]. Management Science, 1998,44(12):1637-1649.
[5]Lobel A. Solving large-scale multiple-depot vehicle scheduling problems[A]. In Computer- aided Transit Scheduling. Lecture Notes in Economics and Mathematical System[C]. Springer-Verlag, 1999,193-220.
[6]Mesquita M. & Paixao J.M.P.. Exact algorithms for the multi-depot vehicle scheduling problem based on multicommodity network flow type formulations[A]. In Computer-aided Transit Scheduling. Lecture Notes in Economics and Mathematical System[C]. Springer-Verlag, 1999, 221-243.
[7]Banihashemi M. & Haghani A.. Optimization model for large-scale bus transit scheduling problems[J]. Transportation Research Record, 2000, 1733:23-30.
[8]Haghani A. & Banihashemi M.. Heuristic approaches for solving large-scale bus transit vehicle scheduling problem with route time constraints[J]. Transportation Research Part A: Policy and Practice,2002,36(4):309-333.
[9]Haghani A. & Banihashemi M.. A comparative analysis of bus transit vehicle scheduling models[J]. Transportation Research Part B:Methodological, 2003,37(4):301-322.
[10]Huisman D., Freling R., Wagelmans A.O.M.. A robust solution approach to the dynamic vehicle scheduling problem[J]. Transportation Science, 2004, 38(4):447-458.
[11]Qukil A., Hatem B.A., Jacques D., Hicham E.G.. Stabilized column generation for highly degenerate multiple-depot vehicle scheduling problems[J]. Computers and Operations Research, 2007,34(3):817-834.
[12]Laurent B., Jin-Kao H.. Iterated local search for the multiple depot vehicle scheduling problem[J]. Computers and Industrial Engineering, 2009, 57(1):227-286.
[13]Kliewer N., Mellouli T., Suhl L.. A new solution model for multi-depot multivehicle-type vehicle scheduling in suburban public transport[A]. In Proceedings of the 13th Mini-EURO Conference and the 9th Meeting of the EUROWoring Group on Transportation[C], Bari, 2002.
[14]Natalia Kliewer, Taieb Mellouli, Leena Suhl. A time-space network based exact optimization model for multi-depot bus scheduling[J]. European Journal of Operational Research, 2005, 175(3):1616-1627.
[15]Vitali Gintner, Natalia Kliewer, Leena Suhl. Solving large multiple-depot multiple-vehicle-type bus scheduling problems in practice[J]. OR Spectrum, 2005, 27(4):507-523.
[16]Naumann M., Leena S., Stefan K.. A stochastic programming approach for robust vehicle scheduling in public bus transport[J]. Procedia-Social and Behavioral Sciences, 2011, 20:826-835.
[17]Zhi-Yuan Chen. The comparison between connection-based network and time-space network on multiple-depot multiple-vehicle-type scheduling problem[D]. National Taiwan University of Science and Technology,2005.
[18]Pepin A.S., Desaulniers G, Hertz A., Huisman D.. Comparison of heuristic approaches for the multiple depot vehicle scheduling problem[OL]. http://hdl.handle.net/1765/8069.
[19]王明仪.车辆调度问题数学方法的新发展[J].公路交通科技,1985,(4)：71—74.
[20]李军.车辆调度问题的分派启发式算法[J].系统工程理论与实践,1999,(1)：27-33.
[21]李军.有时间窗的车辆调度问题的网络启发式算法[J].系统工程,1999,17(2)：66-71.
[22]张飞舟等.智能交通系统中的公交车辆调度方法研究[J].中国公路学报,2003,16(2)：82-85.
[23]童刚.遗传算法在公交调度中的应用研究[J].计算机工程,2005,31(13)：29-31.
[24]沈吟东,夏家宏.公交区域运营模式在我国的应用研究[J].科技进步与对策,2004,21(8)：88-90.
[25]李臻,雷定猷.多车场车辆优化调度模型及算法[J].交通运输工程学报,2004,4(1)：83-86.
[26]钟石泉,贺国光.多车场车辆调度智能优化研究[J].华东交通大学学报,2004,21(6)：25-29.
[27]钟石泉,贺国光.多车场有时间窗的多车型车辆调度及其禁忌算法研究[J].运筹学学报;2005,9(4)：67-73.
[28]杨威.公交区域运营调度系统关键问题研究[D].北京交通大学,2006.
[29]郎茂祥.多配送中心车辆调度问题的模型与算法研究[J].交通运输系统工程与信息,2006,6(5)：65-69.
[30]杨元峰.基于模拟退火遗传算法的多车场车辆调度问题的研究与应用[D].苏州大学,2006.
[31]邹迎.公交区域调度行车计划编制方法研究[J].交通运输系统工程与信息,2007,7(3)：78-82.
[32]方鹤.面向区域的公交调度方法研究[D].河北工业大学,2007.
[33]王海星.公交车辆区域调度理论与方法研究——以电动车为背景[D].北京交通大学,2007.
[34]刘志刚,、申金升,杨威.基于禁忌搜索的公交区域调度配车模型研究[J].交通运输工程与信息学报,2007,5(4)：63-67.
[35]刘志刚.城市公共交通区域运营调度系统协同优化问题研究[D].北京交通大学,2008.
[36]王大勇,臧学运,王海星.公交区域车辆调度优化研究现状与发展[J].北京交通大学学报,2008,32(3)：42-.45.
[37]何迪APTS下公交车辆区域调度问题研究[D].四西南交通大学,2009.
[38]杨智伟,赵骞,赵胜川.基于人工免疫算法的公交车辆调度优化问题研究[J].武汉理工大学学报(交通科学与工程版),2009,33(5)：1004-1007.
[39]孙红,谭笑.遗传算法在车辆调度优化问题中的研究[J].计算机工程与应用,2010,46(24)：246-248.
[40]魏明,靳文舟,孙博.求解区域公交车辆调度问题的蚁群算法研究[J].公路交通科技,2011,28(6)：141—152.
[41]Avishai Ceder. Public Transit Planning and Operation: Theory, Model and Practice[M]关伟等,译.北京：清华大学出版社,2010.
[42]陈阳.基于智能调度系统的公交线路调度优化研究[D].南京林业大学,2009.
[43]黄溅华,关伟,张国伍.公共交通实时调度控制方法研究[J].系统工程学报,2000,15(3)：277-280.
[44]Hane C., Barnhart C., Johnson E.L. et al. The fleet assignment problem: Solving a large integer program[J]. Mathematical Programming, 1995,70(2):211-232.
[45]Mole R.H., Jameson S.R.. A Sequential Route-building Algorithm Employing a Generalised Savings Criterion[J]. Journal of the Operational Research Society, 1976, 27(2): 503-511.
[46]Westerlund A., Gothe-Lundgren M., Larsson T.. A Stabilized Column Generation Scheme for the Traveling Salesman Subtour Problem[J]. Discrete Applied Mathematics, 2006, 154(15): 2212-2238.
[47]赵鹏,张秀媛,孙晚华.管理运筹学[M].北京：清华大学出版社,2008.
[48]段凡丁.关于最短路径的SPFA快速算法[J].西南交通大学学报,1994,29(2)：207-212.
[49]王莹.动车组运用计划和乘务计划的优化方法研究[D].北京交通大学,2009.
[50]Shaw P.. Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems[J]. Proceedings CP-98(Fourth International Conference on Principles and Practice of Constraint Programming), 1998.
[51]Campbell A.M., Savelsbergh M.. Efficient Insertion Heuristics for Vehicle Routing and Scheduling Problems[J]. Transportation Science, 2004, 38(3): 369-378.
[2]Bertossi A.A., Carraresi P., Gallo G.. On Some Matching Problems Arising in Vehicle Scheduling Models[J]. Networks, 1987, 17(3):271-281.
[3]Celso C. Ribeiro, Francois Soumis. A Column Generation Approach to the Multiple-depot Vehicle Scheduling Problem[J]. Operations Research, 1994, 42(1):41-52.
[4]Lobel A. Vehicle scheduling in public transit and lagrangean pricing[J]. Management Science, 1998,44(12):1637-1649.
[5]Lobel A. Solving large-scale multiple-depot vehicle scheduling problems[A]. In Computer- aided Transit Scheduling. Lecture Notes in Economics and Mathematical System[C]. Springer-Verlag, 1999,193-220.
[6]Mesquita M. & Paixao J.M.P.. Exact algorithms for the multi-depot vehicle scheduling problem based on multicommodity network flow type formulations[A]. In Computer-aided Transit Scheduling. Lecture Notes in Economics and Mathematical System[C]. Springer-Verlag, 1999, 221-243.
[7]Banihashemi M. & Haghani A.. Optimization model for large-scale bus transit scheduling problems[J]. Transportation Research Record, 2000, 1733:23-30.
[8]Haghani A. & Banihashemi M.. Heuristic approaches for solving large-scale bus transit vehicle scheduling problem with route time constraints[J]. Transportation Research Part A: Policy and Practice,2002,36(4):309-333.
[9]Haghani A. & Banihashemi M.. A comparative analysis of bus transit vehicle scheduling models[J]. Transportation Research Part B:Methodological, 2003,37(4):301-322.
[10]Huisman D., Freling R., Wagelmans A.O.M.. A robust solution approach to the dynamic vehicle scheduling problem[J]. Transportation Science, 2004, 38(4):447-458.
[11]Qukil A., Hatem B.A., Jacques D., Hicham E.G.. Stabilized column generation for highly degenerate multiple-depot vehicle scheduling problems[J]. Computers and Operations Research, 2007,34(3):817-834.
[12]Laurent B., Jin-Kao H.. Iterated local search for the multiple depot vehicle scheduling problem[J]. Computers and Industrial Engineering, 2009, 57(1):227-286.
[13]Kliewer N., Mellouli T., Suhl L.. A new solution model for multi-depot multivehicle-type vehicle scheduling in suburban public transport[A]. In Proceedings of the 13th Mini-EURO Conference and the 9th Meeting of the EUROWoring Group on Transportation[C], Bari, 2002.
[14]Natalia Kliewer, Taieb Mellouli, Leena Suhl. A time-space network based exact optimization model for multi-depot bus scheduling[J]. European Journal of Operational Research, 2005, 175(3):1616-1627.
[15]Vitali Gintner, Natalia Kliewer, Leena Suhl. Solving large multiple-depot multiple-vehicle-type bus scheduling problems in practice[J]. OR Spectrum, 2005, 27(4):507-523.
[16]Naumann M., Leena S., Stefan K.. A stochastic programming approach for robust vehicle scheduling in public bus transport[J]. Procedia-Social and Behavioral Sciences, 2011, 20:826-835.
[17]Zhi-Yuan Chen. The comparison between connection-based network and time-space network on multiple-depot multiple-vehicle-type scheduling problem[D]. National Taiwan University of Science and Technology,2005.
[18]Pepin A.S., Desaulniers G, Hertz A., Huisman D.. Comparison of heuristic approaches for the multiple depot vehicle scheduling problem[OL]. http://hdl.handle.net/1765/8069.
[19]王明仪.车辆调度问题数学方法的新发展[J].公路交通科技,1985,(4)：71—74.
[20]李军.车辆调度问题的分派启发式算法[J].系统工程理论与实践,1999,(1)：27-33.
[21]李军.有时间窗的车辆调度问题的网络启发式算法[J].系统工程,1999,17(2)：66-71.
[22]张飞舟等.智能交通系统中的公交车辆调度方法研究[J].中国公路学报,2003,16(2)：82-85.
[23]童刚.遗传算法在公交调度中的应用研究[J].计算机工程,2005,31(13)：29-31.
[24]沈吟东,夏家宏.公交区域运营模式在我国的应用研究[J].科技进步与对策,2004,21(8)：88-90.
[25]李臻,雷定猷.多车场车辆优化调度模型及算法[J].交通运输工程学报,2004,4(1)：83-86.
[26]钟石泉,贺国光.多车场车辆调度智能优化研究[J].华东交通大学学报,2004,21(6)：25-29.
[27]钟石泉,贺国光.多车场有时间窗的多车型车辆调度及其禁忌算法研究[J].运筹学学报;2005,9(4)：67-73.
[28]杨威.公交区域运营调度系统关键问题研究[D].北京交通大学,2006.
[29]郎茂祥.多配送中心车辆调度问题的模型与算法研究[J].交通运输系统工程与信息,2006,6(5)：65-69.
[30]杨元峰.基于模拟退火遗传算法的多车场车辆调度问题的研究与应用[D].苏州大学,2006.
[31]邹迎.公交区域调度行车计划编制方法研究[J].交通运输系统工程与信息,2007,7(3)：78-82.
[32]方鹤.面向区域的公交调度方法研究[D].河北工业大学,2007.
[33]王海星.公交车辆区域调度理论与方法研究——以电动车为背景[D].北京交通大学,2007.
[34]刘志刚,、申金升,杨威.基于禁忌搜索的公交区域调度配车模型研究[J].交通运输工程与信息学报,2007,5(4)：63-67.
[35]刘志刚.城市公共交通区域运营调度系统协同优化问题研究[D].北京交通大学,2008.
[36]王大勇,臧学运,王海星.公交区域车辆调度优化研究现状与发展[J].北京交通大学学报,2008,32(3)：42-.45.
[37]何迪APTS下公交车辆区域调度问题研究[D].四西南交通大学,2009.
[38]杨智伟,赵骞,赵胜川.基于人工免疫算法的公交车辆调度优化问题研究[J].武汉理工大学学报(交通科学与工程版),2009,33(5)：1004-1007.
[39]孙红,谭笑.遗传算法在车辆调度优化问题中的研究[J].计算机工程与应用,2010,46(24)：246-248.
[40]魏明,靳文舟,孙博.求解区域公交车辆调度问题的蚁群算法研究[J].公路交通科技,2011,28(6)：141—152.
[41]Avishai Ceder. Public Transit Planning and Operation: Theory, Model and Practice[M]关伟等,译.北京：清华大学出版社,2010.
[42]陈阳.基于智能调度系统的公交线路调度优化研究[D].南京林业大学,2009.
[43]黄溅华,关伟,张国伍.公共交通实时调度控制方法研究[J].系统工程学报,2000,15(3)：277-280.
[44]Hane C., Barnhart C., Johnson E.L. et al. The fleet assignment problem: Solving a large integer program[J]. Mathematical Programming, 1995,70(2):211-232.
[45]Mole R.H., Jameson S.R.. A Sequential Route-building Algorithm Employing a Generalised Savings Criterion[J]. Journal of the Operational Research Society, 1976, 27(2): 503-511.
[46]Westerlund A., Gothe-Lundgren M., Larsson T.. A Stabilized Column Generation Scheme for the Traveling Salesman Subtour Problem[J]. Discrete Applied Mathematics, 2006, 154(15): 2212-2238.
[47]赵鹏,张秀媛,孙晚华.管理运筹学[M].北京：清华大学出版社,2008.
[48]段凡丁.关于最短路径的SPFA快速算法[J].西南交通大学学报,1994,29(2)：207-212.
[49]王莹.动车组运用计划和乘务计划的优化方法研究[D].北京交通大学,2009.
[50]Shaw P.. Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems[J]. Proceedings CP-98(Fourth International Conference on Principles and Practice of Constraint Programming), 1998.
[51]Campbell A.M., Savelsbergh M.. Efficient Insertion Heuristics for Vehicle Routing and Scheduling Problems[J]. Transportation Science, 2004, 38(3): 369-378.