A Particle Swarm Optimization hyper-heuristic for the Dynamic Vehicle Routing Problem

Michał Okulewicz , Jacek Mańdziuk

Abstract

This paper presents a method for choosing a Particle Swarm Optimization based optimizer for the Dynamic Vehicle Routing Problem on the basis of the initially available data of a given problem instance. The optimization algorithm is chosen on the basis of a prediction made by a linear model trained on that data and the relative results obtained by the optimization algorithms. The achieved results suggest that such a model can be used in a hyper-heuristic approach as it improved the average results, obtained on the set of benchmark instances, by choosing the appropriate algorithm in 82% of significant cases. Two leading multi-swarm Particle Swarm Optimization based algorithms for solving the Dynamic Vehicle Routing Problem are used as the basic optimization algorithms: Khouadjia’s et al. Multi–Environmental Multi–Swarm Optimizer and authors’ 2–Phase Multiswarm Particle Swarm Optimization.
Author Michał Okulewicz ZSIMO
Michał Okulewicz,,
- Department of Artificial Intelligence and Computational Methods
, Jacek Mańdziuk ZSIMO
Jacek Mańdziuk,,
- Department of Artificial Intelligence and Computational Methods
Pages215-227
Publication size in sheets0.6
Book Papa Gregor, Mernik Marjan (eds.): Proceedings of the Seventh International Conference on Bioinspired Optimization Methods and their Applications, BIOMA 2016, 2016, Jozef Stefan Institute, ISBN 978-961-264-093-4
Keywords in EnglishDynamic vehicle routing problem, Hyper-heuristic, Particle swarm optimization
Abstract in PolishPraca prezentuje możliwość wykorzystania danych definiujących zamówienia w rozwiązywaniu problemu dynamicznej marszrutyzacji. Wykorzystanie danych polega na zbudowaniu modelu liniowego, opartego na cechach rozkładu wielkości i położenia zamówień, przewidującego względną jakość wyniku uzyskanego przez algorytmy MEMSO i 2MPSO rozwiązujące problem dynamicznej marszrutyzacji. Proponowane podejście pozwoliło na poprawną identyfikację 82% instancji testowych spośród tych o statystycznie istotnej różnicy pomiędzy średnimi wynikami uzyskiwanymi przez wykorzystywane algorytmy.
DOIDOI:10.13140/RG.2.2.27509.58082
URL http://bioma.ijs.si/proceedings/2016/15%20-%20A%20Particle%20Swarm%20Optimization%20Hyper-Heuristic%20for%20the%20Dynamic%20Vehicle%20Routing%20Problem.pdf
Languageen angielski
Score (nominal)0
Citation count*0
Cite
Share Share



* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Back