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 !