A Variable Neighborhood Search Algorithm for Cost-Balanced Travelling Salesman Problem

Abstract

Travelling salesman problem (TSP) can be described as finding minimum Hamilton cycle cost for a network consisting of starting/ending nodes and intermediate nodes. It is one of the most practiced classical combinatorial optimization problems due to its several application areas as well as its convertibility to various problem types. For this reason, many researchers and practitioners have studied on several variations of the problem. Despite its simple structure, obtaining an exact solution becomes harder as the problem dimension increases. Therefore, heuristic algorithms have been widely adopted by various researchers in order to obtain near optimal solutions. Within the scope of this study, one of the recent variants of TSP which is known as Cost-Balanced TSP is considered and a solution approach based on the variable neighborhood search algorithm has been proposed. Computational experiments have been performed on twenty-two publicly available datasets which includes small, medium and large-scale instances. Efficiency of proposed solution approach has been discussed according to the computational results. © Springer Nature Switzerland AG 2021.