Wydział Automatyki, Elektroniki i Informatyki

24-letni absolwent Politechniki Śląskiej okazał się najlepszy w międzynarodowej rywalizacji dla algorytmików w ramach projektu norweskiej organizacji SINTEF. W swojej pracy magisterskiej Jakub Nalepa - na co dzień pracujący jako Software Engineer w firmie technologicznej Future Processing - opracował równoległy algorytm i osiągnął najlepszy wynik w rozwiązaniu opisanego problemu. Poprawił dotychczasowy rekord dla jednej z instancji problemów testowych o 30 proc.

Jak najefektywniej, tj. najmniejszą liczbą aut, wybierając najkrótsze drogi i w określonym czasie, dowieźć towar do 800 klientów? 24-letni Jakub Nalepa z Gliwic, absolwent Politechniki Śląskiej, na co dzień pracujący w firmie technologicznej Future Processing znalazł najlepszą jak dotychczas odpowiedź na to pytanie. W ramach pracy magisterskiej Nalepa opracował równoległy algorytm
i osiągnął najlepszy wynik w rozwiązaniu opisanego powyżej problemu.

Zadanie wydaje się być proste przy założeniu, że klientów jest 10. Przeciętny komputer jest wówczas w stanie podać optymalny wynik w ok. 2 sekundy. Ale już w przypadku 20 lokalizacji czas podania najlepszego rozwiązania to rząd wielu lat.

- Problem trasowania pojazdów z oknami czasowymi jest obecny w wielu aspektach codziennego życia: planujemy rozkład jazdy autobusów miejskich, czy dostarczenie produktów od producenta do klientów – mówi prof. dr hab. inż. Zbigniew Czech z Politechniki Śląskiej, promotor Jakuba Nalepy – Zminimalizowanie liczby pojazdów implikuje redukcję liczby zatrudnionych kierowców. Dzięki temu można znacznie obniżyć koszty utrzymania floty. Przy aktualnych cenach benzyny, równie ważne staje się zmniejszenie przebytej trasy. Problem trasowania ma duże znaczenie strategiczne i finansowe dla każdego z nas.

Do rozwiązania problemu Nalepa stworzył dwustopniowy algorytm. Najpierw, za pomocą algorytmu heurystycznego zminimalizował liczbę samochodów. Potem, posługując się algorytmem memetycznym, zoptymalizował trasę. Dla jednego z wariantów problemu, oznaczonego kryptonimem c1_8_2, Jakubowi Nalepie udało się zminimalizować liczbę niezbędnych samochodów dostawczych do 73, a trasę, którą mają do przejechania zmniejszyć do 29.589,70 km.

- Samo zrozumienie specyfiki problemu zajęło mi sześć miesięcy, a kolejne osiem poświęciłem
na napisanie rozwiązania, które stworzyłem, używając interfejsu OpenMP dla programu napisanego w C++ - mówi Jakub Nalepa - Wydaje mi się, że te algorytmy mają duży potencjał
i że kolejne ulepszenia mogą dać w rezultacie kolejne światowe wyniki.

Testowanie opracowanych przez Nalepę rozwiązań wymagało zaangażowania polskiego superkomputera Galera, który mieści się w Gdańsku. W roku 2010 komputer zajmował 297. miejsce na liście 500 najszybszych komputerów świata (lista: http://www.top500.org/). Galera składa się z 1344 procesorów czterordzeniowych i ma wydajność ok. 50 TeraFLOPS, co oznacza, że potrafi wykonać 50 bilionów operacji zmiennoprzecinkowych w ciągu sekundy.

Swoim rozwiązaniem Nalepa poprawił światowy wynik dla jednej z instancji problemów testowych wymyślonych przez Gehringa i Hombergera. Najlepsze rozwiązania na świecie publikowane
są na stronie największej w Skandynawii niezależnej organizacji badawczej SINTEF – tam też znalazło się rozwiązanie Nalepy.

- Mam nadzieję, że będę dalej współpracował z Jakubem - mówi prof. dr hab. inż. Zbigniew Czech
z Politechniki Śląskiej - Uważam, że ma duży potencjał i wielki zapał do pracy.

Prof. dr hab. inż. Zbigniew Czech w swojej pracy naukowej skupia się na programowaniu równoległym, algorytmach heurystycznych, haszowaniu doskonałym, algorytmach ewolucyjnych.

Algorytmy są również pasją 24-letniego Jakuba Nalepy.

- Programowaniem równoległym (OpenMP, MPI) zainteresowałem się trzy lata temu. Podczas wymiany studenckiej w ramach programu Erasmus, miałem okazję pracować w Szwecji,
w Linköping, na superkomputerze Neolith, który w 2007 roku został sklasyfikowany na 23. miejscu listy najszybszych superkomputerów na świecie – dodaje Jakub Nalepa.

Nalepa ukończył studia ze średnią 4,74 i 13 września 2011 r. obronił z wynikiem bardzo dobrym z wyróżnieniem pracę magisterską pod kierunkiem prof. dr hab. inż. Zbigniewa Czecha na Wydziale Automatyki, Elektroniki i Informatyki Politechniki Śląskiej. Po osiągnięciu tego ważnego sukcesu planuje kontynuować pracę nad dalszym udoskonaleniem swojego algorytmu, co będzie stanowiło podstawę jego rozprawy doktorskiej.

Dzięki unikalnej kulturze organizacyjnej Future Processing, Jakub Nalepa pogodził z sukcesem pracę nad algorytmem z obowiązkami zawodowymi. Obecnie pracuje w Future Processing nad systemem obrazowania medycznego, statystyczną analizą obrazów medycznych oraz wyekstrahowanych z nich cech w systemie wspomagającym diagnostykę nowotworową.

Nalepa jest zauroczony Skandynawią, lubi tenis stołowy, siatkówkę, pływanie i chodzenie po górach. Lubi muzykę rockową lat 60. i 70., od wczesnego Pink Floyd, Black Sabbath, King Crimson aż po mniej znany brytyjski Arzachel.

Jego motto to: "The game is over for software that is written only for a single processor" - Robert Crooke, Intel.

* * *

Future Processing

Powstała w 2000 r. firma Future Processing zajmuje się tworzeniem wyspecjalizowanego oprogramowania komputerowego na potrzeby międzynarodowego handlu, przemysłu i usług. Początkowo działalność firmy była związana z rynkiem komputerowej wizji w zastosowaniach medycznych i systemach bezpieczeństwa. W 2007 roku rozpoczęły się projekty dla rynku usług finansowych i transportowych.

Od samego początku swego istnienia Future Processing współpracuje z Politechniką Śląską w Gliwicach w zakresie rozwoju, badań i edukacji. Obecnie firma zatrudnia ponad 300 osób i posiada biura w Bytomiu, Gliwicach i Opolu.

W czerwcu br. został ukończony pierwszy etap budowy parku technologicznego FPark w Gliwicach, należącego do firmy.

Future Processing jest od 2007 r. Certyfikowanym Partnerem Microsoftu. Firma posiada również certyfikat ISO 9001 : 2000.

Dodatkowych informacji udziela:

Jarosław Kacprzak

PR Manager

Future Processing Sp. z o.o.

tel. kom.: +48 501 361 021

e-mail: jkacprzak@future-processing.com