A constant approximation algorithm for the uniform a priori capacitated vehicle routing problem with unit demands

DOI10.1016/j.ipl.2020.105960zbMath1442.90165OpenAlexW3016225340MaRDI QIDQ783689

Teresa Anna Steiner, Finn Fernstrøm

Publication date: 4 August 2020

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2020.105960

zbMATH Keywords

vehicle routing problemapproximation algorithmsa priori optimization

Mathematics Subject Classification ID

Transportation, logistics and supply chain management (90B06) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items

Stochastic hub location problems with Bernoulli demands

Uses Software

• VRP

Cites Work

• Deterministic sampling algorithms for network design
• The A priori traveling repairman problem
• Improved bounds for vehicle routing solutions
• Algorithms for the universal and a priori TSP
• Heuristics for unequal weight delivery problems with a fixed error guarantee
• The vehicle routing problem: An overview of exact and approximate algorithms
• Stochastic vehicle routing
• A review of dynamic vehicle routing problems
• Technical Note—Approximation Algorithms for VRP with Stochastic Demands
• Selecting Good a Priori Sequences for Vehicle Routing Problem with Stochastic Demand
• Technical Note—Heuristics for Delivery Problems with Constant Error Guarantees
• A Constant Approximation Algorithm for the a priori Traveling Salesman Problem
• Bounds and Heuristics for Capacitated Routing Problems
• A Priori Solution of a Traveling Salesman Problem in Which a Random Subset of the Customers Are Visited
• Algorithms and Data Structures
• A Vehicle Routing Problem with Stochastic Demand