Francesco Cavaliere, University of Bologna

Abstract

Vehicle Routing Problems (VRPs) are a class of combinatorial optimization problems with a wide range of applications. In the past decades, numerous heuristic and exact approaches have been proposed to solve various VRP variants. However, developing a unifying framework for VRP heuristics is complex due to the balance required between the generality of the approach and the specificity in exploiting problem characteristics. A successful framework proposed by Vidal et al. [1] separated generic and variant-specific components of the algorithm. This separation helped to achieve a good compromise between efficiency and generality. However, the wide adoption of such a framework has been limited, possibly due to the absence of a public library to aid researchers with new heuristics ideas and techniques. In this ongoing work, we aim to extend the Resource Extension Function framework to generalize it to other classes of constraints and objective functions. Additionally, we plan to study and develop a taxonomy of VRP constraints and introduce reflection capabilities to the framework to enable specialized handling of the most costly operations, while still maintaining the generality of the unifying approach. Furthermore, we will apply the same rationale to the algorithmic counterpart and present a framework that can assist in the development of meta-heuristics by decomposing them into basic algorithmic components and providing ways to compose them together.

[Video]