An Additive Branch-and-Bound Algorithm for the Pickup and Delivery Traveling Salesman Problem with LIFO or FIFO Loading

Abstract

This paper introduces an additive branch-and-bound algorithm for two variants of the pickup and delivery traveling salesman problem in which loading and unloading operations have to be performed either in a Last-In-First-Out (LIFO) or in a First-In-First-Out (FIFO) order. Two relaxations are used within the additive approach: the assignment problem and the shortest spanning r-arborescence problem. The quality of the lower bounds is further improved by a set of elimination rules applied at each node of the search tree to remove from the problem arcs that cannot belong to feasible solutions because of precedence relationships. The performance of the algorithm and the effectiveness of the elimination rules are assessed on instances from the literature.

Keywords:

• Traveling salesman problem
• pickup and delivery
• LIFO loading
• FIFO loading
• additive branch-and-bound