Name
Title | ||
|---|---|---|
A branch-and-bound algorithm for the double travelling salesman problem with two stacks |
Abstract | ||
|---|---|---|
This article studies the double traveling salesman problem with two stacks. A number of requests have to be served where each request consists in the pickup and delivery of an item. All the pickup operations have to be performed before any delivery can take place. A single vehicle is available that starts from a depot, performs all the pickup operations and returns to the depot. Then, it performs all the delivery operations and returns to the depot. The items are loaded in two stacks, each served independently from the other with a last-in-first-out policy. The objective is the minimization of the total cost of the pickup and delivery tours. We propose a branch-and-bound approach to solve the problem. The algorithm uses properties of the problem both to tighten the lower bounds and to avoid the exploration of redundant subtrees. Computational results performed on benchmark instances reveal that the algorithm outperforms the other exact approaches for this problem. © 2012 Wiley Periodicals, Inc. NETWORKS, 2013 © 2013 Wiley Periodicals, Inc. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1002/net.21468 | Networks |
Keywords | Field | DocType |
computational result,article study,pickup operation,benchmark instance,double travelling salesman problem,branch-and-bound algorithm,wiley periodicals,branch-and-bound approach,inc. networks,salesman problem,delivery operation,delivery tour,branch and bound,lifo | Mathematical optimization,Branch and bound,Stack (abstract data type),FIFO and LIFO accounting,Minification,Travelling salesman problem,Pickup,Total cost,Mathematics | Journal |
Volume | Issue | ISSN |
61 | 1 | 0028-3045 |
Citations | PageRank | References |
16 | 0.66 | 23 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Francesco Carrabs | 1 | 199 | 15.55 |
| R. Cerulli | 2 | 252 | 23.85 |
| Maria Grazia Speranza | 3 | 1217 | 77.86 |