Algorytmizacja procesu wyznaczania długości ścieżek w sieci rozbudowanej podstawą optymalizacji zagadnień transportowych

• Autorzy: Ignaciuk S. , Wawrzosek J. , Kubera E. , Baryła-Paśnik M. , Piekarski W.

Warianty tytułu

EN

Algorithmization of the process determining the length of paths in expanded networks

• Języki publikacji: PL

Abstrakty

PL

Matematyczne metody optymalizacyjne służą jako narzędzie wykorzystywane przy podejmowaniu decyzji w działalności transportowej. Graf jest powszechnie stosowany do prezentacji problemów logistycznych. Znanym zagadnieniem w literaturze przedmiotu jest wyznaczanie najkrótszej ścieżki w grafie nie-skierowanym o nieujemnych wagach na krawędziach pomiędzy dwoma węzłami tej sieci. Odmianą tego zagadnienia jest problem znalezienia najkrótszych ścieżek pomiędzy wszystkimi parami węzłów grafu. Działanie takie w zakresie zagadnień transportowych ma na celu utworzenie pełnej macierzy odległości między wszystkimi węzłami grafu (wyznaczenie najkrótszych odległości między wszystkimi punktami na-dania i odbioru towaru). Współczesne techniki informatyczne pozwalają na przechowywanie w pamięci komputera pełnych danych zawierających informację obejmującą odległość między dwoma dowolnymi węzłami sieci i ciąg węzłów opisujących tą najkrótszą ścieżkę. W oparciu o taką istniejącą bazę można dokonywać optymalizacji procesów transportowych. Celem pracy jest wskazanie algorytmu, który na bazie wag przypisanych krawędziom grafu nieskierowanego (interpretowanymi jako odległości między dwoma węzłami) wyznacza macierz najkrótszych odległości między wszystkimi węzłami grafu oraz dodatkowo wyznacza ścieżki najkrótszych połączeń. Proces ten prowadzi m.in. do zastąpienia macierzy rzadkiej przez macierzą pełną. Równocześnie proces modelowania stanowi przejście pomiędzy zagadnieniami z zakresu teorii grafów a teorii przestrzeni metrycznych. Tak utworzona macierz pełna może stanowić podstawę do tworzenia bazy pełnych cykli Hamiltona lub innych zagadnień systemów transportowych. Wstępna analiza zaproponowanego tu algorytmu etapowego wskazuje, że jest on porównywalny ze znanymi algorytmami, a w niektórych przypadkach działa nawet szybciej. Kolejnym krokiem w następnej pracy będą czynności odwrotne do opisanych powyżej. Połączenie obu procedur pozwala na kontrolę procesu tworzenia minimal-nego grafu rozpinającego wszystkie najkrótsze ścieżki, ewentualnie tworzenie drzewa rozpinającego ścieżki, w których najkrótsze połączenia różnią się od najkrótszych dróg z zadaną z góry dokładnością. Wskazano możliwość wykorzystania wyników w optymalizacji transportu w przemyśle mleczarskim.

EN

A well-known issue in the professional literature is how to determine the shortest path in an undirected graph with non-negative weighted edges between two network nodes. A variation of this issue is to find the shortest paths between all the node pairs of a graph. Modern techniques allow one to store in the computer memory complete data containing information about the distance between any two network nodes and a sequence of nodes describing the shortest path. On the basis of such existing databases optimisation of transportation processes can be undertaken. This study aims at showing an algorithm that basing on the weights of an undirected graph edges (interpreted as the distance in some node pairs) determines the shortest distance matrix between all the nodes of the graph and additionally determines paths of shortest connections. This process leads to the replacement of a sparse matrix by a full matrix. The simultaneous modelling process forms transition between issues of the graph theory and the theory of metric spaces. The full matrix formed this way may lend itself to create the base of complete Hamilton cycles or other issues in transportation systems. An initial analysis of the stage-form algorithm proposed here indicates that it is comparable with known algorithms, and in some cases it works even faster. The next step in the subsequent study will consist in operations being reversed in comparison to the ones described above. Combining both procedures will allow for controlling the process of creating a minimal graph spanning all the shortest paths, and possibly creating a graph spanning paths, whose shortest connections differ from the shortest paths with pre-determined accuracy. The possibility of using the results for optimisation of transport in the dairy industry was shown.

Słowa kluczowe

PL

spójny graf nieskierowany; macierz odległości; macierz rzadka; optymalizacja; cykl Hamiltona

EN

connected undirected graph; distance matrix; optimization; sparse matrix; Hamiltonian cycle

• Wydawca: Sieć Badawcza Łukasiewicz - Poznański Instytut Technologiczny
• Czasopismo: Logistyka
• Rocznik: 2015
• Tom: nr 5
• Strony: 145--154, CD1
• Opis fizyczny: Bibliogr. 15 poz., tab.

Twórcy

autor

Ignaciuk S.

• Uniwersytet Przyrodniczy w Lublinie, Katedra Zastosowań Matematyki i Informatyki

autor

Wawrzosek J.

• Uniwersytet Przyrodniczy w Lublinie, Katedra Zastosowań Matematyki i Informatyki

autor

Kubera E.

• Uniwersytet Przyrodniczy w Lublinie, Katedra Zastosowań Matematyki i Informatyki

autor

Baryła-Paśnik M.

• Uniwersytet Przyrodniczy w Lublinie, Katedra Energetyki i Środków Transportu

autor

Piekarski W.

• Uniwersytet Przyrodniczy w Lublinie, Katedra Energetyki i Środków Transportu

Bibliografia

• 1. Baryła-Paśnik M., Piekarski W., Ignaciuk Sz., Piecak A., Wawrzosek J., Kuna-Broniowska I., 2014: Przegląd metod optymalizacji procesów transportowych w przemyśle rolno-spożywczym ze szczególnym uwzględnieniem przemysłu mleczarskiego. Logistyka 2014 nr 6 dodatek CD ROM nr 4, s. 12034-12039
• 2. Błażewicz J., Pesch E., Sterna M. 2000: The disjunctive graph machine representation of the job shop scheduling problem. European Journal of Operational Research, 127, 317–31.
• 3. Błażewicz J., Pesch E., Sterna M. 2005: A novel representation of graph structures in web mining and data analysis. Omega vol. 33, 65–71.
• 4. Cormen T.H., Leiserson C.E., Rivest R.L., Stein C. 2007: Wprowadzenie do algorytmów. WNT.
• 5. Dijkstra E.W. 1959: A note on two problems in connexion with graphs. In Numerische Mathematik, 1, 269–271.
• 6. Fronczak A., Fronczak P. 2009: Świat sieci złożonych : od fizyki do Internetu. Wydawnictwo Naukowe PWN, Warszawa.
• 7. Held M., Karp R.M. 1970: The traveling-salesman problem and minimum spanning trees, Operations Research 18, 1138-1162.
• 8. Held M., Karp R.M. 1971: The traveling-salesman problem and minimum spanning trees: part II. Mathematical Programming 1, 6-25.
• 9. Knasiecki M. 2005: Grafy i ich reprezentacje. http://www.algorytm.org/klasyczne/grafy-i-ich-reprezentacje.html
• 10. Kruskal J. B. 1956: On the shortest spanning subtree of a graph and the traveling salesman problem. In Proceedings of the American Mathematical Society, vol. 7, no. 1, 48-50.
• 11. Odrzywolek A. 2009: Aproksymacja funkcji wielu zmiennych. Instytut Fizyki UJ Kraków http://www.slideshare.net/VA00/aproksymacja-funkcji-wielu-zmiennych
• 12. Rydzak R. 2002: Sieciowe problemy optymalizacji. http://rydzak_ryszard.republika.pl/
• 13. Sikora W. (ed.) 2008: Badania operacyjne. PWE, Warszawa.
• 14. Trzaskalik T. 2008: Wprowadzenie do badań operacyjnych z komputerem. PWE, Warszawa.
• 15. Wilson R. J. 2012: Wprowadzenie do teorii grafów. Wydawnictwo Naukowe PWN, Warszawa