Optimizing Single-Depot Vehicle Scheduling Problem: Fixed-Interval Model and Algorithm

摘要

Intelligent transportation systems (ITS) play an important role in public transit. This study addresses modeling and algorithm for the optimal single-depot vehicle scheduling problem (SDVSP) in the intelligent public transit operation, which has been implemented successfully in practice. The problem is formulated as a fixed-interval scheduling model in accord with job shop scheduling theory, which aims to assign ideal jobs to machines at appropriate times to maximize production in computer science or industrial engineering. This model allows transportation engineers to make use of those out-of-the-box theories and solution methods already developed for fixed-interval scheduling problems. In this article, the SDVSP with multiple vehicle types is established as a non-preemptive online multiprocessor-task fixed-interval scheduling model. As conventional solution methods for solving fixed interval scheduling problems are no longer available for the proposed model, this article develops the algorithm based on the FIFO (first in, first out) rule to find the optimal vehicle scheduling solution, and the optimal criterion is proved via competitive analysis. A case study is carried out to evaluate the proposed methodology by using field data collected from one transit system.