An approximability result of the multi-vehicle scheduling problem on a path with release and handling times

DOI10.1016/j.tcs.2003.09.010zbMath1067.90143MaRDI QIDQ1884949

Yoshiyuki Karuno, Hiroshi Nagamochi

Publication date: 27 October 2004

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2003.09.010

zbMATH Keywords

Dynamic programming; Discrete optimization; Polynomial time approximation scheme; Vehicle scheduling

Mathematics Subject Classification ID

90B35: Deterministic scheduling theory in operations research

90C59: Approximation methods and heuristics in mathematical programming

90C27: Combinatorial optimization

90C39: Dynamic programming

Related Items

Approximation schemes for Euclidean vehicle routing problems with time windows, Routing open shop and flow shop scheduling problems, Approximation algorithms for single vehicle scheduling problems with release and service times on a tree or cycle, The multiple traveling salesman problem on spiders, Set covering in fuel-considered vehicle routing problems, Heuristic approaches for solving transit vehicle scheduling problem with route and fueling time constraints, Minmax subtree cover problem on cacti, A Quasi-polynomial Time Approximation Scheme for Euclidean CVRPTW, Single-vehicle scheduling problems with release and service times on a line

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A \(\frac{5}{3}\)-approximation algorithm for scheduling vehicles on a path with release and handling times
• Single-vehicle scheduling with time window constraints
• Vehicle scheduling on a tree with release and handling times
• \((p-1)/(p+1)\)-approximate algorithms for \(p\)-traveling salesmen problems on a tree with minmax objective
• A polynomial approximation scheme for problem \(F2/r_ j/C_{\text{max}}\)
• 2-approximation algorithms for the multi-vehicle scheduling problem on a path with release and handling times.
• A heuristic with worst-case analysis for minimax routing of two travelling salesmen on a tree
• Better approximation ratios for the single-vehicle scheduling problems on line-shaped networks
• Routing and Scheduling on a Shoreline with Release Times
• Special cases of traveling salesman and repairman problems with time windows
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• A Polynomial Approximation Scheme for a Constrained Flow-Shop Scheduling Problem
• Technical Note—Routing and Location-Routing p-Delivery Men Problems on a Path
• VEHICLE SCHEDULING ON A TREE TO MINIMIZE MAXIMUM LATENESS
• Complexity Of The Single Vehicle Scheduling Problem On Graphs
• Sales‐delivery man problems on treelike networks