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

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. (...)
Więcej w tej kategorii: « Logistyka zaopatrzenia w budownictwie Relacje między rachunkiem kosztów logistyki a benchmarkingiem »
Zaloguj się by skomentować