Multi-agent Pickup and Delivery Planning with Transfers

Abstract

In Pickup and Delivery Problems (PDPs), mobile vehicles retrieve and deliver a set of items. The PDP is a well-studied, NP-hard problem. Examples of the PDP include mail and courier services, taxis, ridesharing services, and robots such as our own CoBots and CreBots, which retrieve and deliver items for the occupants of a building, and are the motivation for this thesis. The goal of the PDP is to find a schedule that delivers as many items as possible at the lowest cost, under various constraints such as time windows and vehicle capacities. We augment the PDP with transfers to form the PDP with Transfers (PDP-T). Instead of having a single vehicle retrieve and deliver each item, vehicles can transfer items to other vehicles (or chains of vehicles) for delivery. Allowing transfers makes lower cost solutions feasible, but increases the number of possible schedules exponentially. In this thesis, we contribute a series of algorithms to form schedules for variants of the PDP-T. We introduce the Very Large Neighborhood Search with Transfers (VLNS-T) algorithm to plan schedules for the most general version of the PDP-T, with constraints including time windows, capacities, vehicle start and end locations, maximum item transport times, and maximum vehicle route durations. We also contribute algorithms for simplified variants of the PDP-T, which take advantage of the problem structure to find solutions more quickly and more effectively than the general algorithm for specific PDP-T variants, some with provable guarantees. We also study the challenges of deploying PDP-T schedules on physical robots, and execute PDP-T schedules on the CoBots. The robots reschedule their tasks in response to new requests, delays, failures, and shared information from other robots. We also introduce the CreBots, which transfer items fully autonomously. Our PDP-T algorithms are evaluated on benchmark problems, on the CoBots, and on problems on city maps sampled from real world taxi data, demonstrating that lower cost schedules can be found with transfers.