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 not given access to the characteristic function. Instead, we 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%.

合作式车辆路径规划是通过共享交付信息并代表其它公司执行交付请求，以实现规模经济，从而降低成本、温室气体排放和道路拥堵。通过将该问题建模为一种联盟谈判游戏，我们提出了一种可扩展且考虑了公司自利性质的分散式方法，代理人使用改进的独立近距离策略优化方法进行学习，在正确识别最优联盟方面的准确性达到79％，平均最优解差距为4.2％，运行时间减少了62％。

强化学习在合作车辆路径规划中的应用