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

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

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

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

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

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

JC - Počítačový hardware a software

OECD FORD obor

—

Projekt

<a href="/cs/project/TE01020197" target="_blank" >TE01020197: Centrum aplikované kybernetiky 3</a><br>

Návaznosti

S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2013

Kód důvěrnosti údajů

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

Název statě ve sborníku

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

—

Počet stran výsledku

16

Strana od-do

149-164

Název nakladatele

Springer

Místo vydání

Heidelberg

Místo konání akce

Dunedin

Datum konání akce

1. 12. 2013

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—