Department of Business Administration2024-11-0920211568-494610.1016/j.asoc.2020.1070242-s2.0-85099253826http://dx.doi.org/10.1016/j.asoc.2020.107024https://hdl.handle.net/20.500.14288/7825This 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.Computer scienceArtificial intelligenceComputer scienceInterdisciplinary applicationsA multi-start granular skewed variable neighborhood tabu search for the roaming salesman problemJournal Article1872-968163259930000110851