1 Wyższa Szkoła Informatyki i Zarządzania w Bielsku-Białej Wydział Informatyki Kierunek studiów : Informatyka Specjalność : Systemy informatyczne Praca dyplomowa inżynierska : Optymalizacja dostaw towarów za pomocą algorytmu pszczelego Dyplomant : Artur Kurstak Nr albumu : 3025 Promotor : prof. nadzw. dr hab. inż. Konrad Wala Bielsko-Biała, 2011

2  Celem pracy jest stworzenie programu komputerowego który ma na celu wyznaczanie optymalnych lub przybliżonych tras dostaw dla firmy transportowej która zatrudnia pewna liczbę dostawców oraz współpracuje z firmami wielodziałowymi rozproszonymi w całym obsługiwanym regionie. Dodatkowo program ten powinien mieć możliwość wprowadzania ilości firm oraz oddziałów tych firm, powinien również generować wykres przedstawiający wyznaczone trasy. Dzięki takiemu narzędziu pracownicy firmy będą o wiele szybciej dostarczać towary.

3  System informatyczny bazujący na algorytmie pszczelim wyznacza w akceptowalnym czasie wystarczająco tanie trasy rozwożenia towarów. Program ten oszczędza czas który jest potrzebny na dostarczenie towarów, ma to wpływ na poprawę jakości usług świadczonych przez firmę. Przez skrócenie czasu dostaw towarów firma może dostarczyć więcej przesyłek.

4  Program C++ Builder 6 Personal to środowisko programistyczne umożliwiające bardzo szybkie stworzenie aplikacji zarówno konsolowych jak również okienkowych dla platform Microsoft Windows (98, 2000, 2003, XP, Vista oraz Windows 7). Językiem programowania, jak sama nazwa mówi, jest C++. Program zawiera bardzo wiele komponentów stworzonych już do naszego wykorzystania, które bardzo ułatwiają prace nad tworzeniem nowych projektów. Dodatkowym atutem programu jest możliwość tworzenia i dodawania własnych komponentów.

5  Algorytmy konstrukcyjne – ich nazwa wzięła się od przeznaczenia algorytmów, służą one do konstruowania rozwiązań dla iteracyjnego poprawiania rozwiązań. Głównym zadaniem algorytmu konstrukcyjnego to znalezienie najlepszego rozwiązania problemu w czasie wielomianowym. Natomiast wiele mniejszą uwagę zwraca się na jakość znalezionych rozwiązań.

6  Metaheurystkę i algorytm pszczeli (ang. Artificial Bee Colony Algorithm) opracował doktorant – Afshin Ghanbarzadeh oraz jego współpracownicy, jest on inspirowany naturą. Został zaimplementowano poprzez obserwacje poszukiwania pożywienia przez pszczoły. Pszczoły wykształciły techniki np. „taniec pszczół” (and. waggle dance) który to usprawnia technikę komunikacyjną z innymi pszczołami na temat gdzie znajdują się oraz jak duże są to źródła pożywienia. Algorytm ten ma wyznaczyć rozwiązanie przybliżone w postaci m tras rozwożenia towaru.

7  n – liczba pszczół zwiadowców,  m – liczba wybranych lokalizacji z n odwiedzonych przez zwiadowców,  e – liczba najlepszych (elitarnych) lokalizacji wybranych z m  nep – liczba pszczół rekrutowanych dla e najlepszych lokalizacji,  nsp – liczba pszczół rekrutowana dla pozostałych (m-e) wybranych lokalizacji,

8  Program zawiera algorytm który generuje początkową populacje. Dane wejściowe będą obrazować konkretny przykład problemu do rozwiązania (przydatne będzie to do numerycznego badania). Liczba firm, miast, pododdziałów oraz odległości będą ustalane przez użytkownika(dane opisujące są typu integer). Program daje również możliwość ustawienia parametrów algorytmu optymalizującego.

9

10

11  Biblioteka vcl – (ang VCL- Visual Component Library ) – jest to biblioteka komponentów, wykorzystywana jest jako „magazyn” w tworzeniu aplikacji. Stworzone komponenty odpowiadają w niej różnym obiektom programu(chodzi tutaj o menu, przyciski, obrazki itp.) Stworzone komponenty dzięki tej bibliotece zawierają w sobie dużą ilość kodu dzięki temu użytkownik nie musi programować tak dużo żeby stworzyć podstawowe funkcje programu.

12

13

14

15  T.H. Cormen, C.E. Leiserson, R. L. Rivest. “Wprowadzenie do algorytmów” WNT, Warszawa 1997.  D. T. Pham, Ghanbarzadeh A, Koc E, Otri S, Rahim S and Zaidi M. The Bees Algorithm. Technical Note, Manufacturing Engineering Centre, Cardiff University, UK, 2005  Jerzy Gebosz “Symfonia Programowanie w języku C++ orientowane obiektowo“ wydawnictwo Edition2000, 2001  Sanjoy Dasgupta „Algorytmy” wydawnictwo PWN, 2006  Ewa Krok, Zbigniew Stępnakowski „Podstawy algorytmów. Schematy blokowe” Difin,2008

16  Celem pracy było stworzenie systemu komputerowego który będzie w akceptowalnym czasie wyznaczał optymalną drogę komiwojażera. Celem stworzenia takiej aplikacji była pomoc w szybszym dostarczaniu towarów co miało usprawnić działanie firmy transportowej.   Testowanie programu pokazuje że większa ilość iteracji daje lepsze rozwiązania.   Dzięki zastosowanemu algorytmowi pszczelemu praca może być wykorzystywana w celach dydaktycznych.