Dynamic Vehicle Routing with Stochastic Time Constraints
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 ac...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers
2011
|
| Online Access: | http://hdl.handle.net/1721.1/65357 https://orcid.org/0000-0002-0505-1400 |
| Summary: | 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. |
|---|