Column Generation-based Heuristic Approach for Electric Bus and Driver Scheduling on Single Bus Lines

被引：0
|
作者：
Liu H.-X. [1 ]
Wu A.-F. [1 ]
Long J.-C. [1 ,2 ]
Zhou J. [1 ]
机构：
[1] School of Automotive and Transportation Engineering, Hefei University of Technology, Hefei
[2] Anhui Province Key Laboratory of Industry Safety and Emergency Technology, Hefei University of Technology, Hefei
来源：
Long, Jian-Cheng (jianchenglong@hfut.edu.cn) | 1600年 / Science Press卷 / 21期
基金：
中国国家自然科学基金;
关键词：
Column generation; Constrained shortest path; Electric bus; Integrated scheduling; Time-space network; Urban traffic;
D O I：
10.16097/j.cnki.1009-6744.2021.04.026
中图分类号：
学科分类号：
摘要：
This paper investigates the integrated electric buses and drivers scheduling problem for single bus lines. The trips are assigned to both electric buses and drivers to generate vehicle utilization plan and driver scheduling plan, which considers the range anxiety of electric bus and the constraints of driver's continuous working hours and total working time. The procedure ensures that all trips are covered by vehicle utilization plan and driver schedule plan and the deadhead trip generated by vehicle utilization plan are also covered by driver schedule plan. The column generation based heuristic algorithm is designed to solve the problem, which can be decomposed into a master problem and two pricing subproblems. The master problem determines driver schedules and electric bus routes from the feasible vehicle routes set and driver schedules set and ensure that all trips and deadhead trips generated by vehicle utilization are covered by electric buses and drivers. The pricing subproblem is described as two shortest path problems with resource constraints based on time-space networks to generate feasible vehicle routes and driver schedules. Then the pure diving heuristic approach is used to obtain the integer solution. Three random bus routes in Hefei city are used as examples to test the effectiveness of the proposed algorithm. Copyright © 2021 by Science Press.
引用
收藏
页码：211 / 220
页数：9
相关论文
共 14 条
  • [1] PENG H Q, ZHANG G W., Green traffic and urban sustainable development, Journal of Transportation Systems Engineering and Information Technology, 38, 11, pp. 1-6, (2018)
  • [2] FRELING R, WAGELMANS A P M, PAIO J M P., An overview of models and techniques for integrating vehicle and crew scheduling, Computer-Aided Transit Scheduling, pp. 441-460, (1999)
  • [3] HUISMAN D, FRELING R, WAGELMANS A P M., Multiple-depot integrated vehicle and crew scheduling, Transportation Science, 39, 4, pp. 491-502, (2005)
  • [4] STEINZEN I, GINTNER V, KLIEWER N, Et al., A time-space network approach for the integrated vehicle and crew scheduling problem with multiple depots, Transportation Science, 44, 3, pp. 367-382, (2010)
  • [5] TANG C Y, YANG K Q, WU N., Optimizing flexible vehicle scheduling for single-line battery electric buses, Journal of Transportation Systems Engineering and Information Technology, 20, 3, pp. 156-162, (2020)
  • [6] LI J Q., Transit bus scheduling with limited energy, Transportation Science, 48, 4, pp. 521-539, (2016)
  • [7] YANG Y, GUAN W, MA J H., Battery electric transit bus scheduling problem based on column generation approach, Journal of Transportation Systems Engineering and Information Technology, 16, 5, pp. 198-204, (2016)
  • [8] DESROCHERS M, SOUMIS F., A column generation approach to the urban transit crew scheduling problem, Transportation Science, 23, 1, pp. 1-13, (1989)
  • [9] LIN D Y, HSU C L., A column generation algorithm for the bus driver scheduling problem, Journal of Advanced Transportation, 50, 8, pp. 1598-1615, (2016)
  • [10] CHEN M M, NIU H M., An optimization model for bus crew scheduling with multiple depots, Journal of Transportation Systems Engineering and Information Technology, 13, 5, pp. 159-166, (2013)
12