Simulation-based approach to Vehicle Routing Problem with Traffic Jams

Jacek Mańdziuk , Maciej Świechowski

Abstract

Capacitated Vehicle Routing Problem (CVRP) is a well-known NP-hard optimization problem. In this paper, we transform it into a non-deterministic dynamic version by introducing traffic jams (TJ). The paper is the first attempt of applying the Upper Confidence Bounds applied to Trees (UCT) algorithm in the domain of dynamic transportation problems. In short, UCT is an extension to the Monte Carlo Tree Search (MCTS) method, however, unlike MCTS which makes use of uniformly distributed simulations, the UCT algorithm aims at maintaining an optimal balance between exploration and exploitation. The MCTS/UCT algorithm is enhanced by the usage of knowledge-based actions, which shares common traits with the human way of solving this task. Our solution is compared with an Ant Colony Optimization method showing its upper-hand and raising hope for a crossdomain applicability of the proposed approach.
Author Jacek Mańdziuk ZSIMO
Jacek Mańdziuk,,
- Department of Artificial Intelligence and Computational Methods
, Maciej Świechowski
Maciej Świechowski,,
-
Pages1-8
Publication size in sheets0.5
Book PROCEEDINGS OF 2016 IEEE SYMPOSIUM SERIES ON COMPUTATIONAL INTELLIGENCE (SSCI), 2016, IEEE, ISBN 978-1-5090-4240-1
Keywords in EnglishVehicle Routing Problem (VRP), Optimization under uncertainty, Upper Confidence Bound applied to Trees (UCT)
Abstract in PolishProblem transportowy z ograniczeniem pojemności (ang. Capacitated Vehicle Routing Problem, w skrócie CVRP) jest znanym NP-trudnym problemem optymalizacyjnym, ktory w niniejszej pracy rozszerzany jest do wersji problemu stochastycznego poprzez dodanie w jego definicji mozliwosci wystepowania (z okreslonym prawdopodobienstwem) zatorow drogowych.
DOIDOI:10.1109/SSCI.2016.7850028
URL https://www.researchgate.net/publication/311563496_Simulation-based_approach_to_Vehicle_Routing_Problem_with_Traffic_Jams
Languageen angielski
Score (nominal)15
ScoreMinisterial score [Punktacja MNiSW] = 15.0, 27-06-2017, BookChapterMatConf
Ministerial score (2013-2016) [Punktacja MNiSW (2013-2016)] = 15.0, 27-06-2017, BookChapterMatConf
Citation count*0
Cite
Share Share

Get link to the record
msginfo.png


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