Local search algorithms for multiple-depot vehicle routing and for multiple traveling salesman problems with proved performance guarantees

DOI10.1007/s10878-012-9580-xzbMath1335.90107MaRDI QIDQ489718

Uri Yovel, Asaf Levin

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

zbMATH Keywords

vehicle routing; traveling salesman; local search; approximation algorithms

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90B06: Transportation, logistics and supply chain management

90C27: Combinatorial optimization

Uses Software

• VRP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An analysis of the extended Christofides heuristic for the \(k\)-depot TSP
• Theoretical aspects of local search.
• The vehicle routing problem. Latest advances and new challenges.
• New local search approximation techniques for maximum generalized satisfiability problems
• \(\frac 32\)-approximation algorithm for two variants of a 2-depot Hamiltonian path problem
• The traveling salesman problem and its variations.
• An approximation algorithm for a symmetric generalized multiple depot, multiple travelling salesman problem
• Fast local search algorithms for the handicapped persons transportation problem
• The Design of Approximation Algorithms
• PTAS FOR k-TOUR COVER PROBLEM ON THE PLANE FOR MODERATELY LARGE VALUES OF k
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Worst-Case Analysis of Heuristics for Multidepot Capacitated Vehicle Routing Problems
• An Analysis of Several Heuristics for the Traveling Salesman Problem
• On Syntactic versus Computational Views of Approximability
• Approximate Local Search in Combinatorial Optimization
• A Survey of Approximation Results for Local Search Algorithms