Sukces inżyniera oprogramowania ze Śląska :: Artykuły / Polski Serwis Naukowy

Polecamy również:

Optyczne rozwiązania problemów biomedycznych, Marsylia, Francja

"Myślenie na głos" pomaga rozwiązywać zadania z matematyki

PAN proponuje rozwiązania w sprawie tzw. dopalaczy

Rozwiązania na rzecz szybszego Internetu

NEMO odkrywa nowe rozwiązania biopaliwowe

W jaki sposób najefektywniej, czyli wykorzystując jak najmniejszą liczbą aut, wybierając najkrótsze drogi i w określonym czasie, dowieźć towar do 800 klientów? Najlepszą, jak dotychczas, odpowiedź na to pytanie znalazł Jakub Nalepa z Gliwic.

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 Nalepa - na co dzień pracujący 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.

"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" - zwrócił uwagę promotor Nalepy, prof. Zbigniew Czech z Politechniki Śląskiej.

"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" - dodał profesor.

Podobne zadanie wydaje się być proste przy założeniu, że klientów jest np. 10. Przeciętny komputer jest wówczas w stanie podać optymalny wynik w dwie sekundy. Ale już w przypadku 20 lokalizacji czas podania najlepszego rozwiązania zajmuje lata.

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 Nalepie udało się zminimalizować liczbę niezbędnych samochodów dostawczych do 73, a trasę, którą mają do przejechania zmniejszyć do 29,6 tys. km.

Nalepa mówi, że samo zrozumienie specyfiki problemu zajęło mu pół roku, kolejnych osiem miesięcy poświęcił na napisanie rozwiązania. "Wydaje mi się, że te algorytmy mają duży potencjał i że kolejne ulepszenia mogą dać w rezultacie kolejne światowe wyniki" - ocenił.

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

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. Czecha na Wydziale Automatyki, Elektroniki i Informatyki Politechniki Śląskiej. Teraz chce kontynuować pracę nad dalszym udoskonaleniem swojego algorytmu, co będzie stanowiło podstawę jego rozprawy doktorskiej.

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

PAP - Nauka w Polsce

kon/ agt/bsz

komentuj publikację

Czy wiesz że...?

wersja BETA

Twierdzenie o dualności rezultat przedstawiający cztery możliwości dotyczące istnienia rozwiązań optymalnych i dopuszczalnych problemu programowania liniowego w postaci standardowej. pełny tekst

Własność optymalnej podstruktury jest własnością problemów, które można rozwiązywać za pomocą algorytmów. Mówi się, że dany problem ma własność optymalnej podstruktury, jeżeli jego optymalne rozwiązanie jest funkcją optymalnych rozwiązań podproblemów. pełny tekst

Inżynieria oprogramowania dziedzina inżynierii systemów zajmująca się wszelkimi aspektami produkcji oprogramowania: od analizy i określenia wymagań, przez projektowanie i wdrożenie, aż do ewolucji gotowego oprogramowania. Podczas gdy informatyka zajmuje się teoretycznymi aspektami produkcji oprogramowania, inżynieria oprogramowania koncentruje się na stronie praktycznej. pełny tekst

Własność optymalnej podstruktury jest własnością problemów, które można rozwiązywać za pomocą algorytmów. Mówi się, że dany problem ma własność optymalnej podstruktury, jeżeli jego optymalne rozwiązanie jest funkcją optymalnych rozwiązań podproblemów. pełny tekst

Moduł "Czy wiesz że...?" (wersja testowa, beta): definicje/pojęcia wygenerowane w obrębie tego modułu pochodzą z Wikipedii i udostępniane są na licencji Creative Commons: uznanie autorstwa, na tych samych warunkach, z możliwością obowiązywania dodatkowych ograniczeń. Dostęp do pełnej wersji każdego hasła (oraz dokładnch informacji na temat licencji, autora oraz edycji) możliwy jest po kliknięciu w odnośnik opisany jako "pełny tekst".