BUS AND DRIVER SCHEDULING IN
URBAN MASS TRANSIT SYSTEMS
OVERVIEW
URBAN BUS TRANSPORTATION
LARGE NUMBERS
OPERATIONS PLANNING PROCESS
GOAL OF THIS TALK
BUS SCHEDULING
PROBLEM DEFINITION
PROBLEM DEFINITION (CONT’D)
PROBLEM DEFINITION (CONT’D)
PROBLEM DEFINITION (CONT’D)
PROBLEM DEFINITION (CONT’D)
PROBLEM DEFINITION (CONT’D)
NETWORK STRUCTURE
SOLUTION METHODOLOGIES
A. Löbel
(1998)
Vehicle scheduling in public transit and lagrangean
pricing
Management Science 44
MULTI-COMMODITY MODEL
COLUMN GENERATION
LAGRANGEAN PRICING
RESULTS
A. Hadjar, O. Marcotte,
F. Soumis (2001)
A branch-and-cut approach for the multiple
depot vehicle scheduling problem
Les Cahiers du GERAD, G-2001-25
SET PARTITIONING MODEL
BRANCH-AND-PRICE-AND-CUT
RESULTS
VARIANTS
DUTY SCHEDULING
PROBLEM DEFINITION
PROBLEM DEFINITION (CONT’D)
PROBLEM DEFINITION (CONT’D)
PROBLEM DEFINITION (CONT’D)
PROBLEM DEFINITION (CONT’D)
PROBLEM DEFINITION (CONT’D)
SET PARTITIONING MODEL
NETWORK STRUCTURE
SOLUTION METHODOLOGY
R. Borndörfer, M.
Grötschel,
A. Löbel (2001)
Scheduling duties by adaptive
column generation
ZIB-Report 01-02
Konrad-Zuse-Zentrum für Informationstchnik, Berlin
HEURISTIC BRANCH-AND-PRICE
HEURISTIC BRANCH-AND-PRICE
RESULTS
SIMULTANEOUS BUS AND DUTY
SCHEDULING – PROBLEM DEFINITION
PROBLEM DEFINITION (CONT’D)
BUS AND DUTY
SCHEDULING
NETWORK STRUCTURE
SOLUTION METHODOLOGIES
R. Freling, D. Huisman,
A.P.M. Wagelmans (2000)
Models and algorithms for integration
of vehicle and crew scheduling
Econometric Institute Report EI2000-10/A
Erasmus University, Rotterdam
MIXED SET PARTITIONING /
FLOW MODEL
COLUMN GENERATION /
HEURISTIC
COLUMN GENERATION /
HEURISTIC
RESULTS
K. Haase, G.
Desaulniers,
J. Desrosiers (2001)
Simultaneous vehicle and
crew scheduling in urban mass transit systems
Transportation Science 35
SET PARTITIONING MODEL
BUS AND DUTY
SCHEDULING
NETWORK STRUCTURE
EXACT BRANCH-AND-PRICE
HEURISTIC BRANCH-AND-PRICE
EXACT RESULTS
HEURISTIC RESULTS
VARIANTS
FUTURE RESEARCH ON
SIMULTANEOUS BUS AND DUTY SCHEDULING
CONCLUSION
GILBERT’S MEASURE
THANK YOU !