×

An algorithm for mapping the asymmetric multiple traveling salesman problem onto colored Petri nets. (English) Zbl 1461.90158

Summary: 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) – a mathematical modeling language – to 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.

MSC:

90C35 Programming involving graphs or networks
90C27 Combinatorial optimization
68W40 Analysis of algorithms
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bektas, T.; The multiple traveling salesman problem: An overview of formulations and solution procedures; Omega: 2006; Volume 34 ,209-219.
[2] Hoffman, K.L.; Padberg, M.; Rinaldi, G.; Traveling Salesman Problem; Encyclopedia of Operations Research and Management Science: Boston, MA, USA 2013; ,1573-1578.
[3] Ratzer, A.V.; Wells, L.; Lassen, H.M.; Laursen, M.; Qvortrup, J.F.; Stissing, M.S.; Westergaard, M.; Christensen, S.; Jensen, K.; CPN Tools for Editing, Simulating, and Analysing Coloured Petri Nets; Applications and Theory of Petri Nets 2003: Berlin, Germany 2003; ,450-462.
[4] Jensen, K.; Coloured petri nets: A high level language for system design and analysis; Advances in Petri Nets 1990: Berlin, Heidelberg 1989; ,342-416.
[5] Petri, C.A.; Kommunikation mit Automation; Diss. Univ. Bonn: 1962; Volume 2 ,128.
[6] Jensen, K.; Kristensen, L.M.; ; Coloured Petri Nets: Modelling and Validation of Concurrent Systems: Berlin, Germany 2009; . · Zbl 1215.68153
[7] Laporte, G.; Nobert, Y.; A Cutting Planes Algorithm for the m-Salesmen Problem; J. Oper. Res. Soc.: 1980; Volume 31 ,1017-1023. · Zbl 0441.90067
[8] Kara, I.; Bektas, T.; Integer linear programming formulations of multiple salesman problems and its variations; Eur. J. Oper. Res.: 2006; Volume 174 ,1449-1458. · Zbl 1103.90065
[9] Kulkarni, R.V.; Bhave, P.R.; Integer programming formulations of vehicle routing problems; Eur. J. Oper. Res.: 1985; Volume 20 ,58-67.
[10] Iqbal Ali, A.; Kennington, J.L.; The asymmetric M-travelling salesmen problem: A duality based branch-and-bound algorithm; Discrete Appl. Math.: 1986; Volume 13 ,259-276. · Zbl 0603.90132
[11] Fogel, D.B.; A parallel processing approach to a multiple traveling salesman problem using evolutionary programming; Proceedings of the fourth annual symposium on parallel processing: ; ,318-326.
[12] Carter, A.E.; Ragsdale, C.T.; A new approach to solving the multiple traveling salesperson problem using genetic algorithms; Eur. J. Oper. Res.: 2006; Volume 175 ,246-257. · Zbl 1137.90690
[13] Cordeau, J.-F.; Gendreau, M.; Laporte, G.; A tabu search heuristic for periodic and multi-depot vehicle routing problems; Networks: 1997; Volume 30 ,105-119. · Zbl 0885.90037
[14] Song, C.-H.; Lee, K.; Lee, W.D.; Extended simulated annealing for augmented TSP and multi-salesmen TSP; Proceedings of the 2003 International Joint Conference on Neural Networks: ; ,2340-2343.
[15] Wacholder, E.; Han, J.; Mann, R.C.; A neural network algorithm for the multiple traveling salesmen problem; Biol. Cybern.: 1989; Volume 61 ,11-19. · Zbl 0679.68108
[16] Hosseinabadi, A.A.R.; Kardgar, M.; Shojafar, M.; Shamshirband, S.; Abraham, A.; GELS-GA: Hybrid metaheuristic algorithm for solving Multiple Travelling Salesman Problem; Proceedings of the 14th International Conference on Intelligent Systems Design and Applications: ; ,76-81.
[17] Hong, S.; Padberg, M.W.; Technical Note—A Note on the Symmetric Multiple Traveling Salesman Problem with Fixed Charges; Oper. Res.: 1977; Volume 25 ,871-874. · Zbl 0388.90054
[18] Rao, M.R.; Technical Note—A Note on the Multiple Traveling Salesmen Problem; Oper. Res.: 1980; Volume 28 ,628-632. · Zbl 0442.90068
[19] Jonker, R.; Volgenant, T.; Technical Note—An Improved Transformation of the Symmetric Multiple Traveling Salesman Problem; Oper. Res.: 1988; Volume 36 ,163-167. · Zbl 0643.90093
[20] Bellmore, M.; Hong, S.; Transformation of Multisalesman Problem to the Standard Traveling Salesman Problem; J. ACM: 1974; Volume 21 ,500-504. · Zbl 0283.90036
[21] Wu, N.; Necessary and sufficient conditions for deadlock-free operation in flexible manufacturing systems using a colored Petri net model; IEEE Trans. Syst. Man Cybern. Part C Appl. Rev.: 1999; Volume 29 ,192-204.
[22] Piera, M.À.; Narciso, M.; Guasch, A.; Riera, D.; Optimization of Logistic and Manufacturing Systems through Simulation: A Colored Petri Net-Based Methodology; Simulation: 2004; Volume 80 ,121-129.
[23] Zaitsev, D.A.; Switched LAN simulation by colored Petri nets; Math. Comput. Simul.: 2004; Volume 65 ,245-249. · Zbl 1077.68530
[24] van der Aalst, W.M.P.; Petri net based scheduling; Oper. Res. Spektrum: 1996; Volume 18 ,219-229. · Zbl 0865.90077
[25] Shojafar, M.; Pooranian, Z.; Abawajy, J.H.; Meybodi, M.R.; An efficient scheduling method for grid systems based on a hierarchical stochastic petri net; J. Comput. Sci. Eng.: 2013; Volume 7 ,44-52.
[26] Shojafar, M.; Pooranian, Z.; Meybodi, M.R.; Singhal, M.; ALATO: An efficient intelligent algorithm for time optimization in an economic grid based on adaptive stochastic Petri net; J. Intell. Manuf.: 2015; Volume 26 ,641-658.
[27] Gini, M.; Multi-robot allocation of tasks with temporal and ordering constraints; Proceedings of the 31st AAAI Conference on Artificial Intelligence, AAAI 2017: ; ,4863-4869.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.