Variable Neighborhood Search with Hill-Climbing Algorithm for Large Scale Optimization

Abstract Multiple maximum scatter traveling salesperson problem (MMSTSP) can be used to model the applications such as maximizing the benefits of multiple workflows with multiple machines, the scheduling optimization of logistics and manufacturing with multiple vehicles (machines). In computer science and operation research, MMSTSP are utilized to simulate some applications, where the scale easily tends to large scale. However, the traditional algorithms for large scale optimization are still limited on solution quality and convergence speed, these algorithms are based on heuristic rules and usually lack mathematical theoretical support. Aiming at this problem, this paper gives a novel hybrid variable neighborhood search based on hill-climbing algorithm (VNSHA) as the local optimization with Wiener process for solving large scale MMSTSP. The solutions of MMSTSP are optimized by the initialization operator, where the cities are inserted into the tours with the distance as max as possible, then the variable neighborhood search (VNS) and an extended hill-climbing algorithm (Interior and external neighborhood search optimization) with Wiener process are used for further optimization. During this process, the traveling routes can be optimized by changing the cities visiting sequence based on Wiener process. Experiments can show that the proposed algorithm VNSHA demonstrates better solution quality than the state-of-the-art algorithms for large scale optimization of MMSTSP.