A Lagrangian-based algorithm for a multiple depot, multiple traveling salesmen problem

DOI10.1016/j.nonrwa.2008.03.014zbMath1163.90722OpenAlexW2138388627MaRDI QIDQ1026674

Swaroop Darbha, W. A. Malik, Sai Yadlapalli, Meir Pachter

Publication date: 29 June 2009

Published in: Nonlinear Analysis. Real World Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.nonrwa.2008.03.014

zbMATH Keywords

Lagrangian relaxationdynamic programmingcombinatorial optimizationmotion planningtraveling salesman problem (TSP)unmanned vehiclesDubins' vehicles

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Dynamic programming (90C39)

Related Items

A new mixed integer programming model for curriculum balancing: application to a Turkish university, Minimization of the total traveling distance and maximum distance by using a transformed-based encoding EDA to solve the multiple traveling salesmen problem, Multi-depot multiple TSP: a polyhedral study and computational results, A hyper-heuristic based artificial bee colony algorithm for \(k\)-interconnected multi-depot multi-traveling salesman problem, An analysis of the extended Christofides heuristic for the \(k\)-depot TSP, A simple model for the multiple traveling salesmen problem with single depot and multiple sink, An improved approximation algorithm for the maximum TSP, A 3/2-Approximation Algorithm for the Multiple TSP with a Fixed Number of Depots, New Imperialist Competitive Algorithm to solve the travelling salesman problem

Uses Software

• YALMIP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Survivable networks, linear programming relaxations and the parsimonious property
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• On Curves of Minimal Length with a Constraint on Average Curvature, and with Prescribed Initial and Terminal Positions and Tangents
• Integer Programming Formulation of Traveling Salesman Problems
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Heuristic analysis, linear programming and branch and bound
• Technical Note—A Note on the Multiple Traveling Salesmen Problem
• Traveling Salesperson Problems for the Dubins Vehicle
• Solution of a Large-Scale Traveling-Salesman Problem
• The Traveling-Salesman Problem and Minimum Spanning Trees
• The traveling-salesman problem and minimum spanning trees: Part II