IDEAS home Printed from https://ideas.repec.org/a/spr/joheur/v31y2025i2d10.1007_s10732-025-09553-6.html
   My bibliography  Save this article

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

Author

Listed:
  • Shaowen Lan

    (Fuzhou University)

  • Yongliang Lu

    (Fuzhou University)

  • Wenjuan Fan

    (Hefei University of Technology)

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.

Suggested Citation

  • Shaowen Lan & Yongliang Lu & Wenjuan Fan, 2025. "An adaptive variable neighborhood search for the traveling salesman problem with job-times," Journal of Heuristics, Springer, vol. 31(2), pages 1-65, June.
  • Handle: RePEc:spr:joheur:v:31:y:2025:i:2:d:10.1007_s10732-025-09553-6
    DOI: 10.1007/s10732-025-09553-6
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10732-025-09553-6
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.

    File URL: https://libkey.io/10.1007/s10732-025-09553-6?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Andreas Stenger & Daniele Vigo & Steffen Enz & Michael Schwind, 2013. "An Adaptive Variable Neighborhood Search Algorithm for a Vehicle Routing Problem Arising in Small Package Shipping," Transportation Science, INFORMS, vol. 47(1), pages 64-80, February.
    2. Tiniç, Gizem Ozbaygin & Karasan, Oya E. & Kara, Bahar Y. & Campbell, James F. & Ozel, Aysu, 2023. "Exact solution approaches for the minimum total cost traveling salesman problem with multiple drones," Transportation Research Part B: Methodological, Elsevier, vol. 168(C), pages 81-123.
    3. Gerhard Reinelt, 1991. "TSPLIB—A Traveling Salesman Problem Library," INFORMS Journal on Computing, INFORMS, vol. 3(4), pages 376-384, November.
    4. Francesco Carrabs & Jean-François Cordeau & Gilbert Laporte, 2007. "Variable Neighborhood Search for the Pickup and Delivery Traveling Salesman Problem with LIFO Loading," INFORMS Journal on Computing, INFORMS, vol. 19(4), pages 618-632, November.
    5. Michel Gendreau & Alain Hertz & Gilbert Laporte, 1992. "New Insertion and Postoptimization Procedures for the Traveling Salesman Problem," Operations Research, INFORMS, vol. 40(6), pages 1086-1094, December.
    6. M. Bellmore & G. L. Nemhauser, 1968. "The Traveling Salesman Problem: A Survey," Operations Research, INFORMS, vol. 16(3), pages 538-558, June.
    7. Yvan Dumas & Jacques Desrosiers & Eric Gelinas & Marius M. Solomon, 1995. "An Optimal Algorithm for the Traveling Salesman Problem with Time Windows," Operations Research, INFORMS, vol. 43(2), pages 367-371, April.
    8. Chen, Cheng & Demir, Emrah & Huang, Yuan, 2021. "An adaptive large neighborhood search heuristic for the vehicle routing problem with time windows and delivery robots," European Journal of Operational Research, Elsevier, vol. 294(3), pages 1164-1180.
    9. Merrill M. Flood, 1956. "The Traveling-Salesman Problem," Operations Research, INFORMS, vol. 4(1), pages 61-75, February.
    10. Baniasadi, Pouya & Foumani, Mehdi & Smith-Miles, Kate & Ejov, Vladimir, 2020. "A transformation technique for the clustered generalized traveling salesman problem with applications to logistics," European Journal of Operational Research, Elsevier, vol. 285(2), pages 444-457.
    11. Pierre Hansen & Nenad Mladenović & Raca Todosijević & Saïd Hanafi, 2017. "Variable neighborhood search: basics and variants," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 5(3), pages 423-454, September.
    12. G. A. Croes, 1958. "A Method for Solving Traveling-Salesman Problems," Operations Research, INFORMS, vol. 6(6), pages 791-812, December.
    13. G Laporte, 2010. "A concise guide to the Traveling Salesman Problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(1), pages 35-40, January.
    14. Helsgaun, Keld, 2000. "An effective implementation of the Lin-Kernighan traveling salesman heuristic," European Journal of Operational Research, Elsevier, vol. 126(1), pages 106-130, October.
    15. Doppstadt, C. & Koberstein, A. & Vigo, D., 2016. "The Hybrid Electric Vehicle – Traveling Salesman Problem," European Journal of Operational Research, Elsevier, vol. 253(3), pages 825-842.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Burger, M. & Su, Z. & De Schutter, B., 2018. "A node current-based 2-index formulation for the fixed-destination multi-depot travelling salesman problem," European Journal of Operational Research, Elsevier, vol. 265(2), pages 463-477.
    2. Lucas García & Pedro M. Talaván & Javier Yáñez, 2022. "The 2-opt behavior of the Hopfield Network applied to the TSP," Operational Research, Springer, vol. 22(2), pages 1127-1155, April.
    3. Zang, Xiaoning & Jiang, Li & Liang, Changyong & Fang, Xiang, 2023. "Coordinated home and locker deliveries: An exact approach for the urban delivery problem with conflicting time windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 177(C).
    4. Bruce Golden & Zahra Naji-Azimi & S. Raghavan & Majid Salari & Paolo Toth, 2012. "The Generalized Covering Salesman Problem," INFORMS Journal on Computing, INFORMS, vol. 24(4), pages 534-553, November.
    5. Pop, Petrică C. & Cosma, Ovidiu & Sabo, Cosmin & Sitar, Corina Pop, 2024. "A comprehensive survey on the generalized traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 314(3), pages 819-835.
    6. Jean-Charles Créput & Amir Hajjam & Abderrafiaa Koukam & Olivier Kuhn, 2012. "Self-organizing maps in population based metaheuristic to the dynamic vehicle routing problem," Journal of Combinatorial Optimization, Springer, vol. 24(4), pages 437-458, November.
    7. Marcel Turkensteen & Dmitry Malyshev & Boris Goldengorin & Panos M. Pardalos, 2017. "The reduction of computation times of upper and lower tolerances for selected combinatorial optimization problems," Journal of Global Optimization, Springer, vol. 68(3), pages 601-622, July.
    8. A. S. Santos & A. M. Madureira & M. L. R. Varela, 2018. "The Influence of Problem Specific Neighborhood Structures in Metaheuristics Performance," Journal of Mathematics, Hindawi, vol. 2018, pages 1-14, July.
    9. Manerba, Daniele & Mansini, Renata & Riera-Ledesma, Jorge, 2017. "The Traveling Purchaser Problem and its variants," European Journal of Operational Research, Elsevier, vol. 259(1), pages 1-18.
    10. Gary R. Waissi & Pragya Kaushal, 2020. "A polynomial matrix processing heuristic algorithm for finding high quality feasible solutions for the TSP," OPSEARCH, Springer;Operational Research Society of India, vol. 57(1), pages 73-87, March.
    11. Majid Namazi & M. A. Hakim Newton & Conrad Sanderson & Abdul Sattar, 2023. "Solving travelling thief problems using coordination based methods," Journal of Heuristics, Springer, vol. 29(4), pages 487-544, December.
    12. Xujin Chen & Xiaodong Hu & Xiaohua Jia & Zhongzheng Tang & Chenhao Wang & Ying Zhang, 2021. "Algorithms for the metric ring star problem with fixed edge-cost ratio," Journal of Combinatorial Optimization, Springer, vol. 42(3), pages 499-523, October.
    13. William Cook & Daniel G. Espinoza & Marcos Goycoolea, 2007. "Computing with Domino-Parity Inequalities for the Traveling Salesman Problem (TSP)," INFORMS Journal on Computing, INFORMS, vol. 19(3), pages 356-365, August.
    14. K Sang-Ho & G Young-Gun & K Maing-Kyu, 2003. "Application of the out-of-kilter algorithm to the asymmetric traveling salesman problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 54(10), pages 1085-1092, October.
    15. Gianpaolo Ghiani & Gilbert Laporte & Frédéric Semet, 2006. "The Black and White Traveling Salesman Problem," Operations Research, INFORMS, vol. 54(2), pages 366-378, April.
    16. William Cook & Paul Seymour, 2003. "Tour Merging via Branch-Decomposition," INFORMS Journal on Computing, INFORMS, vol. 15(3), pages 233-248, August.
    17. L Vogt & C A Poojari & J E Beasley, 2007. "A tabu search algorithm for the single vehicle routing allocation problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(4), pages 467-480, April.
    18. Shahin Gelareh & Bernard Gendron & Saïd Hanafi & Rahimeh Neamatian Monemi & Raca Todosijević, 2020. "The selective traveling salesman problem with draft limits," Journal of Heuristics, Springer, vol. 26(3), pages 339-352, June.
    19. Mauro Dell’Amico & Roberto Montemanni & Stefano Novellani, 2020. "Matheuristic algorithms for the parallel drone scheduling traveling salesman problem," Annals of Operations Research, Springer, vol. 289(2), pages 211-226, June.
    20. Sheldon H. Jacobson & Shane N. Hall & Laura A. McLay & Jeffrey E. Orosz, 2005. "Performance Analysis of Cyclical Simulated Annealing Algorithms," Methodology and Computing in Applied Probability, Springer, vol. 7(2), pages 183-201, June.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:joheur:v:31:y:2025:i:2:d:10.1007_s10732-025-09553-6. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.