A scatter search hybrid approach for team orienteering problem | [Journal of Theoretical and Applied Information Technology • 2020]

Author(s):

1. HAMZAH ALKHAZALEH: IT Department, School of Engineering and Technology, Aldar University College,Dubai, UAE

2. MASRI AYOB: Faculty Of Information Science & Technology, Universiti Kebangsaan Malaysia (UKM), 43600 Bangi, Selangor, Darul Ehsan, Malaysia.

3. AMER IBRAHIM: IT Department, School of Engineering and Technology, Aldar University College, Dubai, UAE

4. NAHIL ABED: IT Department, School of Engineering and Technology, Aldar University College, Dubai, UAE

5. MOHAMMAD HABLI: IT Department, School of Engineering and Technology, Aldar University College, Dubai, UAE

6. TAWFIK SAID: IT Department, School of Engineering and Technology, Aldar University College, Dubai, UAE

Abstract:

The Team Orienteering Problem (TOP) is a particular vehicle routing problem in which the aim is to search a fixed number of paths that maximize the scores associated with a set of given locations within a limited time. Scatter Search explores a search space of solutions systematically by evolving a small set of reference solutions. It has strategies for diversification (in diversification generation and subset generation methods); and intensification (in the improvement and updating method). However, all these methods are very time consuming. This paper proposes a scatter search hybrid approach (SSHA) to deal with the TOP by reduce processing time and maintaining a good set of references solutions in terms of diversity and quality. It uses some new operators, called reference set queen bee-method to initializing and updating the RefSet, and greedy select parents to selecting pairs from a reference set for the combination method to generate a new solution. Furthermore, to improve the quality of the solution, a local search is employed, called steepest descent to explore neighborhood in a fully deterministic manner and then selects the best neighbour. Experiments conducted on the standard benchmark of TOP clearly show that proposed approach outperforms the solving methods in the scientific literature. Our algorithm detects all but one of the best known solutions. A statistical test was conducted to determine the algorithm that performed better compared with the others. The results revealed that SSHA outperformed all state-of-the-art algorithms and was comparable to one algorithm.

Page(s): 3375-3391

DOI: DOI not available

Published: Journal: Journal of Theoretical and Applied Information Technology, Volume: 98, Issue: 16, Year: 2020

Keywords:

Team Orienteering Problem , Scatter Search Algorithm

References:

References are not available for this document.

Citations

Citations are not available for this document.

Citations

Downloads

Views