For many NP-hard combinatorial optimization problems, the existence of constraints complicates the implementation of a heuristic search procedure. In this paper, we propose a general heuristic framework that extends the well known Variable Neighborhood Search algorithm to include dynamic constraint penalization. We specifically focus on what are known as scheduled penalty methods and call the new algorithm scheduled-penalty Variable Neighborhood Search. The proposed method is tested on two well known constrained combinatorial optimization problems, namely the Traveling Salesman Problem with Time Windows and the Orienteering Problem with Time Windows. Our results demonstrate the effectiveness of the proposed algorithm, which is capable of producing high-quality solutions to the well known benchmark problems chosen in this paper with only minimal problem-specific tailoring of the general algorithm. Moreover, we introduce new best known solutions for some instances from the orienteering problem with time windows literature.

Scheduled penalty variable neighborhood search

MANNI, Emanuele
2014-01-01

Abstract

For many NP-hard combinatorial optimization problems, the existence of constraints complicates the implementation of a heuristic search procedure. In this paper, we propose a general heuristic framework that extends the well known Variable Neighborhood Search algorithm to include dynamic constraint penalization. We specifically focus on what are known as scheduled penalty methods and call the new algorithm scheduled-penalty Variable Neighborhood Search. The proposed method is tested on two well known constrained combinatorial optimization problems, namely the Traveling Salesman Problem with Time Windows and the Orienteering Problem with Time Windows. Our results demonstrate the effectiveness of the proposed algorithm, which is capable of producing high-quality solutions to the well known benchmark problems chosen in this paper with only minimal problem-specific tailoring of the general algorithm. Moreover, we introduce new best known solutions for some instances from the orienteering problem with time windows literature.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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/11587/389630
 Attenzione

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

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