A survey on matheuristics for routing problems

In this paper, we survey the literature on matheuristics proposed to solve vehicle routing problems. A matheuristic makes use of mathematical programming models in a heuristic framework. Matheuristics have been applied to several different routing problems and include a number of different approaches. We propose a classification in three classes of matheuristics: decomposition approaches, improvement heuristics and branch-and-price/column generation-based approaches. The contribution of this paper is to offer to researchers interested in routing problems a structured overview of the most successful ideas to combine heuristic schemes and mathematical programming models to obtain high quality solutions. Moreover, we analyze the state of the art and provide insights and hints for future research.