Timezone: »

Coalitional Bargaining via Reinforcement Learning: An Application to Collaborative Vehicle Routing
Stephen Mak · Liming Xu · Tim Pearce · Michael Ostroumov · Alexandra Brintrup
Event URL: https://openreview.net/forum?id=W0EYBnJ8-3 »

Collaborative Vehicle Routing is where delivery companies cooperate by sharing their delivery information and performing delivery requests on behalf of each other. This achieves economies of scale and thus reduces cost, greenhouse gas emissions, and road congestion. But which company should partner with whom, and how much should each company be compensated? Traditional game theoretic solution concepts, such as the Shapley value or nucleolus, are difficult to calculate for the real-world problem of Collaborative Vehicle Routing due to the characteristic function scaling exponentially with the number of agents. This would require solving the Vehicle Routing Problem (an NP-Hard problem) an exponential number of times. We therefore propose to model this problem as a coalitional bargaining game where --- crucially --- agents are \emph{not} given access to the characteristic function. Instead, we \emph{implicitly} reason about the characteristic function, and thus eliminate the need to evaluate the VRP an exponential number of times --- we only need to evaluate it once. Our contribution is that our decentralised approach is both scalable and considers the self-interested nature of companies. The agents learn using a modified Independent Proximal Policy Optimisation. Our RL agents outperform a strong heuristic bot. The agents correctly identify the optimal coalitions 79\% of the time with an average optimality gap of 4.2\% and reduction in run-time of 62\%.

Author Information

Stephen Mak (University of Cambridge)
Liming Xu
Tim Pearce (University of Cambridge)
Michael Ostroumov
Alexandra Brintrup (University of Cambridge)

More from the Same Authors

  • 2021 : Counter-Strike Deathmatch with Large-Scale Behavioural Cloning »
    Tim Pearce · Jun Zhu
  • 2018 : Poster Session 1 »
    Stefan Gadatsch · Danil Kuzin · Navneet Kumar · Patrick Dallaire · Tom Ryder · Remus-Petru Pop · Nathan Hunt · Adam Kortylewski · Sophie Burkhardt · Mahmoud Elnaggar · Dieterich Lawson · Yifeng Li · Jongha (Jon) Ryu · Juhan Bae · Micha Livne · Tim Pearce · Mariia Vladimirova · Jason Ramapuram · Jiaming Zeng · Xinyu Hu · Jiawei He · Danielle Maddix · Arunesh Mittal · Albert Shaw · Tuan Anh Le · Alexander Sagel · Lisha Chen · Victor Gallego · Mahdi Karami · Zihao Zhang · Tal Kachman · Noah Weber · Matt Benatan · Kumar K Sricharan · Vincent Cartillier · Ivan Ovinnikov · Buu Phan · Mahmoud Hossam · Liu Ziyin · Valerii Kharitonov · Eugene Golikov · Qiang Zhang · Jae Myung Kim · Sebastian Farquhar · Jishnu Mukhoti · Xu Hu · Gregory Gundersen · Lavanya Sita Tekumalla · Paris Perdikaris · Ershad Banijamali · Siddhartha Jain · Ge Liu · Martin Gottwald · Katy Blumer · Sukmin Yun · Ranganath Krishnan · Roman Novak · Yilun Du · Yu Gong · Beliz Gokkaya · Jessica Ai · Daniel Duckworth · Johannes von Oswald · Christian Henning · Louis-Philippe Morency · Ali Ghodsi · Mahesh Subedar · Jean-Pascal Pfister · RĂ©mi Lebret · Chao Ma · Aleksander Wieczorek · Laurence Perreault Levasseur