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

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.