A matheuristic for the MinMax capacitated open vehicle routing problem

TY - JOUR

T1 - A matheuristic for the MinMax capacitated open vehicle routing problem

AU - Lysgaard, Jens

AU - López Sánchez, Ana Dolores

AU - Hernández-Díaz, Alfredo García

PY - 2020

Y1 - 2020

N2 - 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.

AB - 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.

KW - COVRP

KW - MinMax objective

KW - matheuristic

KW - vehicle routing problem

UR - http://www.scopus.com/inward/record.url?scp=85052670816&partnerID=8YFLogxK

U2 - 10.1111/itor.12581

DO - 10.1111/itor.12581

M3 - Journal article

SN - 0969-6016

VL - 27

SP - 394

EP - 417

JO - International Transactions in Operational Research

JF - International Transactions in Operational Research

IS - 1

ER -