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

Nowa wersja Specyfikacji Ogólnych GS1

Nowa wersja Specyfikacji Ogólnych GS1

Pojawiła się nowa wersja Specyfikacji Ogólnych GS1. To już siedemnasta odsłona dokumentu, który zawiera techniczne...

Polski transport zadłużony

Polski transport zadłużony

Krajowy Rejestr Długów Biura Informacji Gospodarczej SA opublikował raport dotyczący  finansów  polskiego transportu. Sytuacja jest...

FedEx wraz UEFA for Children stworzyły dziecięcą eskortę na mecz…

FedEx wraz UEFA for Children stworzyły dziecięcą eskortę na mecz finałowy Ligi Europy UEFA

FedEx Express, firma świadcząca usługi przewozów ekspresowych, wraz z Fundacją UEFA for Children i szwedzkimi...

Ostatnio na forum

Ogłoszenia

Brak aktywnych ogłoszeń.

 Instytut Logistyki i Magazynowania

Logowanie

LOGOWANIE

Rejestracja

Rejestracja użytkownika
lub Anuluj