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

Amazon otworzy w Sosnowcu nowe centrum logistyki e-commerce

Amazon otworzy w Sosnowcu nowe centrum logistyki e-commerce

Amazon planuje otwarcie nowego centrum logistyki e-commerce w Sosnowcu. Zadaniem nowego centrum będzie wspieranie realizacji...

Ekol kontynuuje rozwój w Polsce

Ekol kontynuuje rozwój w Polsce

Ekol Logistics rozpoczął działalność w Polsce w maju 2015 r. i właśnie otworzył nowy magazyn...

PEKAES wzmacnia międzynarodową sieć połączeń

PEKAES wzmacnia międzynarodową sieć połączeń

Operator logistyczny PEKAES wprowadził regularne, bezpośrednie połączenie do Rumunii. Po Czechach, Słowacji i Niemczech to...

Ostatnio na forum

Ogłoszenia

Brak aktywnych ogłoszeń.

 Instytut Logistyki i Magazynowania

Logowanie

LOGOWANIE

Rejestracja

Rejestracja użytkownika
lub Anuluj