Column generation (CG) is a vital method to solve large-scale problems by
dynamically generating variables. It has extensive applications in common
combinatorial optimization, such as vehicle routing and scheduling problems,
where each iteration step requires solving an NP-hard constrained shortest path
problem. Although some heuristic methods for acceleration already exist, they
are not versatile enough to solve different problems. In this work, we propose
a reinforcement learning-based hyper-heuristic framework, dubbed RLHH, to
enhance the performance of CG. RLHH is a selection module embedded in CG to
accelerate convergence and get better integer solutions. In each CG iteration,
the RL agent selects a low-level heuristic to construct a reduced network only
containing the edges with a greater chance of being part of the optimal
solution. In addition, we specify RLHH to solve two typical combinatorial
optimization problems: Vehicle Routing Problem with Time Windows (VRPTW) and
Bus Driver Scheduling Problem (BDSP). The total cost can be reduced by up to
27.9\% in VRPTW and 15.4\% in BDSP compared to the best lower-level heuristic
in our tested scenarios, within equivalent or even less computational time. The
proposed RLHH is the first RL-based CG method that outperforms traditional
approaches in terms of solution quality, which can promote the application of
CG in combinatorial optimization.

基于强化学习的超启发式框架，在列生成中提供更好的整数解和加速收敛，通过减少含潜在最优解边的网络规模，在解决车辆路径和巴士司机调度问题中比传统方法降低至多 27.9% 和 15.4% 的总成本。