On Dynamic Vehicle Routing With Time Constraints
On Dynamic Vehicle Routing With Time Constraints
复制标题
DOI：
10.1109/tro.2014.2344451
复制
发表时间：
2014-08
影响因子：
7.8
通讯作者：
S. Bopardikar;Stephen L. Smith;F. Bullo
中科院分区：
文献类型：
--
作者：
S. Bopardikar;Stephen L. Smith;F. Bullo
我们考虑的问题下，服务需求的精确时间约束的动态车辆路径。需求是在环境中顺序生成的，并且每个需求都需要在其生成后的固定有限时间间隔之后被精确地服务。我们设计的服务车辆的路由策略，以最大限度地提高在稳定状态下的需求服务的比例。主要贡献如下。首先，我们证明了这个问题是由一个适当的有向无环图结构，导致一个计算效率高的路由算法的基础上的最长路径计算。其次，在假设需求是均匀随机产生的环境中，并通过泊松过程的时间，我们提供了两个分析下界的最长路径策略的服务分数。第一个界限是相对于最优的非因果版本的政策，即，基于所有未来需求请求的知识的策略。第二个界限是车辆动力学和需求生成率的显式函数，因此，可用作设计工具。最后，我们提出了数值结果来支持解析界。
We consider the problem of dynamic vehicle routing under exact-time constraints on servicing demands. Demands are sequentially generated in an environment, and every demand needs to be serviced exactly after a fixed finite interval of time after it is generated. We design routing policies for a service vehicle to maximize the fraction of demands serviced at steady state. The main contributions are as follows. First, we demonstrate that this problem is described by an appropriate directed acyclic graph structure which leads to a computationally efficient routing algorithm based on a longest-path computation. Second, under the assumption of the demands being generated uniformly randomly in the environment and via a Poisson process in time, we provide two analytic lower bounds on the service fraction of the longest path policy. The first bound is relative to an optimal noncausal version of the policy, i.e., a policy based on knowledge of all future demand requests. The second bound is an explicit function of the vehicle dynamics and demand generation rate and, therefore, useful as a design tool. Finally, we present numerical results to support the analytic bounds.