Volume 39 Issue 3
Jun.  2021
Turn off MathJax
Article Contents
Article Navigation >  Journal of Transport Information and Safety  > 2021  >  39(3): 50-59
KONG Yunfeng. A Metaheuristic Algorithm for Multi-objective Transit Bus and Driver Scheduling Problems[J]. Journal of Transport Information and Safety, 2021, 39(3): 50-59. doi: 10.3963/j.jssn.1674-4861.2021.03.007
Citation: KONG Yunfeng. A Metaheuristic Algorithm for Multi-objective Transit Bus and Driver Scheduling Problems[J]. Journal of Transport Information and Safety, 2021, 39(3): 50-59. doi: 10.3963/j.jssn.1674-4861.2021.03.007
shu

A Metaheuristic Algorithm for Multi-objective Transit Bus and Driver Scheduling Problems

doi: 10.3963/j.jssn.1674-4861.2021.03.007

  • Key Laboratory of Geospatial Technology for the Middle and Lower Yellow River Regions of Ministry of Education, Henan University, Kaifeng 475000, Henan, China

  • Received Date: 2020-10-14
    Abstract
  • This article introduces a metaheuristic algorithm for multi-objective transit bus and driver scheduling problems, such as fuel or electronic vehicles, single route/multiple routes, and driving the same bus on the same day in most transit companies in China.The work aims to minimize the fixed bus cost, the bus travel cost, the fixed driver cost, and the allowance for drivers and to satisfy various operational rules on vehicles and drivers.The algorithm starts from an initial solution and iteratively improves the solution by local search and perturbation.It is also enhanced by two search strategies such as population-based search and variable neighborhood decent search.The performance of the proposed algorithm is tested on 62 single-route instances and 11 multi-route instances.There are three important findings for transit operations in China from the experimentation.Electronic vehicles may replace fuel buses by increasing 0.8% and 1.6% vehicles for single-route and multi-route instances, respectively.Compared with single-route scheduling, multi-route scheduling has the potentials to reduce 4.6% of vehicles and 2.4% of drivers.If the drivers are allowed to drive different buses in their daily works, the number of vehicles required can be reduced significantly, especially for the single-route instances.The general-purpose metaheuristic algorithm in the work is essential for developing intelligent public transit systems in China.

     

    • FullText(HTML)
  • loading
    • References(18)
  • [1]
    CEDER A, WILSON N H M. Bus network design[J]. Transportation Research Part B: Methodological, 1986(20): 331-344. http://citec.repec.org/d/eee/transb/v_20_y_1986_i_4_p_331-344.html
    [2]
    KEPAPTSOGLOU K, KARLAFTIS M G. Transit Route network design problem: review[J]. Journal of Transportation Engineering, 2009, 135(8): 491-505. doi: 10.1061/(ASCE)0733-947X(2009)135:8(491)
    [3]
    PINE R. NIEMEYER J, CHISHOLM R. Transit scheduling: Basic and advanced manuals[R]. Washington, D. C. : World Transit Research, 1998.
    [4]
    National Academies of Sciences, Engineering, and Medicine. Controlling system costs: basic and advanced scheduling manuals and contemporary issues in transit scheduling[M]. Washington, D. C. : The National Academies Press, 2009.
    [5]
    LOURENCO H R, PAIXAO J M, PORTUGAL R, et al. Multiobjective metaheuristics for the bus driver scheduling problem[J]. Transportation Science, 2001, 35(3): 331-343. doi: 10.1287/trsc.35.3.331.10147
    [6]
    DE LEONE R, FESTA P, MARCHITTO E, et al. A bus driver scheduling problem: a new mathematical model and a GRASP approximate solutionJ]. Journal of Heuristics, 2011, 17(4): 441-466. doi: 10.1007/s10732-010-9141-3
    [7]
    LIN D, HSU C. A column generation algorithm for the bus driver scheduling problem[J]. Journal of Advanced Transportation, 2016, 50(8): 1598-1615. doi: 10.1002/atr.1417
    [8]
    VALOUXIS C, HOUSOS E. Combined bus and driver scheduling[J]. Computers & Operations Research, 2002, 29(3): 243-259. http://www.sciencedirect.com/science/article/pii/S0305054800000678
    [9]
    魏明, 靳文舟, 孙博. 求解区域公交车辆调度问题的蚁群算法研究[J]. 公路交通科技, 2011, 28(6): 141-145. doi: 10.3969/j.issn.1002-0268.2011.06.023

    WEI Ming, JIN Wenzhou, SUN Bo. Ant colony algorithm for regional bus scheduling problem[J]. Journal of Highway and Transportation Research and Development, 2011, 28(6): 141-145. (in Chinese) doi: 10.3969/j.issn.1002-0268.2011.06.023
    [10]
    李一凡, 杨友磊. 基于整数规划的多车场多车型公交车辆调度问题研究[J]. 综合运输, 2019, 41(12): 61-66. https://www.cnki.com.cn/Article/CJFDTOTAL-YSZH201912013.htm

    LI Yifan, YANG Youlei. Multiple depots and types bus scheduling problems based on integer programming[J]. China Transportation Review, 2019, 41(12): 61-66. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-YSZH201912013.htm
    [11]
    姚恩建, 卢沐阳, 刘宇环, 等. 考虑充电约束的电动公交区域行车计划编制[J]. 华南理工大学学报(自然科学版), 2019, 47(9): 68-73. https://www.cnki.com.cn/Article/CJFDTOTAL-HNLG201909011.htm

    YAO Enjian, LU Muyang, LIU Yuhuan, et al. Electric bus area driving plan preparation considering charging constraints[J]. Journal of South China University of Technology(Natural Science Edition), 2019, 47(9): 68-73. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-HNLG201909011.htm
    [12]
    滕靖, 林琳, 陈童. 纯电动公交时刻表和车辆排班计划整体优化[J]. 同济大学学报(自然科学版), 2019, 47(12): 1748-1755. doi: 10.11908/j.issn.0253-374x.2019.12.009

    TENG Jing, LIN Lin, CHEN Tong. Optimizing the combination of timetable and vehicle scheduling for pure electric buses[J]. Journal of Tongji University(Natural Science), 2019, 47(12): 1748-1755. (in Chinese) doi: 10.11908/j.issn.0253-374x.2019.12.009
    [13]
    唐春艳, 杨凯强, 邬娜. 单线纯电动公交车辆柔性调度优化[J]. 交通运输系统工程与信息, 2020, 20(3): 156-162. https://www.cnki.com.cn/Article/CJFDTOTAL-YSXT202003025.htm

    TANG Chunyan, YANG Kaiqiang, WU Na. Optimizing flexible vehicle scheduling for single-line battery electric buses[J]. Journal of Transportation Systems Engineering and Information Technology, 2020, 20(3): 156-162. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-YSXT202003025.htm
    [14]
    刘涛. 公交驾驶员排班与轮班问题的模型与算法研究[D]. 北京: 北京交通大学, 2013.

    LIUTao. Models and algorithms for bus driver run cutting and rostering[D]. Beijing: Beijing Jiaotong University, 2013. (in Chinese)
    [15]
    陈明明, 牛惠民. 多车场公交乘务排班问题优化[J]. 交通运输系统工程与信息, 2013, 13(5): 159-166. https://www.cnki.com.cn/Article/CJFDTOTAL-YSXT201305024.htm

    Chen Mingming, NIU Huimin. An optimization model for bus crew scheduling with multiple depots[J]. Journal of Transportation Systems Engineering and Information Technology, 2013, 13(5): 159-166. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-YSXT201305024.htm
    [16]
    陈程. 基于多目标优化算法的公交车辆调度研究[D]. 北京: 北京邮电大学, 2014.

    CHENCheng. The research on vehicle scheduling problem based on multi-objective optimization algorithms[D]. Beijing: Beijing University of Posts and Telecommunications, 2014. (in Chinese)
    [17]
    陈明明. 城市公共交通乘务调度优化理论和方法[D]. 兰州: 兰州交通大学, 2016.

    CHEN Mingming. Theory and method for crew scheduling problem of urban public Transport[D]. Lanzhou: Lanzhou Jiaotong University, 2016. (in Chinese)
    [18]
    侯彦娥, 孔云峰, 朱艳芳等. 公交司机排班问题的混合元启发算法研究[J]. 交通运输系统工程与信息, 2018, 18(1): 133-138. https://www.cnki.com.cn/Article/CJFDTOTAL-YSXT201801021.htm

    HOU Yane, KONG Yunfeng, ZHU Yanfang, et al. A hybrid metaheuristic algorithm for the transit bus and driver scheduling problem[J]. Journal of Transportation Systems Engineering and Information Technology, 2018, 18(1): 133-138. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-YSXT201801021.htm
    • Relative Articles
    • Supplements(0)
    • Cited By
  • 加载中

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Figures(1)  / Tables(7)

    Get Citation
    PDF
    XML

    Article Metrics

    Article views (435) PDF downloads(24) Cited by()
    Proportional views
    Related

    Copyright Editorial Office of Transport Information and Safety鄂ICP备05003336号-2

    Address：No. 1178，Heping Avenue, Wuchang, Wuhan, CHINA (430063)

    Tel：027-86580355 Email：jtjsj@vip.163.com

    Supported by: Beijing Renhe Information Technology Co. Ltd  

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return