3-approximation algorithm for a two depot, heterogeneous traveling salesman problem

DOI10.1007/s11590-010-0256-0zbMath1259.90116OpenAlexW1996380018MaRDI QIDQ691417

Sai Yadlapalli, Sivakumar Rathinam, Swaroop Darbha

Publication date: 30 November 2012

Published in: Optimization Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11590-010-0256-0

zbMATH Keywords

traveling salesman problemheterogeneous vehicle

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items

A primal-dual approximation algorithm for a two depot heterogeneous traveling salesman problem ⋮ The hierarchical traveling salesman problem ⋮ A general variable neighborhood search variants for the travelling salesman problem with draft limits ⋮ Decomposition-based exact algorithms for risk-constrained traveling salesman problems with discrete random arc costs ⋮ Heuristics for routing heterogeneous unmanned vehicles with fuel constraints ⋮ 3-approximation algorithm for a two depot, heterogeneous traveling salesman problem ⋮ New approximation algorithms for the heterogeneous weighted delivery problem ⋮ New approximation algorithms for the heterogeneous weighted delivery problem ⋮ Approximation algorithms for solving the heterogeneous Chinese postman problem

Uses Software

• TSPLIB

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Survivable networks, linear programming relaxations and the parsimonious property
• 3-approximation algorithm for a two depot, heterogeneous traveling salesman problem
• Analyzing the Held-Karp TSP bound: A monotonicity property with application
• The ellipsoid method and its consequences in combinatorial optimization
• The traveling salesman. Computational solutions for RSP applications
• The traveling salesman problem and its variations
• \(\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 3/2-Approximation Algorithm for Multiple Depot Multiple Traveling Salesman Problem

This page was built for publication: 3-approximation algorithm for a two depot, heterogeneous traveling salesman problem