A matheuristic for the asymmetric capacitated vehicle routing problem
MetadataShow full item record
In this paper, we propose a novel matheuristic for the Asymmetric Capacitated Vehicle Routing Problem (ACVRP). This optimization-based approach combines some heuristic concepts with compact mixed-integer linear programming (MILP) formulations. Basically, the proposed matheuristic includes three sequential stages. First, the problem size is heuristically reduced by discarding unpromising arcs. Second, a starting feasible solution is derived. Finally, an optimization-based improvement procedure is invoked to iteratively generate near-optimal solutions. This latter procedure requires solving a sequence of two- or three-vehicle ACVRP reduced instances. A peculiar feature of the solution strategy is that all the three stages are solely based on solving compact MILP formulations using a commercial solver and it does not resort to any constructive heuristic nor metaheuristic. We describe the results of extensive computational experiments, that were carried out on a large set of benchmark instances with up to 200 nodes, and we provide empirical evidence that the proposed matheuristic often delivers high-quality solutions.
Showing items related by title, author, creator and subject.
Lifted Polynomial Size Formulations for the Homogeneous and Heterogeneous Vehicle Routing Problems Leggieri V; Haouari M (2017)We propose compact formulations for the symmetric and asymmetric capacitated vehicle routing problems. These formulations are obtained by lifting, using the Reformulation–Linearization Technique, a novel polynomial size ...
Leggieri V; Haouari M (2017)Green vehicle routing (GVRP) is an active research area that is concerned with the development and analysis of distribution activities with eco-friendly vehicles. We propose a practical solution approach for the GVRP that ...
High-level fuzzy logic guidance system for an unmanned surface vehicle (USV) tasked to perform autonomous launch and recovery (ALR) of an autonomous underwater vehicle (AUV) Pearson D; An E; Dhanak M; von Ellenrieder K; Beaujean P (IEEE, 2014)