Single-vehicle scheduling problems with release and service times on a line

DOI10.1002/net.20393zbMath1207.90061MaRDI QIDQ3082601

Zhaohui Liu, Wei Yu

Publication date: 16 March 2011

Published in: Networks (Search for Journal in Brave)

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

zbMATH Keywords

vehicle routing; approximation algorithm; vehicle scheduling

Mathematics Subject Classification ID

90B35: Deterministic scheduling theory in operations research

90C59: Approximation methods and heuristics in mathematical programming

90B20: Traffic problems in operations research

Related Items

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, Improved algorithms for single vehicle scheduling on tree/cycle networks, Vehicle scheduling problems with two agents on a line, Routing and scheduling problems with two agents on a line-shaped network, Two-agent vehicle scheduling problem on a line-shaped network

Cites Work

• A \(\frac{5}{3}\)-approximation algorithm for scheduling vehicles on a path with release and handling times
• 2-approximation algorithms for the multi-vehicle scheduling problem on a path with release and handling times.
• An approximability result of the multi-vehicle scheduling problem on a path with release and handling times
• Linear time approximation schemes for vehicle scheduling problems
• Better approximation ratios for the single-vehicle scheduling problems on line-shaped networks
• Routing and Scheduling on a Shoreline with Release Times
• The complexity of the travelling repairman problem
• Special cases of traveling salesman and repairman problems with time windows
• Technical Note—Routing and Location-Routing p-Delivery Men Problems on a Path
• A note on the traveling repairman problem