# PILS: Exploring high-order neighborhoods by pattern mining and injection

arXiv: https://arxiv.org/abs/1912.11462 · HTML: https://mlsanity.com/paper/1912.11462/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Dec 2019.

## Built on by (most cited first, 6 of 6)

- [Heuristics for Vehicle Routing Problem: A Survey and Recent Advances](https://mlsanity.com/paper/2303.04147/) (2023)
- [GELD: A Unified Neural Model for Efficiently Solving Traveling Salesman Problems Across Different Scales](https://mlsanity.com/paper/2506.06634/) (2025)
- [Spatial-temporal-demand clustering for solving large-scale vehicle routing problems with time windows](https://mlsanity.com/paper/2402.00041/) (2024)
- [Feature-Guided Metaheuristic with Diversity Management for Solving the Capacitated Vehicle Routing Problem](https://mlsanity.com/paper/2407.20777/) (2024)
- [Hybrid Node-Destroyer Model with Large Neighborhood Search for Solving the Capacitated Vehicle Routing Problem](https://mlsanity.com/paper/2508.08659/) (2025)
- [Edge-Selector Model Applied for Local Search Neighborhood for Solving Vehicle Routing Problems](https://mlsanity.com/paper/2508.14071/) (2025)

## Abstract (arXiv)

We introduce pattern injection local search (PILS), an optimization strategy that uses pattern mining to explore high-order local-search neighborhoods, and illustrate its application on the vehicle routing problem. PILS operates by storing a limited number of frequent patterns from elite solutions. During the local search, each pattern is used to define one move in which 1) incompatible edges are disconnected, 2) the edges defined by the pattern are reconnected, and 3) the remaining solution fragments are optimally reconnected. Each such move is accepted only in case of solution improvement. As visible in our experiments, this strategy results in a new paradigm of local search, which complements and enhances classical search approaches in a controllable amount of computational time. We demonstrate that PILS identifies useful high-order moves (e.g., 9-opt and 10-opt) which would otherwise not be found by enumeration, and that it significantly improves the performance of state-of-the-art population-based and neighborhood-centered metaheuristics.