Równoległy koewolucyjny algorytm memetyczny rozwiązywania problemów trasowania pojazdów z oknami czasowymi
Identyfikator grantu: PT00952
Kierownik projektu: Tomasz Jastrząb
Realizatorzy:
- Mirosław Błocho
- Jakub Nalepa
Politechnika Śląska
Wydział Automatyki, Elektroniki i Informatyki
Gliwice
Data otwarcia: 2022-02-21
Streszczenie projektu
Na podstawie dotychczasowych prac wykonawców projektu, opracowany zostanie nowy, równoległy, koewolucyjny algorytm memetyczny rozwiązywania problemów trasowania pojazdów z oknami czasowymi. Algorytm będzie ukierunkowany zarówno na problemy marszrutyzacji (ang. Vehicle Routing Problem with Time Windows, VRPTW), jak i problemy odbioru i dostawy (ang. Pickup and Delivery Problem with Time Windows, PDPTW). W ramach prowadzonych prac, przewidywane jest opracowanie m.in. nowych schematów kooperacji i migracji rozwiązań z uwzględnieniem wsparcia dla optymalizacji wielokryterialnej.
Celem projektu jest opracowanie algorytmu, który będzie w stanie osiągać wyniki co najmniej zbliżone do wyników światowych, a nawet poprawić wybrane wyniki dla znanych zbiorów benchmarkowych takich jak: zbiory Solomona lub Gehringa & Hombergera (dla problemów VRPTW) oraz zbiory Li & Lima (dla problemów PDPTW).
Złożoność problemów (zarówno problem VRPTW, jak i PDPTW jest problemem NP-trudnym), a także idea kooperacji między procesami działającymi niezależnie nad różnymi populacjami rozwiązań, uzasadnia potrzebę wykorzystania superkomputera. Opracowany w wyniku badań algorytm równoległy zostanie zaimplementowany w języku C/C++ z użyciem standardu MPI (Message Passing Interface).
Celem projektu jest opracowanie algorytmu, który będzie w stanie osiągać wyniki co najmniej zbliżone do wyników światowych, a nawet poprawić wybrane wyniki dla znanych zbiorów benchmarkowych takich jak: zbiory Solomona lub Gehringa & Hombergera (dla problemów VRPTW) oraz zbiory Li & Lima (dla problemów PDPTW).
Złożoność problemów (zarówno problem VRPTW, jak i PDPTW jest problemem NP-trudnym), a także idea kooperacji między procesami działającymi niezależnie nad różnymi populacjami rozwiązań, uzasadnia potrzebę wykorzystania superkomputera. Opracowany w wyniku badań algorytm równoległy zostanie zaimplementowany w języku C/C++ z użyciem standardu MPI (Message Passing Interface).
Publikacje
- M. Błocho, T. Jastrząb, J. Nalepa, A Parallel Cooperative Co-evolutionary Memetic Algorithm for Solving the VRPTW, International Conference on Computational Science (ICCS 2023) -, (2023) -
- M. Błocho, T. Jastrząb, J. Nalepa, Parallel Cooperative Memetic Co-evolution for VRPTW, GECCO '23 Companion: Proceedings of the Companion Conference on Genetic and Evolutionary Computation -, (2023) 53-54