Have a personal or library account? Click to login
Traveling salesman problem parallelization by solving clustered subproblems Cover

Traveling salesman problem parallelization by solving clustered subproblems

By: Vadim Romanuke  
Open Access
|Dec 2023

References

  1. Archetti C., Peirano L., Speranza M. G., Optimization in multimodal freight transportation problems: A Survey, European Journal of Operational Research, 299 (1), 2022, 1 — 20.
  2. Bosch R., Herman A., Continuous line drawings via the traveling salesman problem, Operations Research Letters, 32 (4), 2004, 302 — 303.
  3. Chambers L. D., The Practical Handbook of Genetic Algorithms, Chapman and Hall/CRC, 2000.
  4. Cheikhrouhou O., Khoufi I., A comprehensive survey on the Multiple Traveling Salesman Problem: Applications, approaches and taxonomy, Computer Science Review, 40, 2021, Article ID 100369.
  5. Colorni A., Dorigo M., Maffioli F., Maniezzo V., Righini G., Trubian M., Heuristics from nature for hard combinatorial optimization problems, International Transactions in Operational Research, 3 (1), 1996, 1 — 21.
  6. Cormen T. H., Leiserson C. E., Rivest R. L., Stein C., Chapter 23: Minimum Spanning Trees, in: Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001, pp. 561 — 579.
  7. Du D.-Z., Pardalos P. M., Handbook of Combinatorial Optimization, New York, NY, USA, Springer, 1998.
  8. Fiechter C.-N., A parallel tabu search algorithm for large traveling salesman problems, Discrete Applied Mathematics, 51 (3), 1994, 243 — 267.
  9. Gower J. C., Ross G. J. S., Minimum spanning trees and single linkage cluster analysis, Applied Statistics, 18 (1), 1969, 54 — 61.
  10. Graham R. L., Hell P., On the history of the minimum spanning tree problem, Annals of the History of Computing, 7 (1), 1985, 43 — 57.
  11. Hartigan J. A., Wong M. A., Algorithm AS 136: A k-means clustering algorithm, Journal of the Royal Statistical Society, Series C, 28 (1), 1979, 100 — 108.
  12. Haupt R. L., Haupt S. E., Practical Genetic Algorithms, John Wiley & Sons, 2003.
  13. Hertz A., Widmer M., Guidelines for the use of meta-heuristics in combinatorial optimization, European Journal of Operational Research, 151 (2), 2003, 247 — 252.
  14. Honda K., Nagata Y., Ono I., A parallel genetic algorithm with edge assembly crossover for 100,000-city scale TSPs, 2013 IEEE Congress on Evolutionary Computation, June 20 — 23, 2013, Cancún, México, pp. 1278 — 1285.
  15. https://en.wikipedia.org/wiki/Concorde_TSP_Solver
  16. https://www.math.uwaterloo.ca/tsp/concorde/
  17. https://www.math.uwaterloo.ca/tsp/data/ml/monalisa.html
  18. Király A., Abonyi J., Redesign of the supply of mobile mechanics based on a novel genetic optimization algorithm using Google Maps API, Engineering Applications of Artificial Intelligence, 38, 2015, 122 — 130.
  19. Kneusel R., Random Numbers and Computers, Springer International Publishing, 2018.
  20. Kota L., Jarmai K., Mathematical modeling of multiple tour multiple traveling salesman problem using evolutionary programming, Applied Mathematical Modelling, 39 (12), 2015, 3410 — 3433.
  21. Macgregor J. N., Ormerod T., Human performance on the traveling salesman problem, Perception & Psychophysics, 58 (4), 1996, 527 — 539.
  22. Manfrin M., Birattari M., Stützle T., Dorigo M., Parallel ant colony optimization for the traveling salesman problem, in: Dorigo M., Gambardella L. M., Birattari M., Martinoli A., Poli R., Stützle T. (eds.), Ant Colony Optimization and Swarm Intelligence. ANTS 2006. Lecture Notes in Computer Science, vol. 4150. Springer, Berlin, Heidelberg, 2006, pp. 224 — 234.
  23. Miranda P. A., Blazquez C. A., Obreque C., Maturana-Ross J., Gutierrez-Jarpa G., The bi-objective insular traveling salesman problem with maritime and ground transportation costs, European Journal of Operational Research, 271 (3), 2018, 1014 — 1036.
  24. Press W. H., Teukolsky S. A., Vetterling W. T., Flannery B. P., Section 16.1. Gaussian Mixture Models and k-Means Clustering, in: Numerical Recipes: The Art of Scientific Computing (3rd edition), New York, NY, Cambridge University Press, 2007.
  25. Romanuke V. V., Division-by-q dichotomization for interval uncertainty reduction by cutting off equal parts from the left and right based on expert judgments under short-termed observations, Foundations of Computing and Decision Sciences, 45 (2), 2020, 125 — 155.
  26. Romanuke V. V., Hard and soft adjusting of a parameter with its known boundaries by the value based on the experts’ estimations limited to the parameter, Electrical, Control and Communication Engineering, 10, 2016, 23 — 28.
  27. Santini A., Viana A., Klimentova X., Pedroso J. P., The probabilistic travelling salesman problem with crowdsourcing, Computers & Operations Research, 142, 2022, Article ID 105722.
  28. Schneider J., Froschhammer C., Morgenstern I., Husslein T., Singer J. M., Searching for backbones — an efficient parallel algorithm for the traveling salesman problem, Computer Physics Communications, 96 (2–3), 1996, 173 — 188.
  29. Sofianopoulou S., Mitsopoulos I., A review and classification of heuristic algorithms for the inventory routing problem, International Journal of Operational Research, 41 (2), 2021, 282 — 298.
DOI: https://doi.org/10.2478/fcds-2023-0020 | Journal eISSN: 2300-3405 | Journal ISSN: 0867-6356
Language: English
Page range: 453 - 481
Submitted on: Aug 20, 2022
Accepted on: May 14, 2023
Published on: Dec 21, 2023
Published by: Poznan University of Technology
In partnership with: Paradigm Publishing Services
Publication frequency: 4 issues per year

© 2023 Vadim Romanuke, published by Poznan University of Technology
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.