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.