Scalable Metaheuristic Optimization of Asymmetric and Clustered TSP Variants using Iterated Local Search

Abstract

Iterated Local Search (ILS) is a well-established metaheuristic that has been widely applied to combinatorial optimization problems owing to its balance between solution diversification and intensification.  This work emphasizes ILS for the scope of the Asymmetrical Traveling Salesman Problem (ATSP) and the Asymmetrical Generalized Traveling Salesman Problem (AGTSP) respectively, which accounts for the directionally dependent costs of routes and cluster of nodes recognized in the routing difficulties of real-world applications.  The experiment also assesses whether ILS can explore difficult search regions while also conserving solution quality and avoiding rapid convergence.  This study examines the feasibility of ILS when using TSPLIB benchmark instances subject to directed route costs, time windows and load capacity constraints, while including a realistic routing network, including depots, customers and stops, alongside an examination of the systematic conversion of symmetric TSP instances into asymmetric representations to accurately capture directionally dependent travel costs.  The results demonstrate that ILS can produce high quality solutions to both the ATSP and AGTSP under conditions of increasingly complicated routing.  Future research will be directed towards improving ILS with a hybrid metaheuristic framework and subject to large scale logistics datasets to improve viability and scale capability.