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.
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)
Hamel, AH; Benker, H (1998)A general optimal control problem for ordinary differential equations is considered. For this problem, some improvements of the algorithm of Sakawa are discussed. We avoid any convexity assumption and show with an example ...
Forced oscillations for singular dynamical systems with an application to the restricted three body problem Bertotti, ML (Elsevier, 1991)We consider forced dynamical systems with two degrees of freedom having singular potentials and we prove existence of infinitely many classical (noncollision) periodic solutions. These solutions have a prescribed rotation ...