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

Shaowen Lan, Yongliang Lu () and Wenjuan Fan
Additional contact information
Shaowen Lan: Fuzhou University
Yongliang Lu: Fuzhou University
Wenjuan Fan: Hefei University of Technology

Journal of Heuristics, 2025, vol. 31, issue 2, No 1, 65 pages

Abstract: Abstract 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.

Keywords: Heuristics; Traveling salesman problem; Job scheduling problem; Traveling salesman problem with job-times; Variable neighborhood search (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10732-025-09553-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joheur:v:31:y:2025:i:2:d:10.1007_s10732-025-09553-6

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-025-09553-6

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().