Fair collaborative vehicle routing: A deep multi-agent reinforcement learning approach
作者: Stephen Mak, Liming Xu, Tim Pearce, Michael Ostroumov, Alexandra Brintrup
分类: cs.LG
发布日期: 2023-10-26
备注: Final, published version can be found here: https://www.sciencedirect.com/science/article/pii/S0968090X23003662
期刊: Volume 157, December 2023, 104376
DOI: 10.1016/j.trc.2023.104376
💡 一句话要点
提出深度多智能体强化学习解决公平协作车辆路径规划问题
🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)
关键词: 协作车辆路径规划 深度强化学习 多智能体系统 博弈论 收益分配 路径优化 去中心化学习
📋 核心要点
- 现有方法在解决协作车辆路径规划时，计算复杂度高，无法有效处理多个代理的合作与补偿问题。
- 本文提出将协作车辆路径规划建模为合作博弈，通过深度多智能体强化学习实现代理间的协商与收益分配。
- 实验结果表明，所提方法在运行时间上减少了88%，且与Shapley值的相关性较高，显示出良好的公平性与效率。
📝 摘要（中文）
协作车辆路径规划是指承运商通过共享运输请求并相互执行运输请求来实现合作。这种方式可以实现规模经济，从而降低成本、温室气体排放和道路拥堵。然而，如何选择合作伙伴以及如何进行合理的补偿是一个挑战。传统的博弈论解决方案计算复杂，随着代理数量的增加，特征函数呈指数级增长。本文提出将该问题建模为一个合作博弈，通过深度多智能体强化学习进行求解，且代理不直接访问特征函数，而是隐式推理。我们的贡献在于首次同时考虑了路径分配和收益分配问题，并且在没有访问特征函数的情况下实现了高效求解。通过去中心化的机器学习，代理之间进行协商，达成与Shapley值高度相关的结果，运行时间减少了88%。
🔬 方法详解
问题定义：本文解决的是协作车辆路径规划中的路径分配和收益分配问题。现有方法在计算特征函数时复杂度高，难以高效求解。
核心思路：通过深度多智能体强化学习，代理在没有直接访问特征函数的情况下进行隐式推理，实现协商与收益分配。
技术框架：整体框架包括多个智能体，代理通过去中心化的学习机制进行协商，形成合作策略。主要模块包括状态表示、策略学习和收益分配机制。
关键创新：首次同时考虑路径分配和收益分配问题，且不依赖于计算复杂的特征函数，显著降低了计算成本。
关键设计：采用深度强化学习算法，设计了适应性的损失函数和网络结构，以优化代理间的协商过程和收益分配效果。具体参数设置和网络结构细节在实验部分进行了详细描述。
🖼️ 关键图片
📊 实验亮点
实验结果显示，所提方法在运行时间上减少了88%，且在收益分配上与Shapley值的相关性较高，表明该方法在公平性和效率上均有显著提升，优于传统博弈论方法。
🎯 应用场景
该研究的潜在应用领域包括物流运输、共享经济和智能交通系统等。通过优化车辆路径规划，可以有效降低运输成本和环境影响，提升运输效率，具有重要的实际价值和社会意义。
📄 摘要（原文）
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%.