A 3/2-Approximation Algorithm for the Multiple TSP with a Fixed Number of Depots
From MaRDI portal
Publication:2802244
DOI10.1287/ijoc.2015.0650zbMath1338.90358OpenAlexW1857333123MaRDI QIDQ2802244
Publication date: 25 April 2016
Published in: INFORMS Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/ijoc.2015.0650
Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)
Related Items
Approximation algorithms for the \(k\)-depots Hamiltonian path problem, An extension of the Christofides heuristic for a single-depot multiple Hamiltonian path problem, An extension of the Christofides heuristic for the generalized multiple depot multiple traveling salesmen problem, Approximating the multiple-depot multiple-terminal Hamiltonian path problem, Exact and heuristic algorithms for routing AGV on path with precedence constraints, New approximation algorithms for the heterogeneous weighted delivery problem, New approximation algorithms for the heterogeneous weighted delivery problem, Reducing Path TSP to TSP
Cites Work
- An analysis of the extended Christofides heuristic for the \(k\)-depot TSP
- Approximation algorithms for multiple terminal, Hamiltonian path problems
- A Lagrangian-based algorithm for a multiple depot, multiple traveling salesmen problem
- Analysis of Christofides' heuristic: some paths are more difficult than cycles
- A variation of the generalized assignment problem arising in the New Zealand dairy industry
- Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem
- A tabu search heuristic for the multi-depot vehicle routing problem
- \(\frac 32\)-approximation algorithm for two variants of a 2-depot Hamiltonian path problem
- An approximation algorithm for a symmetric generalized multiple depot, multiple travelling salesman problem
- A Unified Modeling and Solution Framework for Vehicle Routing and Local Search-Based Metaheuristics
- State-of-the Art Review—Evolutionary Algorithms for Vehicle Routing
- Approximation Algorithms for Some Postman Problems
- New assignment algorithms for the multi-depot vehicle routing problem
- Approximations for minimum and min-max vehicle routing problems
