Approximation results for min-max path cover problems in vehicle routing

DOI10.1002/nav.20434zbMath1202.90040OpenAlexW2055845740MaRDI QIDQ3065634

Chung-Lun Li, Zhou Xu, Liang Xu

Publication date: 6 January 2011

Published in: Naval Research Logistics (NRL) (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/nav.20434

zbMATH Keywords

vehicle routingapproximation algorithmsapproximation hardnessmin-max path cover

Mathematics Subject Classification ID

Minimax problems in mathematical programming (90C47) Abstract computational complexity for mathematical programming problems (90C60) Transportation, logistics and supply chain management (90B06) Approximation methods and heuristics in mathematical programming (90C59) Deterministic network models in operations research (90B10)

Related Items (12)

Improved approximation algorithms for some min-max and minimum cycle cover problems ⋮ Improved Approximation Algorithms for Min-Max and Minimum Vehicle Routing Problems ⋮ A min-max vehicle routing problem with split delivery and heterogeneous demand ⋮ A multi‐vehicle covering tour problem with speed optimization ⋮ Better approximability results for min-max tree/cycle/path cover problems ⋮ Scheduling on a graph with release times ⋮ New approximation algorithms for the minimum cycle cover problem ⋮ Vehicle routing with subtours ⋮ New approximation algorithms for the rooted budgeted cycle cover problem ⋮ Approximation algorithms for some minimum postmen cover problems ⋮ New approximation algorithms for the rooted budgeted cycle cover problem ⋮ Approximation results for a min-max location-routing problem

Uses Software

• VRP

Cites Work

• Unnamed Item
• Min-max tree covers of graphs.
• Approximation hardness of min-max tree covers
• \((p-1)/(p+1)\)-approximate algorithms for \(p\)-traveling salesmen problems on a tree with minmax objective
• Approximation algorithms for some vehicle routing problems
• A faster 2-approximation algorithm for the minmax \(p\)-traveling salesmen problem on a tree
• Approximating the minmax rooted-tree cover in a tree
• On the approximability of the traveling salesman problem
• Technical Note—Heuristics for Delivery Problems with Constant Error Guarantees
• Bounds and Heuristics for Capacitated Routing Problems
• Approximation algorithms for the capacitated traveling salesman problem with pickups and deliveries
• Approximations for minimum and min-max vehicle routing problems
• Combinatorial optimization. Theory and algorithms.

This page was built for publication: Approximation results for min-max path cover problems in vehicle routing