Approximation Results for a Balanced Capacitated Vehicle Routing Problem

This paper addresses a variant of the capacitated vehicle routing problem which targets balancing the load of the tours. The aim of this problem is to find a set of tours covering all the requests such that the loads of the tours are balanced. This problem is called balanced capacitated vehicle routing problem (BCVRP) and holds a central place in logistics management and distribution. We present an approximation algorithm with a precise formulation of the problem under the assumptions that the distance between the locations is symmetric and satisfies the triangle inequality.