ADOPT: Combining parameter tuning and adaptive operator ordering for solving a class of orienteering problems

• Main Authors: GUNAWAN, Aldy, LAU, Hoong Chuin, LU, Kun
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2018
• Subjects: Design of experiment; Adaptive operator ordering; Local search; Reinforcement learning; Orienteering problem; Databases and Information Systems; Operations Research, Systems Engineering and Industrial Engineering
• Online Access: https://ink.library.smu.edu.sg/sis_research/4221; https://ink.library.smu.edu.sg/context/sis_research/article/5224/viewcontent/ADOPT_Combining_Parameter_Tuning_and_Adaptive_Operator_Ordering_for_solving_a_Class_of_Orienteering_Problems.pdf
• Institution: Singapore Management University

Two fundamental challenges in local search based metaheuristics are how to determine parameter configurations and design the underlying Local Search (LS) procedure. In this paper, we propose a framework in order to handle both challenges, called ADaptive OPeraTor Ordering (ADOPT). In this paper, The ADOPT framework is applied to two metaheuristics, namely Iterated Local Search (ILS) and a hybridization of Simulated Annealing and ILS (SAILS) for solving two variants of the Orienteering Problem: the Team Dependent Orienteering Problem (TDOP) and the Team Orienteering Problem with Time Windows (TOPTW). This framework consists of two main processes. The Design of Experiment (DOE) process, which is based on a 2k factorial design, determines important parameters to tune and the best configuration for those parameters. The ADOPT process accommodates a reinforcement learning mechanism (based on Learning Automata) that calculates the probability of selecting an operator of LS. The probability values would be used to generate a sequence/order of operators for the next LS iteration, based on three different ordering strategies: rank-based, random and fitness proportionate selections. Our computational results show the superiority of the ADOPT framework with the fitness proportionate selection strategy against other ordering strategies in solving benchmark instances. In general, SAILS with the fitness proportionate selection strategy is competitive and comparable to the state-of-the-art algorithms. The proposed framework is able to improve the performances of both ILS and SAILS by discovering 11 new best known solutions of the benchmark TOPTW instances.