Large Neighborhood Search based on Neural Construction Heuristics
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.
Code (1)
Tasks
reinforcement-learningReinforcement Learning (RL)Methods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Local Branching Relaxation Heuristics for Integer Linear Programs
Large Neighborhood Search (LNS) is a popular heuristic algorithm for solving combinatorial optimization problems (COP). It starts with an initial solution to the problem and iteratively improves it by searching a large n…
Combinatorial OptimizationFast Neighborhood Search Heuristics for the Colored Bin Packing Problem
The Colored Bin Packing Problem (CBPP) is a generalization of the Bin Packing Problem (BPP). The CBPP consists of packing a set of items, each with a weight and a color, in bins of limited capacity, minimizing the number…
Adaptive Anytime Multi-Agent Path Finding Using Bandit-Based Large Neighborhood Search
Anytime multi-agent path finding (MAPF) is a promising approach to scalable path optimization in large-scale multi-agent systems. State-of-the-art anytime MAPF is based on Large Neighborhood Search (LNS), where a fast in…
Multi-Agent Path FindingThompson SamplingG-LNS: Generative Large Neighborhood Search for LLM-Based Automatic Heuristic Design
While Large Language Models (LLMs) have recently shown promise in Automated Heuristic Design (AHD), existing approaches typically formulate AHD around constructive priority rules or parameterized local search guidance, t…
Matheuristics to optimize refueling and maintenance planning of nuclear power plants
Planning the maintenance of nuclear power plants is a complex optimization problem, involving a joint optimization of maintenance dates, fuel constraints and power production decisions. This paper investigates Mixed Inte…