Scheduling of vehicles and crews, traditionally performed sequentially by scheduling vehicles prior to crews, has to be carried out simultaneously in particular settings such as the ex-urban mass transit. This is one of the first few papers dealing with the integrated scheduling of vehicles and crews, and the first to focus on the ex-urban case. Here, crews are tighly dependent on vehicles activities, and crews deadheadings are highly constrained. In this paper, we present a MILP model for the problem and propose an integrated approach to vehicle and crew scheduling which exploits the network structure of the problem. A heuristic method based on lagrangean relaxation is presented, which detrmines a set of pieces of work suitable for both vehicles activities as well as for crew duties. Crew duties are fixed step by step while vehicles are scheduled once all the trips have been partitioned into pieces of work. Extended use is made of Bundle methods taylored for the optimization of polyhedral functions, resource constrained shortest paths algortihms, and dual gredy heuristics for the set partitioning problem. Computational results are provided for an Italian public transit operator which show the improvements w.r.t. the sequential approach for the ex-urban instances.
Models and algorithms for vehicles and crew scheduling in ex-urban mass transit
NONATO, Maddalena;
1999
Abstract
Scheduling of vehicles and crews, traditionally performed sequentially by scheduling vehicles prior to crews, has to be carried out simultaneously in particular settings such as the ex-urban mass transit. This is one of the first few papers dealing with the integrated scheduling of vehicles and crews, and the first to focus on the ex-urban case. Here, crews are tighly dependent on vehicles activities, and crews deadheadings are highly constrained. In this paper, we present a MILP model for the problem and propose an integrated approach to vehicle and crew scheduling which exploits the network structure of the problem. A heuristic method based on lagrangean relaxation is presented, which detrmines a set of pieces of work suitable for both vehicles activities as well as for crew duties. Crew duties are fixed step by step while vehicles are scheduled once all the trips have been partitioned into pieces of work. Extended use is made of Bundle methods taylored for the optimization of polyhedral functions, resource constrained shortest paths algortihms, and dual gredy heuristics for the set partitioning problem. Computational results are provided for an Italian public transit operator which show the improvements w.r.t. the sequential approach for the ex-urban instances.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
