Fair collaborative vehicle routing: A deep multi-agent reinforcement
  learning approach
Stephen Mak Liming Xu Tim Pearce Michael Ostroumov Alexandra Brintrup
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%.