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

Tai-Yu Ma ()
Additional contact information
Tai-Yu Ma: LET - Laboratoire d'économie des transports - UL2 - Université Lumière - Lyon 2 - ENTPE - École Nationale des Travaux Publics de l'État - CNRS - Centre National de la Recherche Scientifique

Post-Print from HAL

Abstract: 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.

Keywords: Vehicle routing problem; heuristic; cross entropy (search for similar items in EconPapers)
Date: 2011-09-19
Note: View the original document on HAL open archive server: https://shs.hal.science/halshs-00592118v2
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Published in J.W. Böse et al. ICCL 2011, Lecture Notes in Computer Science (LNCS) 6971, Springer-Verlag Berlin Heidelberg, pp.59-73, 2011

Downloads: (external link)
https://shs.hal.science/halshs-00592118v2/document (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hal:journl:halshs-00592118

Access Statistics for this paper

More papers in Post-Print from HAL
Bibliographic data for series maintained by CCSD ().