Decentralized Combinatorial Auctions for Dynamic and Large-Scale Collaborative Vehicle Routing

Johan Los; Frederik Schulte; Margaretha Gansterer; Richard F. Hartl; Matthijs T.J. Spaan; Rudy R. Negenborn

doi:10.1007/978-3-030-59747-4_14

Decentralized Combinatorial Auctions for Dynamic and Large-Scale Collaborative Vehicle Routing

Johan Los^*, Frederik Schulte, Margaretha Gansterer, Richard F. Hartl, Matthijs T.J. Spaan, Rudy R. Negenborn

^*Corresponding author for this work

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

6 Citations (Scopus)

52 Downloads (Pure)

Abstract

While collaborative vehicle routing has a significant potential to reduce transportation costs and emissions, current approaches are limited in terms of applicability, unrealistic assumptions, and low scalability. Centralized planning generally assumes full information and full control, which is often unacceptable for individual carriers. Combinatorial auctions with one central auctioneer overcome this problem and provide good results, but are limited to small static problems. Multi-agent approaches have been proposed for large dynamic problems, but do not directly take the advantages of bundling into account. We propose an approach where participants can individually outsource orders, while a platform can suggest bundles of the offered requests to improve solutions. We consider bundles of size 2 and 3 and show that travel costs can be decreased with 1.7% compared to the scenario with only single order auctions. Moreover, experiments on data from a Dutch transportation platform company show that large-scale collaboration through a platform results in system-wide savings of up to 79% for 1000 carriers.

Original language	English
Title of host publication	Computational Logistics
Subtitle of host publication	Proceedings of the 11th International Conference, ICCL 2020
Editors	Eduardo Lalla-Ruiz, Martijn Mes, Stefan Voß
Publisher	Springer
Pages	215-230
ISBN (Electronic)	978-3-030-59747-4
ISBN (Print)	978-3-030-59746-7
DOIs	https://doi.org/10.1007/978-3-030-59747-4_14
Publication status	Published - 2020
Event	11th International Conference on Computational Logistics, ICCL 2020 - Enschede, Netherlands Duration: 28 Sept 2020 → 30 Sept 2020

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	12433 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	11th International Conference on Computational Logistics, ICCL 2020
Country/Territory	Netherlands
City	Enschede
Period	28/09/20 → 30/09/20

Bibliographical note

Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-care

Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

Keywords

Bundling
Collaborative transportation
Collaborative vehicle routing
Combinatorial auctions
Dynamic Pickup and Delivery Problem
Logistics
Multi-Agent System
Platform-based transportation

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

Access to Document

10.1007/978-3-030-59747-4_14

Los2020_Chapter_DecentralizedCombinatorialAuctFinal published version, 335 KB

Cite this

Los, J., Schulte, F., Gansterer, M., Hartl, R. F., Spaan, M. T. J., & Negenborn, R. R. (2020). Decentralized Combinatorial Auctions for Dynamic and Large-Scale Collaborative Vehicle Routing. In E. Lalla-Ruiz, M. Mes, & S. Voß (Eds.), Computational Logistics: Proceedings of the 11th International Conference, ICCL 2020 (pp. 215-230). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12433 LNCS). Springer. https://doi.org/10.1007/978-3-030-59747-4_14

Los, Johan ; Schulte, Frederik ; Gansterer, Margaretha et al. / Decentralized Combinatorial Auctions for Dynamic and Large-Scale Collaborative Vehicle Routing. Computational Logistics: Proceedings of the 11th International Conference, ICCL 2020. editor / Eduardo Lalla-Ruiz ; Martijn Mes ; Stefan Voß. Springer, 2020. pp. 215-230 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{d106da2410784ad4b82dd9b81097a98b,

title = "Decentralized Combinatorial Auctions for Dynamic and Large-Scale Collaborative Vehicle Routing",

abstract = "While collaborative vehicle routing has a significant potential to reduce transportation costs and emissions, current approaches are limited in terms of applicability, unrealistic assumptions, and low scalability. Centralized planning generally assumes full information and full control, which is often unacceptable for individual carriers. Combinatorial auctions with one central auctioneer overcome this problem and provide good results, but are limited to small static problems. Multi-agent approaches have been proposed for large dynamic problems, but do not directly take the advantages of bundling into account. We propose an approach where participants can individually outsource orders, while a platform can suggest bundles of the offered requests to improve solutions. We consider bundles of size 2 and 3 and show that travel costs can be decreased with 1.7% compared to the scenario with only single order auctions. Moreover, experiments on data from a Dutch transportation platform company show that large-scale collaboration through a platform results in system-wide savings of up to 79% for 1000 carriers.",

keywords = "Bundling, Collaborative transportation, Collaborative vehicle routing, Combinatorial auctions, Dynamic Pickup and Delivery Problem, Logistics, Multi-Agent System, Platform-based transportation",

author = "Johan Los and Frederik Schulte and Margaretha Gansterer and Hartl, {Richard F.} and Spaan, {Matthijs T.J.} and Negenborn, {Rudy R.}",

note = "Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.; 11th International Conference on Computational Logistics, ICCL 2020 ; Conference date: 28-09-2020 Through 30-09-2020",

year = "2020",

doi = "10.1007/978-3-030-59747-4_14",

language = "English",

isbn = "978-3-030-59746-7",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "215--230",

editor = "Eduardo Lalla-Ruiz and Martijn Mes and Stefan Vo{\ss}",

booktitle = "Computational Logistics",

}

Los, J, Schulte, F, Gansterer, M, Hartl, RF, Spaan, MTJ & Negenborn, RR 2020, Decentralized Combinatorial Auctions for Dynamic and Large-Scale Collaborative Vehicle Routing. in E Lalla-Ruiz, M Mes & S Voß (eds), Computational Logistics: Proceedings of the 11th International Conference, ICCL 2020. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12433 LNCS, Springer, pp. 215-230, 11th International Conference on Computational Logistics, ICCL 2020, Enschede, Netherlands, 28/09/20. https://doi.org/10.1007/978-3-030-59747-4_14

Decentralized Combinatorial Auctions for Dynamic and Large-Scale Collaborative Vehicle Routing. / Los, Johan; Schulte, Frederik; Gansterer, Margaretha et al.
Computational Logistics: Proceedings of the 11th International Conference, ICCL 2020. ed. / Eduardo Lalla-Ruiz; Martijn Mes; Stefan Voß. Springer, 2020. p. 215-230 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12433 LNCS).

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

TY - GEN

T1 - Decentralized Combinatorial Auctions for Dynamic and Large-Scale Collaborative Vehicle Routing

AU - Los, Johan

AU - Schulte, Frederik

AU - Gansterer, Margaretha

AU - Hartl, Richard F.

AU - Spaan, Matthijs T.J.

AU - Negenborn, Rudy R.

N1 - Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

PY - 2020

Y1 - 2020

N2 - While collaborative vehicle routing has a significant potential to reduce transportation costs and emissions, current approaches are limited in terms of applicability, unrealistic assumptions, and low scalability. Centralized planning generally assumes full information and full control, which is often unacceptable for individual carriers. Combinatorial auctions with one central auctioneer overcome this problem and provide good results, but are limited to small static problems. Multi-agent approaches have been proposed for large dynamic problems, but do not directly take the advantages of bundling into account. We propose an approach where participants can individually outsource orders, while a platform can suggest bundles of the offered requests to improve solutions. We consider bundles of size 2 and 3 and show that travel costs can be decreased with 1.7% compared to the scenario with only single order auctions. Moreover, experiments on data from a Dutch transportation platform company show that large-scale collaboration through a platform results in system-wide savings of up to 79% for 1000 carriers.

AB - While collaborative vehicle routing has a significant potential to reduce transportation costs and emissions, current approaches are limited in terms of applicability, unrealistic assumptions, and low scalability. Centralized planning generally assumes full information and full control, which is often unacceptable for individual carriers. Combinatorial auctions with one central auctioneer overcome this problem and provide good results, but are limited to small static problems. Multi-agent approaches have been proposed for large dynamic problems, but do not directly take the advantages of bundling into account. We propose an approach where participants can individually outsource orders, while a platform can suggest bundles of the offered requests to improve solutions. We consider bundles of size 2 and 3 and show that travel costs can be decreased with 1.7% compared to the scenario with only single order auctions. Moreover, experiments on data from a Dutch transportation platform company show that large-scale collaboration through a platform results in system-wide savings of up to 79% for 1000 carriers.

KW - Bundling

KW - Collaborative transportation

KW - Collaborative vehicle routing

KW - Combinatorial auctions

KW - Dynamic Pickup and Delivery Problem

KW - Logistics

KW - Multi-Agent System

KW - Platform-based transportation

UR - http://www.scopus.com/inward/record.url?scp=85092236968&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-59747-4_14

DO - 10.1007/978-3-030-59747-4_14

M3 - Conference contribution

AN - SCOPUS:85092236968

SN - 978-3-030-59746-7

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 215

EP - 230

BT - Computational Logistics

A2 - Lalla-Ruiz, Eduardo

A2 - Mes, Martijn

A2 - Voß, Stefan

PB - Springer

T2 - 11th International Conference on Computational Logistics, ICCL 2020

Y2 - 28 September 2020 through 30 September 2020

ER -

Los J, Schulte F, Gansterer M, Hartl RF, Spaan MTJ , Negenborn RR. Decentralized Combinatorial Auctions for Dynamic and Large-Scale Collaborative Vehicle Routing. In Lalla-Ruiz E, Mes M, Voß S, editors, Computational Logistics: Proceedings of the 11th International Conference, ICCL 2020. Springer. 2020. p. 215-230. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-59747-4_14

Decentralized Combinatorial Auctions for Dynamic and Large-Scale Collaborative Vehicle Routing

Abstract

Publication series

Conference

Bibliographical note

Keywords

UN SDGs

Access to Document

Other files and links

Fingerprint

Cite this