Multi-depot vehicle routing problem: a comparative study of alternative formulations

ABSTRACT

This paper proposes a two-commodity flow formulation for the MDVRP considering a heterogeneous vehicle fleet and maximum routing time. Its computational performance is compared to a traditional formulation, the so called three-index formulation, which is adapted to fit the same problem. With the creation of subtours being a problem within such formulations, four alternative sets of constraints are considered to eliminate them: the Dantzig–Fulkerson–Johnson constraint, the Miller–Tucker–Zemlin constraint, the transit load constraint, and the arrival time constraint. The resulting mixed-integer linear programming models are then applied to a number of benchmark instances and the obtained performance results are compared.

KEYWORDS:

• Multi-depot
• vehicle routing
• MILP
• subtour elimination

Disclosure statement

No potential conflict of interest was reported by the authors.

ORCID

Tânia Rodrigues Pereira Ramos http://orcid.org/0000-0002-2321-2431