A guided-ejection memetic algorithm for the three-objective VRPTW: Fleet, distance and workload balance

Abstract

The vehicle routing problem with time windows (VRPTW) underpins distribution and field-service operations, yet most multi-objective treatments optimise only fleet size and travelled distance, and rely on generic evolutionary operators that struggle to move the discrete, rugged fleet-size axis. We study a three-objective VRPTW that additionally minimises the imbalance of driver working times, a criterion of direct operational and fairness relevance, and propose MO-GEMA, a decomposition-based memetic algorithm built on three coordinated, routing-specific ideas. First, guided ejection search, hitherto a single-objective fleet minimiser, is lifted into a dedicated objective-axis operator that drives the fleet dimension from within the decomposition. Second, a balance-aware ruin operator dismantles the longest-duration routes for reconstruction, explicitly creating room to even out working times. Third, a weight-directed scalar local search shapes each subproblem so that the population spreads across the trade-off surface rather than collapsing onto a single corner. Beyond the algorithm, we provide guarantees rarely available for memetic routing solvers: the soundness and completeness of the Tchebycheff decomposition, the correctness and hypervolume monotonicity of the external archive, and a computable fleet lower bound that doubles as a provable early-stop signal for the guided-ejection operator. On the 100-customer Solomon instances, under an equal wall-clock budget, MO-GEMA attains the best overall mean hypervolume of 0.732 and the lowest IGD+ of 0.205 among ten algorithms, surpassing nine multi-objective baselines that span the classical (NSGA-II), decomposition (MOEA/D), learning-augmented (RL-AOS) and VRPTW-specific (MDLS, CLG-GA) families; the strongest of them, MDLS, reaches only 0.596, and MO-GEMA Pareto-dominates a far larger share of every baseline's front than the reverse. The same engine does not forfeit single-objective quality: on the hard R2 and RC2 classes, it matches or beats all seven algorithms of a recent state-of-the-art study on 16 of 19 instances under the classical lexicographic objective.