In recent years, Flash Delivery services have gained great popularity. Flash Delivery is a service where goods of daily need can be ordered on-demand and subsequently are delivered to the customer within a short time window, for example, in the next ten minutes. Operational efficiency and cost management are vital for sustainability in this competitive landscape, especially in the long term. To this end, this thesis aims to improve operational planning for Flash Delivery Operations. It focuses on two fundamental questions critical for the success of Flash Deliveries: the associated Vehicle Routing Problem and the associated Fleet Sizing Problem. The Vehicle Routing Problem aims to determine how to best utilize a given fleet of vehicles to deliver the requested orders efficiently, while the Fleet Sizing Problem involves finding the optimal number of vehicles required to serve the given demand. The primary objective of this dissertation is to provide algorithmic contributions, specifically focusing on optimizing vehicle routing and fleet sizing for Flash Delivery services.
First, the Flash Delivery Problem is formally defined and modeled as a Markov Decision Process. This serves as the basis for the dissertation's research and subsequent investigations. The thesis then proposes a novel routing algorithm for Flash Deliveries from multiple depots, which effectively handles multiple depots for order pick-up and dynamically determines the optimal depot for each order. The depots are distributed within the city, for example, using existing stores, this differs from other logistical processes using large warehouses outside of the city. Additionally, this approach allows vehicles to visit depots to load additional orders before distributing their loaded ones, resulting in more agile planning. The scalability of this method is demonstrated in scenarios involving thousands of orders and tens of vehicles.
The proposed routing method is then extended to accommodate heterogeneous vehicles and heterogeneous modes of transportation. Experiments using a fleet featuring trucks and drones demonstrate that this approach serves more orders while requiring less total traveled distance compared to a state-of-the-art method for heterogeneous vehicles. The effects of fleet size and fleet composition between drones and trucks are also examined. More drones were able to deliver more requests at the cost of an increase in traveled distance.
The Fleet Sizing Problem represents the second major challenge addressed in this dissertation. The balance between having too many vehicles, which can be very expensive, and having too few, which leads to unmet promises and undelivered orders, is crucial for operational success. Typically, the Fleet Sizing Problem involves a fixed set of tasks with no flexibility in their execution. However, this thesis introduces a novel problem, adding flexibility in time through the allowance of slight delays in individual transportation tasks. We propose modeling and solving the novel problem as a Mixed Integer Linear Program. By incorporating this flexibility, the problem opens up a broader trade-off space between the required number of agents, traffic, and added delays. As a result, fleet sizes can be significantly decreased. To illustrate the practical application of this algorithm, a case study involving taxi rides in Manhattan is presented.
To conclude this thesis, fleet sizing is combined with the previously proposed routing methods for Flash Delivery, resulting in a novel approach. Our method groups individual delivery requests and generates optimized operational plans using a variation of the earlier proposed routing techniques. These plans are then used for fleet sizing. To assess the effectiveness of our approach, we compare it against applying routing and fleet sizing separately. The results clearly demonstrate the value of our proposed method.
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.
In summary, this thesis makes significant contributions to the operational optimization of Flash Delivery services by addressing key challenges in vehicle routing and fleet sizing. We propose novel methods to improve efficiency and effectiveness in planning Flash Delivery operations.