Fragment-based solution of two skip pickup and delivery problems
提出一种基于片段的精确分支切割算法，用于解决两种跳过取送货问题，在废物和建筑行业有应用，性能比现有最优算法快至少两个数量级。
• Exact branch-and-cut algorithm using fragments. • Algorithm is easily configured to solve flexible or fix return problems. • First use of fragments in a problem where requests must be served multiple time. • Significantly outperforms existing exact algorithms for the problem. We present a new fragment-based model for two versions of the Skip Pickup and Delivery Problem (SPDP). Our new algorithm outperforms the state-of-the-art for these problems by at least two orders of magnitude. In these particular SPDPs, skips must be picked up from their origin, emptied at various treatment facilities, and returned to their origin or to a different delivery location, subject to certain balancing constraints. The problem, which has applications in the waste and building industries, is to create route plans for vehicles of capacity two. We model the problem using an extension of the recently proposed method of fragments for Pickup and Delivery Problems (PDP) and integrate it in a Branch and Cut algorithm. Our algorithm is generic enough to solve both versions of the problem with the addition of a single constraint. For both versions of the problem, we identify and prove many new optimal solutions and significantly reduce runtime for the instances already solved.