Multi-criterion optimisation of transport orders with the innovative evolutionary approach

• Authors: Radosław Bułat , Michał Radziszewski

Title variants

PL

Wielokryterialna optymalizacja zleceń transportowych przy użyciu innowacyjnego podejścia ewolucyjnego

• Languages of publication: EN

Abstracts

EN

One of the common problems encountered frequently in logistic issues is PDPTW (pickup and delivery problem with time windows) where a limited transport base is to be used to expedite goods in an efficient way from point A to point B. Every organisation, both business and non-profit is, for obvious reasons, unable to grasp the whole logistic process without the aid of automation, so it has to be equipped with a logistics support system. A viable alternative to other analytical solutions can therefore come in the form of a system based on genetic algorithms, which takes into account the limitations of the infrastructure, the time frame and the resulting penalty for any delay. This platform should also allow for the transition from a mathematically defined solution to a problem (however little practical use it has) to the real logistical problems based on the actual needs of the industry. Such a system was implemented, and with the basic genetic operators (cloning, mutation and crossover) is able to plan a solution for any arbitrarily defined, solvable problem of transportation, with the help of any algorithm using those operators. After starting the program and entering the dataset, the pre-set number of simulated generations of the genetic algorithm is started with the default chosen SPEA algorithm (strength Pareto evolutionary algorithm). The results of the simulation in the form of the final set of solutions are being saved to a file. For the algorithm applied to the test problem, the optimal solution for each variable, or middle-ground solutions were found.

PL

Jednym ze standardowych problemów spotykanych często w zagadnieniach logistycznych jest PDPTW (Pickup and Delivery Problem with Time Windows), gdzie dysponując ograniczoną bazą transportową, należy w sposób efektywny transportować towary z punktu A do B. Każda organizacja, zarówno biznesowa, jak i o charakterze niekomercyjnym, z oczywistych powodów niemożności ogarnięcia całościowo procesów logistycznych bez pomocy automatyzacji musi być wyposażona w system wsparcia logistycznego. Alternatywą dla innych rozwiązań analitycznych może być zatem system oparty na algorytmach genetycznych, biorący pod uwagę możliwości infrastruktury oraz ramy czasowe i wynikające z nich kary za opóźnienia. Platforma ta powinna też umożliwić przejście od rozwiązywania problematu zdefiniowanego matematycznie (jednak mającego nikłe zastosowanie praktyczne) do problemów logistycznych opartych na faktycznych potrzebach przemysłowych. System taki został zaimplementowany i przy użyciu podstawowych operatorów genetycznych – klonowania, mutacji i krzyżówki jest w stanie planować rozwiązania dla dowolnie zdefiniowanego rozwiązywalnego problemu transportowego oraz dowolnie zdefiniowanego algorytmu używającego tych operatorów. Po uruchomieniu programu i wprowadzeniu danych rozpoczynana jest symulacja zadanej ilości pokoleń algorytmu genetycznego, domyślnie wykonywanych według algorytmu SPEA (Strength Pareto Evolutionary Algorithm). Wyniki symulacji w postaci końcowego zbioru rozwiązań wypisywane są do pliku. Dla zastosowanego algorytmu dla problemu testowego znalezione zostały rozwiązania optymalne dla każdej ze zmiennych bądź rozwiązania pośrednie.

Keywords

EN

genetic algorithms; PDPTW; SPEA; logistic support system

PL

algorytmy genetyczne; PDPTW; SPEA; system wsparcia logistycznego

• Publisher: Małopolska Wyższa Szkoła Ekonomiczna
• Journal: Zeszyty Naukowe Małopolskiej Wyższej Szkoły Ekonomicznej w Tarnowie
• Year: 2011
• Issue: 1(17)
• Pages: 43-53

Dates

printed

2011-06

Contributors

author

Radosław Bułat

• Jesuit University of Philosophy and Education "Ignatianum" in Krakow

author

Michał Radziszewski

• AGH University of Science and Technology in Krakow

References

• Beier F.J., Rutkowski K. 1995. Logistyka. Warszawa: Szkoła Główna Handlowa. ISBN 83-86689-06-4.
• Chaberek M. 2001. "Modelowanie systemu wsparcia logistycznego organizacji". In: Modelowanie procesów i systemów logistycznych. Part One. Gdańsk: Wydawnictwo Uniwersytetu Gdańskiego, pp. 69–80.
• Michalewicz Z. 1996. Algorytmy genetyczne + struktury danych = programy ewolucyjne. Transl. by Z. Nahorski. Warszawa: Wydawnictwa Naukowo-Techniczne.
• Haupt R.L., Haupt S.E. 1998. Practical genetic algorithms. New York: John Wiley and Sons.
• Kalyanmoy D. 2001. Multi-objective optimization using evolutionary algorithms. New York: John Wiley and Sons. ISBN-10: 047187339X.
• Goldberg D. 1989. Genetic algorithms in search, optimization, and machine learning. Reading: Addison-Wesley Professional. ISBN-10: 0201157675.