An Online Approach to Solve the Dynamic Vehicle Routing Problem with Stochastic Trip Requests for Paratransit Services
An Online Approach to Solve the Dynamic Vehicle Routing Problem with Stochastic Trip Requests for Paratransit Services
复制标题
DOI：
10.48550/arxiv.2203.15127
复制
发表时间：
2022-03
期刊：
影响因子：
--
通讯作者：
Michael Wilbur;S. U. Kadir;Youngseo Kim;Geoffrey Pettet;Ayan Mukhopadhyay;Philip Pugliese;Samitha Samaranaya
中科院分区：
文献类型：
--
作者：
Michael Wilbur;S. U. Kadir;Youngseo Kim;Geoffrey Pettet;Ayan Mukhopadhyay;Philip Pugliese;Samitha Samaranaya
许多运营辅助运输和微型运输服务的运输机构必须对实时到达的出行请求做出响应，这需要解决不确定性下的组合和顺序决策问题。为了避免导致长期显著低效率的决策，车辆应通过优化非近视效用函数或通过将请求放在一起并优化近视效用函数来分配。虽然前一种方法通常是离线的，但后者可以在线执行。我们指出了两个主要问题，这种方法时，适用于辅助客运服务在实践中。首先，很难将辅助传输请求批处理在一起，因为它们在时间上是稀疏的。第二，运输机构运作的环境是动态变化的（例如，交通状况可以随时间改变），导致离线学习的估计变得陈旧。为了解决这些挑战，我们提出了一个完全在线的方法来解决动态车辆路径问题（DVRP）的时间窗口和随机出行请求，是强大的不断变化的环境动态建设。我们专注于场景中的请求是相对稀疏的，我们的问题是由应用程序paratransit服务的动机。我们将DVRP表示为马尔可夫决策过程，并使用蒙特卡罗树搜索来评估任何给定状态的操作。在优化非近视效用函数的同时考虑随机请求在计算上具有挑战性;事实上，这种问题的动作空间在实践中非常大。为了解决大的动作空间，我们利用问题的结构来设计算法，可以对树搜索的有希望的动作进行采样。我们的实验使用真实世界的数据，从我们的合作伙伴机构表明，所提出的方法优于现有的国家的最先进的方法，无论是在性能和鲁棒性。
Many transit agencies operating paratransit and microtransit ser-vices have to respond to trip requests that arrive in real-time, which entails solving hard combinatorial and sequential decision-making problems under uncertainty. To avoid decisions that lead to signifi-cant inefficiency in the long term, vehicles should be allocated to requests by optimizing a non-myopic utility function or by batching requests together and optimizing a myopic utility function. While the former approach is typically offline, the latter can be performed online. We point out two major issues with such approaches when applied to paratransit services in practice. First, it is difficult to batch paratransit requests together as they are temporally sparse. Second, the environment in which transit agencies operate changes dynamically (e.g., traffic conditions can change over time), causing the estimates that are learned offline to become stale. To address these challenges, we propose a fully online approach to solve the dynamic vehicle routing problem (DVRP) with time windows and stochastic trip requests that is robust to changing environmental dynamics by construction. We focus on scenarios where requests are relatively sparse-our problem is motivated by applications to paratransit services. We formulate DVRP as a Markov decision process and use Monte Carlo tree search to evaluate actions for any given state. Accounting for stochastic requests while optimizing a non-myopic utility function is computationally challenging; indeed, the action space for such a problem is intractably large in practice. To tackle the large action space, we leverage the structure of the problem to design heuristics that can sample promising actions for the tree search. Our experiments using real-world data from our partner agency show that the proposed approach outperforms existing state-of-the-art approaches both in terms of performance and robustness.