Local search algorithms for multiple-depot vehicle routing and for multiple traveling salesman problems with proved performance guarantees
DOI10.1007/S10878-012-9580-XzbMATH Open1335.90107OpenAlexW2005363060MaRDI QIDQ489718FDOQ489718
Authors: Asaf Levin, Uri Yovel 
Publication date: 21 January 2015
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-012-9580-x
Recommendations
- A 3/2-Approximation Algorithm for Multiple Depot Multiple Traveling Salesman Problem
- A 3/2-approximation algorithm for the multiple TSP with a fixed number of depots
- Constant-factor approximations for cycle cover problems
- FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
- An extension of the Christofides heuristic for the generalized multiple depot multiple traveling salesmen problem
Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Transportation, logistics and supply chain management (90B06)
Cites Work
- The design of approximation algorithms
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- An analysis of the extended Christofides heuristic for the \(k\)-depot TSP
- An Analysis of Several Heuristics for the Traveling Salesman Problem
- Title not available (Why is that?)
- The vehicle routing problem. Latest advances and new challenges.
- \(\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
- Title not available (Why is that?)
- The traveling salesman problem and its variations.
- Title not available (Why is that?)
- Title not available (Why is that?)
- On Syntactic versus Computational Views of Approximability
- A Survey of Approximation Results for Local Search Algorithms
- Theoretical aspects of local search.
- Fast local search algorithms for the handicapped persons transportation problem
- New local search approximation techniques for maximum generalized satisfiability problems
- PTAS for \(k\)-tour cover problem on the plane for moderately large values of \(k^*\)
- Worst-Case Analysis of Heuristics for Multidepot Capacitated Vehicle Routing Problems
- Approximate Local Search in Combinatorial Optimization
Cited In (4)
- A Lagrangian-based algorithm for a multiple depot, multiple traveling salesmen problem
- Locating depots for capacitated vehicle routing
- Approximation algorithms for solving the trip-constrained vehicle routing cover problems
- An iterated local search algorithm for latency vehicle routing problems with multiple depots
Uses Software
This page was built for publication: Local search algorithms for multiple-depot vehicle routing and for multiple traveling salesman problems with proved performance guarantees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q489718)
