Publication: A multi-start granular skewed variable neighborhood tabu search for the roaming salesman problem
Program
KU-Authors
KU Authors
Co-Authors
Shahmanzari, Masoud
Publication Date
Language
Type
Embargo Status
Journal Title
Journal ISSN
Volume Title
Alternative Title
Abstract
This paper presents a novel hybrid metaheuristic algorithm for the Roaming Salesman Problem (RSP), called Multi-Start Granular Skewed Variable Neighborhood Tabu Search (MS-GSVNTS). The objective in RSP is to design daily tours for a traveling campaigner who collects rewards from activities in cities during a fixed planning horizon. RSP exhibits a number of exclusive features: It is selective which implies that not every node needs a visit. The rewards of cities are time-dependent. Daily tours can be either an open or a closed tour which implies the absence of a fixed depot. Instead, there is a campaign base that is to be attended frequently. Multiple visits are allowed for certain cities. The proposed method MS-GSVNTS is tested on 45 real-life instances from Turkey which are built with actual travel distances and times and on 10 large scale instances. Computational results suggest that MS-GSVNTS is superior to the existing solution methods developed for RSP. It produces 50 best known solutions including 18 ties and 32 new ones. The performance of MS-GSVNTS can be attributed to its multi-start feature, rich neighborhood structures, skewed moves, and granular neighborhoods.
Source
Publisher
Elsevier
Subject
Computer science, Artificial intelligence, Computer science, Interdisciplinary applications
Citation
Has Part
Source
Applied Soft Computing
Book Series Title
Edition
DOI
10.1016/j.asoc.2020.107024