Approximation algorithms for single vehicle scheduling problems with release and service times on a tree or cycle

DOI10.1016/j.tcs.2012.01.046zbMath1242.90074MaRDI QIDQ428867

Xiaoguang Bao, Zhaohui Liu

Publication date: 25 June 2012

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

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

zbMATH Keywords

tree; cycle; vehicle routing; approximation algorithm; vehicle scheduling

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90B35: Deterministic scheduling theory in operations research

68W25: Approximation algorithms

Related Items

Approximation schemes for Euclidean vehicle routing problems with time windows, The multiple traveling salesman problem on spiders, Set covering in fuel-considered vehicle routing problems, Improved algorithms for single vehicle scheduling on tree/cycle networks, Vehicle scheduling problems with two agents on a line, Two-agent vehicle scheduling problem on a line-shaped network, A Quasi-polynomial Time Approximation Scheme for Euclidean CVRPTW

Cites Work

• A \(\frac{5}{3}\)-approximation algorithm for scheduling vehicles on a path with release and handling times
• Vehicle routing problems on a line-shaped network with release time constraints
• Vehicle scheduling on a tree 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
• Approximation Algorithms for the Multi-Vehicle Scheduling Problem
• Single-vehicle scheduling problems with release and service times on a line
• Better approximation ratios for the single-vehicle scheduling problems on line-shaped networks
• Routing and Scheduling on a Shoreline with Release Times
• Single Vehicle Scheduling Problems on Path/Tree/Cycle Networks with Release and Handling Times
• Special cases of traveling salesman and repairman problems with time windows
• Complexity Of The Single Vehicle Scheduling Problem On Graphs