Routing a Fleet of Automated Vehicles in a Capacitated Transportation Network

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F19%3A00339684" target="_blank" >RIV/68407700:21230/19:00339684 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1109/IROS40897.2019.8967723" target="_blank" >https://doi.org/10.1109/IROS40897.2019.8967723</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1109/IROS40897.2019.8967723" target="_blank" >10.1109/IROS40897.2019.8967723</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Routing a Fleet of Automated Vehicles in a Capacitated Transportation Network

Popis výsledku v původním jazyce

Routing of a fleet of automated unit-occupancy vehicles in a capacitated transportation network is an emerging problem that needs to be addressed to realize large-scale automated transportation systems. We adopt an existing network-flow-based model for the problem and present a new reformulation based on Dantzig-Wolfe decomposition. This reformulation allows us to apply the column generation solution technique which, in turn, enables us to solve large-scale problem instances with tens of thousands of requests on networks with thousands of links. We empirically compare our method to the state-of-the-art approach on several standard benchmark instances and find that the computational time of our solution approach scales qualitatively better in all tested problem instance parameters: namely, in the size of the transportation network, in the magnitude of demand intensity, and in the number of demand flows.

Název v anglickém jazyce

Routing a Fleet of Automated Vehicles in a Capacitated Transportation Network

Popis výsledku anglicky

Routing of a fleet of automated unit-occupancy vehicles in a capacitated transportation network is an emerging problem that needs to be addressed to realize large-scale automated transportation systems. We adopt an existing network-flow-based model for the problem and present a new reformulation based on Dantzig-Wolfe decomposition. This reformulation allows us to apply the column generation solution technique which, in turn, enables us to solve large-scale problem instances with tens of thousands of requests on networks with thousands of links. We empirically compare our method to the state-of-the-art approach on several standard benchmark instances and find that the computational time of our solution approach scales qualitatively better in all tested problem instance parameters: namely, in the size of the transportation network, in the magnitude of demand intensity, and in the number of demand flows.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2019

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

2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)

ISBN

978-1-7281-4004-9

ISSN

2153-0858

e-ISSN

2153-0866

Počet stran výsledku

7

Strana od-do

8223-8229

Název nakladatele

IEEE

Místo vydání

Piscataway, NJ

Místo konání akce

Macau

Datum konání akce

4. 11. 2019

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

WRD - Celosvětová akce

Kód UT WoS článku

—