PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Tytuł artykułu

Algorytm hybrydowy wielokrotnego startu dla rozwiązywania problemu sekwencyjnego uporządkowania

Autorzy
Identyfikatory
Warianty tytułu
EN
A multistart hybrid algorithm to solving the sequential ordering problem
Języki publikacji
PL
Abstrakty
PL
Problem sekwencyjnego uporządkowania (SOP) jest podobny do asymetrycznego problemu komiwojażera. Celem jest wyznaczenie w skierowanym grafie ważonym ścieżki Hamiltona o minimalnej wadze, przy dodatkowym spełnieniu relacji pierwszeństwa wierzchołków. W niniejszej pracy zaprezentowano algorytm hybrydowy wielokrotnego startu rozwiązywania problemu SOP. Algorytm ten jest połączeniem algorytmów symulowanego wyżarzania i lokalnej optymalizacji. Dodatkowo przedstawiono wyniki przeprowadzonych badań eksperymentalnych.
EN
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.
Czasopismo
Rocznik
Strony
29--55
Opis fizyczny
Bibliogr. 47 poz.
Twórcy
autor
  • Politechnika Śląska, Instytut Informatyki, ul. Akademicka 16, 44-100 Gliwice, Polska
autor
  • Politechnika Śląska, Instytut Informatyki, ul. Akademicka 16, 44-100 Gliwice, Polska
Bibliografia
  • 1. 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.
  • 2. Aarts E., Korst J., Michiels W.: Simulated Annealing. [in:] Search Methodologies Introductory Tutorials in Optimization and Decision Support Technique, Springer, New York, NY, USA 2000, p. 187-210.
  • 3. 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.
  • 4. Alonso-Ayuso A., Detti P., Escudero L. F., Ortufio 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.
  • 5. Anghinolfi D., Montemanni R., Paolucci M., Gambardella L. M.: A hybrid particie swarm optimization approach for the sequential ordering problem. Computers & Operations Re¬search, Vol. 38, Issue 7,201 l,p. 1076-1085.
  • 6. 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, October24, 1958.
  • 7. 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.
  • 8. Cormen T. H., Leiserson C. E., Rivest R. L.: Wprowadzenie do algorytmów. WNT, Warszawa 2007.
  • 9. Dantzig G. B., Fulkerson R., Johnson S. M.: Solution of a large-scale traveling salesman problem. Operations Research, Vol. 2, Issue4, 1954, p. 393-410.
  • 10. Escudero L. F.: An inexact algorithm for the sequential ordering problem. European Journal of Operational Research, Vol. 37, Issue 2, 1988, p. 236-249.
  • 11. 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.
  • 12. Escudero L. F., Ortuno M. T.: On Due-Date Based Valid Cuts for the Sequential Ordering Problem. Top, Vol. 5, Issue 1, 1997, p. 159-166.
  • 13. 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.
  • 14. 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.
  • 15. Gambardella L. M., Montemanni R., Weyland D.: An Enhanced Ant Colony System for the Sequential Ordering Problem. Operations Research Proceedings 2012, p. 355—360.
  • 16. Grótschel M., Padberg M. W.: On the symmetric travelling salesman problem I: Inequalities. Mathematical Programming, Vol. 16, 1979, p. 265-280.
  • 17. Guerriero F., Mancini M.: A cooperative parallel rollout algorithm for the sequential ordering problem. Parallel Computing, Vol. 29, No. 5, 2003, p. 663-677.
  • 18. Hernfdvólgyi I. T.: Solving the sequential ordering problem with automatically generated lower bounds. [in:] Proceedings of Operations Research, Springer-Verlag Berlin, Heidelberg, Germany 2003, p. 355-362.
  • 19. Homaifar A., Guan S., Liepins G. E.: A New Approach on the Traveling Salesman Problem by Genetic Algorithms. In Proceedings of the Fifth International Conference on Genetic Algorithms, 1993, p. 460-466.
  • 20. Johnson D. S., McGeoch, L. A.: The Traveling Salesman Problem: A Case Study in Local Optimization. [in:] Local Search in Combinatorial Optimisation, John Wiley and Sons Ltd, London, UK 1997, p. 215-310.
  • 21. Jungnickel D.: Graphs, networks and algorithms. Springer, Berlin, Germany 1999.
  • 22. Kirkpatrick S.: Optimization by Simulated Annealing: Quantitative Studies. Journal of Statistical Physics, Vol. 34, Issue 5-6, 1984, p. 975-986.
  • 23. Kirkpatrick S., Gelatt C. D., Vecchi M. P.: Optimization by simulated annealing. Science, Vol. 220, No. 4598, 1983. p. 671-680.
  • 24. Landau L. D., Lifszyc J. M.: Fizyka statystyczna część 1. Wydawnictwo Naukowe PWN, Warszawa 2012.
  • 25. Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G., Shmoys D. B.: The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. John Wiley & Sons, 1985.
  • 26. 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.
  • 27. Lin S.: Computer solutions of the traveling salesman problem. Bell System Technical Journal, Vol. 44, 1965, p. 2245-2269.
  • 28. Lin S., Kernighan B. W.: An Effective Heuristic Algorithm for the Traveling-Salesman Problem. Operations Research, Vol. 21, No. 2, 1973, p. 498-516.
  • 29. Little J. D. C, Murty K. G., Sweeney D. W., Kareł C: An algorithm for the traveling salesman problem. Operations Research, VoI. 11, 1963, p. 972-989.
  • 30. 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.
  • 31. Metropolis N., Ułam S.: The Monte Carlo Method. Journal of the American Statistical Association, Vol. 44, No. 247, 1949, p. 335-341.
  • 32. Michalewicz Z., Fogel D. B.: How to Solve It: Modern Heuristics, Springer, New York, NY, USA 2000.
  • 33. Michalewicz Z., Fogel D. B.: Jak to rozwiązać czyli nowoczesna heurystyka. WNT, Warszawa 2006.
  • 34. Michalewicz Z.: Algorytmy genetyczne + struktury danych = programy ewolucyjne. WNT, Warszawa 1996.
  • 35. Mojana M., Montemanni R., Di Caro G., Gambardella L. M.: A branch and bound approach for the sequential ordering problem. Lecture Notes in Management Science, Vol. 4, 2012, p. 266-273.
  • 36. 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.
  • 37. Montemanni R., Smith D. H., Gambardella L. M.: Ant Colony Systems for Large Sequential Ordering Problems. [in:] Proceedings of the 2007 IEEE Swarm Intelligence Symposium (SIS 2007), 2007, p. 60-67.
  • 38. Osman I. H., Kelly J. P.: Meta-Heuristics: An Overview. [in:] Meta-heuristics: Theory and Applications. Kluwer Academic Publishers, 1996.
  • 39. 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.
  • 40. 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.
  • 41. Rayward-Smith V. J., Osman I. H., Reeves C. R., Smith G. D.: Modern Heuristic Search Methods. John Wiley & Sons Ltd., Chichester, England 1996.
  • 42. Reeves C. R.: Modern heuristic techniques for combinatorial problems. John Wiley & Sons, Inc. New York, NY, USA 1993.
  • 43. Reinelt G.: The Traveling Salesman: computational solutions for TSP applications. Springer-Verlag Berlin, Heidelberg, Germany 1994.
  • 44. Sanvicente-Sanchez H., Frausto-Solis J.: MPSA: A Methodology to Parallelize Simulated Annealing and It s Application to the Traveling Salesman Problem. MICAI 2002, LNAI 2313,2002, p. 89-97.
  • 45. 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.
  • 46. Yang R.: Solving Large Traveling Salesman Problems with Smali Populations. Genetic Algorithms in Engineering Systems: Innovations and Applications, GALESIA 97 Second International Conference On (Conf. Publ. No. 446), 1997, p. 157-162.
  • 47. 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/.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-954c6232-82a0-4ebf-8ea5-5f9e6ec8581a
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.