A Hybrid Symbiotic Organisms Search Algorithm with Variable Neighbourhood Search for Solving Symmetric and Asymmetric Traveling Salesman Problem

International Conference on Industrial and Systems Engineering 2017

Umam, M.I.H.^1 ; Santosa, B.^1

Departement of Industrial Engineering, Institut Teknologi Sepuluh Nopember, Kampus ITS, Sukolilo-Surabaya

60111, Indonesia^1

关键词: Asymmetric traveling salesman problem;    Combinatorial problem;    Commercial applications;    Initial solution;    Optimization techniques;    Original algorithms;    Search Algorithms;    Variable neighbourhood search;   

Others  :  https://iopscience.iop.org/article/10.1088/1757-899X/337/1/012005/pdf
DOI  :  10.1088/1757-899X/337/1/012005

来源: IOP

【 摘 要 】

Combinatorial optimization has been frequently used to solve both problems in science, engineering, and commercial applications. One combinatorial problems in the field of transportation is to find a shortest travel route that can be taken from the initial point of departure to point of destination, as well as minimizing travel costs and travel time. When the distance from one (initial) node to another (destination) node is the same with the distance to travel back from destination to initial, this problems known to the Traveling Salesman Problem (TSP), otherwise it call as an Asymmetric Traveling Salesman Problem (ATSP). The most recent optimization techniques is Symbiotic Organisms Search (SOS). This paper discuss how to hybrid the SOS algorithm with variable neighborhoods search (SOS-VNS) that can be applied to solve the ATSP problem. The proposed mechanism to add the variable neighborhoods search as a local search is to generate the better initial solution and then we modify the phase of parasites with adapting mechanism of mutation. After modification, the performance of the algorithm SOS-VNS is evaluated with several data sets and then the results is compared with the best known solution and some algorithm such PSO algorithm and SOS original algorithm. The SOS-VNS algorithm shows better results based on convergence, divergence and computing time.