Approximation Algorithms for Vehicle Routing Problems with Stochastic Demands on Trees

2013/04/22 by Vidyarthi, Shalabh, Shukla, Kaushal K
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1304.5991

Abstract

We consider the vehicle routing problem with stochastic demands (VRPSD) on tree structured networks with a single depot. The problem we are concerned with in this paper is to find a set of tours for the vehicle with minimum expected length. Every tour begins at the depot, visits a subset of customers and returns to the depot without violating the capacity constraint. Randomized approximation algorithm achieving approximation guarantees of 2 for split-delivery VRPSD, and 3 for un-split delivery VRPSD are obtained.

Related

• A Framework for Vehicle Routing Approximation Schemes in Trees
• An Approximation Algorithm for Distance-Constrained Vehicle Routing on Trees
• A Tight 4/3 Approximation for Capacitated Vehicle Routing in Trees
• Approximation Algorithms for the Cumulative Vehicle Routing Problem with Stochastic Demands
• A Tight (1.5+ε)-Approximation for Unsplittable Capacitated Vehicle Routing on Trees