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

Rekordowe wakacje w PKP Intercity

Rekordowe wakacje w PKP Intercity

Od czerwca do końca sierpnia 2017 roku z usług PKP Intercity skorzystało o ponad 1,3...

W życie wchodzi CETA - umowa o wolnym handlu pomiędzy…

W życie wchodzi CETA - umowa o wolnym handlu pomiędzy Kanadą a Unią Europejską

Podpisana 30 października 2016 roku w Brukseli umowa o wolnym handlu pomiędzy Kanadą a Unią...

Dwuwymiarowy łańcuch dostaw, czyli jak wdrażać dyrektywę fałszywkową

Dwuwymiarowy łańcuch dostaw, czyli jak wdrażać dyrektywę fałszywkową

Instytut Logistyki i Magazynowania zaprasza 5.10.2017 r. na szkolenie pt. "Dwuwymiarowy łańcuch dostaw, czyli jak...

Ostatnio na forum

Ogłoszenia

menadżer zespołu w dziale handlowym

szukam pracowników

2017-09-22


specjalista ds. zakupów i sprzedaży

szukam pracowników

2017-09-22

 Instytut Logistyki i Magazynowania

Logowanie

LOGOWANIE

Rejestracja

Rejestracja użytkownika
lub Anuluj