A metaheuristic approach to solve Dynamic Vehicle Routing Problem in continuous search space

Michał Okulewicz , Jacek Mańdziuk

Abstract

This paper investigates a hypothesis that in case of hard optimization problems, selection of the proper search space is more relevant than the choice of the solving algorithm. Dynamic Vehicle Routing Problem is used as as a test problem and the hypothesis is verified experimentally on the well-known set of benchmark instances. The paper compares Particle Swarm Optimization (PSO) and Differential Evolution (DE) operating in two continuous search spaces (giving in total four distinctive approaches) and a state-of-the art discrete encoding utilizing Genetic Algorithm (GA). The advantage of selected continuous search space over a discrete one is verified on the basis of quality of the final solution and stability of intermediate partial solutions. During stability analysis it has been observed that practical level of uncertainty, resulting from the dynamic nature of the problem, is lower than could be expected from a popular degree of dynamism measure. In order to challenge that issue, benchmark problems have been solved also with a higher level of dynamism and an empirical degree of dynamism has been proposed as an additional measure of the amount of uncertainty of the problem. The results obtained by both continuous algorithms outperform those of state-of-the-art algorithms utilizing discrete problem representation, while the performance differences between them (PSO and DE) are minute. Apart from higher numerical efficiency in solving DVRP, the use of continuous problem encoding proved its advantage over discrete encoding also in terms of stability of the requests-to-vehicles assignment in intermediate solutions generated during the optimization process. Such sequences generated by the proposed continuous approach were approximately 40% more accurate with respect to the final solution than their counterparts generated with the discrete encoding. Analysis of these sequences of intermediate solutions for several benchmark sets resulted in designing a penalty term that takes into account a specific dynamic nature of the optimized problem. An addition of this penalty term improved the above-mentioned stability of partial solutions by another 10%.
Author Michał Okulewicz (FMIS / DAICM)
Michał Okulewicz,,
- Department of Artificial Intelligence and Computational Methods
, Jacek Mańdziuk (FMIS / DAICM)
Jacek Mańdziuk,,
- Department of Artificial Intelligence and Computational Methods
Journal seriesSwarm and Evolutionary Computation, ISSN 2210-6502, (A 50 pkt)
Issue year2019
Vol48
Pages44-61
Publication size in sheets0.85
Keywords in Polishdynamiczny problem marszrutyzacji, optymalizacja dynamiczna, ciągła przestrzeń przeszukiwań, problem marszrutyzacji, optymalizacja rojem cząstek, ewolucja różnicowa
Keywords in EnglishDynamic Vehicle Routing Problem, dynamic optimization, continuous search space, Vehicle Routing Problem, Particle Swarm Optimization, Differential Evolution
ASJC Classification2600 General Mathematics; 1700 General Computer Science
Abstract in PolishPraca prezentuje ciągłą przestrzeń przeszukiwania zastosowaną do dynamicznego dyskretnego problemu optymalizacji - problemu marszrutyzacji z nieznanymi zamówieniami. Praca wskazuje na pierwszeństwo wyboru przestrzeni przeszukiwania nad wyborem algorytmu, jako możliwą przyczynę sukcesu danej metody optymalizacji. Ponadto w pracy analizowana jest natura dynamizmu w problemie marszrutyzacji, zaproponowana jest metoda uwzględniająca tę naturę w procesie optymalizacji (poprzez czynnik kary w funkcji jakości rozwiązania) oraz podane są wyniki dla ponadstandardowych wartości tzw. czasu odcięcia, co zwiększa dynamizm omawianego problemu optymalizacyjnego.
DOIDOI:10.1016/j.swevo.2019.03.008
URL https://www.sciencedirect.com/science/article/pii/S2210650218306114
Languageen angielski
Score (nominal)50
ScoreMinisterial score = 50.0, 08-07-2019, ArticleFromJournal
Publication indicators Scopus SNIP (Source Normalised Impact per Paper): 2016 = 2.756; WoS Impact Factor: 2017 = 3.818 (2) - 2017=4.607 (5)
Citation count*
Cite
Share Share

Get link to the record


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