In this paper we merge two problem independent search strategies, namely Local Branching and Sliced Neighbor- hood Search. They both integrate CP tree search with local search concepts, but while local branching is very effective in exploring small neighborhoods, its performances decrease when dealing with diversification and large neighborhood ex- ploration. On the other hand Sliced Neighborhood Search is an effective method for exploring random slices of large neighborhoods and in moving away arbitrarily far from an incumbent solution. For this reason we obtain very good results in improving a reference solution: Local Branching obtains a 35% improvement when SNS is integrated aggres- sively both in the neighborhood exploration and in the di- versification strategy. The tests were conducted on large instances of the Travelling Salesman Problem with Time Windows.

F. Parisini, M. Milano (2011). Improving CP-based Local Branching via Sliced Neighborhood Search. NEW YORK : ACM [10.1145/1982185.1982380].

Improving CP-based Local Branching via Sliced Neighborhood Search

MILANO, MICHELA
2011

Abstract

In this paper we merge two problem independent search strategies, namely Local Branching and Sliced Neighbor- hood Search. They both integrate CP tree search with local search concepts, but while local branching is very effective in exploring small neighborhoods, its performances decrease when dealing with diversification and large neighborhood ex- ploration. On the other hand Sliced Neighborhood Search is an effective method for exploring random slices of large neighborhoods and in moving away arbitrarily far from an incumbent solution. For this reason we obtain very good results in improving a reference solution: Local Branching obtains a 35% improvement when SNS is integrated aggres- sively both in the neighborhood exploration and in the di- versification strategy. The tests were conducted on large instances of the Travelling Salesman Problem with Time Windows.
2011
Proceedings of the 2011 ACM Symposium on Applied Computing (SAC)
887
892
F. Parisini, M. Milano (2011). Improving CP-based Local Branching via Sliced Neighborhood Search. NEW YORK : ACM [10.1145/1982185.1982380].
F. Parisini; M. Milano
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/119569
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? ND
social impact