Top

The Journal of Supercomputing

Published in:

15-03-2021

Distributed and incremental travelling salesman algorithm on time-evolving graphs

Authors: Shalini Sharma, Jerry Chou

Published in: The Journal of Supercomputing | Issue 10/2021

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Travelling salesman problem (TSP) is a graph problem that has been widely used in many applications, especially for transportation and logistics. Because TSP is a NP hard problem, minimizing the complexity of TSP algorithms is an important problem. Many heuristic algorithms have been proposed to compute the TSP tours of a given static graph. But limited studies have been done on time-evolving graph (TEG) where the graph can change over time due to update events, such as weight changes on edges or vertices. It is a more challenging problem because the speed of TSP computations must be high enough to catch up the graph update frequency. In this paper, we make the very first attempt to minimize the computation time of solving TSP on time-evolving graphs. By exploring parallel computing power and reusing previous computing results, we proposed a distributed and incremental TSP algorithm which can be implemented on vertex-centric parallel graph computing frameworks to efficiently find TSP tours on large changing graphs. Our incremental algorithm can maintain shortest TSP tour with minimum amount of recomputation. Through our experimental evaluation, we have shown incremental TSP algorithm is 98% faster than distributed algorithm.

previous article A novel dual-biological-community swarm intelligence algorithm with a commensal evolution strategy for multimodal problems

next article Research on GPU parallel algorithm for direct numerical solution of two-dimensional compressible flows

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Abdolrashidi A, Ramaswamy L (2016) Continual and cost-effective partitioning of dynamic graphs for optimizing big graph processing systems. In: 2016 IEEE International Congress on Big Data (BigData Congress), pp. 18–25 . https://doi.org/10.1109/BigDataCongress.2016.12

Anagnostopoulos A, Kumar R, Mahdian M, Upfal E, Vandin F (2012) Algorithms on evolving graphs. In: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS ’12, pp. 149–160. ACM, New York, NY, USA . https://doi.org/10.1145/2090236.2090249

Bahmani B, Kumar R, Mahdian M, Upfal E (2012) Pagerank on an evolving graph. In: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’12, pp. 24–32. ACM, New York, NY, USA . https://doi.org/10.1145/2339530.2339539

Blelloch GE, Gu Y, Shun J, Sun Y (2020) Randomized incremental convex hull is highly parallel. In: Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’20, p. 103–115. Association for Computing Machinery, New York, NY, USA . https://doi.org/10.1145/3350755.3400255

Brighen A, Slimani H, Rezgui A, Kheddouci H (2019) Listing all maximal cliques in large graphs on vertex-centric model. J. Supercomput. 75(8), 4918–4946 . http://dblp.uni-trier.de/db/journals/tjs/tjs75.html#BrighenSRK19

Chen P (2013) An improved genetic algorithm for solving the traveling salesman problem. In: 2013 Ninth International Conference on Natural Computation (ICNC), pp. 397–401 . https://doi.org/10.1109/ICNC.2013.6818008

Chen Z, Shen HT, Zhou X, Yu JX (2009) Monitoring path nearest neighbor in road networks. In: Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data, SIGMOD ’09, pp. 591–602

Cheng R, Hong J, Kyrola A, Miao Y, Weng X, Wu M, Yang F, Zhou L, Zhao F, Chen E (2012) Kineograph: Taking the pulse of a fast-changing and connected world. In: Proceedings of the 7th ACM European Conference on Computer Systems, EuroSys ’12, pp. 85–98. ACM, New York, NY, USA . https://doi.org/10.1145/2168836.2168846

Desikan P, Pathak N, Srivastava J, Kumar V (2005) Incremental page rank computation on evolving graphs. In: Special Interest Tracks and Posters of the 14th International Conference on World Wide Web, WWW ’05, pp. 1094–1095. ACM, New York, NY, USA . https://doi.org/10.1145/1062745.1062885

10.

Doekemeijer N, Varbanescu AL (2014) A survey of parallel graph processing frameworks. In: Delft University of Technology Parallel and Distributed Systems Report Series

11.

Dorigo M, Maniezzo V, Colorni A (1996) Ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics) 26(1), 29–41 . https://doi.org/10.1109/3477.484436

12.

Ediger D, McColl R, Riedy J, Bader DA (2012) Stinger: High performance data structure for streaming graphs. In: 2012 IEEE Conference on High Performance Extreme Computing, pp. 1–5 . https://doi.org/10.1109/HPEC.2012.6408680

13.

Fan W, Li J, Luo J, Tan Z, Wang X, Wu Y (2011) Incremental graph pattern matching. In: Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data, SIGMOD ’11, pp. 925–936. ACM, New York, NY, USA . https://doi.org/10.1145/1989323.1989420

14.

Fan W, Liu M, Tian C, Xu R, Zhou J (2020) Incrementalization of graph partitioning algorithms. Proc. VLDB Endow 13(10):1261–1274. https://doi.org/10.14778/3389133.3389142CrossRef

15.

Fan W, Wang X, Wu Y (2013) Incremental graph pattern matching. ACM Trans. Database Syst. 38(3) https://doi.org/10.1145/2489791

16.

Filippidou I, Kotidis Y (2015) Online and on-demand partitioning of streaming graphs. In: 2015 IEEE International Conference on Big Data (Big Data), pp. 4–13 . https://doi.org/10.1109/BigData.2015.7363735

17.

Gao J, Zhou C, Yu JX (2016) Toward continuous pattern detection over evolving large graph with snapshot isolation. The VLDB Journal 25(2):269–290. https://doi.org/10.1007/s00778-015-0416-zCrossRef

18.

Glover F, Laguna M (1999) Tabu search I, vol. 1. Springer US . https://doi.org/10.1287/ijoc.1.3.190

19.

Han M, Daudjee K (2015) Giraph unchained: Barrierless asynchronous parallel execution in pregel-like graph processing systems. Proc. VLDB Endow. 8(9), 950–961. https://doi.org/10.14778/2777598.2777604

20.

Han W, Miao Y, Li K, Wu M, Yang F, Zhou L, Prabhakaran V, Chen W, Chen E (2014) Chronos: A graph engine for temporal graph analysis. In: Proceedings of the Ninth European Conference on Computer Systems, EuroSys ’14, pp. 1: 1:14. ACM, New York, NY, USA . https://doi.org/10.1145/2592798.2592799

21.

Hoffman Karla L.and Padberg M, Rinaldi G (2013) Traveling Salesman Problem, pp. 1573–1578. Springer

22.

Holland JH (1975) Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology. Control and Artificial Intelligence. University of Michigan Press, Ann Arbor, MIMATH

23.

Ji S, Zhao Y, Zhao X (2019) A low-latency computing framework for time-evolving graphs. J. Supercomput. 75(7):3673–3692. https://doi.org/10.1007/s11227-018-2725-7CrossRef

24.

Kao JS, Chou J (2016) Distributed incremental pattern matching on streaming graphs. In: Proceedings of the ACM Workshop on High Performance Graph Processing, HPGP ’16, pp. 43–50. ACM, New York, NY, USA . https://doi.org/10.1145/2915516.2915519

25.

Kennedy J, Eberhart R (1995) Particle swarm optimization. In: Proceedings of ICNN’95 - International Conference on Neural Networks, vol. 4, pp. 1942–1948 vol.4 . https://doi.org/10.1109/ICNN.1995.488968

26.

Kirkpatrick S, Gelatt CD, Vecchi MP (1983) Optimization by simulated annealing. Science 220(4598):671–680. https://doi.org/10.1126/science.220.4598.671MathSciNetCrossRefMATH

27.

Li B, Gao Z, Niu J, Lv Y, Zhang H (2015) Vertex-centric parallel algorithms for identifying key vertices in large-scale graphs. In: 2015 IEEE 17th International Conference on High Performance Computing and Communications, 2015 IEEE 7th International Symposium on Cyberspace Safety and Security, and 2015 IEEE 12th International Conference on Embedded Software and Systems, pp. 225–231

28.

Lin B, Sun X, Salous S (2016) Solving travelling salesman problem with an improved hybrid genetic algorithm. Journal of Computer and Communications 04:98–106. https://doi.org/10.4236/jcc.2016.415009CrossRef

29.

Lin S, Kernighan BW (1973) An effective heuristic algorithm for the traveling-salesman problem. Oper. Res. 21(2):498–516MathSciNetCrossRef

30.

Low Y, Gonzalez J, Kyrola A, Bickson D, Guestrin C, Hellerstein J (2010) Graphlab: A new framework for parallel machine learning. In: Proceedings of the Twenty-Sixth Conference on Uncertainty in Artificial Intelligence, UAI’10, p. 340–349. AUAI Press, Arlington, Virginia, USA

31.

Malewicz G, Austern MH, Bik AJ, Dehnert JC, Horn I, Leiser N, Czajkowski G (2010) Pregel: A system for large-scale graph processing. In: Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, SIGMOD ’10, pp. 135–146. ACM, New York, NY, USA . https://doi.org/10.1145/1807167.1807184

32.

Noyes D (2018) The top 20 valuable facebook. Web page . https://zephoria.com/top-15-valuable-facebook-statistics/. Last visited on 07/02/2018

33.

Junjie Pan , Dingwei Wang(2006) An ant colony optimization algorithm for multiple travelling salesman problem. In: First International Conference on Innovative Computing, Information and Control - Volume I (ICICIC’06), vol. 1, pp. 210–213

34.

Rapoport A, Horvath WJ (1961) A study of a large sociogram. Behavioral Science 6(4):279–291CrossRef

35.

Rosenkrantz DJ, Stearns RE, Lewis PM (1974) Approximate algorithms for the traveling salesperson problem. In: Proceedings of the 15th Annual Symposium on Switching and Automata Theory (Swat 1974), SWAT ’74, p. 33–42. IEEE Computer Society, USA . https://doi.org/10.1109/SWAT.1974.4

36.

Roy A, Mihailovic I, Zwaenepoel W (2013) X-stream: Edge-centric graph processing using streaming partitions. In: Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles, SOSP ’13, pp. 472–488. ACM, New York, NY, USA . https://doi.org/10.1145/2517349.2522740

37.

Salihoglu S, Widom J (2013) Gps: A graph processing system. In: Proceedings of the 25th International Conference on Scientific and Statistical Database Management, SSDBM. Association for Computing Machinery, New York, NY, USA . https://doi.org/10.1145/2484838.2484843

38.

Shalini Sharma J (2020) Chou: A survey of computation techniques on time evolving graphs. International Journal of Big Data Intelligence (IJBDI) 01. https://doi.org/10.1504/IJBDI.2020.106151

39.

Simmhan Y, Kumbhare AG, Wickramaarachchi C, Nagarkar S, Ravi S, Raghavendra CS, Prasanna VK (2013) Goffish: A sub-graph centric framework for large-scale graph analytics. CoRR abs/1311.5949 . http://arxiv.org/abs/1311.5949

40.

Tsourakakis C, Gkantsidis C, Radunovic B, Vojnovic M (2014) Fennel: Streaming graph partitioning for massive scale graphs. In: Proceedings of the 7th ACM International Conference on Web Search and Data Mining, WSDM ’14, pp. 333–342. ACM, New York, NY, USA . https://doi.org/10.1145/2556195.2556213

41.

Wang GQ, Wang J, Li M, Li H, Yuan Y (2015) Robot path planning based on the travelling salesman problem. Chemical engineering transactions 46:307–312

42.

Wickramaarachchi C, Frincu M, Prasanna V (2014) Enabling real-time pro-active analytics on streaming graphs. algorithms 15, 18

43.

Yang J, Shi X, Marchese M, Liang Y (2008) Ant colony optimization method for generalized tsp problem. Progress in Natural Science - PROG NAT SCI 18. https://doi.org/10.1016/j.pnsc.2008.03.028

44.

Yuan L, Qin L, Lin X, Chang L, Zhang W (2017) Effective and efficient dynamic graph coloring. Proc. VLDB Endow. 11(3), 338–351 . https://doi.org/10.14778/3157794.3157802

45.

Yuan P, Zhang W, Xie C, Jin H, Liu L, Lee K (2014) Fast iterative graph computation: A path centric approach. In: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC ’14, pp. 401–412. IEEE Press, Piscataway, NJ, USA . https://doi.org/10.1109/SC.2014.38

Title: Distributed and incremental travelling salesman algorithm on time-evolving graphs
Authors: Shalini Sharma
Jerry Chou
Publication date: 15-03-2021
Publisher: Springer US
Published in: The Journal of Supercomputing / Issue 10/2021
Print ISSN: 0920-8542
Electronic ISSN: 1573-0484
DOI: https://doi.org/10.1007/s11227-021-03716-5

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Other articles of this Issue 10/2021

A novel dual-biological-community swarm intelligence algorithm with a commensal evolution strategy for multimodal problems

Replication and data management-based workflow scheduling algorithm for multi-cloud data centre platform

DYRE: a DYnamic REconfigurable solution to increase GPGPU’s reliability

-version of the neutrosophic cubic set: application in the negative influences of Internet

CSMA/CA channel hopping in IoT environment toward intelligent multi-user diversity

Simple method of selecting totalistic rules for pseudorandom number generator based on nonuniform cellular automaton

Premium Partner