操作员(生物学)
计算
数学优化
计算机科学
整数规划
启发式
邻里(数学)
线性规划
整数(计算机科学)
选择(遗传算法)
数学
线性地图
时间复杂性
算法
分界
作者
Robin Gaborit,Evelien van der Hurk,Otto Anker Nielsen,Yu Jiang
标识
DOI:10.1016/j.ejor.2026.01.032
摘要
• 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.
科研通智能强力驱动
Strongly Powered by AbleSci AI