travelling salesman problem variable neighborhood

Help | Advanced Search

Mathematics > Optimization and Control

Title: a variable neighborhood search for flying sidekick traveling salesman problem.

Abstract: The efficiency and dynamism of Unmanned Aerial Vehicles (UAVs), or drones, present substantial application opportunities in several industries in the last years. Notably, the logistic companies gave close attention to these vehicles envisioning reduce delivery time and operational cost. A variant of the Traveling Salesman Problem (TSP) called Flying Sidekick Traveling Salesman Problem (FSTSP) was introduced involving drone-assisted parcel delivery. The drone is launched from the truck, proceeds to deliver parcels to a customer and then is recovered by the truck in a third location. While the drone travels through a trip, the truck delivers parcels to other customers as long as the drone has enough battery to hover waiting for the truck. This work proposes a hybrid heuristic that the initial solution is created from the optimal TSP solution reached by a TSP solver. Next, an implementation of the General Variable Neighborhood Search is used to obtain the delivery routes of truck and drone. Computational experiments show the potential of the algorithm to improve the delivery time significantly. Furthermore, we provide a new set of instances based on well-known TSPLIB instances.

Submission history

Access paper:.

• Other Formats

References & Citations

• Google Scholar
• Semantic Scholar

BibTeX formatted citation

Bibliographic and Citation Tools

Code, data and media associated with this article, recommenders and search tools.

• Institution

arXivLabs: experimental projects with community collaborators

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs .

Subscribe to the PwC Newsletter

Join the community, edit social preview.

Add a new code entry for this paper

Remove a code repository from this paper, mark the official implementation from paper authors, add a new evaluation result row.

• TRAVELING SALESMAN PROBLEM

Remove a task

Add a method, remove a method, edit datasets, a variable neighborhood search for flying sidekick traveling salesman problem.

11 Apr 2018  ·  Julia C. Freitas , Puca Huachi V. Penna · Edit social preview

The efficiency and dynamism of Unmanned Aerial Vehicles (UAVs), or drones, present substantial application opportunities in several industries in the last years. Notably, the logistic companies gave close attention to these vehicles envisioning reduce delivery time and operational cost. A variant of the Traveling Salesman Problem (TSP) called Flying Sidekick Traveling Salesman Problem (FSTSP) was introduced involving drone-assisted parcel delivery. The drone is launched from the truck, proceeds to deliver parcels to a customer and then is recovered by the truck in a third location. While the drone travels through a trip, the truck delivers parcels to other customers as long as the drone has enough battery to hover waiting for the truck. This work proposes a hybrid heuristic that the initial solution is created from the optimal TSP solution reached by a TSP solver. Next, an implementation of the General Variable Neighborhood Search is used to obtain the delivery routes of truck and drone. Computational experiments show the potential of the algorithm to improve the delivery time significantly. Furthermore, we provide a new set of instances based on well-known TSPLIB instances.

Code Edit Add Remove Mark official

Tasks edit add remove, datasets edit, results from the paper edit, methods edit add remove.

• Help & FAQ

Precedence-Constrained Colored Traveling Salesman Problem: An Augmented Variable Neighborhood Search Approach

• Electrical and Computer Engineering

Research output : Contribution to journal › Article › peer-review

A colored traveling salesman problem (CTSP) as a generalization of the well-known multiple traveling salesman problem utilizes colors to distinguish the accessibility of individual cities to salesmen. This work formulates a precedence-constrained CTSP (PCTSP) over hypergraphs with asymmetric city distances. It is capable of modeling the problems with operations or activities constrained to precedence relationships in many applications. Two types of precedence constraints are taken into account, i.e., 1) among individual cities and 2) among city clusters. An augmented variable neighborhood search (VNS) called POPMUSIC-based VNS (PVNS) is proposed as a main framework for solving PCTSP. It harnesses a partial optimization metaheuristic under special intensification conditions to prepare candidate sets. Moreover, a topological sort-based greedy algorithm is developed to obtain a feasible solution at the initialization phase. Next, mutation and multi-insertion of constraint-preserving exchanges are combined to produce different neighborhoods of the current solution. Two kinds of constraint-preserving k -exchange are adopted to serve as a strong local search means. Extensive experiments are conducted on 34 cases. For the sake of comparison, Lin-Kernighan heuristic, two genetic algorithms and three VNS methods are adapted to PCTSP and fine-tuned by using an automatic algorithm configurator-irace package. The experimental results show that PVNS outperforms them in terms of both search ability and convergence rate. In addition, the study of four PVNS variants each lacking an important operator reveals that all operators play significant roles in PVNS.

All Science Journal Classification (ASJC) codes

• Information Systems
• Human-Computer Interaction
• Electrical and Electronic Engineering
• Control and Systems Engineering
• Computer Science Applications
• Colored traveling salesman problem (CTSP)
• constrained optimization
• machine learning
• partial optimization metaheuristic under special intensification conditions (POPMUSIC)
• precedence constraint
• variable neighborhood search (VNS)

Access to Document

• 10.1109/TCYB.2021.3070143

Other files and links

• Link to publication in Scopus
• Link to the citations in Scopus

Fingerprint

• Traveling salesman problem Engineering & Materials Science 100%
• Color Engineering & Materials Science 20%
• Genetic algorithms Engineering & Materials Science 19%
• Set theory Engineering & Materials Science 17%
• Experiments Engineering & Materials Science 9%

T1 - Precedence-Constrained Colored Traveling Salesman Problem

T2 - An Augmented Variable Neighborhood Search Approach

AU - Xu, Xiangping

AU - Li, Jun

AU - Zhou, Mengchu

AU - Yu, Xinghuo

N1 - Publisher Copyright: © 2013 IEEE.

PY - 2022/9/1

Y1 - 2022/9/1

N2 - A colored traveling salesman problem (CTSP) as a generalization of the well-known multiple traveling salesman problem utilizes colors to distinguish the accessibility of individual cities to salesmen. This work formulates a precedence-constrained CTSP (PCTSP) over hypergraphs with asymmetric city distances. It is capable of modeling the problems with operations or activities constrained to precedence relationships in many applications. Two types of precedence constraints are taken into account, i.e., 1) among individual cities and 2) among city clusters. An augmented variable neighborhood search (VNS) called POPMUSIC-based VNS (PVNS) is proposed as a main framework for solving PCTSP. It harnesses a partial optimization metaheuristic under special intensification conditions to prepare candidate sets. Moreover, a topological sort-based greedy algorithm is developed to obtain a feasible solution at the initialization phase. Next, mutation and multi-insertion of constraint-preserving exchanges are combined to produce different neighborhoods of the current solution. Two kinds of constraint-preserving k -exchange are adopted to serve as a strong local search means. Extensive experiments are conducted on 34 cases. For the sake of comparison, Lin-Kernighan heuristic, two genetic algorithms and three VNS methods are adapted to PCTSP and fine-tuned by using an automatic algorithm configurator-irace package. The experimental results show that PVNS outperforms them in terms of both search ability and convergence rate. In addition, the study of four PVNS variants each lacking an important operator reveals that all operators play significant roles in PVNS.

AB - A colored traveling salesman problem (CTSP) as a generalization of the well-known multiple traveling salesman problem utilizes colors to distinguish the accessibility of individual cities to salesmen. This work formulates a precedence-constrained CTSP (PCTSP) over hypergraphs with asymmetric city distances. It is capable of modeling the problems with operations or activities constrained to precedence relationships in many applications. Two types of precedence constraints are taken into account, i.e., 1) among individual cities and 2) among city clusters. An augmented variable neighborhood search (VNS) called POPMUSIC-based VNS (PVNS) is proposed as a main framework for solving PCTSP. It harnesses a partial optimization metaheuristic under special intensification conditions to prepare candidate sets. Moreover, a topological sort-based greedy algorithm is developed to obtain a feasible solution at the initialization phase. Next, mutation and multi-insertion of constraint-preserving exchanges are combined to produce different neighborhoods of the current solution. Two kinds of constraint-preserving k -exchange are adopted to serve as a strong local search means. Extensive experiments are conducted on 34 cases. For the sake of comparison, Lin-Kernighan heuristic, two genetic algorithms and three VNS methods are adapted to PCTSP and fine-tuned by using an automatic algorithm configurator-irace package. The experimental results show that PVNS outperforms them in terms of both search ability and convergence rate. In addition, the study of four PVNS variants each lacking an important operator reveals that all operators play significant roles in PVNS.

KW - Colored traveling salesman problem (CTSP)

KW - constrained optimization

KW - hypergraph

KW - machine learning

KW - partial optimization metaheuristic under special intensification conditions (POPMUSIC)

KW - precedence constraint

KW - variable neighborhood search (VNS)

UR - http://www.scopus.com/inward/record.url?scp=85107223116&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85107223116&partnerID=8YFLogxK

U2 - 10.1109/TCYB.2021.3070143

DO - 10.1109/TCYB.2021.3070143

M3 - Article

C2 - 34033558

AN - SCOPUS:85107223116

SN - 2168-2267

JO - IEEE Transactions on Cybernetics

JF - IEEE Transactions on Cybernetics

Precedence-Constrained Colored Traveling Salesman Problem: An Augmented Variable Neighborhood Search Approach

Ieee account.

• Change Username/Password
• Update Address

Purchase Details

• Payment Options
• Order History
• View Purchased Documents

Profile Information

• Communications Preferences
• Profession and Education
• Technical Interests
• US & Canada: +1 800 678 4333
• Worldwide: +1 732 981 0060
• Contact & Support
• About IEEE Xplore
• Accessibility
• Terms of Use
• Nondiscrimination Policy
• Privacy & Opting Out of Cookies

A not-for-profit organization, IEEE is the world's largest technical professional organization dedicated to advancing technology for the benefit of humanity. © Copyright 2024 IEEE - All rights reserved. Use of this web site signifies your agreement to the terms and conditions.

A parallel variable neighborhood search for solving covering salesman problem

• Original Paper
• Published: 14 September 2020
• Volume 16 , pages 175–190, ( 2022 )

Cite this article

• Xiaoning Zang 1 ,
• Li Jiang   ORCID: orcid.org/0000-0001-5599-7395 2 , 3 ,
• Mustapha Ratli 4 &
• Bin Ding 1  

460 Accesses

5 Citations

Explore all metrics

Covering salesman problem (CSP) is to construct a minimum length Hamiltonian cycle over a subset of vertices, in which the vertices not visited on the cycle must be covered by at least one visited vertex. In this paper, the CSP is reformulated as a bilevel CSP (BCSP) with a leader and a follower sub-problem. Two parallel variable neighborhood search (PVNS) heuristics, namely, synchronous “master–slave” PVNS and asynchronous cooperative PVNS, are proposed to solve the BCSP. To test the proposed algorithms, extensive computational experiments on the benchmark instances are performed, and the results indicate the effectiveness of the proposed approaches.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price includes VAT (Russian Federation)

Instant access to the full article PDF.

Rent this article via DeepDyve

Institutional subscriptions

Similar content being viewed by others

A comprehensive survey on NSGA-II for multi-objective optimization and applications

Computational complexity and algorithms for two scheduling problems under linear constraints

Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem

Current, J.R., Schilling, D.A.: The covering salesman problem. Transp. Sci. 23 , 208–213 (1989)

Article   MathSciNet   Google Scholar  

Golden, B., Naji-Azimi, Z., Raghavan, S., Salari, M., Toth, P.: The generalized covering salesman problem. INFORMS J. Comput. 24 , 534–553 (2012)

Salari, M., Naji-Azimi, Z.: An integer programming-based local search for the covering salesman problem. Comput. Oper. Res. 39 , 2594–2602 (2012)

Salari, M., Reihaneh, M., Sabbagh, M.S.: Combining ant colony optimization algorithm and dynamic programming technique for solving the covering salesman problem. Comput. Ind. Eng. 83 , 244–251 (2015)

Article   Google Scholar  

Gendreau, M., Laporte, G., Semet, F.: The covering tour problem. Oper. Res. 45 , 568–576 (1997)

Gendreau, M., Hertz, A., Laporte, G.: New insertion and postoptimization procedures for the traveling salesman problem. Oper. Res. 40 , 1086–1094 (1992)

Balas, E., Ho, A.: Set covering algorithms using cutting planes, heuristics, and subgradient optimization: A computational study. In: Padberg, M.W. (ed.) Combinatorial Optimization Mathematical Programming Studies, vol. 12. Springer, Berlin, Heidelberg (1980). https://doi.org/10.1007/BFb0120886

Chapter   Google Scholar  

Hachicha, M., Hodgson, M.J., Laporte, G., Semet, F.: Heuristics for the multi-vehicle covering tour problem. Comput. Oper. Res. 27 , 29–42 (2000)

Shaelaie, M.H., Salari, M., Naji-Azimi, Z.: The generalized covering traveling salesman problem. Appl. Soft Comput. 24 , 867–878 (2014)

Perez, J.A.M., Moreno-Vega, J.M., Martin, I.R.: Variable neighborhood tabu search and its application to the median cycle problem. Eur. J. Oper. Res. 151 , 365–378 (2003)

Renaud, J., Boctor, F.F., Laporte, G.: Efficient heuristics for median cycle problems. J. Oper. Res. Soc. 55 , 179–186 (2004)

Calvete, H.I., Gale, C., Iranzo, J.A.: An efficient evolutionary algorithm for the ring star problem. Eur. J. Oper. Res. 246 (1), 22–33 (2015)

Labbe, M., Laporte, G., Martin, I.R., Gonzalez, J.J.S.: The ring star problem: polyhedral analysis and exact algorithm. Networks 43 , 177–189 (2004)

Simonetti, L., Frota, Y., de Souza, C.C.: The ring-star problem: a new integer programming formulation and a branch-and-cut algorithm. Discrete Appl. Math. 159 , 1901–1914 (2011)

Kedad-Sidhoum, S., Viet Hung, N.: An exact algorithm for solving the ring star problem. Optimization 59 , 125–140 (2010)

Bean, J.C.: Genetic algorithms and random keys for sequencing and optimization. ORSA J. Comput. 6 , 154–160 (1994)

Calvete, H.I., Gale, C.: Linear bilevel multi-follower programming with independent followers. J. Glob. Optim. 39 , 409–417 (2007)

Affenzeller, M., Winkler, S.M., Wagner, S., Beham, A.: Genetic algorithms and genetic programming: modern concepts and practical applications. Parallel Process. Lett. 7 , 365–379 (2009)

MATH   Google Scholar  

Baldacci, R., Dell’Amico, M.: Heuristic algorithms for the multi-depot ring-star problem. Eur. J. Oper. Res. 203 , 270–281 (2010)

Baldacci, R., Dell’Amico, M., Gonzalez, J.S.: The capacitated m-ring-star problem. Oper. Res. 55 , 1147–1162 (2007)

Mladenovic, N., Hansen, P.: Variable neighborhood search. Comput. Oper. Res. 24 , 1097–1100 (1997)

Hemmelmayr, V.C., Doerner, K.F., Hartl, R.F.: A variable neighborhood search heuristic for periodic routing problems. Eur. J. Oper. Res. 195 , 791–802 (2009)

Jarboui, B., Derbel, H., Hanafi, S., Mladenovic, N.: Variable neighborhood search for location routing. Comput. Oper. Res. 40 , 47–57 (2013)

Hansen, P., Mladenovic, N., Todosijevic, R., Hanafi, S.: Variable neighborhood search: basics and variants. EURO J. Comput. Optim. 5 , 423–454 (2017)

Mjirda, A., Todosijevic, R., Hanafi, S., Hansen, P., Mladenovic, N.: Sequential variable neighborhood descent variants: an empirical study on the traveling salesman problem. Int. Trans. Oper. Res. 24 , 615–633 (2017)

Brimberg, J., Mladenovic, N., Todosijevic, R., Urosevic, D.: A basic variable neighborhood search heuristic for the uncapacitated multiple allocation p-hub center problem. Optim. Lett. 11 , 313–327 (2017)

Crainic, T.G., Hail, N.: Parallel Metaheuristics Applications. Wiley, New York (2005)

Book   Google Scholar  

Eskandarpour, M., Zegordi, S.H., Nikbakhsh, E.: A parallel variable neighborhood search for the multi-objective sustainable post-sales network design problem. Int. J. Prod. Econ. 145 , 117–131 (2013)

Wang, L.-Y., Huang, X., Ji, P., Feng, E.-M.: Unrelated parallel-machine scheduling with deteriorating maintenance activities to minimize the total completion time. Optim. Lett. 8 , 129–134 (2014)

Polat, O.: A parallel variable neighborhood search for the vehicle routing problem with divisible deliveries and pickups. Comput. Oper. Res. 85 , 71–86 (2017)

Herran, A., Colmenar, J.M., Duarte, A.: A variable neighborhood search approach for the Hamiltonian p-median problem. Appl. Soft Comput. 80 , 603–616 (2019)

Lin, S., Kernighan, B.W.: An effective heuristic algorithm for the travelling-salesman problem. Oper. Res. 21 , 498–516 (1973)

Reinelt, G.: TSPLIB—a traveling salesman problem library. ORSA J. Comput. 3 , 376–384 (1991)

Download references

Acknowledgements

This work was supported by the Ministry of Chinese Education, Humanities and Social Sciences under Grant 17YJA630037 and the Project of Graduate Teaching Quality in Hefei University of Technology (Grant No. 110-4116000050).

Author information

Authors and affiliations.

School of Management, University of Science and Technology of China, Hefei, 230026, Anhui, People’s Republic of China

Xiaoning Zang & Bin Ding

School of Management, Hefei University of Technology, Hefei, 230009, Anhui, People’s Republic of China

Key Laboratory of Process Optimization and Intelligent Decision-Making, Ministry of Education, Hefei, 230009, Anhui, People’s Republic of China

Université Polytechnique Hauts-De-France (UPHF)/LAMIH CNRS UMR 8201, Valenciennes Cedex 9, France

Mustapha Ratli

You can also search for this author in PubMed   Google Scholar

Corresponding author

Correspondence to Li Jiang .

Additional information

Publisher's note.

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Zang, X., Jiang, L., Ratli, M. et al. A parallel variable neighborhood search for solving covering salesman problem. Optim Lett 16 , 175–190 (2022). https://doi.org/10.1007/s11590-020-01642-8

Download citation

Received : 15 April 2020

Accepted : 01 September 2020

Published : 14 September 2020

Issue Date : January 2022

DOI : https://doi.org/10.1007/s11590-020-01642-8

Share this article

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

• Covering salesman problem
• Parallel variable neighborhood search
• Bilevel programming
• Find a journal
• Publish with us
• Track your research