City Bus Scheduling Poster


	Research Group Discrete Optimization

Solution of City Bus Scheduling Problems

City bus optimization problems in Bangkok, Thailand

The aim of this research is to optimize the number of buses and their scheduling. This leads to high dimensional integer programming problems. The problems can also be formulated through a graph theory model. Two problem cases are considered:

the Single-Depot Vehicle Scheduling Problem (SDVSP),
the Multiple-Depot Vehicle Scheduling Problem (MDVSP).

Symbols in graph model

depot: a nonempty set of vehicles, D: set of all depots, for each d D, d⁺: start point, d^-: end point
t^-: first stop, t⁺: last stop, : timetabled trips
A_d^t-trip := {(t^-,t⁺)| t _d}(timetabled trips)
A_d^pull-out := {(d⁺,t^-)| t _d} (pull-out trips)
A_d^pull-in := {(t⁺,d^-)| t _d} (pull-in trips)
A_d^d-trip := {(p⁺,q^-)| p,q _d} (dead-head trips)
A_d^u-trip := A_d^pull-out A_d^pull-in A_d^d-trip (unloaded trips)
(d^-,d⁺) (backward arc)
Single-depot case: Digraph D^t_d:=(V^t_d,A^t_d), where V^t_d:={d⁺,d^-} _d⁺ _d^- and A^t_d :=
A_d^t-trip A_d^u-trip {(d⁺,d^-)}
Multiple-depot case: Digraph D^t:=(V^t,A^t), whereas V^t := D⁺D^- ⁺ ^- and A^t:=_{d D}A^td

SDVSP

The Single-Depot Vehicle Scheduling Problem (SDVSP), considers one depot.

Illustration of the SDVSP

Using this graph model, the SDVSP can be solved in polynomial time by a network flow algorithm.

IP Model of SDVSP

s.t. x(t^-,t⁺) = 1,

,
x(

⁺(t⁺)) - x(t^-,t⁺) = 0,

,
x(t^-,t⁺) - x(

^-(t^-)) = 0,

⁺(d^-)) - x(d^-,d⁺) = 0,
x(d^-,d⁺) - x(

^-(d^-)) = 0,

x(d^-,d⁺)

,
0

A^t-trip

A^u-trip,
x integral.

MDVSP

The second model, the Multiple-Depot Vehicle Scheduling Problem (MDVSP), considers multiple depots. The MDVSP is NP-hard.

Illustration of the MDVSP

IP Model of MDVSP

s.t. x(

⁺(t)) = 1,

,
x^d(

⁺(t)) - x^d(

^-(t)) = 0,

_d,

x^d(

⁺(d))

_d,

D,
x

0,
x

{0,1}^A.

Example of MDVSP: City Bus in Bangkok

The real timetable schedules of the city buses are written in the form of graph model, and then transformed to an integer programming model (SDVSP or MDVSP). After that we are trying to solve this problems to obtain the optimal number of buses used.

Method for solving these problems

Branch-and-Cut
Column Generation Techniques
Branch-and-Cut-and-Price
Lagrangean Relaxation-Pricing

Future Work

In summary, MDVSP can be solved by some heuristic algorithms. The disadvantage of these algorithms is that the solution quality decreases when the number of the depots grows. Therefore, further heuristic algorithms for solving MDVSP have to be developed.

Contact

Chotiros Surapholchai
Institute for Computer Science, University of Heidelberg
Im Neuenheimer Feld 368, 69120 Heidelberg, Germany

Tel: +49-6221-545744
Fax: +49-6221-545750
E-mail: Chotiros.Surapholchai@Informatik.Uni-Heidelberg.De

Research Group Discrete Optimization