Hybrid Ant Colony Optimization System

for the

Sequential Ordering Problems

Luca Maria Gambardella

IDSIA
Istituto Dalle Molle di Studi sull'Intelligenza Artificiale
Galleria 2
6928 Manno-Lugano - CH
Phone: +41 91 - 6108660
Fax: +41 91 - 6108661
email: luca@idsia.ch

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

HAS-SOP Problems
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).

HAS-SOP results
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.

Useful Information
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.

Hybrid And System applied to SOP

Instance SOP
New Bounds HAS-SOP
Best Result Quality AVG
(10 expr.) Dev.St. Avg
Time (s)

ESC07 2125 2125 Best Known 2125 0 0.14

ESC11 2075 2075 Best Known 2075 0 0.17

ESC12 1675 1675 Best Known 1675 0 0.16

ESC25 1681 1681 Best Known 1681 0 0.40

ESC47 1288 1288 Best Known 1307.60 29.82 157.2

ESC63 62 62 Best Known 62 0 0.20

ESC78 18230 18230 Best Known 18230 0 3.5

br17.10 55 55 Best Known 55 0 0.36

br17.12 55 55 Best Known 55 0 0.33

ft53.1 [7438,7531] 7531 Best UB* 7531 0 16.30

ft53.2 [7630,8026] 8026 Best UB* 8026 0 17.00

ft53.3 [9473,10262] 10262 Best UB* 10262 0 3.80

ft53.4 14425 14425 Best Known 14425 0 0.50

ft70.1 39313 39313 Best Known 39313 0 20.90

ft70.2 [39803,40419] 40419 Best UB* 40428.6 12.00 41.00

ft70.3 [41305,42535] 42535 Best UB 42535 0 36.80

ft70.4 [53072,53530] 53530 Best UB* 53554.6 20.5 58.3

kro124p.1 [37761,39420] 39420 Best UB* 39420 0 60.80

kro124p.2 [38719,41336] 41336 Best UB* 41442 127.8 53.20

kro124p.3 [41578,49499] 49499 Best UB* 49653.2 66.3 24.2

kro124p.4 [64858,76103] 76103 Best UB 76103 0 34.2

p43.1 27990 28140 28140 0 0.52

p43.2 [28175,28330] 28480 28480 0 0.56

p43.3 [28366,28680] 28835 28835 0 0.30

p43.4 [69569,82960] 83005 83005 0 0.90

prob.42 243 243 Best UB* 246.20 3.16 34.7

prob.100 [1027,1190] 1190 Best UB* 1397.8 38.5 404.4

rbg048a 351 351 Best UB* 351 0 0.18

rbg050c 467 467 Best UB* 467 0 21.73

rbg109a 1038 1038 Best Known 1038 0 27.50

rbg150a [1748,1750] 1750 Best UB 1750 0 128.10

rbg174a 2033 2033 Best Known 2034.6 1.1 189.40

rbg253a [2940,2950] 2950 Best UB* 2950 0 145.00

rbg323a [3137,3141] 3141 Best UB* 3147.6 2.2 271.10

rbg341a [2543,2570] 2570 Best UB* 2613.60 18.1 421.30

rbg358a [2529,2545] 2545 Best UB* 2579.8 4.8 454.10

rbg378a [2761,2816] 2816 Best UB* 2841.8 6.8 500.6