Branch-price-and-cut algorithms for the pickup and delivery problem with time windows and multiple stacks

This paper proposes models and algorithms for the pickup and delivery vehicle routing problem with time windows and multiple stacks. Each stack is rear-loaded and is operated in a last-in-first-out (LIFO) fashion, meaning that when an item is picked up, it is positioned at the rear of a stack. An item can only be delivered if it is in that position. This problem arises in the transportation of heavy or dangerous material where unnecessary handling should be avoided, such as in the transportation of cars between car dealers and the transportation of livestock from farms to slaughterhouses. To solve this problem, we propose two different branch-price-and-cut algorithms. The first solves the shortest path pricing problem with the multi-stack policy, while the second incorporates this policy partly in the shortest path pricing problem and generates additional inequalities to the master problem when infeasible multi-stack routes are encountered. Computational results obtained on instances derived from benchmark instances for the pickup and delivery traveling salesman problem with multiple stacks are reported, and reveal the advantage of incorporating the multi-stack policy in the pricing problem. Instances with up to 75 requests and with one, two and three stacks can be solved optimally within 2 hours of computational time.