第 39 卷 第 8 期
2013 年 8 月
北 京 工 业 大 学 学 报
JOURNAL OF BEIJING UNIVERSITY OF TECHNOLOGY
Vol. 39 No. 8
Aug. 2013
求解多目标区域公交车辆调度问题的遗传算法
魏摇 明
1
, 靳文舟
2
, 孙摇 博
1
(1. 南通大学 交通学院, 江苏 南通摇 226019; 2. 华南理工大学 土木与交通学院, 广州摇 510640)
摘摇 要: 将区域公交车辆调度(RBSP)视为“部分班次被某车辆完成冶的集合划分问题,考虑站场容量、补充燃料和
返回站场最迟时间限制等约束因素,建立一类追求车辆利用效率和公交车辆调度方案的可靠度极大化的多目标混
合整数规划模型. 用约束法将该模型转为单目标规划问题,利用遗传算法求解该问题的非劣解. 研究表明:公交调
度方案的可靠性越高,车辆利用率越低.
关键词: 公交调度区域; 多目标; 可靠度; 遗传算法
中图分类号: U 491郾 3; U 492郾 8 文献标志码: A 文章编号: 0254 - 0037(2013)08 - 1244 - 06
Genetic Algorithm for Multi鄄Objective Regional Bus Scheduling Problem
WEI Ming
1
, JIN Wen鄄zhou
2
, SUN Bo
1
(1. School of Transportation, Nantong University, Nantong 226019, Jiangsu, China;
2. School of Civil Engineering and Transportation, South China University of Technology, Guangzhou 510640, China)
Abstract: Regional bus scheduling, treated as a “part of trips completed by a vehicle冶 set鄄partitioning
problem, ould be formulated as a multi鄄objective mixed integer programming model, where some side
constraints such as depots capacities, fuelling and the latest time of going back to depot were considered.
The previous objective was to maximize vehicle utilization for all buses, and the secondary objective was
to maximize reliability of scheduling plans. Before the model蒺s non鄄inferior solutions were obtained by
genetic algorithm, it was converted into a single objective programming problem with constraint method.
Finally, an example shows that the high reliability of schemes become, the less vehicle utilization will
get.
Key words: regional bus scheduling; multi鄄objective; reliability; genetic algorithm
收稿日期: 2011鄄09鄄30.
基金项目: 国家“863冶计划资助项目(2007AA11Z201);国家自然科学基金资助项目(61174188);华南理工大学中央高校基本
科研业务费资助项目(2012ZM0092).
作者简介: 魏摇 明(1984—),男,讲师,主要从事公交优化调度模型和算法等方面的研究,E鄄mail: mingtian911@ 163. com.
摇 摇 区 域 公 交 车 辆 调 度 ( regional bus scheduling
problem, 简称 RBSP)
[1]
是未来城市公共交通的发
展趋势, 为当前公交优化研究热点之一. 与单线公
交车调度相比,RBSP 根据不同线路在同一时段上
发车频率的不均衡性,通过各站场之间插入可行空
驶班次,统一合理安排分布不同车场所有车辆,在满
足所有线路时刻表对应班次任务的用车需求基础上
提高车辆利用效率,从而显著减少车队规模和降低
营运成本. 文献[2]研究表明 RBSP 是一个 NP鄄hard
问题难题.
目前,国内外学者主要从构建基于“班次节点冶
的最大网络流问题
[2鄄10]
和“部分班次被某辆车完成冶
的集 合划 分 问 题
[11鄄13]
的 混 合 整 数 规 划 模 型 解 决
RBSP,相关文献研究静态 RBSP 已经取得了一定成
果
[3鄄9,11]
,而鲜少涉及动态 RBSP
[10,12]
,仅文献[10]
探讨了一种在未来旅行时间固定或提前被预知假设
情形下的动态 RBSP, 文献[12] 研究了一类随机旅
行时 间 的 动 态 RBSP. 然 而, 上 述 研 究 均 未 涉 及
资源评论
