A branch-and-cut algorithm for a skip pick-up and delivery problem
针对垃圾箱运输的实际问题，提出一种分支切割算法，设计卡车在垃圾站与处理设施间的取送路线，满足容量和时长约束。
In this study we present a branch-and-cut algorithm for a skip pick-up and delivery problem. The study is motivated by a real-life problem in which full skips are transported from waste drop-off stations to treatment facilities where they are emptied, and then brought back to the original drop-off station. The transportation of the skips is done by trucks with the capacity of carrying two containers at a time. The planning problem is to design the routes of the trucks that perform the collection to satisfy a number of requests in a planning period. A truck route starts at the first pick-up, the truck then performs a sequence of pick-ups, treatments, and deliveries, and the route ends at the last delivery. From the truck perspective, the three actions of pick-up, treatment, and delivery can be performed in any order that respects the vehicle capacity of two and the route duration constraint, but for the single request, the three actions must be performed in the stated order. The problem is formulated as a mixed integer linear problem and several classes of valid inequalities are proposed and integrated into a branch-and-cut algorithm.