Dynamic vehicle routing with stochastic time constraints

Marco Pavone, Emilio FrazzoliICRA 2010 · OpenReview

Abstract

In this paper we study a dynamic vehicle routing problem where demands have stochastic deadlines on their waiting times. Specifically, a network of robotic vehicles must service demands whose time of arrival, location and on-site service are stochastic; moreover, once a demand arrives, it remains active for a stochastic amount of time, and then expires. An active demand is successfully serviced when one of the vehicles visits its location before its deadline and provide the required on-site service. The aim is to find the minimum number of vehicles needed to ensure that the steady-state probability that a demand is successfully serviced is larger than a desired value, and to determine the policy the vehicles should execute to ensure that such objective is attained. First, we carefully formulate the problem, and we show its well-posedness by providing some novel ergodic results. Second, we provide a lower bound on the optimal number of vehicles; finally, we analyze two service policies, and we show that one of them is optimal in light load. Simulation results are presented and discussed.
BibTeX
@inproceedings{pavone2010dynamic,
  author = {Marco Pavone and Emilio Frazzoli},
  title = {{Dynamic vehicle routing with stochastic time constraints}},
  booktitle = {IEEE International Conference on Robotics and Automation},
  year = {2010},
  url = {https://openreview.net/forum?id=1mfMTUkRDby},
}

Loading related content...

Figure