Union-Intersection Ant System

Union-Intersection Ant System is an optimization algorithm with multi-nest of ants cooperating with each other, whose goal is to identify the edges belonging to the solution of TSP (denoted as TSP-edge-set). It identifies a part of elements in TSP-edge-set by the intersection of several hero ants´ tours (a hero ant is the one found the best tour in a nest) during an iteration and provides a collapsed solution space for future iterations by the union of these tours, thus a rapid solution to large-scale TSPs comes true. Experiments on the TSP instances with several thousands of cities from TSPLIB show that the convergence time of Union-Intersection Ant System has been significantly compressed compared to MMAS on the premise of the solution quality not worse than that of MMAS, thus the scale of the TSPs solved can reach up to 10000 cites or more. Union-Intersection Ant System is feasible.