logistyka.net.pl - wortal logistyczny | logistyka | e-logistyka | TSL

PARTNER PORTALU:

A+ A A-

Algorytm klasteryzacji w zastosowaniu do problemu trasowania pojazdów

Oceń ten artykuł
(0 głosów)
W artykule scharakteryzowano problematykę klasteryzacji punktów obsługi dla problemu trasowania pojazdów. Przybliżono wybrane metody klasteryzacji opisywane w literaturze przedmiotu. Zaproponowano algorytm klasteryzacji punktów obsługi zmniejszający złożoność obliczeniową problemu trasowania pojazdów.
1. WPROWADZENIE
Problem trasowania pojazdów (ang. Vehicle routing problem VRP) jest rozwinięciem jednego z najstarszych problemów optymalizacyjnych na sieciach - problemu komiwojażera (ang. Traveling Salesman Problem TSP), który polega na odwiedzeniu dokładnie jeden raz każdej z wybranych miejscowości i powrocie do miejscowości, z której rozpoczęto podróż
[7]. Znane są koszty przejazdu miedzy każdą parą miejscowości. Należy zaplanować komiwojażerowi drogę przejazdu w taki sposób, aby mógł on odwiedzić każdą miejscowość dokładnie jeden raz i całkowity koszt podróży był możliwie najmniejszy. W najprostszej formie problem trasowania pojazdów różni się od problemu komiwojażera dodatkowymi ograniczeniami związanymi z liczbą oraz ładownością pojazdów [1].
Problem trasowania pojazdów podobnie jak problem komiwojażera jest zagadnieniem
NP-trudnym, tzn. nie istnieją dla tego zagadnienia algorytmy dokładne rozwiązujące ten problem w czasie zależącym wielomianowo od liczby analizowanych danych. Dowód Nptrudności problemu trasowania pojazdów znaleźć można w pracy [9]. Złożoność problemu trasowania pojazdów jest rzędu O(n-1!) przy czym n oznacza liczbę punktów, jakie należy odwiedzić. Czas trwania obliczeń rośnie wykładniczo względem liczby danych (w tym przypadku względem liczby odwiedzanych punktów, miast). Przykładowo, dla przypadku z 15 miastami liczba możliwych kombinacji trasy przejazdu wyniesie 87.178.291.200, a już dla 20 miast liczba ta wzrośnie prawie 1,4 miliona razy do wartości 1,21645*1017. Dla komputera wykonującego milion operacji w ciągu sekundy czas trwania obliczeń dla 20 miast wyniesie prawie 4 tysiące lat.
W związku z dość długim czasem trwania obliczeń naukowcy skupiają się na poszukiwaniu algorytmów przybliżonych (heurystycznych), które dostarczałyby zadowalająco dobrych wyników w akceptowalnym czasie. Jednym ze sposobów osiągnięcia tego celu jest zmniejszenie złożoności rozpatrywanego przypadku problemu trasowania pojazdów. W literaturze cel ten osiągany jest poprzez stosowanie tzw. metod dwufazowych: najpierw klaster potem trasa (ang. cluster first/route second), najpierw trasa, potem klaster (ang. (...)

Z ostatniej chwili

  • 1
  • 2
  • 3

Efektywna logistyka, bezpieczny łańcuch dostaw - czyli etykieta logistyczna w…

Efektywna logistyka, bezpieczny łańcuch dostaw - czyli etykieta logistyczna w praktyce

Fundacja GS1 Polska serdecznie zaprasza do udziału w wyjątkowym szkoleniu, którego celem jest przekazanie wiedzy...

Sektor logistyczny optymistycznie patrzy w przyszłość - wyniki raportu CBRE…

Sektor logistyczny optymistycznie patrzy w przyszłość - wyniki raportu CBRE i Panattoni Europe

Rynek powierzchni przemysłowo-logistycznych w Polsce rozwija się dynamicznie od kilkunastu lat. CBRE i Panattoni Europe,...

Cross-border e-commerce: Raport Arvato o płatnościach

Cross-border e-commerce: Raport Arvato o płatnościach

Jeden z wiodących dostawców usług dla branży e-commerce, Arvato, przygotował rzetelny raport z rynków zagranicznych...

Ostatnio na forum

Ogłoszenia

Brak aktywnych ogłoszeń.

 Instytut Logistyki i Magazynowania

Logowanie

LOGOWANIE

Rejestracja

Rejestracja użytkownika
lub Anuluj