4552034826

1. Wstęp

Problem marszrutyzacji - problem decyzyjny polegający na wyznaczeniu optymalnych tras przewozowych dla pewnej ściśle określonej ilości środków transportu, której zadaniem jest obsłużenie zbioru klientów znajdujących się w różnych punktach przy zachowaniu ograniczeń. Kryterium optymalizacji jest całkowity koszt transportu (wyrażony odległościowo, cenowo lub czasowo). Istnieją również rozwinięcia problemu uwzględniające więcej, niż jedno kryterium optymalizacji. Problem marszrutyzacji należy do podstawowej problematyki zarządzania operacyjnego flotą środków transportu (rzadziej zarządzania na wyższym szczeblu).

Poniższy rysunek jest graficznym przedstawieniem rozwiązaniem problemu:

2. Problem i analiza

Naszym zadaniem będzie wykonanie oprogramowania potrafiącego wyszukać możliwie najlepszego rozwiązania problemu marszrutyzacji. Danymi wejściowymi będzie zbiór punktów (miast) wraz z zaznaczonym punktem powrotu (magazynu) oraz liczba K, która odpowiada za maksymalną długość(w sensie ilości miast odwiedzanych) dla pojedynczej trasy. Ważną informacją jest, że graf złożony z miast jest grafem pełnym, czyli takim który pozwala nam połączyć każdy wierzchołek (miasto) z każdym innym.

Do rozwiązania tego problemu potrzebne jest wykorzystanie metod heurystycznych dlatego zdecydowaliśmy się na wykorzystanie algorytmu genetycznego, którego poddaliśmy pewnym modyfikacjom w celu zoptymalizowania czasu wyszukiwania rozwiązania.