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

Finn Fernstrøm, Teresa Anna Steiner*

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

Abstract

In this paper we introduce an a priori variant of the capacitated vehicle routing problem and provide a constant factor approximation algorithm, when the demands of customers are independent and identically distributed Bernoulli experiments. In the capacitated vehicle routing problem (CVRP) a vehicle, starting at a depot, must visit a set of customers to deliver the requested quantity of some item. The vehicle has capacity k, which is the maximum number of items that the vehicle can carry at any time, but it can always return to the depot to restock. The objective is to find the shortest tour subject to these constraints. In the a priori CVRP with unit demands the vehicle has to visit a set of active customers, drawn from some distribution. Every active customer has a demand of one. The goal is to find a master tour, which is a feasible solution to the deterministic CVRP, i.e. where all customers are active. Then, given a set of active customers, the tour is shortcut to only visit those customers. The cost of the tour is the expected cost with respect to the distribution of active customers. We consider the model, where every customer is independently active with the same probability. Let N be the number of customers. We provide an algorithm, which takes as input an a priori TSP solution with approximation factor γ, and gives a solution to the a priori CVRP with unit demands, whose cost is at most (1+k/N+γ) times the value of the optimal solution. Specifically, this gives an expected 5.5−approximation by using the 3.5−approximation to the a priori TSP from Van Ee and Sitters [17] and a deterministic 8.5−approximation by using the deterministic 6.5−approximation from Van Zuylen [18].

Original languageEnglish
Article number105960
JournalInformation Processing Letters
Volume159-160
Number of pages6
ISSN0020-0190
DOIs
Publication statusPublished - Jul 2020

Keywords

  • A priori optimization
  • Approximation algorithms
  • Vehicle routing problem

Cite this