Hybrid Genetic Search for the Vehicle Routing Problem with Time Windows: a High-Performance Implementation

Abstract

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.