An Ant Colony System Hybridized with a New Local Search for the Sequential Ordering Problem

References

• Aarts E.H., Lenstra J.K., Aarts E.H., Lenstra J.K. Introduction. Local Search in Combinatorial Optimization (1997) (John Wiley & Sons, Chichester, U.K.) 1–17Crossref, Google Scholar
• Ascheuer N. Hamiltonian path problems in the on-line optimization of flexible manufacturing systems. (1995) (Technische Universität, Berlin, Germany) . Ph.D. thesisGoogle Scholar
• Ascheuer N. Personal communication. (1997) Google Scholar
• Ascheuer N., Escudero L.F., Grotschel M., Stoer M. A cutting plane approach to the sequential ordering problem (with applications to job scheduling in manufacturing). SIAM Journal on Optimization (1993) 3:25–42Crossref, Google Scholar
• Balas E., Fischetti M., Pulleyblank W.R. The precedenceconstrained asymmetric traveling salesman polytope. Mathematical Programming (1995) 65:241–265Crossref, Google Scholar
• Battiti R., Tecchiolli G. The reactive tabu search. ORSA Journal on Computing (1994) 6:126–140Link, Google Scholar
• Bentley J.L. Fast algorithms for geometric traveling salesman problem. ORSA Journal on Computing (1992) 4:387–411Link, Google Scholar
• Chen S., Smith S. Commonality and genetic algorithms. (1996) (The Robotic Institute, Carnegie Mellon University, Pittsburgh, PA) . Technical Report CMU-RI-TR-96-27Google Scholar
• Connolly D.T. An improved annealing scheme for the QAP. European Journal of Operational Research (1990) 46:93–100Crossref, Google Scholar
• 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 dissertationGoogle Scholar
• Dorigo M., Di Caro G., Corne D., Dorigo M., Glover F. The Ant Colony Optimization metaheuristic. New Ideas in Optimization (1999) (McGraw-Hill, London, U.K.) 11–32Google Scholar
• Dorigo M., Di Caro G., Gambardella L.M. Ant algorithms for discrete optimization. Artificial Life (1999) 5:137–172Crossref, Google Scholar
• Dorigo M., Gambardella L.M. Ant Colony System: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation (1997) 1:53–66Crossref, Google Scholar
• 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-016Google Scholar
• Dorigo M., Maniezzo V., Colorni A. The Ant System: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics—Part B (1996) 26:29–41Crossref, Google Scholar
• Escudero L.F. An inexact algorithm for the sequential ordering problem. European Journal of Operational Research (1988) 37:232–253Crossref, Google Scholar
• Escudero L.F., Guignard M., Malik K. A Lagrangian relax-and-cut approach for the sequential ordering problem with precedence relationships. Annals of Operations Research (1994) 50:219–237Crossref, Google Scholar
• Fleurent C., Ferland J. Genetic hybrids for the quadratic assignment problem. DIMACS Series in Mathematical Theoretical Computer Science (1994) 16:190–206Google Scholar
• Fogel D.B.Evolutionary Computation: Toward a New Philosophy of Machine Intelligence (1994) (IEEE Press, New York) Google Scholar
• Gambardella L.M., Dorigo M., Prieditis A., Russell S. Ant-Q: a reinforcement learning approach to the traveling salesman problem. Proceedings of ML-95, Twelfth International Conference on Machine Learning, Tahoe City, CA, July 1995 (1995) (Morgan Kaufmann, Palo Alto, CA) 252–260Crossref, Google Scholar
• Gambardella L.M., Dorigo M. Solving symmetric and asymmetric TSPs by ant colonies. Proceedings of IEEE International Conference on Evolutionary Computation, IEEE-EC 96, Nagoya, Japan, May 1996 (1996) (IEEE Press, Piscataway, NJ) 622–627Crossref, Google Scholar
• Gambardella L.M., Dorigo M. HAS-SOP: an Hybrid Ant System for the sequential ordering problem. (1997) (IDSIA, Lugano, Switzerland) . Technical Report, IDSIA/11-97Google Scholar
• Gambardella L.M., Taillard É.D., Agazzi G., Corne D., Dorigo M., Glover F. MACS-VRPTW: a multiple Ant Colony System for vehicle routing problems with time windows. New Ideas in Optimization (1999a) (McGraw-Hill, London, U.K.) 63–76Google Scholar
• Gambardella L.M., Taillard É.D., Dorigo M. Ant colonies for the quadratic assignment problem. Journal of the Operational Research Society (1999b) 50:167–176Crossref, Google Scholar
• Glover F. Tabu search, Part I. ORSA Journal on Computing (1989a) 1:190–206Link, Google Scholar
• Glover F. Tabu search, Part II. ORSA Journal on Computing (1989b) 2:4–32Link, Google Scholar
• Holland J.H.Adaptation in Natural and Artificial Systems (1975) (University of Michigan Press, Ann Arbor, MI) Google Scholar
• Johnson D.S., McGeoch L.A., Aarts E.H., Lenstra J.K. The traveling salesman problem: a case study. Local Search in Combinatorial Optimization (1997) (John Wiley & Sons, Chichester, U.K.) 215–310Google Scholar
• Kindervater G.A.P., Savelsbergh M.W.P., Aarts E.H., Lenstra J.K. Vehicle routing: handling edge exchanges. Local Search in Combinatorial Optimization (1997) (John Wiley & Sons, Chichester, U.K.) 311–336Google Scholar
• Kirkpatrick S., Gelatt C.D., Vecchi M.P. Optimization by simulated annealing. Science (1983) 220:671–680Crossref, Google Scholar
• Lin S. Computer solutions of the traveling salesman problem. Bell Systems Journal (1965) 44:2245–2269Crossref, Google Scholar
• Lin S., Kernighan B.W. An effective heuristic algorithm for the traveling salesman problem. Operations Research (1973) 21:498–516Link, Google Scholar
• 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. thesisGoogle Scholar
• Psaraftis H.N. K-interchange procedures for local search in a precedence-constrained routing problem. European Journal of Operational Research (1983) 13:341–402Crossref, Google Scholar
• 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)Google Scholar
• Reinelt G.The Traveling Salesman: Computational Solutions for TSP Applications (1994) (LNCS 840, Springer-Verlag, Berlin, Germany) Google Scholar
• Savelsbergh M.W.P. An efficient implementation of local search algorithms for constrained routing problems. European Journal of Operational Research (1990) 47:75–85Crossref, Google Scholar
• Solomon M.M. Algorithms for the vehicle routing and scheduling problems with time windows constraints. Journal of Operational Research (1987) 35:254–265Link, Google Scholar
• Taillard É.D. Robust tabu search for the quadratic assignment problem. Parallel Computing (1991) 17:443–455Crossref, Google Scholar
• Van der Bruggen L.J.J., Lenstra L.K., Schuur P.C. Variable-depth search for the single-vehicle pickup and delivery problem with time windows. Transportation Science (1993) 27:298–311Link, Google Scholar