Integrated Bus Timetabling and Scheduling with a Mutation-Based Evolutionary Scheme Maximizing Headway Quality and Connections

Abstract Public transport planning is a multi-level process that includes various complex tasks. These tasks are traditionally executed sequentially, and the result of each task serves as input for consecutive tasks. A simultaneous integrated consideration of multiple tasks may lead to an overall improved solution, but further increase the complexity of already hard-to-solve planning problems. This work focuses on timetabling and vehicle scheduling and evaluates synergies from the integrated optimization. We investigate an exact sequential, exact integrated, and heuristic approach to solve the combined problem for large public transport networks considering the interlining of vehicles, multiple vehicle types, or multiple depots while additionally aiming to maximize regular “clock-faced’’ headways and transfer connections. Compared to sequential optimization, an integrated approach significantly reduces nominal and operational costs while maintaining high service quality. However, an exact integrated approach is only able to compute solutions for problems of limited size in a reasonable time. We propose an adaptive modular evolutionary extendable scheme that effectively balances computational efficiency and solution quality. By utilizing various problem-specific mutation operators and adaptively applying them based on their impact, the heuristic can compute high-quality solutions for large real-world-inspired public transport networks in a reasonable time while considering short connecting times between lines and regular clock-faced headways.