This work introduces a new variant of the Multi-Depot Vehicle Routing Problem. In this problem, capacity constraints on the vehicles and length constraints on the routes of the drivers are imposed. To favor a better utilization of the available capacities and drivers working times, it is allowed to combine pairs of routes at predefined interchange locations, where two drivers can exchange their vehicles so that, even if each driver must return to his home depot at the end of the journey, vehicles can follow paths from one depot to another one. The objective is to minimize the total operational costs.

The main difficulty in formulating the MDVRPVI is the need for synchronization of the pairs of routes interchanging their vehicles. This requires considering explicitly the direction in which routes are performed. We propose a first MIP formulation of the MDVRPVI, based on the classical three-index vehicle flow formulation of the CVRP. Although, as it is well known, this type of formulations present awkward symmetry problems, this first formulation allows us to obtain optimal solutions to small instances of the MDVRPVI. Moreover, we study the problem structure and analyze the effect of allowing vehicle interchanges on the solution structure and cost. In order to solve larger instances, a two-index flow formulation has been performed. Additionally to the well-known subtour elimination constraints, other families of constraints need to be included to forbid pathological solution structures, such as, paths starting and ending in a different depot where a pair of routes are interchanged.