{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,30]],"date-time":"2026-01-30T09:51:00Z","timestamp":1769766660128,"version":"3.49.0"},"reference-count":27,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2018,9,25]],"date-time":"2018-09-25T00:00:00Z","timestamp":1537833600000},"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>The Multiple Traveling Salesman Problem is an extension of the famous Traveling Salesman Problem. Finding an optimal solution to the Multiple Traveling Salesman Problem (mTSP) is a difficult task as it belongs to the class of NP-hard problems. The problem becomes more complicated when the cost matrix is not symmetric. In such cases, finding even a feasible solution to the problem becomes a challenging task. In this paper, an algorithm is presented that uses Colored Petri Nets (CPN)\u2014a mathematical modeling language\u2014to represent the Multiple Traveling Salesman Problem. The proposed algorithm maps any given mTSP onto a CPN. The transformed model in CPN guarantees a feasible solution to the mTSP with asymmetric cost matrix. The model is simulated in CPNTools to measure two optimization objectives: the maximum time a salesman takes in a feasible solution and the collective time taken by all salesmen. The transformed model is also formally verified through reachability analysis to ensure that it is correct and is terminating.<\/jats:p>","DOI":"10.3390\/a11100143","type":"journal-article","created":{"date-parts":[[2018,9,25]],"date-time":"2018-09-25T11:12:26Z","timestamp":1537873946000},"page":"143","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["An Algorithm for Mapping the Asymmetric Multiple Traveling Salesman Problem onto Colored Petri Nets"],"prefix":"10.3390","volume":"11","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1978-3415","authenticated-orcid":false,"given":"Furqan Hussain","family":"Essani","sequence":"first","affiliation":[{"name":"Artificial Intelligence Lab, Department of Computer Science, Institute of Business Administration, Garden\/Kayani Shaheed Road, Karachi 74400, Pakistan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sajjad","family":"Haider","sequence":"additional","affiliation":[{"name":"Artificial Intelligence Lab, Department of Computer Science, Institute of Business Administration, Garden\/Kayani Shaheed Road, Karachi 74400, Pakistan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2018,9,25]]},"reference":[{"key":"ref_1","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_2","unstructured":"Gass, S.I., and Fu, M.C. (2013). Traveling Salesman Problem. Encyclopedia of Operations Research and Management Science, Springer."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"van der Aalst, W.M.P., and Best, E. (2003). CPN Tools for Editing, Simulating, and Analysing Coloured Petri Nets. Applications and Theory of Petri Nets 2003, Springer.","DOI":"10.1007\/3-540-44919-1"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Jensen, K. (1989). Coloured petri nets: A high level language for system design and analysis. Advances in Petri Nets 1990, Springer.","DOI":"10.1007\/978-3-642-84524-6_2"},{"key":"ref_5","first-page":"128","article-title":"Kommunikation mit Automation","volume":"2","author":"Petri","year":"1962","journal-title":"Diss. Univ. Bonn"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Jensen, K., and Kristensen, L.M. (2009). Coloured Petri Nets: Modelling and Validation of Concurrent Systems, Springer. [1st ed.].","DOI":"10.1007\/b95112"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1017","DOI":"10.1057\/jors.1980.188","article-title":"A Cutting Planes Algorithm for the m-Salesmen Problem","volume":"31","author":"Laporte","year":"1980","journal-title":"J. Oper. Res. Soc."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"1449","DOI":"10.1016\/j.ejor.2005.03.008","article-title":"Integer linear programming formulations of multiple salesman problems and its variations","volume":"174","author":"Kara","year":"2006","journal-title":"Eur. J. Oper. Res."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1016\/0377-2217(85)90284-X","article-title":"Integer programming formulations of vehicle routing problems","volume":"20","author":"Kulkarni","year":"1985","journal-title":"Eur. J. Oper. Res."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1016\/0166-218X(86)90087-9","article-title":"The asymmetric M-travelling salesmen problem: A duality based branch-and-bound algorithm","volume":"13","author":"Kennington","year":"1986","journal-title":"Discrete Appl. Math."},{"key":"ref_11","unstructured":"Fogel, D.B. (, January April). A parallel processing approach to a multiple traveling salesman problem using evolutionary programming. Proceedings of the fourth annual symposium on parallel processing, Fullerton, CA, USA."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1016\/j.ejor.2005.04.027","article-title":"A new approach to solving the multiple traveling salesperson problem using genetic algorithms","volume":"175","author":"Carter","year":"2006","journal-title":"Eur. J. Oper. Res."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1002\/(SICI)1097-0037(199709)30:2<105::AID-NET5>3.0.CO;2-G","article-title":"A tabu search heuristic for periodic and multi-depot vehicle routing problems","volume":"30","author":"Cordeau","year":"1997","journal-title":"Networks"},{"key":"ref_14","unstructured":"Song, C.-H., Lee, K., and Lee, W.D. (2003, January 20\u201324). Extended simulated annealing for augmented TSP and multi-salesmen TSP. Proceedings of the 2003 International Joint Conference on Neural Networks, Portland, OR, USA."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1007\/BF00204755","article-title":"A neural network algorithm for the multiple traveling salesmen problem","volume":"61","author":"Wacholder","year":"1989","journal-title":"Biol. Cybern."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Hosseinabadi, A.A.R., Kardgar, M., Shojafar, M., Shamshirband, S., and Abraham, A. (2014, January 27\u201329). GELS-GA: Hybrid metaheuristic algorithm for solving Multiple Travelling Salesman Problem. Proceedings of the 14th International Conference on Intelligent Systems Design and Applications, Okinawa, Japan.","DOI":"10.1109\/ISDA.2014.7066271"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"871","DOI":"10.1287\/opre.25.5.871","article-title":"Technical Note\u2014A Note on the Symmetric Multiple Traveling Salesman Problem with Fixed Charges","volume":"25","author":"Hong","year":"1977","journal-title":"Oper. Res."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"628","DOI":"10.1287\/opre.28.3.628","article-title":"Technical Note\u2014A Note on the Multiple Traveling Salesmen Problem","volume":"28","author":"Rao","year":"1980","journal-title":"Oper. Res."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1287\/opre.36.1.163","article-title":"Technical Note\u2014An Improved Transformation of the Symmetric Multiple Traveling Salesman Problem","volume":"36","author":"Jonker","year":"1988","journal-title":"Oper. Res."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"500","DOI":"10.1145\/321832.321847","article-title":"Transformation of Multisalesman Problem to the Standard Traveling Salesman Problem","volume":"21","author":"Bellmore","year":"1974","journal-title":"J. ACM"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"192","DOI":"10.1109\/5326.760564","article-title":"Necessary and sufficient conditions for deadlock-free operation in flexible manufacturing systems using a colored Petri net model","volume":"29","author":"Wu","year":"1999","journal-title":"IEEE Trans. Syst. Man Cybern. Part C Appl. Rev."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1177\/0037549704045045","article-title":"Optimization of Logistic and Manufacturing Systems through Simulation: A Colored Petri Net-Based Methodology","volume":"80","author":"Piera","year":"2004","journal-title":"Simulation"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1016\/j.matcom.2003.12.004","article-title":"Switched LAN simulation by colored Petri nets","volume":"65","author":"Zaitsev","year":"2004","journal-title":"Math. Comput. Simul."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/BF01540160","article-title":"Petri net based scheduling","volume":"18","year":"1996","journal-title":"Oper. Res. Spektrum"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"44","DOI":"10.5626\/JCSE.2013.7.1.44","article-title":"An efficient scheduling method for grid systems based on a hierarchical stochastic petri net","volume":"7","author":"Shojafar","year":"2013","journal-title":"J. Comput. Sci. Eng."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"641","DOI":"10.1007\/s10845-013-0824-0","article-title":"ALATO: An efficient intelligent algorithm for time optimization in an economic grid based on adaptive stochastic Petri net","volume":"26","author":"Shojafar","year":"2015","journal-title":"J. Intell. Manuf."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Gini, M. (2017, January 4\u201310). Multi-robot allocation of tasks with temporal and ordering constraints. Proceedings of the 31st AAAI Conference on Artificial Intelligence, AAAI 2017, San Francisco, CA, USA.","DOI":"10.1609\/aaai.v31i1.11145"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/10\/143\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T15:22:16Z","timestamp":1760196136000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/10\/143"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,9,25]]},"references-count":27,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2018,10]]}},"alternative-id":["a11100143"],"URL":"https:\/\/doi.org\/10.3390\/a11100143","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,9,25]]}}}