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

Rekordowe wakacje w PKP Intercity

Rekordowe wakacje w PKP Intercity

Od czerwca do końca sierpnia 2017 roku z usług PKP Intercity skorzystało o ponad 1,3...

W życie wchodzi CETA - umowa o wolnym handlu pomiędzy…

W życie wchodzi CETA - umowa o wolnym handlu pomiędzy Kanadą a Unią Europejską

Podpisana 30 października 2016 roku w Brukseli umowa o wolnym handlu pomiędzy Kanadą a Unią...

Dwuwymiarowy łańcuch dostaw, czyli jak wdrażać dyrektywę fałszywkową

Dwuwymiarowy łańcuch dostaw, czyli jak wdrażać dyrektywę fałszywkową

Instytut Logistyki i Magazynowania zaprasza 5.10.2017 r. na szkolenie pt. "Dwuwymiarowy łańcuch dostaw, czyli jak...

Ostatnio na forum

Ogłoszenia

menadżer zespołu w dziale handlowym

szukam pracowników

2017-09-22


specjalista ds. zakupów i sprzedaży

szukam pracowników

2017-09-22

 Instytut Logistyki i Magazynowania

Logowanie

LOGOWANIE

Rejestracja

Rejestracja użytkownika
lub Anuluj