Multi-depot vehicle routing problem: a comparative study of alternative formulations. Issue 2 (3rd March 2020) - Ramos, Tânia Rodrigues Pereira; Gomes, Maria Isabel; Póvoa, Ana Paula Barbosa
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.