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

• Autorzy: Szymon Ignaciuk , Jacek Wawrzosek , Elżbieta Kubera , Małgorzata Baryła-Paśnik , Wiesław Piekarski

Warianty tytułu

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

• Języki publikacji: PL

Abstrakty

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 nieskierowanym 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 nadania 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 nieskierowane go (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 minimalnego 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.(abstrakt oryginalny)

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 t his 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 describ ing 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 transpor- tation 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 predetermined accuracy. The possibility of using the results for optimisation of transport in the dairy industry was shown.(original abstract)

Słowa kluczowe

PL

Algorytm transportowy; Modele transportowe; Organizacja transportu; Zarządzanie transportem; Transport; Macierze; Macierz wag; Normy macierzowe; Sieć drogowa; Optymalizacja; Sieci logistyczne

EN

Transport algorithm; Transport models; Organization of transport; Transport management; Transport; Matrix; Weight matrix; Matrix norms; Road network; Optimalization; Logistic networks

• Czasopismo: Logistyka
• Rocznik: 2015
• Numer: nr 5, CD 1
• Strony: 145--154

Twórcy

autor

Szymon Ignaciuk

• Uniwersytet Przyrodniczy w Lublinie

autor

Jacek Wawrzosek

• Uniwersytet Przyrodniczy w Lublinie

autor

Elżbieta Kubera

• Uniwersytet Przyrodniczy w Lublinie

autor

Małgorzata Baryła-Paśnik

• Uniwersytet Przyrodniczy w Lublinie

autor

Wiesław Piekarski

• Uniwersytet Przyrodniczy w Lublinie

Bibliografia

• 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 szcze-gólnym uwzględnieniem przemysłu mleczarskiego. Logistyka 2014 nr 6 dodatek CD ROM nr 4, s. 12034-12039
• 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.
• 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.
• Cormen T.H., Leiserson C.E., Rivest R.L., Stein C. 2007: Wprowadzenie do algorytmów. WNT.
• Dijkstra E.W. 1959: A note on two problems in connexion with graphs. In Numerische Mathematik, 1, 269-271.
• Fronczak A., Fronczak P. 2009: Świat sieci złożonych : od fizyki do Internetu. Wydawnictwo Nau-kowe PWN, Warszawa.
• Held M., Karp R.M. 1970: The traveling-salesman problem and minimum spanning trees, Operations Research 18, 1138-1162.
• Held M., Karp R.M. 1971: The traveling-salesman problem and minimum spanning trees: part II. Mathematical Programming 1, 6-25.
• Knasiecki M. 2005: Grafy i ich reprezentacje. http://www.algorytm.org/klasyczne/grafy-i-ich-repre-zentacje.html
• 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.
• Odrzywolek A. 2009: Aproksymacja funkcji wielu zmiennych. Instytut Fizyki UJ Kraków http://www.slideshare.net/VA00/aproksymacja-funkcji-wielu-zmiennych
• Rydzak R. 2002: Sieciowe problemy optymalizacji. http://rydzak_ryszard.republika.pl/
• Sikora W. (ed.) 2008: Badania operacyjne. PWE, Warszawa.
• Trzaskalik T. 2008: Wprowadzenie do badań operacyjnych z komputerem. PWE, Warszawa.
• Wilson R. J. 2012: Wprowadzenie do teorii grafów. Wydawnictwo Naukowe PWN, Warszawa