Title | ||
---|---|---|
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: file 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 oil instances from the literature. |
Year | DOI | Venue |
---|---|---|
2007 | 10.3138/infor.45.4.223 | INFOR |
Keywords | Field | DocType |
traveling salesman problem, pickup and delivery, LIFO loading, FIFO loading, additive branch-and-bound | Bottleneck traveling salesman problem,Branch and bound,Mathematical optimization,FIFO (computing and electronics),Algorithm,FIFO and LIFO accounting,Assignment problem,Travelling salesman problem,2-opt,Mathematics,Operations management,Search tree | Journal |
Volume | Issue | ISSN |
45 | 4 | 0315-5986 |
Citations | PageRank | References |
32 | 1.57 | 12 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Francesco Carrabs | 1 | 199 | 15.55 |
R. Cerulli | 2 | 252 | 23.85 |
Jean-François Cordeau | 3 | 2604 | 127.77 |