一种基于学校上学时间调整的校车调度算法

被引：5

作者：

陈小潘 ^{[1
,2
]}

孔云峰 ^{[1
]}

牛宁 ^{[1
]}

侯彦娥 ^{[1
,2
]}

谢毅 ^{[1
,2
]}

机构：

[1] 河南大学黄河中下游数字地理技术教育部重点实验室

[2] 河南大学计算机与信息工程学院

来源：

小型微型计算机系统 | 2015年 / 36卷 / 09期

关键词：

校车路径问题; 校车调度问题; 上学时间调整; 优化算法;

D O I：

暂无

中图分类号：

U492.22 [];

学科分类号：

082302 ; 082303 ;

摘要：

在给定单校校车路径的基础上,校车调度问题是在满足学校上学时间约束下寻找服务所有路径的最优校车安排.而上学时间的设置对调度的效果有直接影响,目前基于学校上学时间调整的校车调度大多以精确求解方法为主,在大规模案例上求解质量相对较低.针对该问题,设计了一个两阶段启发式求解算法.第一阶段以服务所有路径所需校车数量为优化目标,通过应用构造启发式算法选择学校上学时间;第二阶段在模拟退火算法框架下,使用VRP局部搜索算子求解学校上学时间固定的校车调度问题.模拟实验基于已有校车路径问题的测试案例,结果表明相对于精确求解方法,该算法显著降低了校车数量,能够获得较好的校车路径规划方案.

引用

页码：2159 / 2165

页数：7

共 9 条

[1] 一种求解大规模校车调度问题的元启发式算法 [J].

陈小潘 ;

党兰学 ;

孔云峰 .

地球信息科学学报, 2013, 15 (06) :879-886

[2] 一种求解混载校车路径的启发式算法 [J].

党兰学 ;

王震 ;

刘青松 ;

孔云峰 .

计算机科学, 2013, 40 (07) :248-253

[3]

A school bus scheduling problem [J] . Byung-In Kim,Seongbae Kim,Junhyuk Park.&nbsp&nbspEuropean Journal of Operational Research . 2011 (2)

[4]

A post-improvement procedure for the mixed load school bus routing problem [J] . Junhyuk Park,Hyunchul Tae,Byung-In Kim.&nbsp&nbspEuropean Journal of Operational Research . 2011 (1)

[5]

The school bus routing problem: A review [J] . Junhyuk Park,Byung-In Kim.&nbsp&nbspEuropean Journal of Operational Research . 2009 (2)

[6]

Solving a school bus scheduling problem with integer programming [J] . Armin Fügenschuh.&nbsp&nbspEuropean Journal of Operational Research . 2007 (3)

[7] A multicriteria approach for optimizing bus schedules and school starting times [J].

Fuegenschuh, Armin ;

Martin, Alexander .

ANNALS OF OPERATIONS RESEARCH, 2006, 147 (01) :199-216

[8]

A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows [J] . Russell Bent,Pascal Van Hentenryck.&nbsp&nbspComputers and Operations Research . 2005 (4)

[9] A computerized approach to the New York City school bus routing problem [J].

Braca, J ;

Bramel, J ;

Posner, B ;

SimchiLevi, D .

IIE TRANSACTIONS, 1997, 29 (08) :693-702

← 1 →