Arc based integer programming formulations for the Distance Constrained Vehicle Routing problem

Abstract

The literature on the Distance Constrained Vehicle Routing Problem (DVRP), which is an important extension of the classical Vehicle Routing Problem (VRP), is scarce. In this paper, two new arc based integer programming formulations, with polynomial size are presented. It is shown that, second formulation, designated as strengthened model produces stronger lower bound than the first and existing arc based formulations. This formulation is compared with the recently proposed node based formulation in terms of linear programming relaxations and CPU times computationally. It is observed that, the second model is superior with respect to both performance indicators. It is also shown that the strengthened model can be easily adapted to the cases where additional restrictions imposed on vehicle's route length.