A matheuristic augmented ɛ-constraint framework for a bi-objective Multi-Depot Cumulative Capacitated Vehicle Routing Problem
Journal
European Journal of Operational Research
Publisher
Elsevier BV
Date Issued
2026-06
Author(s)
Segredo, Eduardo
Miranda, Gara
Lalla-Ruiz, Eduardo
Type
Article
Abstract
In this work, we extend the Multi-Depot Cumulative Capacitated Vehicle Routing Problem (MDCCVRP) to consider two objectives. Besides its cumulative aspect, i.e., minimizing the sum of customers’ waiting time, we also consider the travel cost minimization. To tackle this problem, we propose a novel matheuristic framework, called Math-AUGMECON-II, consisting of two stages. In the first stage, a multiobjective memetic algorithm based on the well-known Non-dominated Sorting Genetic Algorithm II (NSGA-II) is used to obtain an approximation to the Pareto front. This approximation of the Pareto front is then optimized in a second stage using the Augmented ɛ-Constraint II (AUGMECON-II) approach. The performance of NSGA-II, AUGMECON-II, and Math-AUGMECON-II is evaluated by their application to a set of well-known instances of the MDCCVRP with different sizes. The analyses based on different metrics, such as the number of solutions, hypervolume, and set coverage, reveal that AUGMECON-II is a suitable choice for small instances, while Math-AUGMECON-II is more appropriate to deal with medium and large instances, including instances with a reduced fleet size. Finally, a trade-off evaluation was carried out to examine the extent to which enhancing one objective impacts the other. It revealed that improving latency leads to an increase in travel cost, while improving travel cost results in a deterioration of latency. This highlights the asymmetric compromise between both objectives. © 2026 The Authors