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

• URL: http://arxiv.org/abs/2310.17485v1
• Date: Thu, 26 Oct 2023 15:42:29 GMT
• Title: Fair collaborative vehicle routing: A deep multi-agent reinforcement learning approach
• Authors: Stephen Mak, Liming Xu, Tim Pearce, Michael Ostroumov, Alexandra Brintrup
• Abstract summary: Collaborative vehicle routing occurs when carriers collaborate through sharing their transportation requests and performing transportation requests on behalf of each other. Traditional game theoretic solution concepts are expensive to calculate as the characteristic function scales exponentially with the number of agents. We propose to model this problem as a coalitional bargaining game solved using deep multi-agent reinforcement learning.
• Score: 49.00137468773683
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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%.

Related papers

• Coalitional Bargaining via Reinforcement Learning: An Application to Collaborative Vehicle Routing [49.00137468773683]
  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.
  arXiv  Detail & Related papers  (2023-10-26T15:04:23Z)
• Using Reinforcement Learning for the Three-Dimensional Loading Capacitated Vehicle Routing Problem [40.50169360761464]
  Collaborative vehicle routing has been proposed as a solution to increase efficiency. Current operations research methods suffer from non-linear scaling with increasing problem size. We develop a reinforcement learning model to solve the three-dimensional loading capacitated vehicle routing problem in approximately linear time.
  arXiv  Detail & Related papers  (2023-07-22T18:05:28Z)
• Safe Model-Based Multi-Agent Mean-Field Reinforcement Learning [48.667697255912614]
  Mean-field reinforcement learning addresses the policy of a representative agent interacting with the infinite population of identical agents. We propose Safe-M$3$-UCRL, the first model-based mean-field reinforcement learning algorithm that attains safe policies even in the case of unknown transitions. Our algorithm effectively meets the demand in critical areas while ensuring service accessibility in regions with low demand.
  arXiv  Detail & Related papers  (2023-06-29T15:57:07Z)
• Multi-Agent Neural Rewriter for Vehicle Routing with Limited Disclosure of Costs [65.23158435596518]
  Solving the multi-vehicle routing problem as a team Markov game with partially observable costs. Our multi-agent reinforcement learning approach, the so-called multi-agent Neural Rewriter, builds on the single-agent Neural Rewriter to solve the problem by iteratively rewriting solutions.
  arXiv  Detail & Related papers  (2022-06-13T09:17:40Z)
• Independent Reinforcement Learning for Weakly Cooperative Multiagent Traffic Control Problem [22.733542222812158]
  We use independent reinforcement learning (IRL) to solve a complex traffic cooperative control problem in this study. To this, we model the traffic control problem as a partially observable weak cooperative traffic model (PO-WCTM) to optimize the overall traffic situation of a group of intersections. Experimental results show that CIL-DDQN outperforms other methods in almost all performance indicators of the traffic control problem.
  arXiv  Detail & Related papers  (2021-04-22T07:55:46Z)
• Vehicular Cooperative Perception Through Action Branching and Federated Reinforcement Learning [101.64598586454571]
  A novel framework is proposed to allow reinforcement learning-based vehicular association, resource block (RB) allocation, and content selection of cooperative perception messages (CPMs) A federated RL approach is introduced in order to speed up the training process across vehicles. Results show that federated RL improves the training process, where better policies can be achieved within the same amount of time compared to the non-federated approach.
  arXiv  Detail & Related papers  (2020-12-07T02:09:15Z)
• Equitable and Optimal Transport with Multiple Agents [48.17429789586127]
  We introduce an extension of the Optimal Transport problem when multiple costs are involved. We aim to share equally between agents the work of transporting one distribution to another. Another point of view is when the goal is to partition equitably goods between agents according to their heterogeneous preferences.
  arXiv  Detail & Related papers  (2020-06-12T15:15:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.