ADOPT: Combining parameter tuning and Adaptive Operator Ordering for solving a class of Orienteering Problems. (July 2018)

• Record Type: Journal Article
• Authors: Gunawan, Aldy; Lau, Hoong Chuin; Lu, Kun
• Is Part Of: Computers & industrial engineering. Volume 121(2018)
• Page Start: 82
• Page End: 96
• Publication Date: 2018-07
• Subjects: Design of experiment -- Adaptive operator ordering -- Local search -- Reinforcement learning -- Orienteering problem; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2018.05.016
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: ADOPT that combines two processes of determining parameter configurations and designing the Local procedure is proposed. ADOPT is applied to two algorithms for solving two variants of the Orienteering Problem. ADOPT with the fitness proportionate selection strategy outperforms over other strategies. Abstract: 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 AD aptive OP eraT or 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 2 k 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.