基于列生成启发式的单线电动公交车与司机整合调度优化

doi:10.16097/j.cnki.1009-6744.2021.04.026

交通运输系统工程与信息 ›› 2021, Vol. 21 ›› Issue (4): 211-220.DOI: 10.16097/j.cnki.1009-6744.2021.04.026

基于列生成启发式的单线电动公交车与司机整合调度优化

刘昊翔^a，吴啊峰^a，龙建成^{*a, b}，周珏^a

合肥工业大学，a. 汽车与交通工程学院；b. 工业安全与应急技术安徽省重点实验室，合肥 230009

收稿日期:2021-04-13 修回日期:2021-06-02 接受日期:2021-06-11 出版日期:2021-08-25 发布日期:2021-08-23
作者简介:刘昊翔(1987- )，女，山东平度人，副研究员，博士。
基金资助:
国家自然科学基金;中央高校基本科研业务费专项资金

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

LIU Hao-xiang^a , WU A-feng^a , LONG Jian-cheng^{* a, b}, ZHOU Jue^a

a. School of Automotive and Transportation Engineering; b. Anhui Province Key Laboratory of Industry Safety and Emergency Technology, Hefei University of Technology, Hefei 230009, China

Received:2021-04-13 Revised:2021-06-02 Accepted:2021-06-11 Online:2021-08-25 Published:2021-08-23
Supported by:
National Natural Science Foundation of China(71801067, 71925001)； Fundamental Research Funds for Central Universities(JZ2020HGTB0026)。

摘要/Abstract

摘要： 在考虑电动公交车里程约束与司机连续工作时间和总工作时间约束的基础上，研究单条公交线路的电动公交车与司机整合调度问题，即将给定时刻表车次分配给电动公交车和司机，同时，生成车辆运营计划和司机排班计划，设计基于列生成启发式方法求解提出的整合调度问题。列生成方法用于生成线性松弛最优解，将整个问题分解为一个主问题和两个定价子问题。其中，主问题从可行车辆行车路径集合和司机车次链集合中选择最优的司机车次链和电动公交车行车路径，覆盖所有车次，并保证车辆运营计划产生的空驶弧都被司机排班计划覆盖；定价子问题描述两个基于时空网络的资源约束最短路问题，分别用于生成可行的车辆路径和司机车次链，并设计深浅算法得到整数可行解。使用合肥市3条公交线路随机生成算例检验提出算法的有效性。

关键词: 城市交通, 整合调度, 列生成算法, 电动公交车, 时空网络, 资源约束最短路

Abstract: 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.

Key words: urban traffic, integrated scheduling, column generation, electric bus, time- space network, constrained shortest path

中图分类号:

U121

刘昊翔, 吴啊峰, 龙建成, 周珏. 基于列生成启发式的单线电动公交车与司机整合调度优化[J]. 交通运输系统工程与信息, 2021, 21(4): 211-220.

LIU Hao-xiang , WU A-feng , LONG Jian-cheng, ZHOU Jue. Column Generation-based Heuristic Approach for Electric Bus and Driver Scheduling on Single Bus Lines[J]. Journal of Transportation Systems Engineering and Information Technology, 2021, 21(4): 211-220.

导出引用管理器 EndNote|Ris|BibTeX

链接本文: http://www.tseit.org.cn/CN/10.16097/j.cnki.1009-6744.2021.04.026

http://www.tseit.org.cn/CN/Y2021/V21/I4/211

参考文献

[1] 彭宏勤, 张国伍. 绿色交通和城市的可持续发展[J]. 交通运输系统工程与信息, 2018, 38(11): 1-6. [PENG H Q, ZHANG G W. Green traffic and urban sustainable development[J]. Journal of Transportation Systems Engineering and Information Technology, 2018, 38(11): 1-6.]

[2] FRELING R, WAGELMANS A P M, PAIO J M P. An overview of models and techniques for integrating vehicle and crew scheduling[C]. Computer-Aided Transit Scheduling, 1999: 441-460.

[3] HUISMAN D, FRELING R, WAGELMANS A P M. Multiple-depot integrated vehicle and crew scheduling [J]. Transportation Science, 2005, 39(4): 491-502.

[4] STEINZEN I, GINTNER V, KLIEWER N, et al. A timespace network approach for the integrated vehicle and crew scheduling problem with multiple depots[J]. Transportation Science, 2010, 44(3): 367-382.

[5] 唐春艳, 杨凯强, 邬娜. 单线纯电动公交车辆柔性调度优化[J]. 交通运输系统工程与信息, 2020, 20(3): 156- 162. [TANG C Y, YANG K Q, WU N. Optimizing flexible vehicle scheduling for single-line battery electric buses[J]. Journal of Transportation Systems Engineering and Information Technology, 2020, 20(3): 156-162.]

[6] LI J Q. Transit bus scheduling with limited energy[J]. Transportation Science, 2016, 48(4): 521-539.

[7] 杨扬, 关伟, 马继辉. 基于列生成算法的电动公交车辆调度计划优化研究[J]. 交通运输系统工程与信息, 2016, 16(5): 198- 204. [YANG Y, GUAN W, MA J H. Battery electric transit bus scheduling problem based on column generation approach[J]. Journal of Transportation Systems Engineering and Information Technology, 2016, 16(5): 198-204.]

[8] DESROCHERS M, SOUMIS F. A column generation approach to the urban transit crew scheduling problem [J]. Transportation Science, 1989, 23(1): 1-13.

[9] LIN D Y, HSU C L. A column generation algorithm for the bus driver scheduling problem[J]. Journal of Advanced Transportation, 2016, 50(8): 1598-1615.

[10] 陈明明, 牛惠民. 多车场公交乘务排班问题优化[J]. 交通运输系统工程与信息, 2013, 13(5): 159-166. [CHEN M M, NIU H M. An optimization model for bus crew scheduling with multiple depots[J]. Journal of Transportation Systems Engineering and Information Technology, 2013, 13(5): 159-166.]

[11] 侯彦娥, 孔云峰, 朱艳芳, 等. 公交司机排班问题的混合元启发算法研究[J]. 交通运输系统工程与信息, 2018, 18(1): 133-138. [ HOU Y E, KONG Y F, ZHU Y F, 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.]

[12] SADYKOV R, VANDERBECK F, PESSOA A, et al. Primal heuristics for branch- and-price: The assets of diving methods[J]. Journal of the Royal Statal Society, 2018, 175(2): 435-451.

[13] KLIEWER N, MELLOULI T, SUHL L. A time-space network based exact optimization model for multi- depot bus scheduling[J]. European Journal of Operational Research, 2006, 175(3): 1616-1627.

[14] LOZANO L, DUQUE D, MEDAGLIA A L. An exact algorithm for the elementary shortest path problem with resource constraints[J]. Transportation Science, 2016, 50 (1): 348-357.

[1]	刘晓冰, 李奉孝, 田欣妹, 闫学东. 基于通勤模式的都市圈中心结构判别研究[J]. 交通运输系统工程与信息, 2022, 22(2): 17-28.
[2]	许奇, 陈越, 黄靖茹, 高顺祥, 张志健. 考虑出行费用的就业可达性分析[J]. 交通运输系统工程与信息, 2022, 22(2): 37-44.
[3]	刘春禹, 刘永红, 罗霞, 朱颖. 混合交通流环境下单交叉口自动驾驶车辆轨迹优化[J]. 交通运输系统工程与信息, 2022, 22(2): 154-162.
[4]	张小雨, 邵春福, 王博彬, 黄士琛. 新冠疫情影响下居民共享出行方式选择行为研究[J]. 交通运输系统工程与信息, 2022, 22(2): 186-196.
[5]	李欣, 戴章, 李怀悦, 胡笳. 基于连续近似模型的轨道交通与常规公交耦合优化设计[J]. 交通运输系统工程与信息, 2022, 22(2): 206-213.
[6]	郝妍熙, 刘戎阳, 胡华, 方勇, 刘志钢. 单向通道行人-自行车混合流建模及自组织现象研究[J]. 交通运输系统工程与信息, 2022, 22(2): 223-229.
[7]	赵传林, 贺少松, 孙淑敏, 王钰涵. 基于理性疏忽理论的交通疏散网络双层优化模型[J]. 交通运输系统工程与信息, 2022, 22(2): 239-246.
[8]	陈小红, 蓝秋雨. 不确定交通需求下交叉口信号配时区间优化模型[J]. 交通运输系统工程与信息, 2022, 22(2): 247-256.
[9]	李冰, 王正辉, 马铭炜, 杨鸿宇, 冯悦. 信号交叉口行人二次过街下右转车通行能力与延误估计模型[J]. 交通运输系统工程与信息, 2022, 22(2): 257-267.
[10]	朱彤, 秦丹, 董傲然, 杜雨萌, 魏雯. 公交驾驶员违规类型同交通事故间的关联分析[J]. 交通运输系统工程与信息, 2022, 22(2): 322-329.
[11]	毛保华, 王敏, 何天健, 陈海波. 城市公共交通服务水平研究回顾和展望[J]. 交通运输系统工程与信息, 2022, 22(1): 2-13.
[12]	王子甲, 贾慧慧, 朱亚迪, 陈峰. 基于智能卡数据的轨道与公交复合网络通勤方式选择行为研究[J]. 交通运输系统工程与信息, 2022, 22(1): 67-73.
[13]	贾斌, 朱凌, 李树凯, 刘家林. 城市轨道交通小交路计划与客流控制协同优化策略[J]. 交通运输系统工程与信息, 2022, 22(1): 124-132.
[14]	牟振华, 汪寒冰, 林本江, 陈逸群, 金程程, 陈艳艳. 基于演化博弈的违章停车动态罚金策略效用仿真评价[J]. 交通运输系统工程与信息, 2022, 22(1): 152-162.
[15]	贾富强, 李引珍, 杨信丰, 马昌喜, 代存杰. 基于演化博弈的政府鼓励条件下共享停车行为分析[J]. 交通运输系统工程与信息, 2022, 22(1): 163-170.

基于列生成启发式的单线电动公交车与司机整合调度优化

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics