Large Neighborhood Search

Ask about this topic

Overview

Large Neighborhood Search tackles hard combinatorial optimization problems by removing part of a feasible solution and rebuilding it, helping the search escape small local minima. It is used for vehicle routing, scheduling, assignment, packing, planning, and facility location, with repair often performed by exact solvers or constraint programming. Newer approaches learn or evolve destroy-and-repair operators using reinforcement learning, language models, graph features, or adaptive selection, and some incorporate neural predictions. Results are strong across many benchmarks, but the best operator can depend on the instance and runtime budget, leaving open how to generalize neighborhood choices while keeping repair effective.

Latest papers

CardsList

14 papers2 papers in the last four weeks, against 1 the four weeks before. 0.0% of all new papers.

  1. Adaptive Operator Selection in Bilevel Large Neighborhood Search for Electric Autonomous Dial-a-Ride Problem under Uncertainty

    Oct 3, 2026Ishara Hewa Pathiranange, Aneta NeumannVehicle RoutingLarge Neighborhood Search

    Machine Learning and Optimisation, School of Computer Science and Information Technology, Adelaide University, Adelaide, Australia

  2. GeoNest: Learning to Select Failure-Aware Neighborhoods for the Irregular Knapsack Problem in a Circular Container

    Sep 30, 2026Zhongman Du, Huiming Zhang, Linlin Yang +2Metaheuristic OptimizationCombinatorial Optimization

    Beihang University, Beijing, China · Communication University of China, Beijing, China · Hangzhou Innovation Institute of Beihang University, Hangzhou, China

  3. SPO: Discovering Adaptive Large Neighborhood Search Operators via Stackelberg Program Optimization

    Sep 25, 2026Xinyi Ke, Kai Li, Junliang Xing +2Large Neighborhood SearchLLM-Based Program Synthesis

    C2DL, Institute of Automation, Chinese Academy of Sciences · School of Artificial Intelligence, University of Chinese Academy of Sciences · Tsinghua University +2

  4. LLM-Guided Graph Generation for Structure-Based Local Improvement Methods

    Aug 13, 2026Hai Xia, Vaidyanathan Peruvemba Ramaswamy, Stefan SzeiderAutomated Heuristic DesignMetaheuristic Optimization

    Algorithms and Complexity Group, TU Wien, Austria

  5. When Is Heterogeneous Distance-Decay Facility Location Tractable? A Structural Classification, Exact Methods, and a Real-World Study

    Jul 18, 2026Zhou He, T. C. E. Cheng, Jichang DongMetaheuristic OptimizationCombinatorial Optimization

    School of Economics and Management, University of Chinese Academy of Sciences, N606-3, #3 Zhongguancun Nanyitiao, Haidian District, Beijing 100190, China · Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University, 11 Yuk Choi Rd, Hung Hom, Hong Kong, China

  6. Dynamical Vehicle Orienteering Problem for Multi-Rotor Unmanned Aerial Vehicles

    Jul 15, 2026František Nekovář, Matej Novosad, Martin Saska +1Trajectory OptimizationBranch and Bound

    Faculty of Electrical Engineering, Czech Technical University, Technicka 2, 166 27, Prague, Czech Republic

  7. A Policy Decomposition Framework for Dynamic Order Fulfillment Operations

    Jul 4, 2026Gal Neria, Michal Tzur, Marlin W. UlmerMetaheuristic OptimizationSupply Chain Management

    Massachusetts Institute of Technology, Cambridge, 02139, MA, USA · School of Industrial and Intelligent Systems Engineering, Tel Aviv University, Tel Aviv, 6997801, Israel · Otto-von-Guericke Universitat Magdeburg, Magdeburg, Germany

  8. Regularized Large Neighborhood Search

    Jun 1, 2026Germain Vivier-Ardisson, Laurent Demonet, Axel Parmentier +1Markov Chain Monte CarloMetaheuristic Optimization

    Google DeepMind & CERMICS · Google Research · CERMICS, ENPC, CNRS, IPP +1

  9. An Enhanced Large Neighborhood Search Approach for the Capacitated Facility Location Problem with Incompatible Customers

    May 27, 2026Ida Gjergji, Lucas Kletzander, Nysret Musliu +1Metaheuristic OptimizationCombinatorial Optimization

    DBAI, TU Wien, Austria · University of Udine, Italy

  10. CP or DP? Why Not Both: A Case Study in the Partial Shop Scheduling Problem

    May 22, 2026Emma Legrand, Roger Kameugne, Pierre SchausDynamic ProgrammingCombinatorial Optimization

    ICTEAM, UCLouvain, Belgium

  11. Efficient Multi-Objective Planning with Weighted Maximization Using Large Neighbourhood Search

    Apr 6, 2026Krishna Kalavadia, Shamak Dutta, Yash Vardhan Pant +1Multi-Objective Motion PlanningMulti-Objective Optimization

    Department of Electrical and Computer Engineering, University of Waterloo, Waterloo, Canada

  12. Large Neighborhood Search for Multi-Agent Task Assignment and Path Finding with Precedence Constraints

    Mar 30, 2026Viraj Parimi, Brian C. WilliamsMulti-Agent Path FindingMulti-Robot Task Allocation

    Massachusetts Institute of Technology

  13. Large Neighborhood Search meets Iterative Neural Constraint Heuristics

    Mar 21, 2026Yudong W. Xu, Wenhao Li, Scott Sanner +1Constraint SatisfactionLarge Neighborhood Search

    Department of Mechanical & Industrial Engineering, University of Toronto · Vector Institute

  14. Large Language Model-Driven Full-Component Evolution of Adaptive Large Neighborhood Search

    Mar 7, 2026Shaohua Yu, Tianyu Chen, Linyan Liu +1Automated Heuristic DesignLarge Neighborhood Search

    School of Intelligent Science and Technology, Nanjing University of Science and Technology, Nanjing 210094, China · School of Mechanical Engineering, Nanjing University of Science and Technology, Nanjing 210094, China · Université Paris-Saclay, CentraleSupélec, Laboratoire Génie Industriel, 91190, Gif-sur-Yvette, France +1