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.