An Efficient Route Minimization Algorithm for the Vehicle Routing Problem with Time Windows based on Agent Negotiation

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F13%3A00207017" target="_blank" >RIV/68407700:21230/13:00207017 - isvavai.cz</a>
Result on the web
<a href="http://link.springer.com/chapter/10.1007/978-3-642-44927-7_11" target="_blank" >http://link.springer.com/chapter/10.1007/978-3-642-44927-7_11</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-642-44927-7_11" target="_blank" >10.1007/978-3-642-44927-7_11</a>

Result language
angličtina
Original language name
An Efficient Route Minimization Algorithm for the Vehicle Routing Problem with Time Windows based on Agent Negotiation
Original language description
We present an efficient route minimization algorithm for the vehicle routing problem with time windows. The algorithm uses a generic agent decomposition of the problem featuring a clear separation between the local planning performed by the individual vehicles and the abstract global coordination achieved by negotiation --- differentiating the presented algorithm from the traditional centralized algorithms. A novel negotiation semantics is introduced on the global coordination planning level allowing customers to be temporarily ejected from the emerging solution being constructed. This allows the algorithm to efficiently backtrack in situations when the currently processed customer cannot be feasibly allocated to the emerging solution. Over the relevant widely-used benchmarks the algorithm equals the best known solutions achieved by the centralized algorithms in 90.7% of the cases with an overall relative error of 0.3%, outperforming the previous comparable agent-based algorithms.
Czech name
—
Czech description
—

Project
<a href="/en/project/TE01020197" target="_blank" >TE01020197: Centre for Applied Cybernetics 3</a><br>
Continuities
S - Specificky vyzkum na vysokych skolach

Publication year
2013
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
Proceedings of the 16th International Conference on Principles and Practice of Multi-Agent Systems
ISBN
978-3-642-44926-0
ISSN
0302-9743
e-ISSN
—
Number of pages
16
Pages from-to
149-164
Publisher name
Springer
Place of publication
Heidelberg
Event location
Dunedin
Event date
Dec 1, 2013
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—

Similar results(10)