A Dynamic Pickup and Delivery Problem in Mobile Networks under Information Constraints

This paper considers a network in which a set of vehicles is responsible for picking up and delivering messages that arrive according to a Poisson process. Message pickup and delivery locations are uniformly distributed in a convex region. The vehicles are required to pickup and deliver the messages so that the average delay is minimized. It is required that the vehicle that picks up a message must be the one to deliver it. This problem is called the dynamic pickup and delivery problem (DPDP) and has applications in the context of autonomous vehicles and wireless ad hoc networks. The control policies considered are separable into two parts: an assignment policy used by a centralized controller to assign arriving messages to the vehicles for service and a service policy used by each vehicle to determine the service routes through its assigned messages. Lower bounds are provided on the delay achievable by separable control policies that depend on the information constraints in place. It is proved that the optimal average delay scaling can be reduced when message destination information is available to the centralized controller in addition to the message source information. The paper also provides policies that achieve these scaling bounds, proving that these bounds are tight.