A Dispatching Policy for the Dynamic and Stochastic Pickup and Delivery Problem

摘要

Real-time vehicle routing problems arise in a number of applications spanning from couriers to emergency services. In this article, we present a new dispatching policy for the dynamic and stochastic pickup and delivery problem, in which a fleet of vehicles must service a set of dynamically occurring customers requests that are partitioned in several classes (according to their priority). The basic idea of our policy is to reserve a fraction of the fleet capacity to the top prior classes that deserve to be serviced as soon as possible. Moreover, our dispatching policy is parameterized and the optimal parameter setting is determined by solving an offline training problem on a sample of the instance population. To asses the quality of our approach, we compare it with two policies already proposed in the literature, namely a reactive and an anticipatory procedure. Computational results on randomly-generated instances indicate that our procedure can often match the quality of an anticipatory algorithm with a computational effort comparable to that of a reactive approach.