Disjoint congruence classes and a timetabling application (Q1026128)

The authors consider a combinatorial problem involving disjoint congruence classes which is motivated by an application in subway timetabling in simplified form. More specifically, the problem is to find pairwise disjoint congruence classes modulo certain given integers, where each of these classes corresponds to the arrival times of a subway line of a given frequency. For a large class of instances of the underlying line scheduling problem a characterization is given when such disjoint congruence classes exist and how they can be determined. Then a generalization is considered, where a minimum distance between consecutive trains (i.e., between congruence classes) is required. Finally, a computational method for solving the general case of this line scheduling problem based on integer linear programming is presented. The approach is briefly illustrated by two numerical examples.