An Auction-Based Multi-Agent System for the Pickup and Delivery Problem with Autonomous Vehicles and Alternative Locations

Johan Los; Frederik Schulte; Matthijs T.J. Spaan; Rudy R. Negenborn

doi:10.1007/978-3-031-05359-7_20

An Auction-Based Multi-Agent System for the Pickup and Delivery Problem with Autonomous Vehicles and Alternative Locations

Johan Los, Frederik Schulte^*, 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

2 Citations (Scopus)

33 Downloads (Pure)

Abstract

The trends of autonomous transportation and mobility on demand in line with large numbers of requests increasingly call for decentralized vehicle routing optimization. Multi-agent systems (MASs) allow to model fully autonomous decentralized decision making, but are rarely considered in current decision support approaches. We propose a multi-agent approach in which autonomous vehicles are modeled as independent decision makers that locally interact with auctioneers for transportation orders. The developed MAS finds solutions for a realistic routing problem in which multiple pickup and delivery alternatives are possible per order. Although information sharing is significantly restricted, the MAS results in better solutions than a centralized Adaptive Large Neighborhood Search with full information sharing on large problem instances where computation time is limited.

Original language	English
Title of host publication	Dynamics in Logistics
Subtitle of host publication	Proceedings of the 8th International Conference LDIC 2022, Bremen, Germany
Editors	Michael Freitag, Aseem Kinra, Herbert Kotzab, Nicole Megow
Publisher	Springer
Pages	244-260
ISBN (Electronic)	978-3-031-05359-7
ISBN (Print)	978-3-031-05358-0
DOIs	https://doi.org/10.1007/978-3-031-05359-7_20
Publication status	Published - 2022
Event	LDIC 2022: 8th International Conference on Dynamics in Logistics (Virtual) - Bremen, Germany Duration: 23 Feb 2022 → 25 Feb 2022

Publication series

Name	Lecture Notes in Logistics
ISSN (Print)	2194-8917
ISSN (Electronic)	2194-8925

Conference

Conference	LDIC 2022: 8th International Conference on Dynamics in Logistics (Virtual)
Country/Territory	Germany
City	Bremen
Period	23/02/22 → 25/02/22

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

Alternative locations
Auctions
Autonomous vehicle routing
Multi-agent system
Pickup and delivery problem
Preferences

Access to Document

10.1007/978-3-031-05359-7_20

Los2022_Chapter_AnAuction-BasedMulti-AgentSystFinal published version, 254 KB

Cite this

Los, J., Schulte, F., Spaan, M. T. J., & Negenborn, R. R. (2022). An Auction-Based Multi-Agent System for the Pickup and Delivery Problem with Autonomous Vehicles and Alternative Locations. In M. Freitag, A. Kinra, H. Kotzab, & N. Megow (Eds.), Dynamics in Logistics : Proceedings of the 8th International Conference LDIC 2022, Bremen, Germany (pp. 244-260). (Lecture Notes in Logistics). Springer. https://doi.org/10.1007/978-3-031-05359-7_20

Los, Johan ; Schulte, Frederik ; Spaan, Matthijs T.J. et al. / An Auction-Based Multi-Agent System for the Pickup and Delivery Problem with Autonomous Vehicles and Alternative Locations. Dynamics in Logistics : Proceedings of the 8th International Conference LDIC 2022, Bremen, Germany. editor / Michael Freitag ; Aseem Kinra ; Herbert Kotzab ; Nicole Megow. Springer, 2022. pp. 244-260 (Lecture Notes in Logistics).

@inproceedings{d263ba582ded4035819a1c74c5f42916,

title = "An Auction-Based Multi-Agent System for the Pickup and Delivery Problem with Autonomous Vehicles and Alternative Locations",

abstract = "The trends of autonomous transportation and mobility on demand in line with large numbers of requests increasingly call for decentralized vehicle routing optimization. Multi-agent systems (MASs) allow to model fully autonomous decentralized decision making, but are rarely considered in current decision support approaches. We propose a multi-agent approach in which autonomous vehicles are modeled as independent decision makers that locally interact with auctioneers for transportation orders. The developed MAS finds solutions for a realistic routing problem in which multiple pickup and delivery alternatives are possible per order. Although information sharing is significantly restricted, the MAS results in better solutions than a centralized Adaptive Large Neighborhood Search with full information sharing on large problem instances where computation time is limited.",

keywords = "Alternative locations, Auctions, Autonomous vehicle routing, Multi-agent system, Pickup and delivery problem, Preferences",

author = "Johan Los and Frederik Schulte 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.; LDIC 2022: 8th International Conference on Dynamics in Logistics (Virtual) ; Conference date: 23-02-2022 Through 25-02-2022",

year = "2022",

doi = "10.1007/978-3-031-05359-7_20",

language = "English",

isbn = "978-3-031-05358-0",

series = "Lecture Notes in Logistics",

publisher = "Springer",

pages = "244--260",

editor = "Freitag, {Michael } and Kinra, {Aseem } and Kotzab, {Herbert } and Megow, {Nicole }",

booktitle = "Dynamics in Logistics",

}

Los, J, Schulte, F , Spaan, MTJ & Negenborn, RR 2022, An Auction-Based Multi-Agent System for the Pickup and Delivery Problem with Autonomous Vehicles and Alternative Locations. in M Freitag, A Kinra, H Kotzab & N Megow (eds), Dynamics in Logistics : Proceedings of the 8th International Conference LDIC 2022, Bremen, Germany. Lecture Notes in Logistics, Springer, pp. 244-260, LDIC 2022: 8th International Conference on Dynamics in Logistics (Virtual), Bremen, Germany, 23/02/22. https://doi.org/10.1007/978-3-031-05359-7_20

An Auction-Based Multi-Agent System for the Pickup and Delivery Problem with Autonomous Vehicles and Alternative Locations. / Los, Johan; Schulte, Frederik ; Spaan, Matthijs T.J. et al.
Dynamics in Logistics : Proceedings of the 8th International Conference LDIC 2022, Bremen, Germany. ed. / Michael Freitag; Aseem Kinra; Herbert Kotzab; Nicole Megow. Springer, 2022. p. 244-260 (Lecture Notes in Logistics).

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

TY - GEN

T1 - An Auction-Based Multi-Agent System for the Pickup and Delivery Problem with Autonomous Vehicles and Alternative Locations

AU - Los, Johan

AU - Schulte, Frederik

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

Y1 - 2022

N2 - The trends of autonomous transportation and mobility on demand in line with large numbers of requests increasingly call for decentralized vehicle routing optimization. Multi-agent systems (MASs) allow to model fully autonomous decentralized decision making, but are rarely considered in current decision support approaches. We propose a multi-agent approach in which autonomous vehicles are modeled as independent decision makers that locally interact with auctioneers for transportation orders. The developed MAS finds solutions for a realistic routing problem in which multiple pickup and delivery alternatives are possible per order. Although information sharing is significantly restricted, the MAS results in better solutions than a centralized Adaptive Large Neighborhood Search with full information sharing on large problem instances where computation time is limited.

AB - The trends of autonomous transportation and mobility on demand in line with large numbers of requests increasingly call for decentralized vehicle routing optimization. Multi-agent systems (MASs) allow to model fully autonomous decentralized decision making, but are rarely considered in current decision support approaches. We propose a multi-agent approach in which autonomous vehicles are modeled as independent decision makers that locally interact with auctioneers for transportation orders. The developed MAS finds solutions for a realistic routing problem in which multiple pickup and delivery alternatives are possible per order. Although information sharing is significantly restricted, the MAS results in better solutions than a centralized Adaptive Large Neighborhood Search with full information sharing on large problem instances where computation time is limited.

KW - Alternative locations

KW - Auctions

KW - Autonomous vehicle routing

KW - Multi-agent system

KW - Pickup and delivery problem

KW - Preferences

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

U2 - 10.1007/978-3-031-05359-7_20

DO - 10.1007/978-3-031-05359-7_20

M3 - Conference contribution

AN - SCOPUS:85129737839

SN - 978-3-031-05358-0

T3 - Lecture Notes in Logistics

SP - 244

EP - 260

BT - Dynamics in Logistics

A2 - Freitag, Michael

A2 - Kinra, Aseem

A2 - Kotzab, Herbert

A2 - Megow, Nicole

PB - Springer

T2 - LDIC 2022: 8th International Conference on Dynamics in Logistics (Virtual)

Y2 - 23 February 2022 through 25 February 2022

ER -

Los J, Schulte F , Spaan MTJ , Negenborn RR. An Auction-Based Multi-Agent System for the Pickup and Delivery Problem with Autonomous Vehicles and Alternative Locations. In Freitag M, Kinra A, Kotzab H, Megow N, editors, Dynamics in Logistics : Proceedings of the 8th International Conference LDIC 2022, Bremen, Germany. Springer. 2022. p. 244-260. (Lecture Notes in Logistics). doi: 10.1007/978-3-031-05359-7_20