An Additive Branch-and-Bound Algorithm for the Pickup and Delivery Traveling Salesman Problem with LIFO or FIFO Loading
- 1 November 2007
- journal article
- Published by Taylor & Francis in INFOR: Information Systems and Operational Research
- Vol. 45 (4) , 223-238
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 literatureKeywords
This publication has 19 references indexed in Scilit:
- Variable Neighborhood Search for the Pickup and Delivery Traveling Salesman Problem with LIFO LoadingINFORMS Journal on Computing, 2007
- A new extension of local search applied to the Dial-A-Ride ProblemEuropean Journal of Operational Research, 1995
- An Efficient Algorithm for the Min-Sum Arborescence Problem on Complete DigraphsINFORMS Journal on Computing, 1993
- An additive bounding procedure for the asymmetric travelling salesman problemMathematical Programming, 1992
- New lower bounds for the Symmetric Travelling Salesman ProblemMathematical Programming, 1989
- Efficient implementation of graph algorithms using contractionJournal of the ACM, 1989
- An Additive Bounding Procedure for Combinatorial Optimization ProblemsOperations Research, 1989
- Efficient algorithms for finding minimum spanning trees in undirected and directed graphsCombinatorica, 1986
- A note on finding optimum branchingsNetworks, 1979
- Optimum branchingsJournal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics, 1967