logistyka.net.pl - wortal logistyczny | logistyka | e-logistyka | TSL

PARTNER PORTALU:

A+ A A-

Algorytm wyznaczania wielo-towarowego maksymalnego przepływu w grafach skierowanych

Oceń ten artykuł
(0 głosów)
W pracy przedstawiono algorytm wyznaczania maksymalnego przepływu wielo-towarowego w oparciu o algorytm Dinica wyznaczania maksymalnego przepływu jedno-towarowego. Algorytmem Dinica wyznaczono ścieżki i płynące nimi strumienie miedzy każda parą s-t. Idea zaprezentowanego algorytmu polega na umożliwieniu przepływu towarów krawędziami wchodzącymi w skład wyznaczonych ścieżek w sposób zrównoważony. Ograniczeniu podlegają jedynie strumienie o największych wartościach.
1. WPROWADZENIE
Przepływ towarów, ludzi, kapitału i informacji oraz zarządzanie tymi strumieniami jest sednem zarządzania logistycznego w firmie. Wielo-towarowy przepływ towarów jest jednym z głównych problemów z obszaru zarządzania logistycznego.
Problem maksymalnego jednostrumieniowego przepływu w grafach skierowanych był badany przez Forda i Fulkersona, którzy oparli swój algorytm o tak zwane ścieżki powiększające strumień przepływający przez sieć, jednakże ich algorytm jest nieograniczony wielomianowo [1]. Dinic w swym algorytmie wyznaczał minimalne ścieżki powiększające i wprowadził pojęcie przepływu blokującego [2]. Algorytm Dinica działa w czasie O(mn2). Dla trzech i więcej towarów w grafach twierdzenie o maksymalnym przepływie i minimalnym przekroju traci swoją moc. Dla przepływu dwu-towarowego Hu przedstawił twierdzenie o maksymalnym przepływie i minimalnym przekroju [8], rozwiązanie dla problemu maksymalnego strumienia dwu-towarowego oparte o nową strategię zaprezentowano w [9].
Wielostrumieniowy przepływ w grafach polega na znalezieniu takiego strumienia wszystkich towarów w grafie, który zaspokaja zapotrzebowanie spływów na towary dostarczane ze źródeł w grafie skierowanym przy uwzględnieniu pojemności krawędzi grafów, przez które przepływa [10]. W przypadku, gdy krawędziom grafu przypisze się wagi reprezentujące koszt problem nie tylko będzie polegał na znalezieniu maksymalnych strumieni towarów w grafie, ale i na tym, aby koszt ich przesyłu był jak najmniejszy [5,6]. Problem równoległego przepływu (concurrent flow problem) jest wersją problemu wyznaczania maksymalnego przepływu wielo-towarowego (maximum multicommodity flow), którego celem jest znalezienie maksymalnej części z takiej, że przynajmniej z procent każdego zapotrzebowania
Di towaru i przy uwzględnieniu pojemności poszczególnych krawędzi przepływa przez sieć grafu [3,4]. Przepływający strumień w grafie może ulegać podziałowi lub też nie. (...)

Z ostatniej chwili

  • 1
  • 2
  • 3

Młodzi logistycy walczą o finał Ogólnopolskiej Olimpiady Logistycznej

Młodzi logistycy walczą o finał Ogólnopolskiej Olimpiady Logistycznej

2 grudnia w kilkunastu miastach w całej Polsce odbył się II etap Ogólnopolskiej Olimpiady Logistycznej....

PKP CARGO dzięki dronom odnotowuje coraz mniej kradzieży

PKP CARGO dzięki dronom odnotowuje coraz mniej kradzieży

PKP CARGO zaprezentowało efekty działań prewencyjnych i przeciw kradzieżowych ze wsparciem dronów. Dzięki ich zastosowaniu...

Analizy DHL umożliwiają lepsze zrozumienie sieci dostawcy

Analizy DHL umożliwiają lepsze zrozumienie sieci dostawcy

DHL poszerza swoje portfolio zarządzania łańcuchem dostaw i analizy poprzez uruchomienie Portalu Transparency DHL Resilience360....

Ostatnio na forum

 Instytut Logistyki i Magazynowania

Logowanie

LOGOWANIE

Rejestracja

Rejestracja użytkownika
lub Anuluj