Hybrid Ant Colony Optimization System
Sequential Ordering Problems
Istituto Dalle Molle di Studi sull'Intelligenza Artificiale
6928 Manno-Lugano - CH
Phone: +41 91 - 6108660
Fax: +41 91 - 6108661
The Sequential Ordering Problem (SOP) with precedence constraints consists of finding a minimum weight Hamiltonian path on a directed graph with weights on the arcs and on the nodes, subject to precedence constraints among nodes.
SOP can also be formulated as a general case of the asymmetric traveling salesman problem (ATSP). In this representation cij is an arc weight (where cij may be different from cji) which can either represent the cost of arc (i, j) when cij>=0, or an ordering constraint when cij=-1
(cij=-1 means that element j must precede, not necessarily immediately, element i).
Hybrid Ant System
HAS-SOP: An Ant Colony System Hybridized with a New Local Search for the Sequential Ordering Problem , Gambardella L.M , Dorigo M., , is the first presented in literature that combines a constructive phase based on ACS algorithm (Dorigo M., Gambardella L.M, Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem, IEEE Transactions on Evolutionary Computation Vol. 1,No. 1,pp. 53-66, 1997 ) with a new TSP based lexicographic search (SOP-3-exchange) to directly handle multiple constraints without an increase in computational time, (Gambardella L.M , Dorigo M. An Ant Colony System Hybridized with a New Local Search for the Sequential Ordering Problem, INFORMS Journal on Computing, vol.12(3), pp. 237-255, 2000)
SOP problems in TSPLIB can be classified as follows: a set of problems (rbgxxxa) are real-life problems derived from a stacker crane application ( Ascheuer N., 1996. Hamiltonian Path Problems in the On-line Optimization of Flexible Manufacturing Systems. ZIB Technical Report TR 96-3); rbgxxxa problems were originally defined as ATSPs with time windows: to obtain SOP instances time window precedences have been relaxed to generate SOP constraints. Prob100 (Ascheuer, 1996) is a randomly generated problem, and problems (ftxx.x, pr43.x and kroxxxp.x) have been generated (Ascheuer, 1996) starting from ATSP instances in TSPLIB and adding a number of random precedence constraints <= k, where k=(n/4, n/2, 2, 2*n) correspond to the problem extension (.1, .2, .3, .4). ESC63 and ESC78 are taken from (Escudero L. F., 1988. An Inexact Algorithm for the Sequential Ordering Problem. European Journal of Operational Research 37, 232-253).
In the following table we present HAS-SOP results for SOP instances available in TSPLIB.
We report in the first column the name of the problem, in the second the new bounds for that instance and in the third HAS-SOP best result.
In Quality column Best Known means that the result has been proved to be optimal, Best UB means that the result is the Best Known Upper Bound for the problem. An * means that the Best Known Result or the Best Known Upper Bound was obtained with HAS-SOP. Notice that HAS-SOP was able to reach the Best Known Result (Best Known Upper Bound) or to improve it for almost all the tested problems.
In the last columns we report average and standard deviation in quality and time after perfomring 10 experiments for each instance using a SUN Ultra-Sparc 20.
Norbert Ascheuer has run his branch&cut program (Ascheuer, 1996) starting from our best found solutions reported in this table. He could not improve any of our solutions within 24-CPU hours on a SUN SPARC Station 4 (110Mhz) machine.
Norbert Ascheuer maintains a web page with SOP references, definitions and results
Marco Dorigo maintains a web page dedicated to Ant Colony Optimization
SOP instances are available in TSPLIB.
Gambardella's researches on other Ant Colony System Optimization problems are available on-line.