Algorytmy optymalizacji tras przejazdu pojazdów

Widuch, J.

Artykuł - szczegóły

Tytuł artykułu

Algorytmy optymalizacji tras przejazdu pojazdów

Autorzy

Widuch J.

Identyfikatory

Warianty tytułu

Optimization algorithms for vehicle routing problem

Języki publikacji

Abstrakty

Wyznaczanie tras przejazdu jest jednym z badanych problemów transportowych. W niniejszej pracy przedstawiono problem wyznaczania połączeń w sieciach komunikacyjnych. Problem ten jest przykładem zadania optymalizacji wielokryterialnej, którego rozwiązaniem jest zbiór rozwiązań niezdominowanych. Przedstawione zostały 4 algorytmy, umożliwiające wyznaczenie połączeń należących do zbioru rozwiązań niezdominowanych. Dodatkowo omówiono inne problemy związane z wyznaczaniem tras przejazdu, które były badane przez pracowników Instytutu Informatyki.

The routing problem is one of the studied transportation problems. In the paper the communication networks routing problem is presented. This problem is an example of mulitcriteria optimization problem which the solution is the set of non-dominated solutions. Four algorithms for determination routes belong to the set of non-dominated solutions are shown. Additionally, other routing problems that have been researched by Staff of the Institute of Informatics are discussed.

Słowa kluczowe

transport optymalizacja wielokryterialna rozwiązanie niezdominowane metoda skalaryzacji drzewo ścieżek algorytm optymalizacji

transportation multicriteria optimization non-dominated solution scalarization method paths tree optimization algorithm

Wydawca

Wydawnictwo Politechniki Śląskiej

Czasopismo

Studia Informatica

Rocznik

2011

Tom

Vol. 32, nr 4A

Strony

83--111

Opis fizyczny

Bibliogr. 55 poz.

Twórcy

autor

Widuch J.

Politechnika Śląska, Instytut Informatyki Gliwice, Akademicka 16, pokój 509, jacek.widuch@polsl.pl

Bibliografia

1. Aho A. V., Hopcroft J. E., Ullman J. D.: Algorytmy i struktury danych. Wydawnictwo Helion, Gliwice 2003.
2. Aho A. V., Hopcroft J. E., Ullman J. D.: Projektowanie i analiza algorytmów. Wydawnictwo Helion, Gliwice 2003.
3. Brumbaugh-Smith J., Shier S.: An empirical investigation of some bicriterion shortest path algorithms. European Journal of Operational Research, Vol. 43, 1989, s. 216-224.
4. Climaco J. C, Martins E. Q. V.: A bicriterion shortest path algorithm. European Journal of Operational Research, Vol. 11, No. 4, 1982, s. 399-404.
5. Coello Coello C. A., van Veldhuizen D. A., Lamont G. B.: Evolutionary algorithms for solving multi-objective problems. Kluwer Academic Publishers, New York 2002.
6. Corley H. W., Moon I. D.: Shortest paths in networks with vector weights. Journal of Optimization Theory and Application, Vol. 46, No. 1, 1985, s. 79-86.
7. Coutinho-Rodrigues J. M., Climaco J. C, Current J. R.: An interactive bi-objective shortest path approach: searching for unsupportet nondominated solutions. Computers & Operations Research, Vol. 26, No. 8, 1999, s. 789-798.
8. Cormen T. H., Leiserson Ch. E., Rivest R. L.: Wprowadzenie do algorytmów. WNT, Warszawa 2000.
9. Czech Z. J., Czarnas P.: Parallel Simulated Annealing for the Vehicle Routing Problem with Time Windows. Proceedings of the lOth Euromicro Workshop on Parallel, Distributed and Network-based Processing, Canary Islands, Spain, January 9-11, 2002, s. 376-383.
10. Daellenbach H. G., De Kluyver C. A.: Note on multiple objective dynamie programming. Journal of the Operational Research Society, Vol. 31, No. 7, 1980, s. 591-594.
11. Debudaj-Grabysz A.: Równolegle algorytmy symulowanego wyżarzania. Rozprawa doktorska, Politechnika Śląska, Gliwice 2006.
12. Debudaj-Grabysz A., Czech Z. J.: A Concurrent Implementation of Simulated Annealing and Its Application to the VRPTW Optimization Problem. Distributed and parallel systems, The Kluwer International Series in Engineering and Computer Science, Vol. 777, Part VI, 2005, s. 201-209.
13. Debudaj-Grabysz A., Czech Z. J.: Theoretical and practical issues of parallel simulated annealing. Parallel Processing and Applied Mathematics, Lecture Notes in Computer Science, Vol. 4967, Springer, Berlin 2008, s. 189-198.
14. DeirOlmo P., Gentili M., Scozzari A.: On finding dissimilar Pareto-optimal paths. European Journal of Operational Research, Vol. 162, No. 1, 2005, s. 70-82.
15. Dijkstra E. W.: A note on two problems in connexion with graphs. Numerical Mathematics, Vol. 1, 1959, s. 269-271.
16. Gandor T.: Przybliżone rozwiązania problemu trasowania pojazdów z przedziałami czasowymi dla dużej liczby klientów. Systemy Wspomagania Decyzji, Instytut Informatyki Uniwersytetu Śląskiego, Katowice 2009, s. 257-277.
17. Gandor T.: Ocena trudności egzemplarzy problemu dostawy z oknami czasowymi. Systemy Wspomagania Decyzji, Instytut Informatyki Uniwersytetu Śląskiego, Katowice 2010, s. 153-168.
18. Garey M., Johnson D.: Computers and intractibility: a guide to the theory of NP-completeness. W. H. Freeman & Co., New York, USA, 1990.
19. Hansen P.: Bicriterion path problems. Multiple Criteria Decision Making: Theory and Application, Springer-Verlag, Berlin, Germany, 1980, s. 109-127.
20. Jungnickeł D.: Graphs, networks and algorithms. Springer, Berlin 1999.
21. Kohl N., Madsen O. B. G.: An Optimization Algorithm for with Time Windows based on Lagrangian Relaxation. Operations Research, Vol. 45, No. 3, 1997, s. 395-406.
22. Kuczora M.: Optymalizacja transportu przesyłek przy wykorzystaniu stałych linii komunikacyjnych i wyróżnionych węzłów sortujących. Studia Informatica, Vol. 23, No. 4(51), 2001, s. 105-124.
23. Lipski W.: Kombinatoryka dla programistów. WNT, Warszawa 1989.
24. Machuca E., Mandow L., Perez de la Cruz J. L.: An Evaluation of Heuristic Functions for Bicriterion Shortest Path Problems. Proceedings of the XIV Portuguese Conference on Artificial Inteligence (EPIA 2009), Universidade de Aveiro, 2009, s. 205-216.
25. Mandow L., Perez de la Cruz J. L.: Frontier search for Bicriterion Shortest Path Problems. Proceeding of the 2008 conference on ECAI 2008 18th European Conference on Artificial Intelligence, lOS Press, 2008, s. 480-484.
26. Mandow L., Perez de la Cruz J. L.: Path recovery in frontier search for multiobjective shortest path problems. Journal of Intelligent Manufacturing, Vol. 21, No. 1, 2008, s. 89-99.
27. Martins E. Q. V.: On a multicriteria shortest path problem. European Journal of Operational Research, Vol. 16, No. 2, 1982, s. 236-245.
28. Martins E. Q. V., Pascoal M. M. B.: An algorithm for ranking optimal paths. Departamento de Matematica, Universidade de Coimbra, Technical Report 01/004, CISUC, 2000 (http://www.mat.uc.pt/~marta/Publicacoes/rank_optimal.ps.gz).
29. Marti R., Gonzalez Velarde J. L., Duarte A.: Heuristics for the bi-objective path dissimilarity problem. Computers & Operations Research, Vol. 36, No. 11, 2009, s. 2905-2912.
30. Mote J., Murthy I., Olson D. L.: A parametric approach to solving bicriterion shortest path problems. European Journal of Operational Research, Vol. 53, No. 1, 1991, s. 81-92.
31. Pareto V.: Course dEconomie Politique, F. Rouge, Lausanne 1896.
32. Peschel M., Riedel C: Polioptymalizacja. Metody podejmowania decyzji kompromisowych w zagadnieniach inżynieryjno-technicznych. WNT, Warszawa 1979.
33. Raith A., Ehrgott M.: A comparison of solution strategies for biobjective shortest path problems. Journal Computers and Operations Research, Vol. 36, No. 4, 2009, s. 1299-1331.
34. Reingold E. M., Nievergelt J., Deo N.: Algorytmy kombinatoryczne. PWN, Warszawa 1985.
35. Skórczyński A.: Modyfikacja widoczności w algorytmach mrówkowych rozwiązujących problem dostawy. Studia Informatica, Vol. 22, nr 4(46), 2001, s. 235-244.
36. Skriver A. J. V., Andersen K.A.: A classification of bicriteria shortest path (BSP) algorithms. Asia-Pacific Journal of Operational Research, Vol. 17, 2000, s. 199-212.
37. Skriver A. J. V., Andersen K.A.: A label correcting approach for solving bicriterion shortest-path problems. Computers & Operations Research, Vol. 27, 2000, s. 507-524.
38. Stadler W.: A survey of Multicriteria Otimization or the Vector Maximum Problem. Part I: 1776-1960, Journal of Optimization Theory & Aplication, Vol. 29, No. 1, 1979, s. 1-52.
39. Sysło M. M., Deo N., Kowalik J. S.: Algorytmy optymalizacji dyskretnej z programami w języku Pascal. Wydawnictwo Naukowe PWN, Warszawa 1995.
40. Szołtysek M.: Rozwiązanie problemu dostawy za pomocą algorytmu przeszukiwania tabu. ZN Pol. Śląskiej, seria: Informatyka, z. 37, nr kol. 1421, 1999, s. 209-221.
41. Szołtysek M.: Problem wyznaczania połączeń autobusowych. Studia Informatica, Vol. 21, No. 3,2000, s. 187-200.
42. Tung C. T., Chew K. L.: A bicriterion Pareto-optimal path algorithm. Asia-Pacific Journal of Operational Research, Vol. 5, 1988, s. 166-172.
43. Ulungu E. L., Teghem J.: Multi-objective combinatorial optimization problems: a survey. Journal of Multi-Criteria Decision Analysis, Vol. 3, No. 2, 1994, s. 83-104.
44. Voorneveld M.: Characterization of Pareto dominance. Operations Research Letters, Vol. 31, No. 1,2003, s. 7-11.
45. White D. J.: The set of efficient solutions for multiple objective shortest path problems. Computers & Operations Research, Vol. 9, No. 2, 1982, s. 101-107.
46. Widuch J.: Problem wyznaczania połączeń w sieciach komunikacyjnych. Studia Informatica Vol. 22, No. 4(46), Gliwice 2001, s. 117-134.
47. Widuch J.: Wyznaczanie połączeń w sieciach komunikacyjnych o zmiennych wagach. Studia Informatica, Vol. 23, No, 4(51), Gliwice 2002, s. 85-104.
48. Widuch J.: Problem wyznaczania optymalnej trasy transportu przesyłek. Studia Informatica, Vol. 24, No. 4(56), Gliwice 2003, s. 67-84.
49. Widuch J.: Algorytmy optymalizacji wielokryterialnej w problemach komunikacyjnych. Rozprawa doktorska, Politechnika Śląska, Gliwice 2008.
50. Widuch J.: Rozwiązanie problemu wyznaczania połączeń w sieciach komunikacyjnych za pomocą zmodyfikowanego algorytmu wyznaczania K najkrótszych ścieżek. Studia Informatica, Vol. 31, No. 1(88), Gliwice 2010, s. 55-70.
51. Widuch J.: Rozwiązanie problemu wyznaczania połączeń w sieciach komunikacyjnych z zastosowaniem metody skalaryzacji. Studia Informatica, Vol. 32, No. 4A(100), Gliwice 2011.
52. Wieczorek B.: Równoległe algorytmy symulowanego wyżarzania dla problemu trasowania pojazdów z ograniczeniami czasowymi. Studia Informatica, Vol. 26, No 1(62), Gliwice 2005, s. 93-105.
53. Wilson R. J.: Wprowadzenie do teorii grafów. Wydawnictwo Naukowe PWN, Warszawa 1998.
54. Zbiory testowe Hombergera dla problemu VRPTW (1.09.2011): http://www.fernuni-hagen.de/WTNF/touren/inhalte/probinst.htm
55. Zbiory testowe Solomona dla problemu VRPTW (1.09.2011): http://web.cba.neu.edu/~msolomon/problems.htm.

Typ dokumentu

Bibliografia

Identyfikator YADDA

bwmeta1.element.baztech-article-BSL1-0019-0010