Research HighlightsHybrid Global Optimization Approach for Efficiently Solving Vehicle Routing Problems
We propose a novel intertwined hybrid approach that exploits synergies among exact and metaheuristic algorithms to solve efficiently various Routing problems. The overall approach is exact, that is, it maintains the theoretical guarantee of reaching an optimal solution, but relies heavily on problem-specific heuristic components to accelerate the search. The backbone of the approach is a new branch-and-cut framework that includes new classes of local-scope cuts, dynamic constraint lifting, and sophisticated heuristic-based cut separation procedures. At each node of the solution tree, a subordinate adaptive memory programming procedure is employed to inform branching decisions and efficiently guide the tree search process. Conversely, knowledge extracted from the relaxation solution at each node is used by a local search-based Path-Relinking algorithm to identify high quality integer feasible solutions, to update the adaptive memory structures reactively and, therefore, to accelerate the updating of the incumbent. (Collaboration with Athens University of Economics and Business) |