Columnwise neighborhood search: A novel set partitioning matheuristic and its application to the VeRoLog Solver Challenge 2019

Caroline Jagtenberg, Oliver Maclaren, Andrew Mason, Andrea Raith, Kevin Shen, Michael Sundvick

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

This article reports on an approach for the VeRoLog Solver Challenge 2019: the fourth solver challenge facilitated by VeRoLog, the EURO Working Group on Vehicle Routing and Logistics Optimization. The authors were awarded third place in this challenge. The routing challenge involved solving two interlinked vehicle routing problems for equipment: one for distribution (using trucks) and one for installation (using technicians). We describe our solution method, based on a matheuristics approach in which the overall problem is heuristically decomposed into components that can then be solved by formulating them as set partitioning problems. To solve these set partitioning problems we introduce a novel method we call “columnwise neighborhood search,” which allows us to explore a large neighborhood of the current solution in an exact manner. By iteratively applying mixed‐integer programming methods, we obtain good quality solutions to our subproblems. We then use a simple local search “fusion” heuristic to further improve the solution to the overall problem. Besides introducing and discussing this solution method, we highlight the problem instances for which our approach was particularly successful in order to obtain general insights about our methodology.
Original languageEnglish
Pages (from-to)273-293
Number of pages21
JournalNetworks
Volume76
Issue number2
Early online date20 Jun 2020
DOIs
Publication statusPublished - Sep 2020

Bibliographical note

Special Issue on Optimization in Vehicle Routing and Logistics.

Fingerprint Dive into the research topics of 'Columnwise neighborhood search: A novel set partitioning matheuristic and its application to the VeRoLog Solver Challenge 2019'. Together they form a unique fingerprint.

Cite this