Article Preview
TopIntroduction And Literature Survey
Discrete optimization (Czyzyk, Mesnier, & Moré, 1998) problem requires the variables to achieve discrete values or a combination of integers in a particular range. Many real-life problems require a combinatorial approach to be solved, for instance, the job scheduling problem. These problems are divided into two categories: 1. integer linear programming 2. combinatorial problems. Some examples of combinatorial optimization are the travelling salesman problem, cutting stock problem, packing problem, and minimum spanning tree problem. Among all these problems, the travelling salesman problem is well known in literature and is challenging to solve. Traveling Salesman Problem (TSP) (Greco, 2008) is a well-known NP-hard combinatorial optimization problem. This problem aims to find a Hamiltonian cycle in the connected graph while the tour cost is minimized. The Hamilton cycle is a path that passes each vertex of the graph just once and returns to the origin vertex. Several exact methods were able to solve the problem, but they were inefficient on large size problems. Moreover, the computational time using the traditional technique was significant, which lead to the development of heuristics and metaheuristics.
TSP problem was solved using various evolutionary optimization algorithms. For instance, Particle Swarm Optimization (Chen & Tan, 2014) (PSO) and Genetic Algorithm (GA) (Larrañaga, Kuijpers, Murga, Inza, & Dizdarevic, 1999) were used to solve TSP problems and are considered a benchmark in this field. A combination of GA, ACO, and PSO named GA-PSO-ACO (Deng, et al., 2012)was proposed by Deng et al. where GA and PSO were used for diversification, and ACO served as exploitation tool. Karaboga, Dervis, and Gorkemli, Beyza in 2001 proposed the Combinatorial Artificial Bee Colony(CABC) (Karaboga & Gorkemli, 2011) algorithm for solving symmetric and Asymmetric TSP. In the following year, by using the 2-opt and 3-opt techniques, this algorithm (Khan & Maiti, 2019) was modified by Khan et al. Simulated Annealing (SA) (van Laarhoven & Aarts, 1987) algorithms by Zhong et al. have been used for solving TSP. Also, a combination of simulated annealing, PSO, and ACO was proposed by Chen and Chien (Chen & Chien, 2011). Ant Colony (AC) (Ariyasingha & Fernando, 2015) optimization algorithm used the simulation of ants searching home to solve multiple TSP introduced by Kencana et al. in 2017. Simulated Annealing (SA) and Symbiotic Organisms Search algorithms (Min-YuanCheng & Prayogo, 2014) were proposed by Ezugwu et al. in 2017.
Firefly Algorithm (FA) (Li, Ma, Zhang, Zhou, & Liu, 2015)was used to solve multiple TSP problem. A discrete Bat algorithm (Luo, et al., 2014) for solving routing problems and TSP and Asymmetric TSP (ATSP) problems was also proposed in the following years. In 2013 a Tabu Search algorithm (Gendreau, Glover, & Kochenberger, 2003) was designed for solving TSP. Aziz Ouaarab in 2013 proposed a Discrete Cuckoo search algorithm (Ouaarab, Ahiod, & Yang, 2016) to solve TSP. The algorithm was a modification to the Cuckoo search to solve discrete problems. This algorithm proved to be very competitive in solving Discrete optimization problems. Based on the social behavior of spider monkeys, the discrete spider monkey algorithm (Akhand, Ayon, Shahriyar, Siddique, & Adeli, 2020) was developed for discrete problems. The invasive weed problem was converted to its discrete form (Ouyang, Peng, Wang, & Wang, 2017) by Ouyang et al. Out of all these algorithms, GA is the state of the art technique that has evolved in many forms over the years. The ACO, DBA, and DCS were very efficient and produced near-optimal solutions for TSP problems. Hence a comparison of the proposed algorithms was made with these algorithms. After the algorithm is developed for the traveling salesman problem, it can have several applications, such as vehicle routing problems, logistics, planning, and scheduling.