Aarhus University Seal

A matheuristic for the MinMax capacitated open vehicle routing problem

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review


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

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.

Original languageEnglish
JournalInternational Transactions in Operational Research
Pages (from-to)394-417
Number of pages24
Publication statusPublished - 2020

    Research areas

  • COVRP, MinMax objective, matheuristic, vehicle routing problem

See relations at Aarhus University Citationformats

ID: 166288046