Approximation algorithms for deadline-TSP and vehicle routing with time-windows

DOI10.1145/1007352.1007385MaRDI QIDQ3580966zbMATH OpenOpenAlexFDO

Authors N. Bansal, Shuchi Chawla, Adam Meyerson, Avrim Blum

Publication date 15 August 2010

Published in Proceedings of the thirty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1007352.1007385

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation algorithms (68W25) Transportation, logistics and supply chain management (90B06)

Recommendations

• Deadline TSP
• Deadline TSP
• Approximation algorithms for time-dependent orienteering.
• scientific article; zbMATH DE number 1839476
• Poly-logarithmic Approximation Algorithms for Directed Vehicle Routing Problems

Cited in

(44)

• Faster algorithms for orienteering and \(k\)-TSP
• An approximation algorithm for vehicle routing with compatibility constraints
• The capacitated orienteering problem
• A bicriteria approximation algorithm for DVRP with time windows
• scientific article; zbMATH DE number 7053373 (Why is no real title available?)
• The robot routing problem for collecting aggregate stochastic rewards
• The multiple TSP with time windows: vehicle bounds based on precedence graphs
• Vehicle routing with time-dependent travel times: theory, practice, and benchmarks
• Adversarial patrolling with spatially uncertain alarm signals
• Orienteering for electioneering
• Earliest deadline first is a 2-approximation for DARP with time windows
• Simple heuristics for the rooted max tree coverage problem
• Scheduling on a graph with release times
• The online food delivery problem on stars
• Approximation schemes for Euclidean vehicle routing problems with time windows
• Poly-logarithmic Approximation Algorithms for Directed Vehicle Routing Problems
• Dynamic traveling repair problem with an arbitrary time window
• The school bus problem on trees
• The directed orienteering problem
• Deadline TSP
• On the adaptivity gap of stochastic orienteering
• Set covering in fuel-considered vehicle routing problems
• Approximation algorithms for the directed \(k\)-Tour and \(k\)-Stroll problems
• Deadline TSP
• Minimum Vehicle Routing with a Common Deadline
• The orienteering problem with time windows applied to robotic melon harvesting
• Running Errands in Time: Approximation Algorithms for Stochastic Orienteering
• Approximation algorithms for the traveling repairman and speeding deliveryman problems
• Approximating a vehicle scheduling problem with time windows and handling times
• Discounted reward TSP
• Delivery route optimization with automated vehicle in smart urban environment
• New approximation algorithms for the rooted budgeted cycle cover problem
• TSP race: minimizing completion time in time-sensitive applications
• Approximation algorithms for some extensions of the maximum profit routing problem
• Clique Inequalities Applied to the Vehicle Routing Problem with Time Windows
• Grasp and delivery for moving objects on broken lines
• Spider covers and their applications
• Combinatorial algorithms for rooted prize-collecting walks and applications to orienteering and minimum-latency problems
• Tour recommendation for groups
• Approximation algorithms for time-dependent orienteering.
• Complexity and approximation for traveling salesman problems with profits
• Pruning 2-connected graphs
• New approximation algorithms for the rooted budgeted cycle cover problem
• The parameterized approximability of TSP with deadlines

This page was built for publication: Approximation algorithms for deadline-TSP and vehicle routing with time-windows

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