Publication Type

Journal Article

Version

publishedVersion

Publication Date

7-2018

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 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.

Keywords

Design of experiment, Adaptive operator ordering, Local search, Reinforcement learning, Orienteering problem

Discipline

Databases and Information Systems | Operations Research, Systems Engineering and Industrial Engineering

Research Areas

Intelligent Systems and Optimization

Publication

Computers and Industrial Engineering

Volume

121

First Page

82

Last Page

96

ISSN

0360-8352

Identifier

10.1016/j.cie.2018.05.016

Publisher

Elsevier

Embargo Period

5-10-2019

Copyright Owner and License

Authors

Additional URL

https://doi.org/10.1016/j.cie.2018.05.016

Download

Share

COinS