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

DOI10.1016/j.tcs.2003.09.010zbMath1067.90143OpenAlexW2005650729MaRDI 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 programmingDiscrete optimizationPolynomial time approximation schemeVehicle scheduling

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Dynamic programming (90C39)

Related Items (10)

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

This page was built for publication: An approximability result of the multi-vehicle scheduling problem on a path with release and handling times