Mar, 2022

解决城市接送服务中随机请求动态车辆路径问题的在线方法

PDF
TL;DR本文提出了一种解决动态车辆路径问题（DVRP）的方法，该方法适用于时间窗口和随机旅行请求，并针对局部交通服务应用。此外，该方法利用了问题的结构设计了启发式算法以便搜索具有很好前景的行动。实验表明，该方法在性能和鲁棒性方面均优于现有最先进的方法。
transit agencyparatransit servicesvehicle routing problemmonte carlo tree searchstochastic requests
发现论文，激发创造
  • 离线车辆路径问题与在线预定：一个新的问题描述及其在患者运输中的应用

    本文研究了一种基于离线车辆路径规划的在线客运服务问题，该问题考虑了灵活的接送时间窗口和实时订车，并提出了一种结合任意算法和基于学习的策略，比现有算法在实现更好的结果的求解方法。

    Apr, 2022

  • 实时车辆位置问题

    本文提出一种新颖的问题：如何在空间和时间上变化的情况下放置车辆以实时满足乘客的需求。研究者使用了四个主要美国城市一千万次乘车请求的数据集，证明了这种请求具有显著的自我相似性，并提出了分布式在线学习算法用于解决实时车辆定位的问题，并且通过观察到的自相似性，确定了算法的预期性能边界。

    Dec, 2017

  • 基于神经网络的动态规划算法应用于顺风车拼车

    本文提出了一种基于 Approximate Dynamic Programming (ADP) 的方法，使用神经网络近似值函数，并展示了与 Deep Reinforcement Learning 的联系，以应对近实时 ride-pooling 问题中整数线性规划和组合复杂性，并在实际数据集上表现出比之前方法高达 16％的效果，显著改进了城市交通问题。

    Nov, 2019

  • 自适应可变需求的自主路由和取货问题的多智能体强化学习

    提出了一个通过自适应路由策略降低等待时间、考虑未来需求以及能够适应不同需求分布的自主汽车调度和接送框架，该框架通过线上游戏算法和线下逼近方案相结合，在美国旧金山的实际出租车需求中得到了验证。

    Nov, 2022

  • 信息采集车辆路径问题：应对紧急风暴响应的随机优化

    本文提出了一种具有信息收集和信念建模能力的随机车辆路径问题的解决方案，该方案可以使用电话来创建有关停电的信仰，并使用实用车辆作为收集其他信息的机制。并使用蒙特卡罗树搜索 (MCTS) 来生成实际策略。实验结果表明，该策略比标准行业启发式方法更快地恢复了电网。

    May, 2016

  • 基于事件的深度强化学习应用于动态车辆调度问题

    本文提出了一种基于半马尔可夫决策过程和离散事件模拟的动态车辆调度问题解决方法，并在纽约市的真实场景下进行了数值实验，结果显示相对于其他启发式策略，该方法的平均等待时间减少了 50%。

    Jul, 2023

  • 使用模型增强的强化学习优化出租车车队的随机路由

    本论文提出了一种基于模型的派遣算法、基于高性能模型无关的强化学习算法和将自顶向下方法和模型无关强化学习的优点结合的新型混合算法，以路线优化策略的形式为车队提供路线规划，研究了面对实时、随机需求的情况下，在小到中型的道路网络中，对街道叫车服务的路线进行优化；使用基于代理的大规模微观仿真平台，评估了提出的算法在人工道路网络和社区基础新加坡道路网络中的表现，结果显示出基于模型的派遣算法、基于高性能模型无关的强化学习算法和混合算法在性能上均表现出色，并且混合算法可以显著加速模型无关学习者的学习过程。

    Oct, 2020

  • 具有软时间窗口的多车辆路径规划问题：一种多智能体强化学习方法

    这篇论文提出了一种基于强化学习的名为 “Multi-Agent Attention Model” 的算法，能够利用较长的离线训练时间快速解决城市物流配送中必不可少的 “多车辆路径问题（MVRPSTW）”，该算法以车辆旅游生成过程为基础，提出了一种具有注意力层的编码器 - 解码器框架来迭代地生成多辆车的路径，通过对不同规模的合成网络进行评估，证明该算法的效果优于谷歌 OR-Tools 和传统方法，并验证了模型的稳健性。

    Feb, 2020

  • 促进动态车辆路径问题中的双边公平性

    我们提出了一个新的框架，即双方公平感知遗传算法（2FairGA），该算法将基因算法从仅关注效用的原始目标扩展到同时包含双方公平性的多个目标。大量实验证明我们提出的框架优于现有技术水平。

    May, 2024

  • 具上下文的随机时间窗车辆路径规划

    我们研究了带时间窗的车辆路径问题（VRPTW）和随机旅行时间，在做出路径决策之前，决策者观察相关的上下文信息，表示为特征变量。尽管有大量有关随机 VRP 的文献，但在此情境中对特征变量的整合受到了限制的关注。我们介绍了上下文随机 VRPTW，该问题在观察到的特征条件下最小化总运输成本和预期迟到惩罚。由于旅行时间和特征的联合分布是未知的，我们提出了使用历史数据提供问题的近似解的新型数据驱动规定模型。我们区分了基于点的近似、样本平均近似和惩罚近似这些规定模型，并从不同角度处理随机旅行时间和特征问题。我们开发了专门的分枝 - 定价割算法来解决这些数据驱动的规定模型。在我们的计算实验中，我们比较了不同方法在多达一百个客户的实例上的样本外成本性能。我们的结果表明，令人惊讶的是，一个基于特征的样本平均近似在大多数设置中优于现有方法和新方法。

    Feb, 2024