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

Publikacje

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


← Powrót do spisu projektów

KONTAKT

Nasi konsultanci służą pomocą przyszłym i początkującym użytkownikom specjalistycznego oprogramowania zainstalowanego na Komputerach Dużej Mocy w Centrum Informatycznym TASK.

Kontakt w sprawach Komputerów Dużej Mocy, oprogramowania/licencji, grantów obliczeniowych, sprawozdań:

kdm@task.gda.pl

Administratorzy odpowiadają na maile w dni robocze w godzinach 8:00 – 15:00.