Rapid re-optimization via learning-enhanced column generation for vehicle routing with driver break scheduling
提出一种结合列生成与机器学习的快速再优化框架，解决车辆路径与驾驶员休息调度的联合优化问题，在欧盟法规下测试，运行时间减少96%以上，成本增加不到2%。
• Identifies critical gaps in routing and driver break scheduling optimization. • ML-enhanced column generation for rapid re-optimization using historical patterns. • Adaptable to diverse regulations (e.g., EU, Australia, New Zealand). • Uses MIP dual values to guide heuristics toward promising search neighborhoods. In many parts of the world, the road freight transportation sector is subject to stringent legal requirements regarding driver hours. These regulations present a significant challenge for developing practical and efficient schedules. The simultaneous optimization of vehicle routing and driver break schedules constitutes a major computational problem. In practice, many real-life vehicle routing problems require periodic planning and must adapt to sudden demand changes; this necessitates efficient re-optimization capabilities. This paper addresses this need by proposing a rapid re-optimization framework for the Vehicle Routing with Driver Break Scheduling. Our method integrates a column generation algorithm with a machine learning heuristic specifically designed for fast re-optimization. We evaluate the proposed approach under European Union Regulation (EC)561/2006 and Directive 2002/15/EC using two sets of benchmark instances, one based on a synthetic data and the other on a real-life data. The results demonstrate that the ML-enhanced approach is substantially faster than the implementation without the ML prediction component, reducing runtime by more than 96% (to just a matter of seconds), while increasing routing cost by less than 2% and yielding a final solution gap of 2.7% above the estimated lower bound.