{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,27]],"date-time":"2026-05-27T17:52:53Z","timestamp":1779904373283,"version":"3.53.1"},"reference-count":47,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2024,8,13]],"date-time":"2024-08-13T00:00:00Z","timestamp":1723507200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["MAKE"],"abstract":"<jats:p>Multimodal Large Language Models (MLLMs) harness comprehensive knowledge spanning text, images, and audio to adeptly tackle complex problems. This study explores the ability of MLLMs in visually solving the Traveling Salesman Problem (TSP) and Multiple Traveling Salesman Problem (mTSP) using images that portray point distributions on a two-dimensional plane. We introduce a novel approach employing multiple specialized agents within the MLLM framework, each dedicated to optimizing solutions for these combinatorial challenges. We benchmarked our multi-agent model solutions against the Google OR tools, which served as the baseline for comparison. The results demonstrated that both multi-agent models\u2014Multi-Agent 1, which includes the initializer, critic, and scorer agents, and Multi-Agent 2, which comprises only the initializer and critic agents\u2014significantly improved the solution quality for TSP and mTSP problems. Multi-Agent 1 excelled in environments requiring detailed route refinement and evaluation, providing a robust framework for sophisticated optimizations. In contrast, Multi-Agent 2, focusing on iterative refinements by the initializer and critic, proved effective for rapid decision-making scenarios. These experiments yield promising outcomes, showcasing the robust visual reasoning capabilities of MLLMs in addressing diverse combinatorial problems. The findings underscore the potential of MLLMs as powerful tools in computational optimization, offering insights that could inspire further advancements in this promising field.<\/jats:p>","DOI":"10.3390\/make6030093","type":"journal-article","created":{"date-parts":[[2024,8,14]],"date-time":"2024-08-14T06:23:05Z","timestamp":1723616585000},"page":"1894-1921","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":26,"title":["Visual Reasoning and Multi-Agent Approach in Multimodal Large Language Models (MLLMs): Solving TSP and mTSP Combinatorial Challenges"],"prefix":"10.3390","volume":"6","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2634-4576","authenticated-orcid":false,"given":"Mohammed","family":"Elhenawy","sequence":"first","affiliation":[{"name":"Accident Research and Road Safety Queensland, Queensland University of Technology, Brisbane, 130 Victoria Park Rd, Kelvin Grove, QLD 4059, Australia"},{"name":"Centre for Data Science, Queensland University of Technology, Brisbane, 2 George St, Brisbane, QLD 4000, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6248-2138","authenticated-orcid":false,"given":"Ahmad","family":"Abutahoun","sequence":"additional","affiliation":[{"name":"Civil Engineering Department, Al-Ahliyya Amman University, Amman 19328, Jordan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6388-0904","authenticated-orcid":false,"given":"Taqwa I.","family":"Alhadidi","sequence":"additional","affiliation":[{"name":"Civil Engineering Department, Al-Ahliyya Amman University, Amman 19328, Jordan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5493-2530","authenticated-orcid":false,"given":"Ahmed","family":"Jaber","sequence":"additional","affiliation":[{"name":"Department of Transport Technology and Economics, Faculty of Transportation Engineering and Vehicle Engineering, Budapest University of Technology and Economics, M\u0171egyetem Rkp. 3., H-1111 Budapest, Hungary"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6835-8338","authenticated-orcid":false,"given":"Huthaifa I.","family":"Ashqar","sequence":"additional","affiliation":[{"name":"Civil Engineering Department, Faculty of Engineering, Arab American University, Jenin P.O. Box 240, Palestine"},{"name":"AI@Columbia, Fu Foundation School of Engineering and Applied Science, Columbia University, New York, NY 10027, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6322-2792","authenticated-orcid":false,"given":"Shadi","family":"Jaradat","sequence":"additional","affiliation":[{"name":"Accident Research and Road Safety Queensland, Queensland University of Technology, Brisbane, 130 Victoria Park Rd, Kelvin Grove, QLD 4059, Australia"},{"name":"Centre for Data Science, Queensland University of Technology, Brisbane, 2 George St, Brisbane, QLD 4000, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-4052-0391","authenticated-orcid":false,"given":"Ahmed","family":"Abdelhay","sequence":"additional","affiliation":[{"name":"Computer and Systems Engineering Department, Faculty of Engineering, Minia University, Minia 2431436, Egypt"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0658-7765","authenticated-orcid":false,"given":"Sebastien","family":"Glaser","sequence":"additional","affiliation":[{"name":"Accident Research and Road Safety Queensland, Queensland University of Technology, Brisbane, 130 Victoria Park Rd, Kelvin Grove, QLD 4059, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andry","family":"Rakotonirainy","sequence":"additional","affiliation":[{"name":"Accident Research and Road Safety Queensland, Queensland University of Technology, Brisbane, 130 Victoria Park Rd, Kelvin Grove, QLD 4059, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2024,8,13]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Liu, S., Chen, C., Qu, X., Tang, K., and Ong, Y.-S. (2023). Large Language Models as Evolutionary Optimizers. arXiv.","DOI":"10.1109\/CEC60901.2024.10611913"},{"key":"ref_2","unstructured":"Yang, C., Wang, X., Lu, Y., Liu, H., Le, Q.V., Zhou, D., and Chen, X. (2023). Large Language Models as Optimizers. arXiv."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Bellodi, E., Bertagnon, A., Gavanelli, M., and Zese, R. (2021). Improving the Efficiency of Euclidean TSP Solving in Constraint Programming by Predicting Effective Nocrossing Constraints, Springer International Publishing.","DOI":"10.1007\/978-3-030-77091-4_20"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Antuori, V., Hebrard, E., Huguet, M.-J., Essodaigui, S., and Nguyen, A. (2020). Leveraging Reinforcement Learning, Constraint Programming and Local Search: A Case Study in Car Manufacturing, Springer International Publishing.","DOI":"10.1007\/978-3-030-58475-7_38"},{"key":"ref_5","unstructured":"Hudson, B., Li, Q., Malencia, M., and Prorok, A. (2021). Graph Neural Network Guided Local Search for the Traveling Salesperson Problem. arXiv."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"625","DOI":"10.1007\/s00521-014-1743-5","article-title":"How Important Is a Transfer Function in Discrete Heuristic Algorithms","volume":"26","author":"Saremi","year":"2014","journal-title":"Neural Comput. Appl."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1007\/s10601-022-09327-y","article-title":"Learning the Travelling Salesperson Problem Requires Rethinking Generalization","volume":"27","author":"Joshi","year":"2022","journal-title":"Constraints"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"102861","DOI":"10.1016\/j.trc.2020.102861","article-title":"Multi-Vehicle Routing Problems with Soft Time Windows: A Multi-Agent Reinforcement Learning Approach","volume":"121","author":"Zhang","year":"2020","journal-title":"Transp. Res. Part. C Emerg. Technol."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"713043","DOI":"10.1155\/2015\/713043","article-title":"Reducing the Size of Combinatorial Optimization Problems Using the Operator Vaccine by Fuzzy Selector With Adaptive Heuristics","volume":"2015","author":"Montiel","year":"2015","journal-title":"Math. Probl. Eng."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"6567","DOI":"10.1007\/s00500-017-2705-5","article-title":"Two Phase Heuristic Algorithm for the Multiple-Travelling Salesman Problem","volume":"22","author":"Xu","year":"2018","journal-title":"Soft Comput."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"100369","DOI":"10.1016\/j.cosrev.2021.100369","article-title":"A Comprehensive Survey on the Multiple Traveling Salesman Problem: Applications, Approaches and Taxonomy","volume":"40","author":"Cheikhrouhou","year":"2021","journal-title":"Comput. Sci. Rev."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Jaradat, S., Alhadidi, T.I., Ashqar, H.I., Hossain, A., and Elhenawy, M. (2024). Exploring Traffic Crash Narratives in Jordan Using Text Mining Analytics. arXiv.","DOI":"10.1109\/ICMI60790.2024.10586010"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.4018\/IJWSR.338222","article-title":"Predictive Analytics in Mental Health Leveraging LLM Embeddings and Machine Learning Models for Social Media Analysis","volume":"21","author":"Radwan","year":"2024","journal-title":"Int. J. Web Serv. Res."},{"key":"ref_14","unstructured":"Ashqar, H.I., Alhadidi, T.I., Elhenawy, M., and Khanfar, N.O. (2024). The Use of Multimodal Large Language Models to Detect Objects from Thermal Images: Transportation Applications. arXiv."},{"key":"ref_15","unstructured":"Alhadidi, T.I., Jaber, A., Jaradat, S., Ashqar, H.I., and Elhenawy, M. (2024). Object Detection Using Oriented Window Learning Vi-Sion Transformer: Roadway Assets Recognition. arXiv."},{"key":"ref_16","unstructured":"Tami, M.A., Ashqar, H.I., and Elhenawy, M. (2024). Using Multimodal Large Language Models for Automated Detection of Traffic Safety Critical Events. arXiv."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Faigl, J., and Hollinger, G.A. (2014). Self-Organizing Map for the Prize-Collecting Traveling Salesman Problem, Springer International Publishing.","DOI":"10.1007\/978-3-319-07695-9_27"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"2003","DOI":"10.1007\/s11071-019-05092-5","article-title":"Continuous Relaxations for the Traveling Salesman Problem","volume":"97","author":"Sahai","year":"2019","journal-title":"Nonlinear Dyn."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"105887","DOI":"10.1016\/j.asoc.2019.105887","article-title":"Discrete Spider Monkey Optimization for Travelling Salesman Problem","volume":"86","author":"Akhand","year":"2020","journal-title":"Appl. Soft Comput."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Guang, R., and Khodadian, S. (2022). Linear Function Approximation as a Resource Efficient Method to Solve the Travelling Salesman Problem. J. Stud. Res., 10.","DOI":"10.47611\/jsrhs.v10i4.2143"},{"key":"ref_21","first-page":"114","article-title":"Solving Travelling Salesman Problem Using Artificial Immune System Optimization (AISO)","volume":"66","author":"Mandal","year":"2022","journal-title":"J. Sci. Res."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"1329","DOI":"10.2174\/1874444301507011329","article-title":"Research on Traveling Salesman Problem Based on the Ant Colony Optimization Algorithm and Genetic Algorithm","volume":"7","author":"Chen","year":"2015","journal-title":"Open Autom. Control Syst. J."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Bar\u00e1n, B., and G\u00f3mez, O.M. (2018). Omicron ACO. A New Ant Colony Optimization Algorithm. Clei Electron. J., 8.","DOI":"10.19153\/cleiej.8.1.5"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Shahadat, A.S.B., Akhand, M.A.H., and Kamal, A.S. (2022). Visibility Adaptation in Ant Colony Optimization for Solving Traveling Salesman Problem. Mathematics, 10.","DOI":"10.3390\/math10142448"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Xu, H., and Lan, H. (2023). An Adaptive Layered Clustering Framework with Improved Genetic Algorithm for Solving Large-Scale Traveling Salesman Problems. Electronics, 12.","DOI":"10.20944\/preprints202302.0412.v1"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1590\/0101-7438.2015.035.03.0465","article-title":"Quantum Inspired Particle Swarm Combined With Lin-Kernighan-Helsgaun Method to the Traveling Salesman Problem","volume":"35","author":"Herrera","year":"2015","journal-title":"Pesqui. Oper."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Evangelos, S., Papalitsas, C., and Andronikos, T. (2022). Experimental Analysis of Quantum Annealers and Hybrid Solvers Using Benchmark Optimization Problems. Mathematics, 10.","DOI":"10.3390\/math10081294"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1515\/jaiscr-2015-0032","article-title":"Optimization of Traveling Salesman Problem Using Affinity Propagation Clustering and Genetic Algorithm","volume":"5","author":"Ashour","year":"2015","journal-title":"J. Artif. Intell. Soft Comput. Res."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"730","DOI":"10.31181\/dmame04092023m","article-title":"Efficient Routing Optimization with Discrete Penguins Search Algorithm for MTSP","volume":"6","author":"Mzili","year":"2023","journal-title":"Decis. Mak. Appl. Manag. Eng."},{"key":"ref_30","unstructured":"Jiang, M., Ruan, Y., Huang, S., Liao, S., Pitis, S., Grosse, R.B., and Ba, J. (2024, August 08). Calibrating Language Models via Augmented Prompt Ensembles. Available online: https:\/\/openreview.net\/forum?id=L0dc4wqbNs#all."},{"key":"ref_31","unstructured":"Pitis, S., Zhang, M.R., Wang, A., and Ba, J. (2023). Boosted Prompt Ensembles for Large Language Models. arXiv."},{"key":"ref_32","first-page":"22199","article-title":"Large Language Models Are Zero-Shot Reasoners","volume":"35","author":"Kojima","year":"2022","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Zheng, J., He, K., Zhou, J., Yan, J., and Li, C.-M. (2022). Reinforced Lin-Kernighan-Helsgaun Algorithms for the Traveling Salesman Problems. arXiv.","DOI":"10.1016\/j.knosys.2022.110144"},{"key":"ref_34","unstructured":"Min, S., Lyu, X., Holtzman, A., Artetxe, M., Lewis, M., Hajishirzi, H., and Zettlemoyer, L. (2024, August 08). Rethinking the Role of Demonstrations: What Makes In-Context Learning Work?. Available online: https:\/\/openreview.net\/forum?id=cnRGMv-Ak7u."},{"key":"ref_35","first-page":"1877","article-title":"Language Models Are Few-Shot Learners","volume":"33","author":"Brown","year":"2020","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"ref_36","unstructured":"Zhang, Z., Zhang, A., Li, M., and Smola, A. (2022). Automatic Chain of Thought Prompting in Large Language Models. arXiv."},{"key":"ref_37","first-page":"24824","article-title":"Chain-of-Thought Prompting Elicits Reasoning in Large Language Models","volume":"35","author":"Wei","year":"2022","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"ref_38","unstructured":"Wang, X., Wei, J., Schuurmans, D., Le, Q., Chi, E., Narang, S., Chowdhery, A., and Zhou, D. (2022). Self-Consistency Improves Chain of Thought Reasoning in Language Models. arXiv."},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Wu, J., Gan, W., Chen, Z., Wan, S., and Yu, P.S. (2023, January 15\u201318). Multimodal Large Language Models: A Survey. Proceedings of the 2023 IEEE International Conference on Big Data (BigData), Sorrento, Italy.","DOI":"10.1109\/BigData59044.2023.10386743"},{"key":"ref_40","unstructured":"Huang, Y., Zhang, W., Feng, L., Wu, X., and Tan, K.C. (2024). How Multimodal Integration Boost the Performance of Llm for Optimization: Case Study on Capacitated Vehicle Routing Problems. arXiv."},{"key":"ref_41","unstructured":"Huang, Z., Shi, G., and Sukhatme, G.S. (2024). From Words to Routes: Applying Large Language Models to Vehicle Routing. arXiv."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"532","DOI":"10.1109\/JSTSP.2022.3162109","article-title":"Collaborative Intelligent Reflecting Surface Networks with Multi-Agent Reinforcement Learning","volume":"16","author":"Zhang","year":"2022","journal-title":"IEEE J. Sel. Top. Signal Process"},{"key":"ref_43","first-page":"29541","article-title":"Learning Distilled Collaboration Graph for Multi-Agent Perception","volume":"34","author":"Li","year":"2021","journal-title":"Adv. Neural Inf. Process Syst."},{"key":"ref_44","unstructured":"Mazumder, S., Liu, B., Ma, N., Wang, S., and Amazon, A.I. (2024, August 08). Continuous and Interactive Factual Knowledge Learning in Verification Dialogues. In Proceedings of the NeurIPS-2020 Workshop on Human and Machine in-the-Loop Evaluation and Learning Strategies, December 2020. Available online: https:\/\/www.cs.uic.edu\/~liub\/publications\/Neurips_workshop_HAMLETS_camera_ready.pdf."},{"key":"ref_45","first-page":"9459","article-title":"Retrieval-Augmented Generation for Knowledge-Intensive Nlp Tasks","volume":"33","author":"Lewis","year":"2020","journal-title":"Adv. Neural Inf. Process Syst."},{"key":"ref_46","doi-asserted-by":"crossref","unstructured":"Deudon, M., Cournut, P., Lacoste, A., Adulyasak, Y., and Rousseau, L.-M. (2018, January 26\u201329). Learning Heuristics for the Tsp by Policy Gradient. Proceedings of the Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 15th International Conference, CPAIOR 2018, Delft, The Netherlands. Proceedings 15.","DOI":"10.1007\/978-3-319-93031-2_12"},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"107823","DOI":"10.1016\/j.cie.2021.107823","article-title":"Integrated Scheduling of Zone Picking and Vehicle Routing Problem with Time Windows in the Front Warehouse Mode","volume":"163","author":"Chen","year":"2022","journal-title":"Comput. Ind. Eng."}],"container-title":["Machine Learning and Knowledge Extraction"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2504-4990\/6\/3\/93\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T15:36:03Z","timestamp":1760110563000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2504-4990\/6\/3\/93"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,13]]},"references-count":47,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2024,9]]}},"alternative-id":["make6030093"],"URL":"https:\/\/doi.org\/10.3390\/make6030093","relation":{},"ISSN":["2504-4990"],"issn-type":[{"value":"2504-4990","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,8,13]]}}}