Trasowanie i optymalizacja tras w dystrybucji - cz. 2
- Jacek Sukany, Radosław Stefaniak
- Kategoria: Logistyka
Artykuł wyróżniony w IV edycji konkursu "Piórem logistyka".
Narzędzie
Przedstawiony wcześniej algorytm genetyczny został zaimplementowany w aplikacji napisanej w LCS, dzięki której korzystanie z algorytmu stało się prostsze.
Przedstawiony wcześniej algorytm genetyczny został zaimplementowany w aplikacji napisanej w LCS, dzięki której korzystanie z algorytmu stało się prostsze.
Do aplikacji wprowadzane są dane o miejscach (adresy odbiorców, ilość towaru). Oczywiście algorytm potrzebuje również danych o zasobach, z których może korzystać podczas wyznaczania tras. Podawane są zatem również dane o dostępnych autach wraz z ich ładownościami.
Pierwszym etapem, który realizuje algorytm jest stworzenie zestawu danych, łatwiejszego do analizy dla algorytmu, czyli przypisaniu każdemu z miejsc odległości od miejsca początkowego (lokalizacja magazynu) i czasu potrzebnego na dojazd. Tworzone są również kombinacje miejscowości (miejscowość „od” i miejscowość „do”), dla których również są podawane odległości i czasy przejazdu. Mając już taki zestaw danych, możliwe jest rozpoczęcie pracy przez algorytm genetyczny.
Schemat pracy aplikacji został przedstawiony na poniższym rysunku.
Źródło: Opracowanie własne
Wynikiem pracy jest arkusz wypełniony reprezentacją lokalizacji (adresów odbiorców). To znaczy podane są w szeregu kody pocztowe albo nazwy miast dla danej trasy, na przykład:
Samochód 1; Paweł; 5:29; 342 km
MAGAZYN => PIEKARY ŚLĄSKIE => BYTOM => GLIWICE => RYBNIK => WODZISŁAW ŚL. => JASIENICA => MAGAZYN
Samochód 2; Staszek; 7:39; 326 km
MAGAZYN => KRAKÓW => KIELCE => TARNÓW => MAGAZYN
W czasie swojej pracy algorytm generuje zestaw rozwiązań początkowych nazywanych populacją zerową. Na ich bazie działają operatory genetyczne takie jak selekcja, krzyżowanie, mutacja i reprodukcja. Działanie operatorów uzależnione jest od funkcji przystosowania. Funkcja ta określa dopasowanie rozwiązań do problemu ze względu na zmienną, która ma podlegać optymalizacji. Na jej podstawie przy wykorzystaniu generatora liczb losowych wybierane są najlepsze rozwiązania, na których działa algorytm genetyczny. Wybór rozwiązań w celu przeprowadzenia na nich dalszych operacji jest nazywany selekcją.
Ostatnio zmieniany w poniedziałek, 12 czerwiec 2006 15:08
Ściągnij załącznik:
Zaloguj się by skomentować