Simulation-based approach to Vehicle Routing Problem with traffic jams
- 1 December 2016
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-8
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.Keywords
This publication has 19 references indexed in Scilit:
- An Automatically Generated Evaluation Function in General Game PlayingIEEE Transactions on Computational Intelligence and AI in Games, 2013
- Application of Particle Swarm Optimization Algorithm to Dynamic Vehicle Routing Problem2013
- A self-adaptive memeplexes robust search scheme for solving stochastic demands vehicle routing problemInternational Journal of Systems Science, 2012
- An improved Clarke and Wright savings algorithm for the capacitated vehicle routing problemScienceAsia, 2012
- Monte-Carlo tree search and rapid action value estimation in computer GoArtificial Intelligence, 2011
- Improving Monte–Carlo Tree Search in Havannah2011
- Multi-Swarm Optimization for Dynamic Combinatorial Problems: A Case Study on Dynamic Vehicle Routing Problem2010
- Creating an Upper-Confidence-Tree Program for Havannah2010
- Computational Intelligence in Mind Games2007
- Complexity of vehicle routing and scheduling problemsNetworks, 1981