Journal
DISCRETE OPTIMIZATION
Volume 21, Issue -, Pages 25-41Publisher
ELSEVIER
DOI: 10.1016/j.disopt.2016.04.005
Keywords
Traveling Salesman problem; Multiple stacks; Polyhedral study; Branch-and-cut
Ask authors/readers for more resources
In the double TSP with multiple stacks, one performs a Hamiltonian circuit to pick up n items, storing them in a vehicle with s stacks of finite capacity q satisfying last in-first-out constraints, and then delivers every item by performing a Hamiltonian circuit. We introduce an integer linear programming formulation with arc and precedence variables. We show that the underlying polytope shares some polyhedral properties with the ATSP polytope, which let us characterize large number of facets of our polytope. We convert these theoretical results into a branch-and-cut algorithm for the double TSP with two stacks. Our algorithm outperforms the existing exact methods and solves instances that were previously unsolved. (C) 2016 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available