A Cross Entropy Multiagent Learning Algorithm for Solving Vehicle Routing Problems with Time Windows

Tai-Yu Ma

doi:10.1007/978-3-642-24264-9_5

A Cross Entropy Multiagent Learning Algorithm for Solving Vehicle Routing Problems with Time Windows

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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 cross entropy 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.

Original language	English
Title of host publication	Computational Logistics
Subtitle of host publication	International Conference on Computational Logistics ICCL 2011
Editors	J.W. Böse, H. Hu , C. Jahn , X. Shi , R. Stahlbock , R. Stahlbock , S. Voß
Publisher	Springer
Number of pages	2
ISBN (Electronic)	978-3-642-24264-9
ISBN (Print)	978-3-642-24263-2
DOIs	https://doi.org/10.1007/978-3-642-24264-9_5
Publication status	Published - 2011
Externally published	Yes

Publication series

Name	Lecture Notes in Computer Science book series (LNCS)
Volume	6971

Keywords

Local Search
Vehicle Route Problem
Local Search Algorithm
Local Search Procedure
Cross Entropy

Access to Document

10.1007/978-3-642-24264-9_5

Cite this

Ma, T.-Y. (2011). A Cross Entropy Multiagent Learning Algorithm for Solving Vehicle Routing Problems with Time Windows. In J. W. Böse, H. Hu , C. Jahn , X. Shi , R. Stahlbock , R. Stahlbock , & S. Voß (Eds.), Computational Logistics: International Conference on Computational Logistics ICCL 2011 (Lecture Notes in Computer Science book series (LNCS); Vol. 6971). Springer. https://doi.org/10.1007/978-3-642-24264-9_5

@inproceedings{f6f62c8279d14949bb345e7c1480f390,

title = "A Cross Entropy Multiagent Learning Algorithm for Solving Vehicle Routing Problems with Time Windows",

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{\textquoteright}s 100-customer problem set, it shows outperforming results in comparison with the classical cross entropy 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 = "Local Search, Vehicle Route Problem, Local Search Algorithm, Local Search Procedure, Cross Entropy",

author = "Tai-Yu Ma",

year = "2011",

doi = "10.1007/978-3-642-24264-9_5",

language = "English",

isbn = "978-3-642-24263-2",

series = "Lecture Notes in Computer Science book series (LNCS)",

publisher = "Springer",

editor = "B{\"o}se, { J.W.} and {Hu }, H. and {Jahn }, C. and {Shi }, X. and {Stahlbock }, R. and {Stahlbock }, R. and {Vo{\ss} }, S.",

booktitle = "Computational Logistics",

address = "Germany",

}

Ma, T-Y 2011, A Cross Entropy Multiagent Learning Algorithm for Solving Vehicle Routing Problems with Time Windows. in JW Böse, H Hu , C Jahn , X Shi , R Stahlbock , R Stahlbock & S Voß (eds), Computational Logistics: International Conference on Computational Logistics ICCL 2011. Lecture Notes in Computer Science book series (LNCS), vol. 6971, Springer. https://doi.org/10.1007/978-3-642-24264-9_5

A Cross Entropy Multiagent Learning Algorithm for Solving Vehicle Routing Problems with Time Windows. / Ma, Tai-Yu.
Computational Logistics: International Conference on Computational Logistics ICCL 2011. ed. / J.W. Böse; H. Hu ; C. Jahn ; X. Shi ; R. Stahlbock ; R. Stahlbock ; S. Voß . Springer, 2011. (Lecture Notes in Computer Science book series (LNCS); Vol. 6971).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - A Cross Entropy Multiagent Learning Algorithm for Solving Vehicle Routing Problems with Time Windows

AU - Ma, Tai-Yu

PY - 2011

Y1 - 2011

N2 - 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 cross entropy 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.

AB - 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 cross entropy 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.

KW - Local Search

KW - Vehicle Route Problem

KW - Local Search Algorithm

KW - Local Search Procedure

KW - Cross Entropy

U2 - 10.1007/978-3-642-24264-9_5

DO - 10.1007/978-3-642-24264-9_5

M3 - Conference contribution

SN - 978-3-642-24263-2

T3 - Lecture Notes in Computer Science book series (LNCS)

BT - Computational Logistics

A2 - Böse, J.W.

A2 - Hu , H.

A2 - Jahn , C.

A2 - Shi , X.

A2 - Stahlbock , R.

A2 - Voß , S.

PB - Springer

ER -

Ma TY. A Cross Entropy Multiagent Learning Algorithm for Solving Vehicle Routing Problems with Time Windows. In Böse JW, Hu H, Jahn C, Shi X, Stahlbock R, Stahlbock R, Voß S, editors, Computational Logistics: International Conference on Computational Logistics ICCL 2011. Springer. 2011. (Lecture Notes in Computer Science book series (LNCS)). doi: 10.1007/978-3-642-24264-9_5