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

DOI10.1016/J.TCS.2012.01.046zbMath1242.90074OpenAlexW2084517609MaRDI 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

treecyclevehicle routingapproximation algorithmvehicle scheduling

Mathematics Subject Classification ID

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

Related Items (8)

The multiple traveling salesman problem on spiders ⋮ 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 ⋮ Scheduling on a graph with release times ⋮ Two-agent vehicle scheduling problem on a line-shaped network ⋮ Improved algorithms for single vehicle scheduling on tree/cycle networks ⋮ Vehicle scheduling problems with two agents on a line

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

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