Optimizing for Transfers in a Multi-vehicle Collection and Delivery Problem

We address the Collection and Delivery Problem (CDP) with multiple vehicles, such that each collects a set of items at different locations and delivers them to a dropoff point. The goal is to minimize either delivery time or the total distance traveled. We introduce an extension to the CDP: what if a vehicle can transfer items to another vehicle before making the final delivery? By dividing the labor among multiple vehicles, the delivery time and cost may be reduced. However, introducing transfers increases the number of feasible schedules exponentially. In this paper, we investigate this Collection and Delivery Problem with Transfers (CDP-T), discuss its theoretical underpinnings, and introduce a two-approximate polynomial time algorithm to minimize total distance travelled. Furthermore, we show that allowing transfers to take place at any location for the CDP-T results in at most a factor of two improvement. We demonstrate our approximation algorithms on large simulated problem instances. Finally, we deploy our algorithms on robots that transfer and deliver items autonomously in an office building.