Generic adaptive heuristics for large neighborhood search
(2010) International conference on principles and practice of constraint programming — Location: St Andrews, Scotland (6.September.2010)
Files
generic.pdf
Open Access - Adobe PDF
- 203.38 KB
Details
- Authors
- Abstract
- The Large Neighborhood Search (LNS) approach for solving Constrained Optimization Problems has been proved to be eective on a wide range of problems. LNS is a local search metaheuristic that uses a complete search method (such as CP) to explore a large neighborhood. At each step, the neighborhood is dened by relaxing a subset, called fragment, of the variables in the current solution. Despite the success of LNS, no general principle has emerged on how to choose the fragment from one restart to the other. Practitioners often prefer to relax randomly the solution to favor diversication. This work focuses on the design of generic adaptive heuristics for choosing automatically the fragment in LNS, improving the standard random choice. The dened heuristics are tested on the Car Sequencing problem for which we introduce a new original relaxation. From those experiments, we conclude that all our heuristics except one are performing better than a random fragment selection. We also show that our mean dynamic impact proximity and min/max dynamic impact proximity heuristics are signicantly better than all the others.
- Affiliations
Citations
Mairy, J.-B., Schaus, P., & Deville, Y. (2010). Generic adaptive heuristics for large neighborhood search. International conference on principles and practice of constraint programming, St Andrews, Scotland. https://hdl.handle.net/2078.5/253958