Aarhus Universitets segl

A matheuristic for the MinMax capacitated open vehicle routing problem

Publikation: Bidrag til tidsskrift/Konferencebidrag i tidsskrift /Bidrag til avisTidsskriftartikelForskningpeer review


  • Jens Lysgaard
  • Ana Dolores López Sánchez, Pablo de Olavide University, Spanien
  • Alfredo García Hernández-Díaz, Pablo de Olavide University, Spanien

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.

TidsskriftInternational Transactions in Operational Research
Sider (fra-til)394-417
Antal sider24
StatusUdgivet - 2020

Se relationer på Aarhus Universitet Citationsformater

ID: 166288046