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

DOI10.1016/j.nonrwa.2008.03.014zbMath1163.90722MaRDI 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 relaxation; dynamic programming; combinatorial optimization; motion planning; traveling salesman problem (TSP); unmanned vehicles; Dubins' vehicles

Mathematics Subject Classification ID

90C27: Combinatorial optimization

90C39: Dynamic programming

Related Items

A new mixed integer programming model for curriculum balancing: application to a Turkish university, Multi-depot multiple TSP: a polyhedral study and computational results, An analysis of the extended Christofides heuristic for the \(k\)-depot TSP, An improved approximation algorithm for the maximum TSP, Minimization of the total traveling distance and maximum distance by using a transformed-based encoding EDA to solve the multiple traveling salesmen problem, A hyper-heuristic based artificial bee colony algorithm for \(k\)-interconnected multi-depot multi-traveling salesman problem, 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, A simple model for the multiple traveling salesmen problem with single depot and multiple sink

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