Lm. Gambardella et M. Dorigo, An ant colony system hybridized with a new local search for the sequentialordering problem, INFORMS J C, 12(3), 2000, pp. 237-255
We present a new local optimizer called SOP-3-exchange for the sequential o
rdering problem that extends a local search for the traveling salesman prob
lem to handle multiple constraints directly without increasing computationa
l complexity. An algorithm that combines the SOP-3-exchange with an Ant Col
ony Optimization algorithm is described, and we present experimental eviden
ce that the resulting algorithm is more effective than existing methods for
the problem. The best-known results for many of a standard test set of 22
problems are improved using the SOP-a-exchange with our Ant Colony Optimiza
tion algorithm or in combination with the MPO/Al algorithm (Chen and Smith
1996).