An iterated local search algorithm for solving the Orienteering Problem with Time Windows

• Main Authors: GUNAWAN, Aldy, LAU, Hoong Chuin, LU, Kun
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2015
• Subjects: Orienteering problem; Time windows; Iterated local search; Operations Research, Systems Engineering and Industrial Engineering; Theory and Algorithms
• Online Access: https://ink.library.smu.edu.sg/sis_research/2794; https://ink.library.smu.edu.sg/context/sis_research/article/3794/viewcontent/IteratedLocalSearchOPTW_2015_EvoCOP_afv.pdf
• Institution: Singapore Management University

The Orienteering Problem with Time Windows (OPTW) is a variant of the Orienteering Problem (OP). Given a set of nodes including their scores, service times and time windows, the goal is to maximize the total of scores collected by a particular route considering a predefined time window during which the service has to start. We propose an Iterated Local Search (ILS) algorithm to solve the OPTW, which is based on several LocalSearch operations, such as swap, 2-opt, insert and replace. We also implement the combination between AcceptanceCriterion and Perturbation mechanisms to control the balance between diversification and intensification of the search. In Perturbation, Shake strategy is introduced. The computational results obtained by our proposed algorithm are compared against optimal solutions or best known solution values obtained by state-of-the-art algorithms. We show experimentally that our proposed algorithm is effective on well-known benchmark instances available in the literature. It is also able to improve the best known solution of some benchmark instances.