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

DOI10.1016/J.TCS.2012.01.046MaRDI QIDQ428867zbMATHOpenAlexFDO

Authors 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

treeapproximation algorithmcyclevehicle routingvehicle scheduling

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Deterministic scheduling theory in operations research (90B35) Approximation algorithms (68W25)

Recommendations

• Better approximation ratios for the single-vehicle scheduling problems on tree/cycle networks
• Improved algorithms for single vehicle scheduling on tree/cycle networks
• Single-vehicle scheduling problems with release and service times on a line
• Single Vehicle Scheduling Problems on Path/Tree/Cycle Networks with Release and Handling Times
• scientific article; zbMATH DE number 2089206

Cites work

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

Cited in

(15)

• A quasi-polynomial time approximation scheme for Euclidean CVRPTW
• The single-node dynamic service scheduling and dispatching problem
• The multiple traveling salesman problem on spiders
• Improved algorithms for single vehicle scheduling on tree/cycle networks
• Single Vehicle Scheduling Problems on Path/Tree/Cycle Networks with Release and Handling Times
• Scheduling on a graph with release times
• Approximation schemes for Euclidean vehicle routing problems with time windows
• scientific article; zbMATH DE number 2089206 (Why is no real title available?)
• Set covering in fuel-considered vehicle routing problems
• Scheduling vehicles on trees
• Better approximation ratios for the single-vehicle scheduling problems on tree/cycle networks
• Single-vehicle scheduling problems with release and service times on a line
• Vehicle scheduling on a graph revisited
• Vehicle scheduling problems with two agents on a line
• Two-agent vehicle scheduling problem on a line-shaped network

This page was built for publication: Approximation algorithms for single vehicle scheduling problems with release and service times on a tree or cycle

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q428867)