EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Fair collaborative vehicle routing: A deep multi-agent reinforcement learning approach

Stephen Mak, Liming Xu, Tim Pearce, Michael Ostroumov, Alexandra Brintrup

Transportation Research Part C: Emerging Technologies · 2023-12 · 157 · 104376

DOI: 10.1016/j.trc.2023.104376 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Transportation Research Part C: Emerging Technologies, 2023-12. Verfasst von Stephen Mak und 4 weiteren Autor:innen. Die Arbeit wurde bisher 31-mal zitiert (Crossref) und nennt 68 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Engineering and Physical Sciences Research Council, Science and Technology Facilities Council.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Collaborative vehicle routing occurs when carriers collaborate through sharing their transportation requests and performing transportation requests on behalf of each other. This achieves economies of scale, thus reducing cost, greenhouse gas emissions and road congestion. But which carrier should partner with whom, and how much should each carrier be compensated? Traditional game theoretic solution concepts are expensive to calculate as the characteristic function scales exponentially with the number of agents. This would require solving the vehicle routing problem (NP-hard) an exponential number of times. We therefore propose to model this problem as a coalitional bargaining game solved using deep multi-agent reinforcement learning, where - crucially - agents are not given access to the characteristic function. Instead, we implicitly reason about the characteristic function; thus, when deployed in production, we only need to evaluate the expensive post-collaboration vehicle routing problem once. Our contribution is that we are the first to consider both the route allocation problem and gain sharing problem simultaneously - without access to the expensive characteristic function. Through decentralised machine learning, our agents bargain with each other and agree to outcomes that correlate well with the Shapley value - a fair profit allocation mechanism. Importantly, we are able to achieve a reduction in run-time of 88%.

Förderung

  • Engineering and Physical Sciences Research Council
  • Science and Technology Facilities Council

Zitieren

APA

Mak, S., Xu, L., Pearce, T., Ostroumov, M., & Brintrup, A. (2023). Fair collaborative vehicle routing: A deep multi-agent reinforcement learning approach. Transportation Research Part C: Emerging Technologies, 157, 104376. https://doi.org/10.1016/j.trc.2023.104376

Vancouver

Mak S, Xu L, Pearce T, Ostroumov M, Brintrup A. Fair collaborative vehicle routing: A deep multi-agent reinforcement learning approach. Transportation Research Part C: Emerging Technologies. 2023;157:104376. doi:10.1016/j.trc.2023.104376

BibTeX
@article{Mak2023,
  author = {Mak, Stephen and Xu, Liming and Pearce, Tim and Ostroumov, Michael and Brintrup, Alexandra},
  title = {Fair collaborative vehicle routing: A deep multi-agent reinforcement learning approach},
  journal = {Transportation Research Part C: Emerging Technologies},
  year = {2023},
  volume = {157},
  pages = {104376},
  doi = {10.1016/j.trc.2023.104376}
}
Kostenlos starten →