Large Neighborhood Search based on Neural Construction Heuristics
This work addresses routing optimization for logistics and transportation, presenting an incremental improvement by integrating learned heuristics into traditional search methods.
The paper tackled the vehicle routing problem with time windows by proposing a Large Neighborhood Search approach that uses a neural network-based construction heuristic as a repair operator, achieving competitive results on standard benchmarks.
We propose a Large Neighborhood Search (LNS) approach utilizing a learned construction heuristic based on neural networks as repair operator to solve the vehicle routing problem with time windows (VRPTW). Our method uses graph neural networks to encode the problem and auto-regressively decodes a solution and is trained with reinforcement learning on the construction task without requiring any labels for supervision. The neural repair operator is combined with a local search routine, heuristic destruction operators and a selection procedure applied to a small population to arrive at a sophisticated solution approach. The key idea is to use the learned model to re-construct the partially destructed solution and to introduce randomness via the destruction heuristics (or the stochastic policy itself) to effectively explore a large neighborhood.