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. (...)

Newsletter

Z ostatniej chwili

  • 1
  • 2
  • 3

Świąteczny szczyt paczkowy

Świąteczny szczyt paczkowy

Na rynku kurierskim rozpoczął się świąteczny szczyt paczkowy. Rośnie liczba zamówień w sklepach internetowych i...

Nowe centrum logistyczne DSV w Pradze

Nowe centrum logistyczne DSV w Pradze

Pod koniec października br. DSV oficjalnie zainaugurowało nowy obiekt w Pradze o powierzchni 23 tys....

Firmy UPS i Sealed Air nawiązały współpracę w celu udostepnienia…

Firmy UPS i Sealed Air nawiązały współpracę w celu udostepnienia wydajnych rozwiązań do pakowania

Firmy UPS i Sealed Air Corporation poinformowały o nawiązaniu strategicznej współpracy, dzięki której sprzedawcy detaliczni,...

Ostatnio na forum

Ogłoszenia

Brak aktywnych ogłoszeń.

 Instytut Logistyki i Magazynowania

Logowanie

LOGOWANIE

Rejestracja

Rejestracja użytkownika
lub Anuluj