Approximation algorithms for regret-bounded vehicle routing and applications to distance-constrained vehicle routing

We consider vehicle-routing problems (VRPs) that incorporate the notion of regret of a client, which is a measure of the waiting time of a client relative to its shortest-path distance from the depot. Formally, we consider both the additive and multiplicative versions of, what we call, the regret-bounded vehicle routing problem (RVRP). In these problems, we are given an undirected complete graph G = ({r} ∪ V,E) on n nodes with a distinguished root (depot) node r, edge costs {c_uv} that form a metric, and a regret bound R. Given a path P rooted at r and a node v ∈ P, let c_P(v) be the distance from r to v along P. The goal is to find the fewest number of paths rooted at r that cover all the nodes so that for every node v covered by (say) path P: (i) its additive regret c_P(v) -- c_rv, with respect to P is at most R in additive-RVRP; or (ii) its multiplicative regret, c_P(v)/c_rv, with respect to P is at most R in multiplicative-RVRP.

Our main result is the first constant-factor approximation algorithm for additive-RVRP. This is a substantial improvement over the previous-best O(log n)-approximation. Additive-RVRP turns out be a rather central vehicle-routing problem, whose study reveals insights into a variety of other regret-related problems as well as the classical distance-constrained VRP (DVRP), enabling us to obtain guarantees for these various problems by leveraging our algorithm for additive-RVRP and the underlying techniques. We obtain approximation ratios of [EQUATION] for multiplicative-RVRP, and [EQUATION] for DVRP with distance bound D via reductions to additive-RVRP; the latter improves upon the previous-best approximation for DVRP.

A noteworthy aspect of our results is that they are obtained by devising rounding techniques for a natural configuration-style LP. This furthers our understanding of LP-relaxations for VRPs and enriches the toolkit of techniques that have been utilized for configuration LPs.