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

Nowe wagony dla dywizji kolejowej OT Logistics poszerzą ofertę transportu…

Nowe wagony dla dywizji kolejowej OT Logistics poszerzą ofertę transportu produktów agro

Grupa Kapitałowa OT Logistics wydzierżawiła nowe wagony typu Tagnpps, które pozwolą spółce na uzupełnienie oferty...

Polskie MŚP współpracują z firmami logistycznymi, aby wzmacniać działalność eksportową…

Polskie MŚP współpracują z firmami logistycznymi, aby wzmacniać działalność eksportową

Wyniki badania, zaprezentowanego przez FedEx Express - spółkę zależną FedEx Corp. i największą na świecie...

DSV wyróżnione aż w trzech kategoriach Rankingu firm TSL

DSV wyróżnione aż w trzech kategoriach Rankingu firm TSL

W tegorocznym Rankingu firm TSL Grupa DSV uplasowała się w pierwszej dziesiątce największych polskich operatorów...

Ostatnio na forum

 Instytut Logistyki i Magazynowania

Logowanie

LOGOWANIE

Rejestracja

Rejestracja użytkownika
lub Anuluj