Wyniki wyszukiwania - BazTech

1

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

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

Logistyka

|

2015

|

nr 5

145--154, CD1

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.

2

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

Widuch J., Klyta A.

Studia Informatica

|

2014

|

Vol. 35, nr 1

29--55

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.

3

Polioptymalizacja transportu odpadów z wykorzystaniem planarnych, parametryzowanych grafów topologicznych

Gaska K., Generowicz A., Iwanicka Z., Kozioł M., Ścierski W., Landrat M.

Logistyka

|

2014

|

nr 6

3780--3792

PL

Zintegrowany system gospodarki odpadami stanowi złożony zbiór obiektów, procesów technologicznych, logistycznych i relacji zachodzących między nimi. Jednym z kluczowych elementów systemu są procesy transportu, determinujące m.in. przepływ strumieni odpadów ze źródeł ich powstawania do miejsc przetwarzania i unieszkodliwiania. Dynamika zmian w ruchu drogowym, w tym zróżnicowane technologie napędu i paliw oraz zmienność sytuacji w eksploatacji pojazdów powoduje wzrost kosztów, których znaczący udział w sumarycznych kosztach systemu gospodarki odpadami skłania do podjęcia działań optymalizacji szeregu parametrów determinujących wartości poszczególnych składników kosztów (stałych i zmiennych). Optymalizacja procesu transportu wymaga podejścia dualnego, wynikającego z ograniczenia kosztów procesów cząstkowych przy jednoczesnym spełnieniu wymagań w zakresie ochrony środowiska oraz bezpieczeństwa życia i zdrowia ludzi. Artykuł przedstawia metodologię optymalizacji procesów transportowych w zintegrowanych systemach gospodarki odpadami, z wykorzystaniem modelu komponentowego parametryzowanych grafów topologicznych.

EN

Integrated waste management system is a complex set of objects, technological processes logistics and relations between them. One of the crucial elements of the system are the processes of transport, determining among other the flow of waste streams from sources to destinations of their formation processing and disposal. Dynamics of changes in traffic, including different propulsion technologies and fuels, and the volatility of the situation in vehicle operating cost increases, the significant share of the aggregated costs of waste management system tends to take action to optimize a number of parameters that determine the value of the individual components of costs (fixed and variable). Optimization of the transport process requires a dual approach, resulting from the reduction of the cost of the partial processes while meeting the requirements of environmental protection and safety of human life and health. This article presents a methodology to optimize transport processes in integrated waste management systems using a model parameterized component topological graphs.

4

The maximum principle of Pontryagin in control of twolegged robot based on human walking system

Żur K. K.

International Journal of Applied Mechanics and Engineering

|

2014

|

Vol. 19, no. 2

407--417

EN

In the paper a hypothesis about state equations of human gait is presented. Instantaneous normalized power developed by human muscles at particular joints of a leg is a control vector in state equations of the human walking system. The maximum principle of Pontryagin in analysis of dynamic human knee joint was presented. The discrete Hamilton function of a knee joint is similar to a discrete square function of normalized power developed by muscles at the knee joint. The results satisfy optimal conditions and could be applied in control of exoskeleton and DAR type robot.

5

Deflection routing with Hamiltonian cycles

Szcześniak I.

Studia Informatica

|

2003

|

Vol. 24, nr 4

251-257

EN

For the mixed routing algorithm running on the networks with non buffering nodes this article presents an improvement in which an Eulerian cycle is replaced with Hamiltonian cycles. The new upper bound on a data packefs end to end number of hops is eąual to or lower than the original upper bound.

PL

W artykule proponuje się ulepszenie mieszanego algorytmu trasującego dla sieci z węzłami, które nie przechowują pakietów (ang. non-buffering nodes). Ulepszenie polega na wykorzystaniu cykli Hamiltona w zamian cyklu Eulera, co sprawia, że górna granica na liczbę skoków pakietu jest mniejsza od (albo w najbardziej niekorzystnym przypadku równa) górnej granicy przed wprowadzeniem ulepszenia.