Using Column Generation for the Bus Line Planning Problem

The Line-planning problem is one of the most important tasks in the planning of a bus line network. It consists of finding an optimal set of bus lines and passenger routes. Therefore, we use two objectives: we minimize the transport operating costs, and we minimize the traveling times of the passengers. In this thesis, we present a new model for the bus line planning, making use of column generation. The main contribution of our model is, in comparison to the existing models, the way we deal with generating new potential bus lines by using practical insights. Furthermore, we discuss the impact of the start set of bus lines, we investigate the complexity of the problem and we consider multiple scenarios, where each scenario is defined by using different input parameters. Computational results are shown for theoretical data as well as for data for the region of Breda, The Netherlands.