Dual-driven path elimination for vehicle routing with idle times and arrival-time consistency
提出一种双驱动方法，利用子问题的对偶信息生成不可行路径消除约束，应用于带空闲时间的一致性旅行商问题，在756个算例中求解了536个最优解。
We present a simple dual-driven methodology for generating infeasible path elimination constraints within branch-and-cut algorithms for vehicle routing problems that incorporate idle times and arrival-time consistency requirements. By leveraging dual information from a feasibility-checking subproblem, the approach systematically identifies the combinatorial sources of infeasibility and uses them to generate and strengthen valid inequalities. We apply the method to the Consistent Traveling Salesperson Problem with idling, which enforces temporal consistency across multiple service days while allowing idle time between tasks. This problem, defined by basic routing and synchronization constraints, serves as an ideal case study to demonstrate the method’s effectiveness. Computational experiments on a benchmark set of 756 instances, based on multi-period extensions of classical TSPLIB datasets, show that the approach solves 536 instances to proven optimality, including cases with up to 100 customers and a five-day planning horizon, all within a two-hour time limit.