{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T02:57:22Z","timestamp":1760237842628,"version":"build-2065373602"},"reference-count":40,"publisher":"MDPI AG","issue":"6","license":[{"start":{"date-parts":[[2020,6,26]],"date-time":"2020-06-26T00:00:00Z","timestamp":1593129600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>In this paper, a novel graph model to figure Collision-Free Multiple Traveling Salesman Problem (CFMTSP) is proposed. In this problem, a group of vehicles start from different nodes in an undirected graph and must visit each node in the graph, following the well-known Traveling Salesman Problem (TSP) fashion without any collision. This paper\u2019s main objective is to obtain free-collision routes for each vehicle while minimizing the traveling time of the slowest vehicle. This problem can be approached by applying speed to each vehicle, and a novel augmented graph model can perform it. This approach accommodates not only the position of nodes and inter-node distances, but also the speed of all the vehicles is proposed. The proposed augmented graph should be able to be used to perform optimal trajectories, i.e., routes and speeds, for all vehicles. An ant colony optimization (ACO) algorithm is used on the proposed augmented graph. Simulations show that the algorithm can satisfy the main objective. Considered factors, such as limitation of the mission successfulness, i.e., the inter-vehicle arrival time on a node, the number of vehicles, and the numbers of vehicles and edges of the graph are also discussed.<\/jats:p>","DOI":"10.3390\/a13060153","type":"journal-article","created":{"date-parts":[[2020,6,29]],"date-time":"2020-06-29T03:40:07Z","timestamp":1593402007000},"page":"153","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Novel Graph Model for Solving Collision-Free Multiple-Vehicle Traveling Salesman Problem Using Ant Colony Optimization"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1676-3980","authenticated-orcid":false,"given":"Anugrah K.","family":"Pamosoaji","sequence":"first","affiliation":[{"name":"Fakultas Teknologi Industri, Universitas Atma Jaya Yogyakarta, Yogyakarta 55281, Indonesia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0797-2083","authenticated-orcid":false,"given":"Djoko Budiyanto","family":"Setyohadi","sequence":"additional","affiliation":[{"name":"Magister Informatika, Universitas Atma Jaya Yogyakarta, Yogyakarta 55281, Indonesia"}]}],"member":"1968","published-online":{"date-parts":[[2020,6,26]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"1161","DOI":"10.1016\/j.jclepro.2019.03.185","article-title":"An improved ant colony optimization algorithm for the multi-depot green vehicle routing problem with multiple objectives","volume":"227","author":"Li","year":"2019","journal-title":"J. Clean. Prod."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/j.apm.2016.01.059","article-title":"Multi-depot vehicle routing problem with time windows considering delivery and installation vehicles","volume":"40","author":"Bae","year":"2016","journal-title":"Appl. Math. Model"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1016\/j.ins.2017.04.020","article-title":"UCT in capacitated vehicle routing problem with traffic jams","volume":"406\u2013407","author":"Mandziuk","year":"2017","journal-title":"Inf. Sci."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/j.omega.2004.10.004","article-title":"The multiple traveling salesman problem: An overview of formulations and solution procedures","volume":"34","author":"Bektas","year":"2006","journal-title":"Omega"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Lawler, E.L. (1985). The Travelling Salesman Problem: A Guided Tour of Combinatorial Optimization, John Wiley and Sons.","DOI":"10.2307\/2582681"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Golden, B., Raghavan, S., and Wasil, E.A. (2008). The vehicle routing problem: Latest advances and new challenges, operations research. Computer Science Interfaces Series, Springer.","DOI":"10.1007\/978-0-387-77778-8"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Khachay, M., and Neznakhina, K. (2017, January 5\u20137). Polynomial time solvable subclass of the generalized traveling salesman problem on grid clusters. Proceedings of the International Conference on Analysis of Images, Social Networks and Texts, Moskow, Russia.","DOI":"10.1007\/978-3-319-73013-4_32"},{"key":"ref_8","first-page":"178","article-title":"Worst case analyses of nearest neighbor heuristic for finding the minimum weight K-cycle","volume":"20","author":"Chalarux","year":"2020","journal-title":"Curr. Appl. Sci. Technol."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1007\/s10898-015-0391-3","article-title":"Approximability of the minimum-weight k-size cycle cover problem","volume":"66","author":"Khachay","year":"2016","journal-title":"J. Glob. Optim."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1108\/IR-12-2014-0437","article-title":"Mathematical model for deadlock resolution in multiple AGV scheduling and routing network: A case study","volume":"42","author":"Fazlollahtabar","year":"2015","journal-title":"Ind. Robot."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"719","DOI":"10.1007\/s00170-015-7343-4","article-title":"Integrated tasks assignment and routing for the estimation of the optimal number of AGVS","volume":"82","author":"Vivaldini","year":"2016","journal-title":"Int. J. Adv. Manuf. Technol."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"943","DOI":"10.1016\/j.ejor.2016.09.001","article-title":"Energy-efficient rail guided vehicle routing for two-sided loading\/unloading automated freight handling systems","volume":"258","author":"Hu","year":"2017","journal-title":"Eur. J. Oper. Res."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"739","DOI":"10.1287\/trsc.2017.0816","article-title":"Path and speed optimization for conflict-free pickup and delivery under time windows","volume":"52","author":"Adamo","year":"2018","journal-title":"Trans. Sci."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"106371","DOI":"10.1016\/j.cie.2020.106371","article-title":"Multi-AGV scheduling for conflict-free path planning in automated container terminals","volume":"142","author":"Zhong","year":"2020","journal-title":"Comput. Ind. Eng."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"100607","DOI":"10.1016\/j.swevo.2019.100607","article-title":"A novel design of differential evolution for solving discrete traveling salesman problems","volume":"53","author":"Ali","year":"2020","journal-title":"Swarm Evol. Comput."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"444","DOI":"10.1016\/j.ejor.2020.01.053","article-title":"A transformation technique for the clustered generalized traveling salesman problem with application to logistics","volume":"2","author":"Baniasadi","year":"2020","journal-title":"Eur. J. Oper. Res."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Pacheco-Valencia, V., Hernandez, J.A., Sigaretta, J.M., and Vakhania, N. (2020). Simple constructive, insertion, and improvement heuristics based on the girding polygon for the Euclidean traveling salesman problem. Algorithms, 13.","DOI":"10.3390\/a13010005"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"481","DOI":"10.1016\/j.asoc.2019.03.001","article-title":"An artificial bee colony algorithm with variable degree of perturbation for the generalized covering traveling salesman","volume":"78","author":"Pandiri","year":"2019","journal-title":"Appl. Soft Comput."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"1138","DOI":"10.1287\/opre.18.6.1138","article-title":"The traveling salesman problem and minimum spanning tree","volume":"18","author":"Held","year":"1970","journal-title":"Oper. Res."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1016\/0166-218X(92)00033-I","article-title":"A parallel tabu search algorithm for large traveling salesman problem","volume":"51","author":"Fiechter","year":"1994","journal-title":"Discret. Appl. Math."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"1013","DOI":"10.1016\/j.neucom.2006.03.013","article-title":"A new approach to solve the traveling salesman problem","volume":"70","author":"Siqueira","year":"2007","journal-title":"Neurocomputing"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1016\/j.ejor.2010.09.010","article-title":"Traveling salesman problem heuristics: Leading methods, implementations and latest advances","volume":"211","author":"Rego","year":"2011","journal-title":"Eur. J. Oper. Res."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Essani, F.H., and Haider, S. (2018). An algorithm for mapping the asymmetric multiple traveling salesman problem onto colored petri nets. Algorithms, 11.","DOI":"10.3390\/a11100143"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/j.engappai.2018.08.015","article-title":"Integrating forecasting in metaheuristic methods to solve dynamic routing problems: Evidence from the logistic processes of tuna vessels","volume":"76","author":"Groba","year":"2018","journal-title":"Eng. Appl. Artif. Intel."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"7237459","DOI":"10.1155\/2019\/7237459","article-title":"A dynamic scheduling method for logistics tasks oriented to intelligent manufacturing workshop","volume":"2019","author":"Xu","year":"2019","journal-title":"Math. Probl. Eng."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"4412","DOI":"10.1007\/s10489-018-1216-0","article-title":"A swarm intelligence approach for the colored traveling salesman problem","volume":"48","author":"Pandiri","year":"2018","journal-title":"Appl. Intell."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"436","DOI":"10.1016\/j.asoc.2018.11.048","article-title":"Mission-oriented ant-team ACO for min\u2013max MTSP","volume":"76","author":"Lu","year":"2019","journal-title":"Appl. Soft. Comput."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1109\/4235.585892","article-title":"Ant colony: A cooperative learning approach to the travelling salesman problem","volume":"1","author":"Dorigo","year":"1997","journal-title":"IEEE Trans. Evol. Comput."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"1896","DOI":"10.1109\/TIE.2010.2051394","article-title":"Navigation function-based control of multiple wheeled vehicles","volume":"58","author":"Widyotriatmo","year":"2011","journal-title":"IEEE Trans. Ind. Electron."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"1001","DOI":"10.1163\/1568553042674662","article-title":"Inevitable collision states\u2014A step towards safer robots?","volume":"18","author":"Fraichard","year":"2004","journal-title":"Adv. Robot."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"696","DOI":"10.1109\/TRO.2011.2120810","article-title":"The hybrid reciprocal velocity obstacle","volume":"27","author":"Snape","year":"2011","journal-title":"IEEE Trans. Robot."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"404","DOI":"10.1109\/TRO.2018.2793890","article-title":"Cooperative collision avoidance for nonholonomic robots","volume":"34","author":"Beardsley","year":"2018","journal-title":"IEEE Trans. Robot."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Makarem, L., and Gillet, D. (2013, January 6\u20139). Model predictive coordination of autonomous vehicles crossing intersections. Proceedings of the 16th International IEEE Conference on Intelligent Transportation Systems (ITSC), Hague, The Netherlands.","DOI":"10.1109\/ITSC.2013.6728489"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"108958","DOI":"10.1016\/j.automatica.2020.108958","article-title":"Decentralized optimal coordination of connected and automated vehicles for multiple traffic scenarios","volume":"117","author":"Mahbub","year":"2020","journal-title":"Automatica"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1007\/s10846-019-01055-5","article-title":"Three-dimensional collision avoidance for multi unmanned aerial. Vehicles Using Velocity Obstacle","volume":"97","author":"Tan","year":"2020","journal-title":"J. Intell. Robot. Syst."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"2610","DOI":"10.1007\/s12555-018-0176-9","article-title":"PSO-based minimum-time motion planning for multiple-vehicle systems considering acceleration and velocity limitations","volume":"17","author":"Pamosoaji","year":"2019","journal-title":"Int. J. Control Autom. Syst."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1016\/j.tre.2013.10.004","article-title":"A Vehicle routing problem with multiple overlapped batches","volume":"61","author":"Yu","year":"2014","journal-title":"Trans. Res. E"},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Baranwal, M., Roehl, B., and Salapaka, S.M. (2017, January 24\u201326). Multiple traveling salesmen and related problems: A maximum-entropy principle-based approach. Proceedings of the 2017 American Control Conference (ACC), Seattle, WA, USA.","DOI":"10.23919\/ACC.2017.7963559"},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Pamosoaji, A.K., and Hong, K.-S. (2015, January 13\u201316). Group-based particle swarm optimization for multiple-vehicles trajectory planning. Proceedings of the 15th International Conference on Control, Automation, and Systems (ICCAS), Busan, Korea.","DOI":"10.1109\/ICCAS.2015.7364742"},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Chalissery, J.M., Renyard, A., Gries, R., Hoefele, D., Alamsetti, S.K., and Gries, G. (2019). Ant sense, and follow, trail pheromones of ant community members. Insects, 10.","DOI":"10.3390\/insects10110383"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/6\/153\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T09:43:15Z","timestamp":1760175795000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/6\/153"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,26]]},"references-count":40,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2020,6]]}},"alternative-id":["a13060153"],"URL":"https:\/\/doi.org\/10.3390\/a13060153","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2020,6,26]]}}}