A school bus scheduling problem

被引：62

作者：

Kim, Byung-In ^{[1
]}

Kim, Seongbae ^{[2
]}

Park, Junhyuk ^{[2
]}

机构：

[1] Pohang Univ Sci & Technol POSTECH, Dept Ind & Management Engn, Pohang 790784, Kyungbuk, South Korea

[2] Inst Informat Technol Inc, Magnolia, TX 77354 USA

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 2012年 / 218卷 / 02期

关键词：

Heuristics; School bus routing problem; Bus scheduling problem; Vehicle routing problem; Assignment problem; TIME WINDOWS; VEHICLE; HEURISTICS;

D O I：

10.1016/j.ejor.2011.11.035

中图分类号：

C93 [管理学];

学科分类号：

120117 [社会管理工程];

摘要：

This paper introduces a school bus scheduling problem wherein trips for each school are given. A trip consists of a sequence of bus stops and their designated school. Each school has its fixed time window within which trips should be completed. A school bus can serve multiple trips for multiple schools. The school bus scheduling problem seeks to optimize bus schedules to serve all the given trips considering the school time windows. We first model the problem as a vehicle routing problem with time windows (VRPTW) by treating a trip as a virtual stop. Two assignment problem based exact approaches are then proposed for special cases and a heuristic algorithm is proposed for more general cases. Benchmark problems and computational experiments are presented. Computational experiments show the effectiveness of the proposed approaches. (C) 2011 Elsevier B.V. All rights reserved.

引用

页码：577 / 585

页数：9

共 24 条

[1]

[Anonymous], 1998, COMBINATORIAL OPTIMI

[2]

Bodin L. D., 1979, Transportation Science, V13, P113, DOI 10.1287/trsc.13.2.113

[3]

Bodin L.D., 1975, Computers and Urban Society, V1, P11, DOI 10.1016/0305-7097(75)90003-4

[4]

Braca J, 1997, IIE TRANS, V29, P693, DOI 10.1080/07408179708966379