April 06, 2022, 9:20 AM - 9:40 AM
Wouter Kool, ORTEC
This paper describes a high-performance implementation of Hybrid Genetic Search (HGS) for the Vehicle Routing Problem with Time Windows (VRPTW) . We added time window support to the state-of-the-art open-source implementation of HGS for the Capacitated Vehicle Routing Problem (HGS-CVRP) , and included additional construction heuristics, a Selective Route Exchange (SREX)  crossover and an intensified local search procedure inspired by the SWAP* neighborhood . 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  benchmark instances. The solver ranked 1st in Phase 1 of the VRPTW track of the 12th DIMACS implementation challenge.