UCT in Capacitated Vehicle Routing Problem with traffic jams

In this paper a dynamic version of the Capacitated Vehicle Routing Problem (CVRP) which takes into account traffic jams is considered. Traffic jams occur randomly according to pre-defined intensity and length distributions. In effect, static CVRP is transformed into a non-deterministic scheduling problem with high uncertainty factor and changing in time internal problem parameters. Our proposed solution to CVRP with traffic jams (CVRPwTJ) relies on application of the Upper Confidence Bounds applied to Trees (UCT) method, which is an extension of the Monte Carlo Tree Search algorithm. The most challenging issue here is finding a suitable mapping of the CVRPwTJ onto a tree-like problem representation required by the UCT. Furthermore, in order to prevent the size of the tree from explosive growth, an efficient mechanism for child nodes selection is proposed. UCT-based approach is compared with four other methods showing promising results and offering prospects for its wider applicability in the domain of stochastic optimization problems.