Primal-dual schema and Lagrangian relaxation for the k-location-routing problem

DOI10.1007/978-3-642-22935-0_9MaRDI QIDQ3088086zbMATH OpenOpenAlexFDO

Authors Tim Carnes, David B. Shmoys

Publication date 17 August 2011

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-22935-0_9

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Transportation, logistics and supply chain management (90B06) Discrete location and assignment (90B80)

Recommendations

• Locating depots for capacitated vehicle routing
• Locating depots for capacitated vehicle routing
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• scientific article; zbMATH DE number 3952495
• Solving the Multi-Depot Location-Routing Problem with Lagrangian Relaxation

Cites work

• A General Approximation Technique for Constrained Forest Problems
• An exact algorithm for minimizing routing and operating costs in depot location
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Combined location-routing problems: A synthesis and future research directions
• Generalized Subtour Elimination Constraints and Connectivity Constraints
• Hamiltonian location problems
• Solving a Family of Multi-Depot Vehicle Routing and Location-Routing Problems

Cited in

(5)

• A 3/2-approximation algorithm for the multiple Hamiltonian path problem with no prefixed endpoints
• A survey of recent research on location-routing problems
• An extension of the Christofides heuristic for the generalized multiple depot multiple traveling salesmen problem
• Improved algorithms for joint optimization of facility locations and network connections
• Locating depots for capacitated vehicle routing

This page was built for publication: Primal-dual schema and Lagrangian relaxation for the \(k\)-location-routing problem

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