An adaptive variable neighborhood search for the traveling salesman problem with job-times

The Traveling Salesman Problem with Job-times (TSPJ) is an extension problem that integrates the Traveling Salesman Problem and the Job Scheduling Problem. TSPJ refers to finding the optimal route for a salesman to visit each location exactly once while assigning one job to each location. Each job can only be assigned once, and its completion time depends on the assigned location. The objective of the TSPJ is to minimize the maximum completion time of all jobs. This paper studies the problem from a new perspective and illustrates the realistic application scenarios of TSPJ. To solve the problem efficiently, we propose a Variable Neighborhood Search algorithm embedded in an adaptive shaking strategy and an intensive local search procedure. The adaptive shaking strategy invokes the small-perturbation or large-perturbation strategy according to the searching states and results during the searching procedure. In the proposed local search procedure, the first improvement strategy is adopted and the parameter of perturbation strength is updated for the following procedures. Experimental results on 310 benchmark instances demonstrate that the proposed algorithm outperforms the state-of-the-art heuristic methods. In particular, the best-known solutions are improved in 241 instances and the proposed algorithm can obtain the same results as the best-known solutions in 60 instances. Two statistical tests show that the results obtained by the proposed algorithm have significant differences from those of the compared methods and therefore verify the superiority of our method.