AI for Retail: On-Demand Last-Mile Logistics

project image

People

Maximilian Kronmueller - PhD candidate
Andres Fielbaum - Postdoctoral researcher
Prof. Javier Alonso-Mora

Funding

This project is funded by Ahold Delhaize.

More Links
Project Website

About the Project

The AI for Retail (AIR) Lab Delft is a joint TU Delft-Ahold Delhaize industry lab. A major focus of this lab’s research is on improving on-demand last-mile logistics or flash deliveries. These are essential to ensure goods can be transported in a timely manner. More specifically, two fundamental questions critical for the success of these operations are tackled: the associated Vehicle Routing Problem and the associated Fleet Sizing Problem. This project aims to contribute algorithms to improve efficiency and effectiveness in the planning of flash delivery operations.

One method developed during this project focuses on anticipatory routing which derives predicted requests from historical data. These requests are used to understand inherent patterns in the demand. A dynamic vehicle routing solver combines these predictions with the already known requests to assign them to a fleet of vehicles. Simulation experiments are conducted to understand the effectiveness of the proposed method. The results suggested that on an average, vehicles travel shorter distances while requiring a smaller number of vehicles in comparison to other existing methods.

Another method developed for vehicle routing focuses on deliveries from multiple local stores with an aim to deliver orders as fast as possible within the same day. Previous research assumed robots have to deliver all loaded orders first before servicing new customers. This assumption was removed in this approach adn helps to incorporate new occuring orders within the existing plan of these robots. An optimisation method is proposed which firstly decides which local store is the most optimal to collect each order and then robots are allowed to visit a depot again to receive more parcels if it increases efficiency. The proposed method is scalable to scenarios with thousands of requests.

Project Demonstrations

Funding & Partners

This project is funded by Ahold Delhaize.

Fleet Sizing for the Flash Delivery Problem from Multiple Stores: a Case Study in Amsterdam
Maximilian Kronmueller, Andres Fielbaum, Javier Alonso-Mora. In IEEE International Conference on Intelligent Transportation Systems (ITSC), 2024.

pdf
In this paper, we present an approach for fleet sizing in the context of flash delivery, a time-sensitive delivery service that requires the fulfilment of customer requests in minutes. Our approach effectively combines individual delivery requests into groups and generates optimized operational plans that can be executed by a single vehicle or autonomous robot. The groups are formed using a modified routing approach for the flash delivery problem. Combining the groups into operational plans is done by solving an integer linear problem. To evaluate the effectiveness of our approach, we compare it against three alternative methods: fixed vehicle routing, non- pooled deliveries and a strategy encouraging the pooling of requests. The results demonstrate the value of our proposed approach, showcasing its ability to optimize the fleet size and improve operational efficiency. Our experimental analysis is based on a real-world dataset provided by a Dutch retailer, allowing us to gain valuable insights into the design of flash delivery operations and to analyze the effect of the maximum allowed delay, the number of stores to pick up goods from and the employed cost functions.

Reducing the Minimal Fleet Size by Delaying Individual Tasks
Maximilian Kronmueller, Andres Fielbaum, Javier Alonso-Mora. In IEEE Transactions on Intelligent Transportation Systems, 2024.

pdf publisher
This work formally defines the problem of fleet sizing with delays (FSD), where the option of delaying individual tasks within fleet sizing is considered. We prove that the FSD problem is NP-hard and solve a formulation of the FSD problem as a mixed integer linear problem (MILP). We then analyze the proposed method in detail in an abstract case and validate it in a case study of taxi rides in Manhattan. We show that fleet sizes can be decreased significantly and that the trade-off space of the number of required vehicles to execution time and added delay can be enlarged.

Online flash delivery from multiple depots
M. Kronmuller, A. Fielbaum, J. Alonso-Mora. In Transportation Letters, 2023.

publisher pdf
We study routing for on-demand last-mile logistics with two crucial novel features: i) Multiple depots, optimizing where to pick-up every order, ii) Allowing vehicles to perform depot returns prior to being empty, thus adapting their routes to include new orders online. Both features result in shorter distances and more agile planning.We propose a scalable dynamic method to deliver orders as fast as possible. Following a rolling horizon approach, each time step the following is executed. First, define potential pick-up locations and identify which groups of orders can be transported together, with which vehicle and following which route. Then, decide which of these potential groups of orders will be executed and by which vehicle by solving an integer linear program. We simulate one day of service in Amsterdam that considers 10,000 requests, compare results to several strategies and test different scenarios. Results underpin the advantages of the proposed method.

Group-based Distributed Auction Algorithms for Multi-Robot Task Assignment
Xiaoshan Bai, Andres Fielbaum, Maximilian Kronmuller, Luzia Knoedler, Javier Alonso-Mora. In IEEE Transactions on Automation Science and Engineering (T-ASE), 2023.

publisher pdf
This paper studies the multi-robot task assignment problem in which a fleet of dispersed robots needs to efficiently transport a set of dynamically appearing packages from their initial locations to corresponding destinations within prescribed time-windows. Each robot can carry multiple packages simultaneously within its capacity. Given a sufficiently large robot fleet, the objective is to minimize the robots' total travel time to transport the packages within their respective time-window constraints. The problem is shown to be NP-hard, and we design two group-based distributed auction algorithms to solve this task assignment problem. Guided by the auction algorithms, robots first distributively calculate feasible package groups that they can serve, and then communicate to find an assignment of package groups. We quantify the potential of the algorithms with respect to the number of employed robots and the capacity of the robots by considering the robots' total travel time to transport all packages. Simulation results show that the designed algorithms are competitive compared with an exact centralized Integer Linear Program representation solved with the commercial solver Gurobi, and superior to popular greedy algorithms and a heuristic distributed task allocation method.

Online Multi-Robot Task Assignment with Stochastic Blockages
N. Wilde, J. Alonso-Mora. In IEEE Conference on Decision and Control (CDC), 2022.

pdf
In this paper we study the multi-robot task assignment problem with tasks that appear online and need to be serviced within a fixed time window in an uncertain environment. For example, when deployed in dynamic, human centered environments, the team of robots may not have perfect information about the environment. Parts of the environment may temporarily become blocked and blockages may only be observed on location. While numerous variants of the Canadian Traveler Problem describe the path planning aspect of this problem, few work has been done on multi-robot task allocation (MRTA) under this type of uncertainty. In this paper, we introduce and theoretically analyze the problem of MRTA with recoverable online blockages. Based on a stochastic blockage model, we compute offline tours using the expected travel costs for the online routing problem. The cost of the offline tours is used in a greedy task assignment algorithm. In simulation experiments we highlight the performance benefits of the proposed method under various settings.

Routing of Heterogeneous Fleets for Flash Deliveries via Vehicle Group Assignment
M. Kronmueller, A. Fielbaum, J. Alonso-Mora. In Proc. 2022 IEEE - Int. Conf. on Intelligent Transportation (ITSC), 2022.

publisher pdf
This paper presents a novel approach to route heterogeneous fleets for flash delivery operations. Flash deliveries offer to serve customers’ wishes in minutes. We investigate a scenario that allows to pick up orders at multiple depots with a heterogeneous vehicle fleet leveraging different modes of transportation. We propose the Heterogeneous Vehicle Group Assignment (HVGA) method, which, given a problem state, identifies potential pick-up locations, calculates potential trips for all modes of transportation and last chooses from the set of potential trips. Experiments to analyze the proposed method are executed using a fleet featuring two modes of transportation, trucks and drones. We compare to a state-of-the-art method. Results show that HVGA is able to serve more orders while requiring less total traveled distance. Further, the effects of the fleet size and fleet composition between drones and trucks are examined by simulating three hours of a flash delivery operation in the city center of Amsterdam.

Anticipatory routing methods for an on-demand ridepooling mobility system
A. Fielbaum, M. Kronmueller, J. Alonso-Mora. In , Transportation, 2021.

publisher pdf
On-demand mobility systems in which passengers use the same vehicle simultaneously are a promising transport mode, yet difficult to control. One of the most relevant challenges relates to the spatial imbalances of the demand, which induce a mismatch between the position of the vehicles and the origins of the emerging requests. Most ridepooling models face this problem through rebalancing methods only, i.e., moving idle vehicles towards areas with high rejections rate, which is done independently from routing and vehicle-to-orders assignments, so that vehicles serving passengers (a large portion of the total fleet) remain unaffected. This paper introduces two types of techniques for anticipatory routing that affect how vehicles are assigned to users and how to route vehicles to serve such users, so that the whole operation of the system is modified to reach more efficient states for future requests. Both techniques do not require any assumption or exogenous knowledge about the future demand, as they depend only on current and recent requests. Firstly, we introduce rewards that reduce the cost of an assignment between a vehicle and a group of passengers if the vehicle gets routed towards a high-demand zone. Secondly, we include a small set of artificial requests, whose request times are in the near future and whose origins are sampled from a probability distribution that mimics observed generation rates. These artificial requests are to be assigned together with the real requests. We propose, formally discuss and experimentally evaluate several formulations for both approaches. We test these techniques in combination with a state-of-the-art trip-vehicle assignment method, using a set of real rides from Manhattan. Introducing rewards can diminish the rejection rate to about nine-tenths of its original value. On the other hand, including future requests can reduce users’ traveling times by about one-fifth, but increasing rejections. Both methods increase the vehicles-hour-traveled by about 10%. Spatial analysis reveals that vehicles are indeed moved towards the most demanded areas, such that the reduction in rejections rate is achieved mostly there.

On-demand Grocery Delivery From Multiple Local Stores With Autonomous Robots
M. Kronmueller, A. Fielbaum, J. Alonso-Mora. In Proc. 3rd IEEE International Symposium on Multi-Robot and Multi-Agent Systems (MRS'21), 2021.

publisher pdf video
The advances in the area of autonomous delivery robots combined with customers' desire for fast delivery, bare potential for same-day delivery operations, specifically with small time windows between ordering and delivery. Most same-day deliveries are operated using a single depot and with vehicles' routes planned and fixed when leaving the depot. In this paper, we relax these two assumptions and focus on on-demand grocery delivery using a fleet of autonomous vehicles or robots. The problem features the opportunity to pick up goods at multiple local stores or depots, for example, supermarkets within the city, and allows robots 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. We propose a novel dynamic method for the same-day delivery problem, 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: For each order potential pick-up locations are identified and feasible trips, i.e., sequences to pick up goods and deliver orders, are calculated. To assign trips to robots an integer-linear program is solved. We simulate one day of service in a city under different conditions with up to 30 autonomous robots, 30 depots and 10,500 orders. Results underpin the advantages of the proposed method and show its versatility with respect to different situations.

Anticipatory Vehicle Routing for Same-Day Pick-up and Delivery using Historical Data Clustering
J. van Lochem, M. Kronmueller, P. van 't Hof, J. Alonso-Mora. In Proc. IEEE Int. Conf. on Intelligent Transportation Systems (ITSC), 2020.

publisher pdf video
In this paper we address the problem of same-day pick-up and delivery where a set of tasks are known a priori and a set of tasks are revealed during operation. The vehicle routes are precomputed based on the known and predicted requests and adjusted online as new requests are revealed. We propose a novel anticipatory insertion method which incorporates a set of predicted requests to beneficially adjust the routes of a fleet of vehicles in real-time. Requests are predicted based on historical data, which is clustered in advance. We exploit inherent patterns of the demand, which are captured by historical data and include them in a dynamic vehicle routing solver based on heuristics and adaptive large neighborhood search. The proposed method is evaluated using numerical simulations on a variety of real-world problems with up to 1655 requests per day. Their degree of dynamism ranges from 0.70 to 0.93. These instances represent dynamic multi-depot pickup and delivery problems with time windows. The method has shown to require less driven kilometers than comparable methods.