Optimisation of bus timetables: An adaptive large neighbourhood search-based matheuristic with a novel operator weight

• Adaptive Large Neighborhood Search for public transport timetabling • Combine Mixed Integer Linear Programming and heuristic repair operators • A novel operator weight formula accounting for the computation times of operators • An intuitive pitfall in the literature when accounting for computation time 1 This study develops an adaptive large neighbourhood search (ALNS) based matheuristic to an acyclic bus timetabling problem with time-dependent travel time and demand data. Two types of repair operators are proposed: a Mixed Integer Linear Programming (MILP) operator that solves a restricted version of the problem where decision variables are defined by a destroy operator, and a heuristic operator that shifts buses’ departing times. Their mixed usage induces the challenge of allocating computation time to different operators with significantly different execution times. Noticing that existing operator selection mechanisms may allocate excessive time to slow operators, this study establishes a novel formula called the inverse-square rule. Computational results on a part of the Copenhagen Network show that (1) the ALNS-framework with the proposed inverse-square rule outperforms exact solution methods across all instances, (2) using a fast heuristic repair operator and a slow MILP repair operator is substantially better than using either one alone, and (3) on average, the inverse-square rule demonstrates better performance than other inverse-power formulas.