Linear time approximation schemes for vehicle scheduling problems

DOI10.1016/J.TCS.2004.05.013MaRDI QIDQ1887080zbMATH OpenOpenAlexFDO

Authors John Augustine, Steven S. Seiden

Publication date 23 November 2004

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

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

zbMATH Keywords

Approximation algorithmDynamic programmingPolynomial time approximation schemeVehicle scheduling

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Deterministic scheduling theory in operations research (90B35) Dynamic programming (90C39) Approximation algorithms (68W25)

Recommendations

• scientific article; zbMATH DE number 2089206
• Approximation algorithms for the multi-vehicle scheduling problem
• Approximating a vehicle scheduling problem with time windows and handling times
• Better approximation ratios for the single-vehicle scheduling problems on line-shaped networks
• Linear programming-based approximation algorithms for multi-vehicle minimum latency problems (extended abstract)
• Linear formulations for the vehicle routing problem with synchronization constraints
• Vehicle scheduling on a graph revisited
• Approximation algorithms for some vehicle routing problems
• An exact algorithm for a vehicle-and-driver scheduling problem
• Publication:4889094

Cites work

• scientific article; zbMATH DE number 3912104 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2080977 (Why is no real title available?)
• scientific article; zbMATH DE number 1486639 (Why is no real title available?)
• scientific article; zbMATH DE number 956787 (Why is no real title available?)
• 2-approximation algorithms for the multi-vehicle scheduling problem on a path with release and handling times.
• Complexity Of The Single Vehicle Scheduling Problem On Graphs
• Complexity of Task Sequencing with Deadlines, Set-Up Times and Changeover Costs
• Reducibility among combinatorial problems
• Routing and Scheduling on a Shoreline with Release Times
• Special cases of traveling salesman and repairman problems with time windows
• The Euclidean traveling salesman problem is NP-complete
• VEHICLE SCHEDULING ON A TREE TO MINIMIZE MAXIMUM LATENESS
• Vehicle scheduling on a tree with release and handling times

Cited in

(15)

• Approximation algorithms for single vehicle scheduling problems with release and service times on a tree or cycle
• Approximation algorithms for a vehicle routing problem
• Improved algorithms for single vehicle scheduling on tree/cycle networks
• scientific article; zbMATH DE number 2080977 (Why is no real title available?)
• Routing open shop and flow shop scheduling problems
• Scheduling on a graph with release times
• Strip packing with precedence constraints and strip packing with release times
• scientific article; zbMATH DE number 2089206 (Why is no real title available?)
• Scheduling vehicles on trees
• Approximation algorithms for the multi-vehicle scheduling problem
• An approximability result of the multi-vehicle scheduling problem on a path with release and handling times
• Approximating a vehicle scheduling problem with time windows and handling times
• 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

This page was built for publication: Linear time approximation schemes for vehicle scheduling problems

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