Fixed Interval Scheduling Formulation of Single-Depot t Vehicle Assignment for Public Transit in China

摘要

Transit vehicle scheduling plays an important role in APTS (Advanced PublicTransportation System). This article investigates the fixed interval schedulingformulation of single-depot vehicle scheduling problem (SDVSP) for public transit. Thefixed interval scheduling problem is an optimization problem of assigning ideal jobs tomachines at appropriate times to maximize production in computer science and industrialengineering. Formulating the transit vehicle assignment problem to the fixed intervalscheduling problem allows transportation engineers to make use of those out-of-the-boxtheories and solution methods already developed for fixed interval scheduling problem.In this paper, transit vehicle scheduling process is re-formulated to fit the fixed intervalscheduling model in job shop scheduling theory. Four different cases are consideredcorresponding to various realistic conditions of vehicle assignment. The SDVSP withmultiple vehicle types is formulated as a non-preemptive online multiprocessor-task fixedinterval scheduling model. To solve the proposed model, the FIFO (First In, First Out)rule is introduced and proved to be the optimal criterion via competitive analysis, thus agreedy algorithm based on FIFO rule is proposed. The algorithm is demonstrated usingfield data collected from some routes scheduling at Shijiazhuang, the Capital of HebeiProvince in China. The optimal solution obtained by SDVSP model provides bettervehicle usage, operating efficiency while maintaining the same level of service comparedwith the outcome of the actual vehicle scheduling.