Logowanie do System sprawozdań KDM

Równoległy algorytm memetyczny dla rozwiązywania problemu odbioru i dostarczania towarów z oknami czasowymi

Kierownik projektu: Jakub Nalepa

Politechnika Śląska

Wydział AEiI, Instytut Informatyki

Gliwice

Streszczenie projektu

Głównym celem projektu jest opracowanie równoległego algorytmu memetycznego dla rozwiązywania NP-trudnego problemu odbioru i dostarczania towarów z oknami czasowymi (ang. pickup and delivery problem with time windows - PDPTW). W problemie PDPTW, towar musi zostać przewieziony pomiędzy klientami, z zachowaniem ograniczeń ładowności pojazdów oraz w określonych oknach czasowych. Minimalizacja liczby tras jest głównym kryterium optymalizacji rozwiązania, a kolejnym jest minimalizacja całkowitej długości tras. Ze względu na dużą złożoność obliczeniową algorytmów dokładnych dla rozwiązywania PDPTW, poszukuje się rozwiązań przybliżonych, których koszt jest bliski kosztowi rozwiązania optymalnego.

Algorytmy memetyczne są hybrydyzacją algorytmów ewolucyjnych, używanych do eksploracji przestrzeni rozwiązań, oraz algorytmów lokalnych ulepszeń, wykorzystywanych do jej eksploatacji. Mimo udowodnionej skuteczności w rozwiązywaniu złożonych problemów optymalizacyjnych, zastosowanie równoległych algorytmów memetycznych dla problemu PDPTW nie było do tej pory eksplorowane, a badacze skupiali się na algorytmach sekwencyjnych.

Równoległy algorytm memetyczny zostanie zaimplementowany w języku C/C++ z użyciem biblioteki Message Passing Interface oraz interfejsu OpenMP, i wykonany na klastrze obliczeniowym (Galera), co umożliwi dokładne zmierzenie jego wielkości charakterystycznych (takich jak przyspieszenie, efektywność itd.). Wyniki dla testów Li i Lima zostaną porównane z najlepszymi rozwiązaniami na świecie.

Praca stanowi kontynuację projektu realizowanego na klastrze Galera (CI TASK) - "Równoległy algorytm memetyczny rozwiązywania problemu marszrutowania pojazdów z oknami czasowymi".

Publikacje

  1. Mirosław Błocho, Jakub Nalepa, A Parallel Algorithm for Minimizing the Fleet Size in the Pickup and Delivery Problem with Time Windows, EuroMPI '15 Proceedings of the 22nd European MPI Users' Group Meeting, ACM -, (2015) 15:1-15:2
  2. Mirosław Błocho, Jakub Nalepa, Impact of Parallel Memetic Algorithm Parameters on Its Efficacy, 11th International Conference, Beyond Databases, Architectures, and Structures, BDAS 2015 -, (2015) 299-308
  3. Jakub Nalepa, Mirosław Błocho, A Parallel Algorithm with the Search Space Partition for the Pickup and Delivery with Time Windows, 2015 10th International Conference on P2P, Parallel, Grid, Cloud and Internet Computing (3PGCIC) -, (2015) 92 - 99
  4. Jakub Nalepa, Mirosław Błocho, Co-operation in the Parallel Memetic Algorithm, International Journal of Parallel Programming, Springer 43(5), (2015) 812-839

Centrum Informatyczne Trójmiejskiej Akademickiej Sieci Komputerowej
ul. G. Narutowicza 11/12, 80-233 Gdańsk   |   tel. 58-347-24-11
email: office@task.gda.pl   |   NIP: 584-020-35-93