Schedule-Based Integrated Inter-City Bus Line Planning for Multiple Timetabled Services via Large Multiple Neighborhood Search

This work addresses line planning for inter-city bus networks, which requires a high level of integration with other planning steps. One key reason is given by passengers choosing a speci?c timetabled service rather than just a line, as is typically the case in urban transportation. Schedule-based modeling approaches are required to incorporate this aspect, i.e., demand is assigned to a speci?c timetabled service. Furthermore, in liberalized markets, there is usually ?erce competition within and across modes. This encourages considering dynamic demand, i.e., not relying on static demand values, but adjusting them based on the trip characteristics. We provide a schedule-based mixed-integer model formulation allowing a bus operator to optimize multiple timetabled services in a travel corridor with simultaneous decisions on both departure time and which stations to serve. The demand behaves dynamically with respect to departure time, trip duration, trip frequency, and cannibalization. To solve this new problem formulation, we introduce a large multiple neighborhood search (LMNS) as an overall metaheuristic approach, together with multiple variations including matheuristics. Applying the LMNS algorithm, we solve instances based on real-world data from the German market. Computation times are attractive and the high quality of the solutions is con?rmed by analyzing examples with known optimal solutions. Moreover, we show that the explicit consideration of the dependencies between the di?erent timetabled services often produces insightful new results that di?er from approaches which only focus on a single service.