Algorytm selekcji klonalnej w marszrutowaniu pojazdów

• Autorzy: Dąbrowski, J.

Warianty tytułu

EN

Application of clonal selection algorithms to solving the vehicle routing problem

• Języki publikacji: PL

Abstrakty

PL

Algorytmy selekcji klonalnej (SK) to algorytmy optymalizacji dyskretnej należące do klasy sztucznych systemów immunologicznych. W pracy przedstawiamy zastosowanie algorytmu SK do rozwiązywania NP-trudnego problemu Capacitated Vehicle Routing Problem (CVRP). Praca zawiera opis algorytmu i jego adaptacji do CVRP, wyniki badań nad parametrami algorytmu oraz eksperymentów komputerowych porównujących efektywność SK z algorytmem symulowanego wyżarzania dla przedstawionego problemu.

EN

Clonal Selection (CS) algorithms are discrete optimization algorithms that belong to the class of Artificial Immune Systems. In this work we present an application of CS principles to solving the NP-hard Capacitated Vehicle Routing Problem. We present details of the algorithm and some results of computer experiments aimed at assesing the parameters of the algorithm, as well as comparing it with a Simulated Annealing algorithm for CVRP.

Słowa kluczowe

PL

selekcja klonalna; marszrutowanie; dyskretna optymalizacja; system immunologiczny sztuczny

EN

clonal selection; vehicle routing; discrete optimization; artificial immune systems

• Czasopismo: Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
• Rocznik: 2009
• Tom: T. 13, z. 2
• Strony: 239-245
• Opis fizyczny: Bibliogr. 7 poz., rys., tab.

Twórcy

autor

Dąbrowski, J.

• Katedra Systemów Geoinformatycznych, Politechnika Gdańska

Bibliografia

• [1] Garret S., How do we evaluate artificial immune systems? Evolutionary Computation 13(2), 2005, 145.
• [2] Ralphs Т.К., Koller G., Julstrom B.A., On the capacitated vehicle routing problem. Mathematical Programming 94 (2-3), 2003, 343.
• [3] Jerne N.K., Towards a network theory of the immune system. Annales d'immunologie 1-2, 1974, 373.
• [4] Taillard E., Parallel iterative search methods for vehicle routing problems. Networks 23, 1993, 661.
• [5] Dąbrowski J., Kubale M., Computer experiments with a parallel clonal selection algorithm for the Graph Coloring Problem. Proc. of IEEE International Symposium on Parallel and Distributed Processing 2008.
• [6] de Castro L.N., von Zuben F.J., Learning and optimization using the clonal selection principle. IEEE Trans. Evolutionary Computation 6 (3), 2002, 239.
• [7] Aronson L.D., Algorithms for vehicle routing - a survey. Delft University of Technology Technical Report 1996, 21.