Set covering heuristics in a Benders decomposition for railway timetabling
针对现有铁路时刻表的短期战术调整问题，提出一种Benders分解方法，通过集合覆盖问题的启发式算法快速生成高质量时刻表，比商业求解器快约20倍，最优性差距约7.5%。
Railway timetabling is a major challenge in the operation of railway. The timetable of a railway determines times, orders and routes of trains on the network and thereby defines the performance of the entire railway system. Railway operators are keen to maximize the economic performance of their railway system, such that timetables should be designed taking into account service requirements that result in a performant railway system In this work, we address a specific subdomain of timetabling, focusing on short-term tactical changes for already existing timetables, modeled with microscopic detail. With a Benders decomposition we propose an approach on this specific microscopic timetabling problem. In the decomposition, we consider quality and optimality of a timetable separately from the feasibility of a timetable. Quality is determined in a set covering problem and feasibility in a mixed-integer scheduling problem. With efficient heuristics on the problem of set covering in our decomposition, high quality solution for the resulting timetables are provided in short time, which enables an interactive design of adapted timetables. The novel approach provides heuristic solutions up to ∼20 times faster than standard approaches by commercial solvers, with an average gap of ∼7.5% in the optimality of solutions. Extensive experiments empirically confirm the benefits of the new approach.