Optimal Delay in Networks with Controlled Mobility

We consider a network in which a set of vehicles is responsible for the pickup and delivery of messages that arrive according to Poisson process with message pickup and delivery locations distributed uniformly at random in a region of bounded area A. The vehicles are required to pickup and deliver the messages so that the average delay is minimized. In this paper, we provide lower bounds on the delay achievable by fully controlled policies, depending on the information constraint in place. We prove that for any policies in which only the source location information is known upon message arrival, the optimal average delay scaling is Θ(λ(n)A/v2n). If in addition to source location, destination locations of messages are known to the vehicles, the optimal average delay scaling can be reduced to Θ(λ(n)A/v2n 3/2 ). We note that these scaling bounds are achievable given the service policies we have previously described in [1].