A multistart hybrid algorithm to solving the sequential ordering problem

Jacek Widuch, Artur Klyta

Abstract


The sequential ordering problem (SOP) is similar to the asymmetric traveling salesman problem. The goal is to find a minimum weight Hamiltonian path on a directed weighted graph satisfying precedence relationships among the vertices. In the paper, a multistart hybrid algorithm to solving SOP is presented. The algorithm based on simulated annealing algorithm and local optimization method. Apart from that results of experimental tests are presented.


Keywords


sequential ordering problem; NP–hard problem; Hamiltonian cycle; Hamiltonian path; heuristic algorithm; simulated annealing; local optimization; hybrid algorithm

Full Text:

PDF (Polski)

References


Aarts E., Korst J.: Simulated annealing and Boltzmann machines: a stochastic approach to combinatorial optimization and neural computing. John Wiley & Sons, Inc. New York, NY, USA 1989.

Aarts E., Korst J., Michiels W.: Simulated Annealing. [in:] Search Methodologies Intro-ductory Tutorials in Optimization and Decision Support Technique, Springer, New York, NY, USA 2000, p. 187–210.

Alcaide D., Rodriguez–Gonzalez A., Sicilia J.: An approach to solve a hierarchical sto-chastic sequential ordering problem. Omega, Vol. 31, Issue 3, 2003, p. 169–187.

Alonso–Ayuso A., Detti P., Escudero L. F., Ortuno M. T.: On Dual Based Lower Bounds for the Sequential Ordering Problem with Precedences and Due Dates. Annals of Opera-tions Research, Vol. 124, Issue 1–4, 2003, p. 111–131.

Anghinolfi D., Montemanni R., Paolucci M., Gambardella L. M.: A hybrid particle swarm optimization approach for the sequential ordering problem. Computers & Operations Re-search, Vol. 38, Issue 7, 2011, p. 1076–1085.

Bock F.: An algorithm for solving traveling–salesman and related network optimization problems. Research Report, Armour Research Foundation, Presented at the Operations Research Society of America Fourteenth National Meeting, St. Louis, October 24, 1958.

Cerny V.: A thermodynamical approach to the traveling salesman problem: an efficient simulation algorithm. Journal of Optimization Theory and Applications, Vol. 45, No. 1, 1985, p. 41–55.

Cormen T. H., Leiserson C. E., Rivest R. L.: Wprowadzenie do algorytmów. WNT, War-szawa 2007.

Dantzig G. B., Fulkerson R., Johnson S. M.: Solution of a large–scale traveling salesman problem. Operations Research, Vol. 2, Issue 4, 1954, p. 393–410.

Escudero L. F.: An inexact algorithm for the sequential ordering problem. European Journal of Operational Research, Vol. 37, Issue 2, 1988, p. 236–249.

Escudero L. F., Guignard M., Malik K.: A Lagrangian relax–and–cut approach for the sequential ordering problem with precedence relationships. Annals of Operations Re-search, Vol. 50, No. 1, 1994, p. 219–237.

Escudero L. F., Ortuno M. T.: On Due-Date Based Valid Cuts for the Sequential Order-ing Problem. Top, Vol. 5, Issue 1, 1997, p. 159–166.

Escudero L. F., Sciomachen A.: Local search procedures for improving feasible solutions to the sequential ordering problem. Annals of Operations Research, Vol. 43, No. 7, 1993, p. 397–416.

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, No. 2, 2000, p. 237–255.

Gambardella L. M., Montemanni R., Weyland D.: An Enhanced Ant Colony System for the Sequential Ordering Problem. Operations Research Proceedings 2012, p. 355–360.

Grötschel M., Padberg M. W.: On the symmetric travelling salesman problem I: Inequali-ties. Mathematical Programming, Vol. 16, 1979, p. 265-280.

Guerriero F., Mancini M.: A cooperative parallel rollout algorithm for the sequential or-dering problem. Parallel Computing, Vol. 29, No. 5, 2003, p. 663–677.

Hernŕdvölgyi I. T.: Solving the sequential ordering problem with automatically generated lower bounds. [in:] Proceedings of Operations Research, Springer–Verlag Berlin, Heidel-berg, Germany 2003, p. 355–362.

Homaifar A., Guan S., Liepins G. E.: A New Approach on the Traveling Salesman Prob-lem by Genetic Algorithms. In Proceedings of the Fifth International Conference on Ge-netic Algorithms, 1993, p. 460–466.

Johnson D. S., McGeoch, L. A.: The Traveling Salesman Problem: A Case Study in Lo-cal Optimization. [in:] Local Search in Combinatorial Optimisation, John Wiley and Sons Ltd, London, UK 1997, p. 215–310.

Jungnickel D.: Graphs, networks and algorithms. Springer, Berlin, Germany 1999.

Kirkpatrick S.: Optimization by Simulated Annealing: Quantitative Studies. Journal of Statistical Physics, Vol. 34, Issue 5–6, 1984, p. 975–986.

Kirkpatrick S., Gelatt C. D., Vecchi M. P.: Optimization by simulated annealing. Sci-ence, Vol. 220, No. 4598, 1983, p. 671–680.

Landau L. D., Lifszyc J. M.: Fizyka statystyczna część 1. Wydawnictwo Naukowe PWN, Warszawa 2012.

Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G., Shmoys D. B.: The Traveling Sales-man Problem: A Guided Tour of Combinatorial Optimization. John Wiley & Sons, 1985.

Lenstra J. K., Rinnooy Kan A. H. G.: Some Simple Applications of the Travelling Salesman Problem. Operational Research Quarterly, Vol. 26, No. 4, Part 1, 1975, p. 717–733.

Lin S.: Computer solutions of the traveling salesman problem. Bell System Technical Journal, Vol. 44, 1965, p. 2245–2269.

Lin S., Kernighan B. W.: An Effective Heuristic Algorithm for the Traveling–Salesman Problem. Operations Research, Vol. 21, No. 2, 1973, p. 498–516.

Little J. D. C., Murty K. G., Sweeney D. W., Karel C.: An algorithm for the traveling salesman problem. Operations Research, Vol. 11, 1963, p. 972–989.

Metropolis N., Rosenbluth A. W., Rosenbluth M. N., Teller A. H., Teller E.: Equation of state calculation by fast computing machines. The Journal of Chemical Physics, Vol. 21, No. 6, 1953, p. 1087–1091.

Metropolis N., Ulam S.: The Monte Carlo Method. Journal of the American Statistical Association, Vol. 44, No. 247, 1949, p. 335–341.

Michalewicz Z., Fogel D. B.: How to Solve It: Modern Heuristics, Springer, New York, NY, USA 2000.

Michalewicz Z., Fogel D. B.: Jak to rozwiązać czyli nowoczesna heurystyka. WNT, War-szawa 2006.

Michalewicz Z.: Algorytmy genetyczne + struktury danych = programy ewolucyjne. WNT, Warszawa 1996.

Mojana M., Montemanni R., Di Caro G., Gambardella L. M.: A branch and bound ap-proach for the sequential ordering problem. Lecture Notes in Management Science, Vol. 4, 2012, p. 266–273.

Montemanni R., Smith D. H., Gambardella L. M.: A heuristic manipulation technique for the sequential ordering problem. Computers & Operations Research, Vol. 35, Issue 12, 2008, p. 3931–3944.

Montemanni R., Smith D. H., Gambardella L. M.: Ant Colony Systems for Large Se-quential Ordering Problems. [in:] Proceedings of the 2007 IEEE Swarm Intelligence Symposium (SIS 2007), 2007, p. 60–67.

Osman I. H., Kelly J. P.: Meta-Heuristics: An Overview. [in:] Meta-heuristics: Theory and Applications. Kluwer Academic Publishers, 1996.

Padberg M. W., Rao M. R.: The travelling salesman problem and a class of polyhedra of diameter two. Mathematical Programming, Vol. 7, Issue 1, 1974, p. 32–45.

Papadimitriou C. H., Steiglitz K.: On the Complexity of Local Search for the Traveling Salesman Problem. SIAM Journal on Computing, Vol. 6, 1977, p. 76–83.

Rayward–Smith V. J., Osman I. H., Reeves C. R., Smith G. D.: Modern Heuristic Search Methods. John Wiley & Sons Ltd., Chichester, England 1996.

Reeves C. R.: Modern heuristic techniques for combinatorial problems. John Wiley & Sons, Inc. New York, NY, USA 1993.

Reinelt G.: The Traveling Salesman: computational solutions for TSP applications. Springer–Verlag Berlin, Heidelberg, Germany 1994.

Sanvicente–Sánchez H., Frausto–Solís J.: MPSA: A Methodology to Parallelize Simu-lated Annealing and It s Application to the Traveling Salesman Problem. MICAI 2002, LNAI 2313, 2002, p. 89–97.

Seo D., Moon B.: A hybrid genetic algorithm based on complete graph representation for the sequential ordering problem. LNCS, Vol. 2723, 2003, p. 669–680.

Yang R.: Solving Large Traveling Salesman Problems with Small Populations. Genetic Algorithms in Engineering Systems: Innovations and Applications, GALESIA 97 Second International Conference On (Conf. Publ. No. 446), 1997, p. 157–162.

TSPLIB, a library of sample instances for the TSP (and related problems) from various sources and of various types: http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/.




DOI: http://dx.doi.org/10.21936/si2014_v35.n1.682