Application of Genetic Algorithms in Logistics

• Autorzy: Wiktorzak A. , Sawicki A. , Malenko N.

Warianty tytułu

PL

Zastosowanie algorytmów genetycznych w logistyce

• Języki publikacji: EN

Abstrakty

EN

The paper presents the problem of determining the optimum route between distribution centres. If a company owns just one distribution centre where from it delivers goods to the market, the establishment of the optimum plan is connected with finding the shortest possible way of delivery to the particular customers. However, if there are more such centres and they are distant from one another, the logistic operator does not only have to establish which distribution centre has to supply goods to a particular customer but also set the order of visiting these centres in such a way that transportation costs are the lowest and the level of supplies in the centres is sufficient. For the solution of the problem genetic algorithms have been used. Genetic algorithms are universal optimizing searching and learning tools which allow for the obtaining of the optimum results by appropriately chosen parameters. New techniques and concepts extending the notion of simple genetic algorithm as, for instance, encoding (adjacency, ordinal and path representations) allow for the adjustment of the algorithm to the requirements of a certain task. Only one issue connected with a travelling salesman has been described and just the forms of encoding of chromosomes have been presented. It is necessary to emphasize quite strongly that the task also requires solutions in reference to the chromosome selection and the proper methods of either crossover or mutation. The authors of the paper consider the possibility of genetic algorithm application to the extended task of Travelling Salesman Problem.

PL

W pracy przedstawiono problem wyznaczania optymalnej trasy pomiędzy centrami dystrybucji. W sytuacji, gdy przedsiębiorstwo posiada tylko jedno centrum dystrybucyjne, z którego dostarcza towary na rynek, wyznaczenie optymalnego planu przewozów wiąże się ze znalezieniem najkrótszej drogi pomiędzy poszczególnymi nabywcami towaru. Jeżeli natomiast takich baz, zlokalizowanych w różnych miejscach, jest więcej, celem jest ustalenie, z którego centrum dystrybucyjnego ma być zaopatrywany w towar dany odbiorca i w jakiej kolejności mają być oni „odwiedzani”, tak aby koszty transportu towaru były jak najmniejsze, przy jednoczesnym uwzględnieniu zasobu dysponowanego przez centra dystrybucyjne towarów. Do rozwiązania tego zagadnienia wykorzystano algorytmy genetyczne. Algorytmy genetyczne to uniwersalne narzędzia optymalizujące, przeszukujące i uczące, które przy zastosowaniu odpowiednio dobranych parametrów pozwalają na otrzymanie optymalnych wyników. Nowe techniki i koncepcję rozszerzające pojęcie prostego algorytmu genetycznego, jak chociażby przytoczone w artykule kodowanie (reprezentacja przyległościowa, porządkowa, ścieżkowa) pozwalają na dopasowanie algorytmu do potrzeb konkretnego zadania. W artykule opisano tylko jedno zagadnienie związane z zadaniem komiwojażera, przestawiono jedynie różne formy kodowania chromosomów. Należy tu wyraźnie podkreślić, że zadanie wymaga również rozwiązań w zakresie selekcji chromosomów, doboru metody krzyżowania czy mutacji. Autorzy pracy rozważają wykorzystanie algorytmu genetycznego dla rozszerzonego problemu komiwojażera.

Słowa kluczowe

EN

genetic algorithms; logistics; distribution centers

PL

algorytmy genetyczne; logistyka; centra dystrybucji

• Wydawca: Sieć Badawcza Łukasiewicz - Poznański Instytut Technologiczny
• Czasopismo: Logistyka
• Rocznik: 2014
• Tom: nr 4
• Strony: 4126--4133
• Opis fizyczny: Bibliogr. 20 poz., rys., pełen tekst na CD

Twórcy

autor

Wiktorzak A.

• The State Higher School of Computer Science and Business Administration in Lomza

autor

Sawicki A.

• The State Higher School of Computer Science and Business Administration in Lomza

autor

Malenko N.

• The State Higher School of Computer Science and Business Administration in Lomza

Bibliografia

• [1] Arabas J., Wykłady z algorytmów ewolucyjnych. Warszawa,WNT, 2001.
• [2] Cormen T. H., Leiserson C. E., Riverst R. L., Wprowadzenie do algorytmów.Warszawa WNT, 2002.
• [3] DeJong K. A., An Analysis of the Behavior of Class of Genetic Adaptive Systems, University of Michigan, 2010.
• [4] Freisieben B., Merz P., New Genet in Local Search Operator for Travelling salesman Problem, Conference on Parallel Problem Solving From nature, app. 890-899, 1996.
• [5] Goldberg D. E., Algorytmy genetyczne i ich zastosowania. Warszawa, WNT, 1998.
• [6] Goldberg D. E., Genetic Algorithms in Search, Optimization, and Machine Learning, MA: Addison-Wesley, 2000.
• [7] Jacyna M., Jachimowski R., Pryciński P., Wspomaganie komputerowe wyznaczania optymalnych tras w wielo¬szczeblowym systemie dystrybucji. Wybrane Zagadnienia Logistyki Stosowanej. Wydawnictwa AGH, Kraków, 2009.
• [8] Larranaga P., Kuijpers C.M.H., Murga R.H., Inza I, Dizdarevic S., Genetic algorithms for the travelling salesman problem: A review of representation. 1999.
• [9] Michalewicz Z., Algorytmy genetyczne + struktury danych = programowanie Ewolucyjne. Wydanie III, Warsza¬wa, WNT, 2003.
• [10] Michlowicz E., Optymalizacja zadań operatora logistycznego. Logistyka nr 3/2009.
• [11] Michlowicz E., Transportation − Production Task Pertaining to Waste Disposal with Use of Cost Convex Func¬tion. Polish Journal of Environmental Studies. Vol. 18, No. 3A, 2009. Hard Publishing Comp., Olsztyn 2009.
• [12] Naef Taher Al Rahedi, Jalal Atoum, Solving TSP problem using New Operator in Genet ic Algorithms, American Journal of Applied Sciences 6(8):1586- 1590, 2009.
• [13] Rutkowska D., Piliński M., Rutkowski L., Sieci neuronowe, algorytmy genetyczne i systemy rozmyte. Wydawnictwo Naukowe PWN, Warszawa-Łódź, 1997.
• [14] Rutkowski L., Metody i techniki sztucznej inteligencji. Wydawnictwo Naukowe PWN, Warszawa, 2012.
• [15] Srinivas M., Patnaik L. M., Adaptive Probabilities of Crossover and Mutation in Genetic Algorithms. IEEE Trans¬actions on Systems, Man and Cybernetics 24(4)1994.
• [16] The Traveling Salesman Problem. [Online] http://www.tsp.gatech.edu/history.
• [17] The Traveling Salesman Problem. [Online] http://www.tsp.gatech.edu/sweden.
• [18] Wiktorzak A. A., Virtual Production Line in Education, Conference materials of International Scientific Confer¬ence, Day Trends of Innovations, Lomza May 2012
• [19] Wiktorzak A. A., Zastosowanie algorytmów genetycznych w diagnostyce edukacyjnej, Working Paper, IBS PAN, Warszawa listopad 2011.
• [20] Wiktorzak A.A., Analiza systemowa i obliczenia inteligentne - przykłady zastosowań, Hołubiec J. (Red.) Analiza systemowa w finansach i zarządzaniu. Wybrane problemy, Tom 10, IBS PAN, Warszawa 2008.