Aarhus Universitets segl

English

Du er her: AU » Om AU » Organisation » A matheuristic for the MinMax capacitated open vehicle ro...

Om AU

A matheuristic for the MinMax capacitated open vehicle routing problem

Publikation: Bidrag til tidsskrift/Konferencebidrag i tidsskrift /Bidrag til avis › Tidsskriftartikel › Forskning › peer review

DOI

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

OriginalsprogEngelsk
TidsskriftInternational Transactions in Operational Research
Vol/bind27
Nummer1
Sider (fra-til)394-417
Antal sider24
ISSN0969-6016
DOI
StatusUdgivet - 2020

Se relationer på Aarhus Universitet Citationsformater

ID: 166288046