Approaches for Increasing The Similarity of Resource Schedules in Public Transport

In public bus transport, timetables usually consist of many trips that are serviced each day. However, there are also some trips that do not repeat daily. This small amount of irregular trips has a large impact when the corresponding resource scheduling problems are solved day by day at minimum costs by optimization tools: vehicle and driver schedules produced for one day may completely differ from schedules for another day. As most companies prefer both cost efficient and similar schedules, scheduling approaches should also consider similarity as an objective. We propose and compare approaches that increase the similarity of resource schedules in two different ways: The first type of approaches solves the scheduling problems of various days separated from each other while similarity is ensured with the help of a common reference schedule. The second type of approaches tackles the scheduling problems of various days simultaneously while the similarity is increased with the help of regular patterns. In addition to heuristic procedures we propose a MIP formulation that includes patterns as variables. The models are solved with a column generation approach. Computational results show that the proposed approaches can highly increase the similarity, while only a few additional costs compared to a cost optimal solution are necessary.