Abstract Summary
Delivery drivers on bikes and vans are a considerable amount of traffic in city centers. Reducing their amount while satisfying residents' needs is a challenge many modern cities face. The new trend of flash-deliveries, where customers order and get their goods within minutes started to contribute to this. In this paper, we investigate same-day delivery operations, specifically with small time windows between ordering and delivery. The problem features the opportunity to pick up goods at multiple local depots, for example, supermarkets within a city, and allows vehicles to perform depot returns prior to being empty, if beneficial. This allows for more agile planning and on average shorter distance to the next depot, resulting in fewer vehicles and traffic. We propose a novel dynamic method for online task assignment and routing, where we aim to deliver orders as fast as possible, minimally within the same day. In each time step (every few seconds or minutes) the following is executed. First, for each order potential pick-up locations are identified and feasible trips, i.e., sequences to pick up goods and deliver orders, are calculated. Then, trips are assigned to vehicles by solving an integer linear program. We simulate one day of service in Amsterdam, compare results to different strategies, and test different scenarios with up to 35 autonomous vehicles, 25 depots, and 10,500 orders. Results underpin the advantages of the proposed method and show its versatility with respect to different situations.