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.

Autore Pugliese

• Manni Emanuele

Tutti gli autori

• B. W. Thomas , E. Manni

Titolo volume/Rivista

COMPUTERS & OPERATIONS RESEARCH

Anno di pubblicazione

2014

ISSN

0305-0548

ISBN

Non Disponibile

Numero di citazioni Wos

Nessuna citazione

Ultimo Aggiornamento Citazioni

Non Disponibile

Numero di citazioni Scopus

Non Disponibile

0

Ultimo Aggiornamento Citazioni

28/04/2018

Settori ERC

Non Disponibile

Codici ASJC

Non Disponibile