AI for Retail: On-Demand Last-Mile Logistics

project image

People

Maximilian Kronmueller
Prof. Javier Alonso-Mora - Autonomous Multi-Robot Lab (AMR) TU Delft
Andres Fielbaum - Key collaborator

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. Part of the labs research focuses on On-Demand Last-Mile Logistics or Falsh Deliveries. 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 ot Flash Delivery operations

Related Publications

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 web
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.

web pdf
Abstract: 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
X. Bai, A. Fielbaum, M. Kronmuller, L. Knoedler, J. Alonso-Mora. In IEEE Transactions on Automation Science and Engineering (T-ASE), 2022.

web pdf
Abstract: 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.

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.

web pdf
Abstract: 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.

web pdf
Abstract: 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.

web pdf video
Abstract: 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.

web pdf video
Abstract: 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.