Branch and Bound and Genetic algorithm for Periodic Timetabling problem

Alperovich Galina
CVUT FEL, Open Informatics, Artificial Intelligence
Combinatorial optimization final project
May, 2016

Abstract

Mathematical optimization in public transport area is becoming a very popular task for the several last years. Periodic timetables are widely used for local, regional, and long-distance traffic because periodic timetable has the property that certain departure times occure in fixed intervals which ensures a very regular service. Timetable is a very important factor in public transport organization: it helps to optimize city resources, provide mobility and reasonable travel times for many people. In current work we have considered step-by-step model construction, formulation as integer linear programming and two ways of solving the task: classical Branch and Bound algorithm and genetic algorithm.

Reference

[1] PERIODIC TIMETABLE GENERATION
Seminar on Algorithms and Models for Railway Optimization
University of Constance
Carole Giesemann SS 2002

[2] MODELS FOR PERIODIC TIMETABLING
Mathias Kinder
Diplomarbeit bei Prof. Dr. M. Gro ̈tschel