VRP Solver

Projekt akademicki rozwiązuje celowo rozbudowany problem trasowania pojazdów. Pięć magazynów, kilka typów pojazdów, punkty dostaw i odbiorów oraz trzy kategorie towarów tworzą przestrzeń rozwiązań, której nie da się praktycznie przeszukać metodą wyczerpującą.

Zamodelowałem domenę i zaimplementowałem w Pythonie autorski algorytm genetyczny, obejmujący reprezentację osobników, ocenę tras, obsługę ograniczeń, selekcję, krzyżowanie i mutację.

Każda trasa musi uwzględniać pojemność pojazdu i kategorie ładunku, a jednocześnie obsłużyć dostawy i odbiory. Pojazdy startują z losowo przypisanych magazynów, zapotrzebowanie powstaje na dwuwymiarowej mapie, a odebrane towary mogą trafić do kolejnych punktów lub wrócić do magazynu.

Solver opisuje lokalizacje za pomocą odległości euklidesowej i ocenia kandydatów na podstawie długości tras oraz kar za niepoprawne plany. Operatory ewolucyjne sprawdzają nowe kombinacje, zachowując wystarczająco dużo prawidłowej struktury, aby z czasem znajdować krótsze i wykonalne rozwiązania.

Aplikacja generuje zbliżone do optymalnych zestawy tras dla tworzonych scenariuszy i pozwala obserwować wpływ parametrów algorytmu na zbieżność, różnorodność populacji oraz jakość wyniku.

W metaheurystykach kluczowa jest dobra reprezentacja problemu. Ulepszanie funkcji dopasowania i zachowywanie wartościowych fragmentów tras często dawało więcej niż zwiększanie złożoności algorytmu. Projekt rozwinął moje rozumienie optymalizacji z wieloma powiązanymi ograniczeniami.