A cross entropy multiagent learning algorithm for solving vehicle routing problems with time windows

Tai-Yu Ma (1)

1 LET - Laboratoire d'économie des transports

The vehicle routing problem with time windows (VRPTW) has been the subject of intensive study because of its importance in real applications. In this paper, we propose a cross entropy multiagent learning algorithm, which considers an optimum solution as a rare event to be learned. The routing policy is node-distributed, controlled by a set of parameterized probability distribution functions. Based on the performance of experienced tours of vehicle agents, these parameters are updated iteratively by minimizing Kullback-Leibler cross entropy in order to generate better solutions in next iterations. When applying the proposed algorithm on Solomon's 100-customer problem set, it shows outperforming results in comparison with the classical CE approach. Moreover, this method needs only very small number of parameter settings. Its implementation is also relatively simple and flexible to solve other vehicle routing problems under various dynamic scenarios.

Mots clés: Vehicle routing problem; heuristic; cross entropy

Domaines: Economies et finances

Tai-Yu Ma. A cross entropy multiagent learning algorithm for solving vehicle routing problems with time windows. J.W. Böse et al. ICCL 2011, Lecture Notes in Computer Science (LNCS) 6971, Springer-Verlag Berlin Heidelberg, pp.59-73, 2011. ⟨halshs-00592118v2⟩