A Lagrangian-based algorithm for a combinatorial motion planning problem

DOI10.1007/978-3-540-74356-9_23MaRDI QIDQ3564143zbMATH OpenOpenAlexFDO

Authors Sai Yadlapalli, W. A. Malik, Siva Rathinam, S. Darbha

Publication date 2 June 2010

Published in Advances in Cooperative Control and Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-74356-9_23

zbMATH Keywords

motion constraintNP-hard

Mathematics Subject Classification ID

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

Recommendations

• A Lagrangian-based algorithm for a multiple depot, multiple traveling salesmen problem
• An interactive algorithm for multi-objective route planning
• Motion planning algorithms for the Dubins Travelling Salesperson Problem
• Two-dimensional path finding subject to geometric constraints
• Path planning for a collection of vehicles with yaw rate constraints

Cites work

• An approximation algorithm for a symmetric generalized multiple depot, multiple travelling salesman problem
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• scientific article; zbMATH DE number 193411 (Why is no real title available?)
• scientific article; zbMATH DE number 1965513 (Why is no real title available?)
• scientific article; zbMATH DE number 2079394 (Why is no real title available?)
• On Curves of Minimal Length with a Constraint on Average Curvature, and with Prescribed Initial and Terminal Positions and Tangents
• Solving a Family of Multi-Depot Vehicle Routing and Location-Routing Problems
• Technical Note—A Note on the Multiple Traveling Salesmen Problem
• The constrained minimum spanning tree problem
• The Lagrangian Relaxation Method for Solving Integer Programming Problems
• The traveling salesman problem and its variations
• The Traveling-Salesman Problem and Minimum Spanning Trees
• The traveling-salesman problem and minimum spanning trees: Part II
• Transformation of multidepot multisalesmen problem to the standard travelling salesman problem
• Traveling Salesperson Problems for the Dubins Vehicle

Cited in

(4)

• Dubins traveling salesman problem with neighborhoods: a graph-based approach
• A note on the Papadimitriou-Silverberg algorithm for planning optimal piecewise-linear motion of a ladder
• A solution of the minimum-time speed planning problem based on lattice theory
• Multi-depot multiple TSP: a polyhedral study and computational results

Describes a project that uses

Uses Software

• YALMIP

This page was built for publication: A Lagrangian-based algorithm for a combinatorial motion planning problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3564143)