| News Details |
Competitive Travelling Salesmen Problem
2021-07-05
Competitive Travelling Salesmen Problem
The travelling salesman problem (TSP) is considered as one of the perplexing optimization problems in transportation and distribution systems. Thus, it has been a fertile area of research which has drawn researching efforts from various communities such as operation research and artificial intelligence. The TSP is generalized version of Hamilton Cycle. A Hamiltonian cycle is a cycle that visits each node only one time in a graph (Shaikh, M., & Panchal, 2012).In TSP, vertices denote to cities; edges denote to the path between cities, and edges cost denote to the distance between cities. The salesmen must start from a city, visit all cities only one time, and return to the first city with minimized cost (Nemati, K., Shamsuddin, M., & Kamarposhti, 2011), (Taba, 2009) . TSP is NP-hard, that's mean there is no known polynomial time that algorithm can find the optimal solution to any given instance (Lawler E, Lenstra J, 1986). There are many applications of TSP some of them are Drilling of printed circuit boards, Overhauling gas turbine engines, X-ray crystallography, Computer wiring, the order-picking problem in warehouses, and the order-picking problem in warehouses, vehicle routing (Davendra, 2010). There are many of variations of TSP. Some of them are Symmetric TSP, Asymmetric TSP, Multiple TSP, Competitive TSP and many others (H., 2013), (Applegate D, Bixby R, 2006) .This study focuses on CTSP which is considered more realistic problem than other variations (Kendall, G. & Li, 2013). In this problem, number of travelling salesmen compete with each other to visit a number of cities. Any salesman will receive a payoff if he is the first one visit a city and he must pay a cost for the distance he traveled(Kendall, G. & Li, 2013). Thus, each salesman goals to visit as many cities not have been visited before as possible with the minimum distance of travel. The CTSP is an NP-complete problem for the salesmen to design their paths and there is strategic interaction between the salesmen due to their conflict of interest (Kendall, G. & Li, 2013).Due to the importance of CTSP, there are many algorithms have been proposed to solve it. Fekete et.al (2004) propose the competing salesmen problem? (CSP), a two-player competitive version of the classical traveling salesman problem. This problem arises when considering two competing salesmen instead of just one. The concern for a shortest tour is replaced by the necessity to reach any of the customers before the opponent does(Fekete, S., Fleischer, F., Fraenkel, A. & Schmitt, 2004). Kendall and Li (2013) have been introduced a new version of the TSP and proposed a “hyper-heuristic methodology” to address it. In a competitive travelling salesmen problem (CTSP), m travelling salesmen want to visit n cities with non-cooperative relationship among them. Any salesman if he visits a city first one will obtain a benefit and pay a cost for traveling to every city. The aim of each salesman is to visit as many cities not have been visited before as possible, with a minimum distance of travel. Because of the competitive factor, each salesman needs to consider the path of other salesmen when designing his own path. Kendall and Li developed a hyper-heuristic methodology due to that the “equilibrium analysis” is hard in the CTSP. This method assumes that each salesman takes a single heuristic (or number of heuristics) to select his path and each salesman knows that the paths of all other salesmen aren’t optimal necessarily. The hyper- heuristic involves of a number of low-level heuristics, each of which can be utilized to initiate a path given the heuristics of the other salesmen, collected with a high-level heuristic that is utilized to choice from the low-level heuristics at each decision point (Kendall, G. & Li, 2013). Mohtadi and Nogondarian (2014) proposed a game theoretic approach for solving the traveling salesman problem in competitive situations. They used to test the problems game theory as a mathematical model. They used tabu search and genetic algorithms. The obtained results show that the computational error is within a reasonable range. Additionally, these results show that tabu search algorithm fined solutions with better quality and less time (Mohtadi, M. & Nogondarian, 2014).Mohannad in (2016) was been used ant colony optimization (ACO) algorithm to solve competitive traveling salesman problem because it is very difficult to compute the Nash equilibrium with large search space. It is inspired from the real ant colony, in which ants leave pheromone trails when looking for source of food in order to guide other ants to the food. In this work he used two different strategies to solve CTSP. In the first strategy, the cities are divided among salesmen equally. To prove the ability of ACO algorithm to solve CTSP, it is compared to (NN) Nearest Neighbors algorithm and (RN) Random Neighbors algorithm which adopted by (Li, J. & Kendall, 2015). In the second strategy, the number of cities is not specific and each salesman will try to visit as much as possible cities according to strategy of the salesman. In this strategy, taken two directions, the first one use for each salesman same plan, while the other uses, for each salesman, every time an update plan. The results that he obtained to it for all experiments clearly indicate that ACO could be a promising method for solving CTSP (Hameed, 2016).
In spite of the importance of competitive salesman problem and its application in our daily life, there is only little research proposed to study it. Consequently, more efficient algorithm that can significantly work well to improve the quality of obtained solution is highly required. Recently, the nature-inspired metaheuristic algorithms can be describe as the most efficient algorithms in tackling and obtaining good quality solutions for complex real-world optimization problems (Esam Taha Yassen, Masri Ayob, 2012). One of these algorithms is Salp Swarm Algorithm (SSA) that has been proposed by (Mirjalili S, Gandomi AH, Mirjalili SZ, Saremi S, Faris H, 2017). SSA has been presented as a powerful method to handle many difficult problems and it has not been applied to the CTSP. So, the main objective is to investigate the performance of the SSA in tackling the Competitive Salesman Problem.
