Równoległy koewolucyjny algorytm memetyczny rozwiązywania problemów trasowania pojazdów z oknami czasowymi

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).


← Powrót do spisu projektów

CONTACT

Our consultants help future and novice users of specialized software installed on High Performance Computers (KDM) at the TASK IT Center.

Contact for High Performance Computers, software / licenses, computing grants, reports:

kdm@task.gda.pl

Administrators reply to e-mails on working days between 8:00 am – 3:00 pm.