A school bus scheduling problem
A school bus scheduling problem
复制标题
DOI：
10.1016/j.ejor.2011.11.035
复制
发表时间：
2012-04-16
影响因子：
6.4
通讯作者：
Park, Junhyuk
中科院分区：
文献类型：
--
作者：
Kim, Byung-In;Kim, Seongbae;Park, Junhyuk
本文介绍了一个给定每个学校班次的校车调度问题。一次旅行包括一系列的公共汽车站和指定的学校。每所学校都有固定的完成行程的时间窗口。一辆校车可以为多所学校提供多次旅行服务。校车调度问题寻求在考虑学校时间窗口的情况下，优化班车时刻表，以满足所有给定的行程。我们首先将该问题建模为带时间窗的车辆路径问题(VRPTW)，将行程视为一个虚拟的停靠点。然后针对特殊情况提出了两种基于指派问题的精确算法，并针对更一般的情况提出了一种启发式算法。给出了基准问题和计算实验。计算实验表明了所提方法的有效性。(C)2011爱思唯尔B.V.保留所有权利。
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.