DNSGA-II-ALNS: A Warm-Start Evolutionary Algorithm for Dynamic Multi-Objective Optimization of Heterogeneous Vehicle Routing with Time Windows

Abstract

Dynamic heterogeneous vehicle routing with time windows requires reoptimization whenever customer arrivals and network disruptions change the decision space and the set of feasible routes. A reoptimized plan is useful in practice only if it does not rewrite the schedule that crews are already executing. This paper presents DNSGA-II-ALNS, an epoch-based dynamic multi-objective evolutionary algorithm. It couples an event-conditioned warm-start projection with an exact marginal assignment cost, feasibility-aware destroy-and-repair search and NSGA-II selection. The projection is not claimed to be a new optimization paradigm: it is a deterministic map between consecutive decision spaces that is defined even when a customer arrival changes their dimension, that introduces no constraint violation, and that leaves every customer unaffected by the event on its current vehicle. The algorithm is compared with seven alternatives under a paired protocol. All 56 Solomon instances are used with ten independent runs, and every method sees the same stored event stream for a given instance and run, a population of 50 and 8000 objective evaluations per epoch. The main empirical finding concerns plan stability. DNSGA-II-ALNS reassigns 11.1% of the persisting customers after an event, whereas a cold restart reassigns 89.2%, and the two groups do not overlap on any of the 56 instances. The reduction is not accompanied by a loss of solution quality, since the eight methods differ by at most 2.6% in total distance and 0.6% in makespan and all of them serve every customer within its time window. In front quality, the algorithm is not separated from the best-ranked method by the applied tests: it obtains the second-best Friedman mean rank (3.000 against 2.446), and the difference is smaller than the Nemenyi critical difference of 1.403. Advantages over the cold restart, MOPSO-ALNS and a memory-MOEA/D control are statistically significant with rank-biserial effect sizes of 0.84–0.87, while the comparisons with MODE-ALNS and the memory-NSGA-II control are not significant. An ablation indicates that the destroy-and-repair operators govern front quality, exceeding a routing-specific genetic control by 6.8–8.7% and a generic real-coded control by 15.9–26.4%. Quality is retained up to 200 customers at a fixed fleet density, but the mean response time rises from 33 to 716 s per epoch, which limits applicability to real-time dispatching. The contribution is accordingly operational rather than a new optimization methodology: comparable front quality at an order of magnitude less plan churn.