Wouter Kool, ORTEC

Abstract

This paper describes a high-performance implementation of Hybrid Genetic Search (HGS) for the Vehicle Routing Problem with Time Windows (VRPTW) [11]. We added time window support to the state-of-the-art open-source implementation of HGS for the Capacitated Vehicle Routing Problem (HGS-CVRP) [10], and included additional construction heuristics, a Selective Route Exchange (SREX) [6] crossover and an intensified local search procedure inspired by the SWAP* neighborhood [11]. The code has been optimized and we used different schedules for growing the size of neighborhood and population based on instance characteristics. For the VRPTW with distance-only objective (not minimizing vehicles) we found several improvements of best known solutions (BKS) for Gehring & Homberger [3] benchmark instances. The solver ranked 1st in Phase 1 of the VRPTW track of the 12th DIMACS implementation challenge.

[Challenge Paper]   [Video]