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

Otwarto wystawę o ochronie zabytków kolejowych zorganizowaną przez PKP CARGO

Otwarto wystawę o ochronie zabytków kolejowych zorganizowaną przez PKP CARGO

W Senacie RP otwarto wystawę pt. „Ochrona Dziedzictwa Kolejowego w Polsce”. Wystawa prezentuje dorobek spółek...

Volvo Trucks wprowadza na rynek zintegrowany system informacji i rozrywki

Volvo Trucks wprowadza na rynek zintegrowany system informacji i rozrywki

Bardziej przyjemna i bezpieczniejsza jazda, łatwiejsze odnajdywanie drogi i sprawniejsze zarządzanie flotą. To główne zalety...

Reaktywowane PUTy znowu naprawiają tabor PKP CARGO

Reaktywowane PUTy znowu naprawiają tabor PKP CARGO

Przeznaczone do likwidacji przez poprzedni Zarząd PKP CARGO punkty utrzymania taboru (PUT) w Południowym Zakładzie...

Ostatnio na forum

Ogłoszenia

Brak aktywnych ogłoszeń.

 Instytut Logistyki i Magazynowania

Logowanie

LOGOWANIE

Rejestracja

Rejestracja użytkownika
lub Anuluj