HAS-SOP: Hybrid Ant System for the Sequential Ordering Problem

We present HAS-SOP, a new approach to solving sequential ordering problems. HAS-SOP combines the ant colony algorithm, a population-based metaheuristic, with a new local optimizer, an extension of a TSP heuristic which directly handles multiple constraints without increasing computational complexity. We compare different implementations of HASSOP and present a new data structure that improves system performance. Experimental results on a set of twenty-three test problems taken from the TSPLIB show that HAS-SOP outperforms existing methods both in terms of solution quality and computation time. Moreover, HAS-SOP improves most of the best known results for the considered problems.