Dołącz do Governautów, zarejestruj się
Załóż konto
Reklama

Drogi użytkowniku!
Wygląda na to, że używasz rozszerzenia blokującego reklamy.
W Governice nie stosujemy nachalnych reklam. Możesz bezpiecznie odblokować je na naszej stronie ;-)
Dział poświęcony jest zagadnieniom logistycznym, takim jak zarządzanie dostawą, dystrybucją, odzyskiem czy transportem. Odnaleźć można tutaj także informacje o certyfikatach w logistyce czy procesach logistycznych. Nie zabraknie również informacji o zasadach magazynowania i zarządzania magazynowaniem.
Problem marszrutyzacji
Problem marszrutyzacji - problem decyzyjny, związany z wyznaczeniem optymalnych tras przewozowych dla określonej liczby środków transportu, mających obsłużyć klientów, znajdujących się w różnych punktach.
Problem marszrutyzacji zaliczany jest do problemów NP-trudnych. Z tego względu zazwyczaj jest rozwiązywany przy pomocy metod heurystycznych. Algorytmy dokładne mogą być wykorzystywane tylko dla problemów o stosunkowo niewielkiej liczbie klientów (do 135)
Problem marszrutyzacji zaliczany jest do problemów NP-trudnych. Z tego względu zazwyczaj jest rozwiązywany przy pomocy metod heurystycznych. Algorytmy dokładne mogą być wykorzystywane tylko dla problemów o stosunkowo niewielkiej liczbie klientów (do 135)
Klasyczne ujęcie problemu
W klasycznym ujęciu problem sformułowany jest w postaci grafu nieskierowanego



Minimalizowana jest funkcja

gdzie:
r – pojazd należący do zbioru jednorodnych (identycznych) pojazdów R
f, g – wierzchołki pomiędzy, którymi odbywa się przewóz
Warunkami ograniczającymi są:
- Występowanie tylko jednej bazy początkowej i końcowej (miejsca, z którego pojazdy rozpoczynają/kończą przewóz), z której/do której wyjeżdża dokładnie jeden pojazd r. W przypadku wierzchołków pośrednich liczba pojazdów wjeżdżających jest równa liczbie pojazdów wyjeżdżających.
- :
– dla bazy początkowej - :
– dla bazy końcowej - :
– dla wierzchołków pośrednich - :: W przypadku, gdy istnieje połączenie pomiędzy punktami 0 oraz n+1 to dopuszczalne są puste drogi
- Przypisanie każdemu klientowi dokładnie jednego pojazdu, który zaspokaja jego zapotrzebowanie (dostawy są niedzielone).
- :
– warunek przypisania dokładnie jednego pojazdu - :
– warunek niedzielonych dostaw
Przykładowe rozwinięcia problemu
W rozwinięciach klasycznego problemu marszrutyzacji występować mogą dodatkowe ograniczenia. Przykładowo:- Warunek nieprzekroczenia pojemności poszczególnych środków transportu (problem CVRP).
- :
- :: gdzie
- ::
– popyt przypisany do danego klienta - ::
– pojemność pojazdów - Ograniczenia czasowe w problemach z oknami czasowymi (pojazd nie przybędzie do określonego wierzchołka przed wykonaniem poprzednich zadań w węzłach poprzedzających)
- :
- :: gdzie
- ::[[ Plik:Problem marszrutyzacji 9.1.png]] – czas rozpoczęcia obsługi klienta f
- ::
– czas przejazdu pomiędzy f, a g - ::
– czas rozpoczęcia obsługi klienta g
Bibliografia
- Problem marszrutyzacji, Wikipedia pl
ostatnia modyfikacja 30 listopada 2017 r.