交通运输系统工程与信息

交通运输系统工程与信息 ›› 2016, Vol. 16 ›› Issue (5): 198-204.

• 系统工程理论与方法 • 上一篇    下一篇

基于列生成算法的电动公交车辆调度计划优化研究

杨扬，关伟*，马继辉   

  1. 北京交通大学城市交通复杂系统理论与技术教育部重点实验室，北京100044
  • 收稿日期:2016-03-28 修回日期:2016-05-10 出版日期:2016-10-25 发布日期:2016-10-25
  • 作者简介:杨扬（1985-），男，河北张家口人，博士生.
  • 基金资助:

    国家重点基础研究发展规划项目/National Key Basic Research Program of China (2012CB725403-5).

Battery Electric Transit Bus Scheduling Problem Based on Column Generation Approach

YANG Yang, GUANWei , MAJi-hui   

  1. MOE Key Laboratory for Urban Transportation Complex Systems Theory and Technology, Beijing Jiaotong University, Beijing 100044, China
  • Received:2016-03-28 Revised:2016-05-10 Online:2016-10-25 Published:2016-10-25

PDF

被引次数

9

摘要：

在公交运营规划过程中，公交车辆计划问题是编制时刻表和调度驾驶员的连接纽带，是公交运营规划过程中的关键问题.相对于传统公交车，电动公交车具有绿色环保，运营里程短，充电资源少等特点.在运营规划方面，电动公交车车辆计划模型约束多，计算难度大.本文应用整数规划，网络流等基本理论，将车次任务，公交场站，充电站作为节点，将车次间的空驶作为边，把电动公交车的车辆计划问题转化为网络模型.在网络模型的基础上应用列生成方法，对电动公交的车辆计划问题进行求解.在实验部分，将列生成算法分别应用于随机生成数据和实际数据.实验结果中，列生成算法结果相比现在使用方案最多节省了1 辆电动车，成本优化最高为8.3%，表明列生成算法在求解电动公交车辆计划问题时效率高，优化结果较好.

关键词: 智能交通, 电动公交车调度, 列生成, 整数规划, 电动车充电

Abstract:

As the key problem in the process of public transit planning, bus scheduling is the connection of timetabling and driver rostering. Compared with traditional bus, the battery electric (BE) transit bus is environmental and short mileage. From the planning point of view, the new characteristics of BE bus brings challenges to the traditional planning method. In this paper, the depot, recharge station and trips are regarded as points, the deadheading between points are regarded as arcs, we formulate the BE bus schedule as a directed network. A tailed column generation approach is employed to solve the BE scheduling problem. Both random and actual data sets are used to test our approach, the results show that the tailed column generation approach performs well in solving the BE scheduling problem.

Key words: intelligent transportation, battery electric bus scheduling, column generation, integer programming, battery recharging

中图分类号: