An algorithm for mapping the asymmetric multiple traveling salesman problem onto colored Petri nets (Q2283818)

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.