Better approximation ratios for the single-vehicle scheduling problems on line-shaped networks

DOI10.1002/net.10028zbMath1024.90008OpenAlexW2011230269MaRDI QIDQ3150129

Toshihide Ibaraki, Yoshiyuki Karuno, Hiroshi Nagamochi

Publication date: 29 September 2002

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.10028

zbMATH Keywords

worst-case analysisapproximate algorithms,performance guarantee,routing and scheduling,

Mathematics Subject Classification ID

Transportation, logistics and supply chain management (90B06) Deterministic scheduling theory in operations research (90B35)

Related Items (11)

An approximability result of the multi-vehicle scheduling problem on a path with release and handling times ⋮ How to collect balls moving in the Euclidean plane ⋮ Routing open shop and flow shop scheduling problems ⋮ Approximation algorithms for the traveling repairman and speeding deliveryman problems ⋮ 2-approximation algorithms for the multi-vehicle scheduling problem on a path with release and handling times. ⋮ Approximation algorithms for single vehicle scheduling problems with release and service times on a tree or cycle ⋮ Data mule scheduling on a path with handling time and time span constraints ⋮ Approximating a vehicle scheduling problem with time windows and handling times ⋮ Single-vehicle scheduling problems with release and service times on a line ⋮ Improved algorithms for single vehicle scheduling on tree/cycle networks ⋮ Vehicle routing problems on a line-shaped network with release time constraints

Cites Work

• The delivery man problem on a tree network
• Vehicle scheduling on a tree with release and handling times
• Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints
• Technical Note—An Exact Algorithm for the Time-Constrained Traveling Salesman Problem
• Routing and Scheduling on a Shoreline with Release Times
• Survey Paper—Time Window Constrained Routing and Scheduling Problems
• On the worst-case performance of some heuristics for the vehicle routing and scheduling problem with time window constraints
• Efficient Solutions to Some Transportation Problems with Applications to Minimizing Robot Arm Travel
• Special cases of traveling salesman and repairman problems with time windows
• Preemptive Ensemble Motion Planning on a Tree
• A Note on the Complexity of a Simple Transportation Problem
• VEHICLE SCHEDULING ON A TREE TO MINIMIZE MAXIMUM LATENESS
• Sales‐delivery man problems on treelike networks

This page was built for publication: Better approximation ratios for the single-vehicle scheduling problems on line-shaped networks