Premium
A matheuristic for the MinMax capacitated open vehicle routing problem
Author(s) -
Lysgaard Jens,
LópezSánchez Ana Dolores,
HernándezDíaz Alfredo G.
Publication year - 2020
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/itor.12581
Subject(s) - mathematical optimization , minimax , integer programming , metaheuristic , vehicle routing problem , computer science , linear programming , heuristic , routing (electronic design automation) , path (computing) , mathematics , computer network , programming language
In this paper, the MinMax‐COVRP (where COVRP is capacitated open vehicle routing problem) is considered as a variation of the COVRP where the objective is to minimize the duration of the longest route. For the purpose of producing high‐quality solutions, elements from the fields of mathematical programming and metaheuristics are combined, resulting in a matheuristic for solving the MinMax‐COVRP. The matheuristic benefits from the diversification produced by a metaheuristic and the intensification from mixed‐integer linear programming (MILP). The initial solution provided by a multistart heuristic is used to seed and accelerate the MILP in which a local branching framework and the separation of k ‐path inequalities are suitably combined. Computational experience shows promising results not only improving the initial solution provided by the multistart algorithm, but also ensuring optimality for most of the small‐ and medium‐sized instances.