Genetic programming improves vehicle routing by tracking search behaviour
Genetic Programming with Behaviour-based Niching for Learning Guided Local Search in Vehicle Routing Problems
Neural and Evolutionary Computing
Summary
Vehicle routing problems involve finding the best routes for delivering goods to many customers. The paper studies a method where computer programs learn to guide the search for good routing solutions using genetic programming. The authors found that looking at how these programs behave, not just how well they perform, helps keep variety in solutions and reduces program complexity. Their new approach balances solution quality and program size better than earlier methods.
What this means in practice
- •For logistics planners: Design routing strategies that adaptively use learnt utility guides improving efficiency on large vehicle routing tasks.
- •For metaheuristic developers: Incorporate behaviour-based niching to maintain diverse solution approaches and control solution complexity in optimization algorithms.
Authors
Saining Liu, Yi Mei, Mengjie Zhang
Abstract
Genetic Programming Guided Local Search (GPGLS) learns utility functions that guide local search for vehicle routing. Its evolving programs can have similar fitness while inducing different search behaviour, making fitness alone an incomplete basis for population diversity management. We propose GPGLS with Behaviour-based Niching (BN-GPGLS), which characterises programs through six operator-level descriptors collected during local search. A current-generation archive selects fitness-competitive, compact representatives from strata of a behaviour score. Fixed policies use archive parents continuously, whereas adaptive policies activate them using training-fitness and standardised behaviour-dispersion signals, optionally with a tree-size condition. We compare four behaviour-based variants with a no-archive GPGLS control and fitness-based niching over 30 seed-matched runs on generated 200-customer instances. BN-Adaptive achieves the best descriptive average rank on a separate 90-instance monitoring set; aggregate routing-cost differences are small. All five archive policies produce lower final-population median tree sizes than the GPGLS control, with paired Wilcoxon comparisons remaining significant after Holm adjustment. These results identify useful solution-quality and program-size trade-offs within the evaluated setting, without attributing the size reductions to behaviour representation alone.