A Polyhedral Approach to Simplified Crew Scheduling and Vehicle Scheduling Problems

Matteo Fischetti (), Andrea Lodi (), Silvano Martello () and Paolo Toth ()
Additional contact information
Matteo Fischetti: Dipartimento di Elettronica e Informatica, Universitàà di Padova, Italy
Andrea Lodi: Dipartimento di Elettronica, Informatica, e Sistemistica, Universitàà di Bologna, Italy
Silvano Martello: Dipartimento di Elettronica, Informatica, e Sistemistica, Universitàà di Bologna, Italy
Paolo Toth: Dipartimento di Elettronica, Informatica, e Sistemistica, Universitàà di Bologna, Italy

Management Science, 2001, vol. 47, issue 6, 833-850

Abstract: Crew and vehicle scheduling are fundamental issues in public transit management. Informally, they can be described as the problem of determining the optimal duties for a set of crews (e.g., bus drivers) or vehicles (e.g., buses) so as to cover a given set of timetabled trips, satisfying a number of constraints laid down by the union contract and company regulations. We consider the simplified but still NP-hard case in which several depots are specified, and limits on both the total time between the start and the end of any duty (spread time) and the total duty operational time (working time) are imposed. We give a 0-1 linear programming formulation based on binary variables associated with trip transitions, which applies to both crew and vehicle scheduling. The model is enhanced by means of new families of valid inequalities, for which exact and heuristic separation procedures are proposed. These techniques are embedded into an exact branch-and-cut algorithm, which also incorporates heuristic procedures. The performance of two implementations of the method (for vehicle scheduling and crew scheduling, respectively) are evaluated through computational testing on both random and real-world test problems from the literature.

Keywords: Crew Scheduling; Vehicle Scheduling; Polyhedral Methods (search for similar items in EconPapers)
Date: 2001
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (14)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.47.6.833.9810 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:47:y:2001:i:6:p:833-850

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().