A Steiner Zone Variable Neighborhood Search Heuristic for the Close-Enough Traveling Salesman Problem. (January 2019)

• Record Type: Journal Article
• Authors: Wang, Xingyin; Golden, Bruce; Wasil, Edward
• Is Part Of: Computers & operations research. Volume 101(2019)
• Page Start: 200
• Page End: 219
• Publication Date: 2019-01
• Subjects: Traveling salesman -- Steiner zone -- Variable neighborhood search -- Heuristic; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2018.07.023
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: SZVNS produced optimal solutions to 93.2% of the small instances ( < = 30 customers). SZVNS produced better or comparable results on large instances ( < = 1000 customers). SZVNS was good at instances with small overlap ratios or nonuniform customer radius. Abstract: This paper addresses a variant of the Traveling Salesman Problem (TSP) known as the Close-Enough Traveling Salesman Problem (CETSP). A salesman does not have to visit the exact location of each customer. Instead, the salesman needs only to get close enough to each customer. This feature allows savings from the classic TSP solution, but also adds complexity to the problem. We develop a Steiner Zone Variable Neighborhood Search heuristic (SZVNS) to solve the CETSP. We conduct computational experiments on 842 instances. SZVNS often produces optimal solutions to the small instances where optimal solutions are known. On the larger instances, SZVNS produces shorter or similar solutions in less time when compared to the solutions produced by state-of-the-art heuristics.