  We study the load balanced capacitated vehicle routing problem (LBCVRP): the
problem is to design a collection of tours for a fixed fleet of vehicles with
capacity Q to distribute a supply from a single depot between a number of
predefined clients, in a way that the total traveling cost is a minimum, and
the vehicle loads are balanced. The unbalanced loads cause the decrease of
distribution quality especially in business environments and exibility in the
logistics activities. The problem being NP-hard, we propose two approximation
algorithms. When the demands are equal, we present a (1-1/Q)p+3/2approximation
algorithm that finds balanced loads. Here, p is the approximation ratio for the
known metric traveling salesman problem (TSP). This result leads to a 2.5-1/Q
approximation ratio for the tree metrics since an optimal solution can be found
for the TSP on a tree. We present an improved 2 approximation algorithm. When
the demands are unequal, we focus on obtaining approximate solutions since
finding balanced loads is NP-complete. We propose an algorithm that provides a
4 approximation for the balance of the loads. We assume a second approach to
get around the difficulties of the feasibility. In this approach, we redefine
and convert the problem into a multi-objective problem. The algorithm we
propose has a 4 factor of approximation.
