An ant colony system hybridized with a new local search for the sequentialordering problem

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).