Journal article
Scheduled penalty Variable Neighborhood Search
Computers & operations research, Vol.52(Part B), pp.170-180
12/01/2014
DOI: 10.1016/j.cor.2013.12.004
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.
Details
- Title: Subtitle
- Scheduled penalty Variable Neighborhood Search
- Creators
- Barrett W. Thomas - University of IowaEmanuele Manni - University of Salento
- Resource Type
- Journal article
- Publication Details
- Computers & operations research, Vol.52(Part B), pp.170-180
- Publisher
- Elsevier Ltd
- DOI
- 10.1016/j.cor.2013.12.004
- ISSN
- 0305-0548
- eISSN
- 1873-765X
- Language
- English
- Date published
- 12/01/2014
- Academic Unit
- Bus Admin College; Business Analytics
- Record Identifier
- 9984380431102771
Metrics
2 Record Views