Algorytm selekcji klonalnej w marszrutowaniu pojazdów

Abstract

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