Dynamic Pickup and Delivery Problems with Insights About Demand-Responsive Transportation Systems

In the last decade, unmanned vehicles have been used increasingly in a number of surveillance and remote sensing applications, to observe and classify unknown “events” which occur in a large workspace over the course of a long mission. Foremost in this domain are unmanned aerial vehicles, or UAVs, which are a major focus for military air forces and also have increasingly non-military applications such as monitoring of livestock, pipelines, or wildfires.

An integral consideration for unmanned vehicle systems is the inherent trade-off between the operating costs—e.g. the number of vehicles in the fleet—and some “quality-of-service” provided—e.g., the average duration between the occurrence of an “event” and the time it is observed. In the past two decades, researchers have developed scalable autonomy for fleets of autonomous vehicles in various scenarios; and by applying techniques from the study of Queuing Theory, they have explicitly quantified the trade-off between fleet size and system performance. Remarkably, they have proved fundamental limitations for fleet performance, showing that their own algorithms are within a constant factor of the best performance that one could possibly achieve.

But autonomous vehicles are finding uses in new domains all the time. With the explosion of e-commerce in the last decade—and with anticipation of continued growth in the near future—large distributors like Amazon and Buy.com are faced with the challenge of scaling their inventory to satisfy never before seen volumes of orders. Scaling their inventory demands scaling their solutions for inventory handling; in other words, the systems which move goods between supply, storage, and shipment on a warehouse floor. Small autonomous, robotic vehicle have been deployed in warehouses in recent years, replacing conventional systems composed largely of static conveyor belts. (Scalability is also particularly relevant in the urban transportation setting, as urban population density continues to increase: As self-driving cars become increasingly reliable in the future, we should anticipate their use as an alternative means for transportation, replacing traditional taxi and courier services.)

This project considers developing scalable autonomy (with provably good performance) for such emerging applications; i.e., applications involving the transport of objects within a physical workspace. Unfortunately, the previous literature, while yielding important guidelines and intuition, is remarkably limited for transportation problems where vehicles have limited carrying capacity.

One fundamental question of the project is: Given a robot with unit carrying capacity and a random process generating demands for transportation—each from a random origin point to a random destination point—can the vehicle be used to ensure that the number of demands waiting for service does not grow unbounded? Our initial investigations have produced a checkable condition that decides this question exactly—i.e., yes, or no—under certain assumptions; and it also provides some valuable insight about the amount of time the vehicle spends either with a passenger on board or without. (The latter condition is generally regarded as an indicator of inefficiency in a transport system, but we have shown that some amount of “empty” time is actually completely unavoidable.)