{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,12]],"date-time":"2024-08-12T09:11:06Z","timestamp":1723453866851},"reference-count":38,"publisher":"Institute for Operations Research and the Management Sciences (INFORMS)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["INFORMS Journal on Computing"],"published-print":{"date-parts":[[2000,8]]},"abstract":" We present a new local optimizer called SOP-3-exchange for the sequential ordering problem that extends a local search for the traveling salesman problem to handle multiple constraints directly without increasing computational complexity. An algorithm that combines the SOP-3-exchange with an Ant Colony Optimization algorithm is described, and we present experimental evidence 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-3-exchange with our Ant Colony Optimization algorithm or in combination with the MPO\/AI algorithm (Chen and Smith 1996). <\/jats:p>","DOI":"10.1287\/ijoc.12.3.237.12636","type":"journal-article","created":{"date-parts":[[2003,4,14]],"date-time":"2003-04-14T12:38:39Z","timestamp":1050323919000},"page":"237-255","source":"Crossref","is-referenced-by-count":241,"title":["An Ant Colony System Hybridized with a New Local Search for the Sequential Ordering Problem"],"prefix":"10.1287","volume":"12","author":[{"given":"Luca Maria","family":"Gambardella","sequence":"first","affiliation":[{"name":"IDSIA, Galleria 2, CH-6928 Manno-Lugano, Switzerland"}]},{"given":"Marco","family":"Dorigo","sequence":"additional","affiliation":[{"name":"IRIDIA, CP 194\/6, Universit\u00e9 Libre de Bruxelles, Ave. F. Roosevelt 50, B-1050 Brussels, Belgium"}]}],"member":"109","reference":[{"key":"B1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-349-25589-4_1"},{"key":"B2","unstructured":"Ascheuer N. Hamiltonian path problems in the on-line optimization of flexible manufacturing systems. (1995) (Technische Universit\u00e4t, Berlin, Germany) . Ph.D. thesis"},{"key":"B4","doi-asserted-by":"publisher","DOI":"10.1137\/0803002"},{"key":"B5","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585767"},{"key":"B6","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.6.2.126"},{"key":"B7","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.4.4.387"},{"key":"B9","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(90)90301-Q"},{"key":"B10","unstructured":"Dorigo M. Ottimizzazione, apprendimento automatico, ed algoritmi basati su metafora naturale. [Optimization, learning and natural algorithms.]. (1992) (Dipartimento di Elettronica e Informazione, Politecnico di Milano, Italy) . Doctoral dissertation"},{"key":"B11","first-page":"11","volume-title":"New Ideas in Optimization","author":"Dorigo M.","year":"1999"},{"key":"B12","doi-asserted-by":"publisher","DOI":"10.1162\/106454699568728"},{"key":"B13","doi-asserted-by":"publisher","DOI":"10.1109\/4235.585892"},{"key":"B14","unstructured":"Dorigo M., Maniezzo V., Colorni A. The Ant System: an autocatalytic optimizing process. (1991) (Dipartimento di Elettronica, Politecnico di Milano, Italy) . Technical Report No. 91-016"},{"key":"B15","doi-asserted-by":"publisher","DOI":"10.1109\/3477.484436"},{"key":"B16","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(88)90333-5"},{"key":"B17","doi-asserted-by":"publisher","DOI":"10.1007\/BF02085641"},{"key":"B18","first-page":"190","volume":"16","author":"Fleurent C.","year":"1994","journal-title":"DIMACS Series in Mathematical Theoretical Computer Science"},{"key":"B19","volume-title":"Evolutionary Computation: Toward a New Philosophy of Machine Intelligence","author":"Fogel D.B.","year":"1994"},{"key":"B20","doi-asserted-by":"publisher","DOI":"10.1016\/B978-1-55860-377-6.50039-6"},{"key":"B21","doi-asserted-by":"publisher","DOI":"10.1109\/ICEC.1996.542672"},{"key":"B22","unstructured":"Gambardella L.M., Dorigo M. HAS-SOP: an Hybrid Ant System for the sequential ordering problem. (1997) (IDSIA, Lugano, Switzerland) . Technical Report, IDSIA\/11-97"},{"key":"B23","first-page":"63","volume-title":"New Ideas in Optimization","author":"Gambardella L.M.","year":"1999"},{"key":"B24","doi-asserted-by":"publisher","DOI":"10.1057\/palgrave.jors.2600676"},{"key":"B25","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1.3.190"},{"key":"B26","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2.1.4"},{"key":"B27","volume-title":"Adaptation in Natural and Artificial Systems","author":"Holland J.H.","year":"1975"},{"key":"B28","first-page":"215","volume-title":"Local Search in Combinatorial Optimization","author":"Johnson D.S.","year":"1997"},{"key":"B29","first-page":"311","volume-title":"Local Search in Combinatorial Optimization","author":"Kindervater G.A.P.","year":"1997"},{"key":"B30","doi-asserted-by":"publisher","DOI":"10.1126\/science.220.4598.671"},{"key":"B31","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1965.tb04146.x"},{"key":"B32","doi-asserted-by":"publisher","DOI":"10.1287\/opre.21.2.498"},{"key":"B33","unstructured":"Or I. Traveling salesman-type combinatorial problems and their relation to the logistics of blood banking. (1976) (Department of Industrial and Engineering and Management Science, Northwestern University, Evanston, IL) . Ph.D. thesis"},{"key":"B34","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(83)90099-1"},{"key":"B35","unstructured":"Pulleyblank W., Timlin M. Precedence constrained routing and helicopter scheduling: heuristic design. (1991) (IBM T.J. Watson Research Center, Yorktown Heights, NY) . IBM Technical Report RC17154 (#76032)"},{"key":"B36","volume-title":"The Traveling Salesman: Computational Solutions for TSP Applications","author":"Reinelt G.","year":"1994"},{"key":"B37","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(90)90091-O"},{"key":"B38","doi-asserted-by":"publisher","DOI":"10.1287\/opre.35.2.254"},{"key":"B39","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(05)80147-4"},{"key":"B40","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.27.3.298"}],"container-title":["INFORMS Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/pubsonline.informs.org\/doi\/pdf\/10.1287\/ijoc.12.3.237.12636","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,2]],"date-time":"2023-04-02T11:49:27Z","timestamp":1680436167000},"score":1,"resource":{"primary":{"URL":"https:\/\/pubsonline.informs.org\/doi\/10.1287\/ijoc.12.3.237.12636"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,8]]},"references-count":38,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2000,8]]}},"alternative-id":["10.1287\/ijoc.12.3.237.12636"],"URL":"https:\/\/doi.org\/10.1287\/ijoc.12.3.237.12636","relation":{},"ISSN":["1091-9856","1526-5528"],"issn-type":[{"value":"1091-9856","type":"print"},{"value":"1526-5528","type":"electronic"}],"subject":[],"published":{"date-parts":[[2000,8]]}}}