Dynamic curriculum improves routing problem solving with genetic programming
DCL-GPGLS: Dynamic Curriculum Learning for Genetic Programming Guided Local Search in Large-Scale Vehicle Routing
Neural and Evolutionary Computing
Summary
Solving large vehicle routing problems efficiently can be very tough because testing all possible solutions takes a lot of time. The authors improved an existing method by making the training process smarter—they let the difficulty of training examples adapt during the learning based on current performance. This approach helps the system focus on examples at just the right difficulty level instead of following a fixed order. Their tests showed this new method gave better results on many unseen routing problems compared to previous strategies.
What this means in practice
- •For logistics software developers: Improve vehicle routing algorithms by dynamically selecting training examples that adjust to solution progress, yielding better route optimization.
- •For transportation operation teams: Use enhanced routing tools trained with adaptive difficulty to generate more efficient delivery routes for large-scale vehicle fleets.
Authors
Saining Liu, Yi Mei, Mengjie Zhang
Abstract
Genetic Programming Guided Local Search (GPGLS) uses genetic programming to evolve utility functions for guided local search in large-scale vehicle routing problems (LSVRPs). Evaluating every GP individual on every training instance at every generation is expensive, so GPGLS is usually trained on small instance batches. Existing curriculum-based GPGLS orders these batches mainly by instance size. Adaptive Curriculum Learning GPGLS (ACL-GPGLS) improves training efficiency by adapting when the search moves between fixed curriculum stages, but the instance difficulty order remains predefined. We propose DCL-GPGLS, which estimates the difficulty of each training instance from the current population's solution quality and updates the estimates during evolution. Each generation then receives a batch near a scheduled difficulty level, with a correction that limits repeated selection of the same instances. Experiments on a fixed training-test split of the CVRPLIB X set show that DCL-GPGLS achieves the best observed average rank and mean test cost among six training policies. It obtains the lowest mean cost on 36 of 65 unseen test instances and is significantly better than the static feedback-derived curriculum, matched in total evaluator calls, on 6 instances, with no significant difference on the remaining 59.