6570141625

2. Definicja dziedziny

Dystrybucja dóbr (transport) polega na obsłudze w określonym czasie grupy klientów przez grupę pojazdów, które są przypisane do jednego lub więcej ośrodków zwanych dalej HUB-ami (cetnrum dystrybucji, magazyn - ogólnie punkt startowy) i obsługiwane przez załogę (lub jednego kierowcę). Pojazdy poruszają się po sieci ścieżek komunikacyjnych (drogi, linie kolejowe, drogi rzeczne, morskie oraz połączenia powietrzne). Problem dystrybucji inaczej nazywany jest problemem marszrutyzacji, w skrócie PM.

2.1.    Grafy - podstawowe definicje

Graf jest podstawową strukturą wykorzystywaną do abstrakcji sieci komunikacyjnej. Graf G jest opisany jako para (V, E), gdzie Ustanowi zbiór wierzchołków grafu G, natomiast E jest zbiorem dwuargumentowych relacji, zwanych dalej krawędziami, grafu G. Istnieją dwa typy grafów ze względu na typ krawędzi: skierowane oraz nieskierowane. W grafie skierowanym rozróżniana jest kolejność wierzchołków w relacji, tj. krawędzie (i,y) =£ (/, i) gdzie i,j E V. W grafie nieskierowanym G, zbiór krawędzi Ustanowi zbiór nieuporządkowanych par krawędzi, tj. krawędzie (£,_/) = (/, i) Vi,j 6 V. Każdy wierzchołek może mieć przypisaną wagę (koszt), definiowaną jako funkcja w(t) ER i E V. Droga lub ścieżka z wierzchołka u do wierzchołka u' w grafie jest ciągiem wierzchołków [v₀, ...v_n}:u = v₀ A u' = v_n, lub inaczej ciągiem krawędzi {(vo,Vi), (fi, v₂),..., (v_n-i,v_n)}. Długość ścieżki l({v₀,... v_n]) stanowi liczbę jej krawędzi, koszt ścieżki c({v₀,... v_n}) stanowi sumę wag krawędzi, z których jest złożona ścieżka. W ścieżce prostej nie ma powtarzających się wierzchołków. Cykl prosty to droga zamknięta, tj. pierwszy wierzchołek stanowi jednocześnie ostatni wierzchołek. Cykl Hamiltona to cykl prosty, zawierający każdy wierzchołek ze zbioru V. Grafy mogą zostać sklasyfikowane jako proste oraz jako zupełne. Graf prosty nie zawiera pętli własnych (krawędzi łączących wierzchołek z nim samym) ani krawędzi wielokrotnych (wielu krawędzi łączących dwa te same wierzchołki). Graf zupełny jest grafem prostym, w którym dla każdej pary węzłów istnieje krawędź je łącząca.

2.2.    Reprezentacja sieci komunikacyjnej

Sieć dróg komunikacyjnych jest reprezentowana za pomocą grafu, w którym krawędzie stanowią drogi, a wierzchołki skrzyżowania oraz lokacje klientów i ośrodków. Graf może być skierowany bądź nieskierowany w zależności od tego, czy drogi reprezentowane przez krawędzie da się przebyć w obie strony (drogi dwukierunkowe) czy tylko w jedną (drogi jednokierunkowe).

8