Scheduled penalty Variable Neighborhood Search

For many NP-hardNP-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.