nach oben

The Journal of Supercomputing

Erschienen in:

11.09.2024

A cloud computing approach to superscale colored traveling salesman problems

verfasst von: Zhicheng Lin, Jun Li, Yongcui Li

Erschienen in: The Journal of Supercomputing | Ausgabe 19/2024

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The colored traveling salesman problem (CTSP) generalizes the well-known multiple traveling salesman problem by utilizing colors to describe the accessibility of cities to individual salesmen. Many centralized algorithms have been developed to solve CTSP instances. This work presents a distributed solving framework and method for CTSP for the first time. The framework consists of multiple container-based computing nodes that rely on specific cloud infrastructures to perform distributed optimization in a pipeline style. In the framework, we develop a distributed Delaunay-triangulation-based variable neighborhood search (DDVNS) algorithm for solving a CTSP case decomposed into many traveling salesman problems. DDVNS exploits a two-stage initialization to generate an initial solution for all TSPs. After that, Delaunay-triangulation-based variable neighborhood search (DVNS) is employed to find local optima. Furthermore, the obtained solutions are improved by reallocating multicolor cities and iterating the search progress, ultimately leading to a group of CTSP solutions. Finally, extensive experiments show that DDVNS outperforms the state-of-the-art centralized VNS algorithms in terms of search efficiency and solution quality. Notably, we can achieve the best solution in a superscale case with 16 salesmen and 160,000 cities within 15 minutes, breaking the best record of CTSPs.

Vorheriger Artikel An energy-temperature aware routing protocol in wireless body area network: a fuzzy-based approach

Nächster Artikel A secure VM live migration technique in a cloud computing environment using blowfish and blockchain technology

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Li J, Zhou M, Sun Q et al (2014) Colored traveling salesman problem. IEEE T Cybernet 45(11):2390–2401. https://doi.org/10.1109/TCYB.2014.2371918CrossRef

Wang D (2019) Applying colored traveling salesman problems to the scheduling and coordination of multiple material handling robots. Dissertation, Southeast University

Meng X, Li J, Dai X et al (2017) Variable neighborhood search for a colored traveling salesman problem. IEEE T Intell Transp 19(4):1018–1026. https://doi.org/10.1109/TITS.2017.2706720CrossRef

Xu X, Li J, Zhou M (2020) Delaunay-triangulation-based variable neighborhood search to solve large-scale general colored traveling salesman problems. IEEE T Intell Transp 22(3):1583–1593. https://doi.org/10.1109/TITS.2020.2972389CrossRef

Li J, Meng X, Dai X (2017) Collision-free scheduling of multi-bridge machining systems: a colored traveling salesman problem-based approach. IEEE/CAA J Autom Sin 5(1):139–147. https://doi.org/10.1109/JAS.2017.7510415MathSciNetCrossRef

Pandiri V, Singh A (2018) A swarm intelligence approach for the colored traveling salesman problem. Appl Intell 48:4412–4428. https://doi.org/10.1007/s10489-018-1216-0CrossRef

He P, Hao JK, Wu Q (2021) Grouping memetic search for the colored traveling salesmen problem. Inform Sci 570:689–707. https://doi.org/10.1016/j.ins.2021.04.090MathSciNetCrossRef

Gong YJ, Chen WN, Zhan ZH et al (2015) Distributed evolutionary algorithms and their models: a survey of the state-of-the-art. Appl Soft Comput 34:286–300. https://doi.org/10.1016/j.asoc.2015.04.061CrossRef

Lin Z, Ding P, Li J (2021) Task scheduling and path planning of multiple AGVs via cloud and edge computing. In: 2021 IEEE International Conference on Networking, Sensing and Control (ICNSC), pp 1–6. https://doi.org/10.1109/ICNSC52481.2021.9702191

10.

Xu X, Li J, Zhou M et al (2022) Precedence-constrained colored traveling salesman problem: an augmented variable neighborhood search approach. IEEE T Cybernet 52(9):9797–9808. https://doi.org/10.1109/TCYB.2021.3070143CrossRef

11.

Alkaya AF, Duman E (2013) Application of sequence-dependent traveling salesman problem in printed circuit board assembly. IEEE T Comp Pack Man 3(6):1063–1076. https://doi.org/10.1109/TCPMT.2013.2252429CrossRef

12.

Ramon-Cortes C, Alvarez P, Lordan F et al (2021) A survey on the distributed computing stack. Comput Sci Rev 42:100422MathSciNetCrossRef

13.

Meng X, Li J, Zhou M et al (2016) Population-based incremental learning algorithm for a serial colored traveling salesman problem. IEEE T Syst Man Cy-s 48(2):277–288. https://doi.org/10.1109/TSMC.2016.2591267CrossRef

14.

Zhou Y, Xu W, Fu ZH et al (2022) Multi-neighborhood simulated annealing-based iterated local search for colored traveling salesman problems. IEEE T Intell Transp 23(9):16072–16082. https://doi.org/10.1109/TITS.2022.3147924CrossRef

15.

Li J, Meng X, Zhou M et al (2016) A two-stage approach to path planning and collision avoidance of multibridge machining systems. IEEE T Syst Man Cy-s 47(7):1039–1049. https://doi.org/10.1109/TSMC.2016.2531648CrossRef

16.

Dong X, Lin Q, Xu M et al (2019) Artificial bee colony algorithm with generating neighbourhood solution for large scale coloured traveling salesman problem. IET Intell Transp Syst 13(10):1483–1491. https://doi.org/10.1049/iet-its.2018.5359CrossRef

17.

Helsgaun K (2017) An Extension of the Lin–Kernighan–Helsgaun TSP Solver for Constrained Traveling Salesman and Vehicle Routing Problems: Technical report. Roskilde Universitet

18.

Sharma S, Chou J (2021) Distributed and incremental travelling salesman algorithm on time-evolving graphs. J Supercomput 77:10896–10920. https://doi.org/10.1007/s11227-021-03716-5CrossRef

19.

Honda K, Nagata Y, Ono I (2013) A parallel genetic algorithm with edge assembly crossover for 100,000-city scale tsps. In: 2013 IEEE Congress on Evolutionary Computation, pp 1278–1285. https://doi.org/10.1109/CEC.2013.6557712

20.

Koubâa A, Cheikhrouhou O, Bennaceur H et al (2017) Move and improve: a market-based mechanism for the multiple depot multiple travelling salesmen problem. J Intell Robot Syst 85:307–330. https://doi.org/10.1007/s10846-016-0400-xCrossRef

21.

Kratzke N, Quint PC (2017) Understanding cloud-native applications after 10 years of cloud computing-a systematic mapping study. J Syst Softw 126:1–16. https://doi.org/10.1016/j.jss.2017.01.001CrossRef

22.

Pahl C, Helmer S, Miori L, et al (2016) A container-based edge cloud paas architecture based on raspberry pi clusters. In: 2016 IEEE 4th International Conference on Future Internet of Things and Cloud Workshops (FiCloudW), pp 117–124. https://doi.org/10.1109/W-FiCloud.2016.36

23.

Wang ZC, Liang K, Bao XG et al (2024) A novel algorithm for solving the prize collecting traveling salesman problem based on DNA computing. IEEE T Nanobiosci 23(2):220–232. https://doi.org/10.1109/TNB.2023.3307458CrossRef

24.

Wu X, Wang Z, Wu T et al (2022) Solving the family traveling salesperson problem in the Adleman–Lipton model based on DNA computing. IEEE T Nanobiosci 21(1):75–85. https://doi.org/10.1109/TNB.2021.3109067CrossRef

25.

Hu Y, Yao Y, Lee WS (2020) A reinforcement learning approach for optimizing multiple traveling salesman problems over graphs. Knowl-Based Syst 204:106244. https://doi.org/10.1016/j.knosys.2020.106244CrossRef

26.

Hu Y, Zhang Z, Yao Y et al (2021) A bidirectional graph neural network for traveling salesman problems on arbitrary symmetric graphs. Eng Appl Artif Intel 97:104061. https://doi.org/10.1016/j.engappai.2020.104061CrossRef

27.

Gao C, Shang H, Xue K, et al (2024a) Towards generalizable neural solvers for vehicle routing problems via ensemble with transferrable local policy. https://arxiv.org/abs/2308.14104, arXiv:2308.14104

28.

Gao H, Zhou X, Xu X et al (2024) Amarl: an attention-based multiagent reinforcement learning approach to the min–max multiple traveling salesmen problem. IEEE Trans Neur Net Lear 35(7):9758–9772. https://doi.org/10.1109/TNNLS.2023.3236629CrossRef

29.

Zhan ZH, Wang ZJ, Jin H et al (2019) Adaptive distributed differential evolution. IEEE T Cybernet 50(11):4633–4647. https://doi.org/10.1109/TCYB.2019.2944873CrossRef

30.

Dokeroglu T, Sevinc E (2022) An island parallel Harris hawks optimization algorithm. Neural Comput Appl 34(21):18341–18368. https://doi.org/10.1007/s00521-022-07367-2CrossRef

31.

Alba E, Dorronsoro B (2005) The exploration/exploitation tradeoff in dynamic cellular genetic algorithms. IEEE Trans Evolut Comput 9(2):126–142. https://doi.org/10.1109/tevc.2005.843751CrossRef

32.

Pang T, Wei J, Chen K, et al (2022) An adaptive differential evolution with mutation strategy pools for global optimization. In: 2022 IEEE Congress on Evolutionary Computation (CEC), pp 1–7. https://doi.org/10.1109/CEC55065.2022.9870292

33.

Pellerin R, Perrier N, Berthaut F (2020) A survey of hybrid metaheuristics for the resource-constrained project scheduling problem. Eur J Oper Res 280(2):395–416. https://doi.org/10.1016/j.ejor.2019.01.063MathSciNetCrossRef

34.

Hemmelmayr VC (2015) Sequential and parallel large neighborhood search algorithms for the periodic location routing problem. Eur J Oper Res 243(1):52–60. https://doi.org/10.1016/j.ejor.2014.11.024MathSciNetCrossRef

35.

Shi J, Zhang Q (2018) A new cooperative framework for parallel trajectory-based metaheuristics. Appl Soft Comput 65:374–386. https://doi.org/10.1016/j.asoc.2018.01.022CrossRef

36.

Kiziloz HE, Dokeroglu T (2018) A robust and cooperative parallel tabu search algorithm for the maximum vertex weight clique problem. Comput Ind Eng 118:54–66. https://doi.org/10.1016/j.cie.2018.02.018CrossRef

37.

Saviniec L, Santos MO, Costa AM et al (2020) Pattern-based models and a cooperative parallel metaheuristic for high school timetabling problems. Eur J Oper Res 280(3):1064–1081. https://doi.org/10.1016/j.ejor.2019.08.001CrossRef

38.

Rudek R (2016) Computational complexity and solution algorithms for a vector sequencing problem. Comput Ind Eng 98:384–400. https://doi.org/10.1016/j.cie.2016.06.009CrossRef

39.

Rios E, Ochi LS, Boeres C et al (2018) Exploring parallel multi-gpu local search strategies in a metaheuristic framework. J Parallel Distr Com 111:39–55. https://doi.org/10.1016/j.jpdc.2017.06.011CrossRef

40.

Lee S, Kim SB (2019) Parallel simulated annealing with a greedy algorithm for Bayesian network structure learning. IEEE T Knowl Data En 32(6):1157–1166. https://doi.org/10.1109/tkde.2019.2899096CrossRef

41.

Almeida ALB, Lima JdC, Carvalho MAM (2022) Systematic literature review on parallel trajectory-based metaheuristics. ACM Comput Surv 55(8):1–34CrossRef

42.

Cao B, Zhao J, Lv Z et al (2017) A distributed parallel cooperative coevolutionary multiobjective evolutionary algorithm for large-scale optimization. IEEE Trans Ind Inform 13(4):2030–2038. https://doi.org/10.1109/TII.2017.2676000CrossRef

43.

Lai J, Lu X, Wang F et al (2019) Broadcast gossip algorithms for distributed peer-to-peer control in ac microgrids. IEEE Trans Ind Appl 55(3):2241–2251. https://doi.org/10.1109/TIA.2019.2898367CrossRef

44.

Wang L, Chen D, Deng Z et al (2011) Large scale distributed visualization on computational grids: a review. Comput Electr Eng 37(4):403–416. https://doi.org/10.1016/j.compeleceng.2011.05.010CrossRef

45.

Zhan ZH, Liu XF, Zhang H et al (2016) Cloudde: a heterogeneous differential evolution algorithm and its distributed cloud version. IEEE T Parallel Distr 28(3):704–716. https://doi.org/10.1109/TPDS.2016.2597826CrossRef

46.

Liao CL, Lee SJ, Chiou YS et al (2018) Power consumption minimization by distributive particle swarm optimization for luminance control and its parallel implementations. Expert Syst Appl 96:479–491CrossRef

47.

Salza P, Ferrucci F (2019) Speed up genetic algorithms in the cloud using software containers. Futur Gener Comput Syst 92:276–289. https://doi.org/10.1016/j.future.2018.09.066CrossRef

48.

Babu S (2010) Towards automatic optimization of mapreduce programs. In: Proceedings of the 1st ACM symposium on Cloud computing (SoCC), pp 137–142. https://doi.org/10.1145/1807128.1807150

49.

Zhang Y, Zhou Y, Lu H et al (2021) Spark cloud-based parallel computing for traffic network flow predictive control using non-analytical predictive model. IEEE Trans Intell Transp 23(7):7708–7720. https://doi.org/10.1109/TITS.2021.3071862CrossRef

50.

Groppe S (2020) Emergent models, frameworks, and hardware technologies for big data analytics. J Supercomput 76(3):1800–1827. https://doi.org/10.1007/s11227-018-2277-xCrossRef

51.

Nasiri H, Nasehi S, Goudarzi M (2019) Evaluation of distributed stream processing frameworks for IoT applications in smart cities. J Big Data 6:1–24. https://doi.org/10.1186/s40537-019-0215-2CrossRef

52.

Dziurzanski P, Zhao S, Przewozniczek M et al (2020) Scalable distributed evolutionary algorithm orchestration using docker containers. J Comput Sci 40:101069. https://doi.org/10.1016/j.jocs.2019.101069CrossRef

53.

Valdez MG, Guervós JJM (2021) A container-based cloud-native architecture for the reproducible execution of multi-population optimization algorithms. Futur Gener Comput Syst 116:234–252. https://doi.org/10.1016/j.future.2020.10.039CrossRef

54.

Khalloof H, Mohammad M, Shahoud S, et al (2020) A generic flexible and scalable framework for hierarchical parallelization of population-based metaheuristics. In: Proceedings of the 12th International Conference on ManagEment of Digital EcoSystems(MEDES), pp 124–131. https://doi.org/10.1016/j.iot.2021.100433

55.

Ivanovic M, Simic V (2022) Efficient evolutionary optimization using predictive auto-scaling in containerized environment. Appl Soft Comput 129:109610. https://doi.org/10.1016/j.asoc.2022.109610CrossRef

56.

Yu Y, Mo J, Deng Q et al (2022) Memristor parallel computing for a matrix-friendly genetic algorithm. IEEE T Evolut Comput 26(5):901–910. https://doi.org/10.1109/TEVC.2022.3144419CrossRef

57.

Keller Tesser R, Borin E (2023) Containers in hpc: a survey. J Supercomput 79(5):5759–5827. https://doi.org/10.1007/s11227-022-04848-yCrossRef

58.

Sayfan G (2017) Mastering kubernetes. Packt Publishing Ltd

59.

Meng Z, Wu Z, Muvianto C et al (2017) A data-oriented m2m messaging mechanism for industrial IoT applications. IEEE Internet Things 4(1):236–246. https://doi.org/10.1109/JIOT.2016.2646375CrossRef

Titel: A cloud computing approach to superscale colored traveling salesman problems
verfasst von: Zhicheng Lin
Jun Li
Yongcui Li
Publikationsdatum: 11.09.2024
Verlag: Springer US
Erschienen in: The Journal of Supercomputing / Ausgabe 19/2024
Print ISSN: 0920-8542
Elektronische ISSN: 1573-0484
DOI: https://doi.org/10.1007/s11227-024-06433-x

A container optimal matching deployment algorithm based on CN-Graph for mobile edge computing

NM-polynomial-based topological indices and graph entropies of porphyrazine

A sentiment-guided session-aware recommender system

Approximating neural distinguishers using differential-linear imbalance

Open Access

Unequal-radius clustering in WSN-based IoT networks: energy optimization and load balancing in UDCOPA protocol

An integrated CRITIC-MABAC model under 2-tuple linguistic cubic q-rung orthopair fuzzy information with advanced aggregation operators, designed for multiple attribute group decision-making

Premium Partner

Bildnachweise

Rittal/© Rittal, NTT Data/© NTT Data, Wildix/© Wildix, Ceyoniq Technology GmbH/© Ceyoniq Technology GmbH, arvato Systems GmbH/© arvato Systems GmbH, Ninox Software GmbH/© Ninox Software GmbH, Everyday Software S.L./© Everyday Software S.L., Redgate/© Redgate, CELONIS Labs GmbH, DC-Datacenter-Group GmbH/© DC-Datacenter-Group GmbH, all for one/© all for one, G Data CyberDefense/© G Data CyberDefense, FAST LTA/© FAST LTA, Vendosoft/© Vendosoft, Kumavision/© Kumavision, Noriis Network AG/© Noriis Network AG, WSW Software GmbH/© WSW Software GmbH

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

A container optimal matching deployment algorithm based on CN-Graph for mobile edge computing

NM-polynomial-based topological indices and graph entropies of porphyrazine

A sentiment-guided session-aware recommender system

Approximating neural distinguishers using differential-linear imbalance

Unequal-radius clustering in WSN-based IoT networks: energy optimization and load balancing in UDCOPA protocol

An integrated CRITIC-MABAC model under 2-tuple linguistic cubic q-rung orthopair fuzzy information with advanced aggregation operators, designed for multiple attribute group decision-making