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.

@en

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.@en

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.

@en

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.@en

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.

@en

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.

@en

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.

@en

The IceCube Neutrino Observatory is able to measure the all-flavor neutrino flux in the energyrange between 100 GeV and several PeV. Due to the different features of the neutrino interactionsand the geometry of the detector, all high-level analyses require a selection of suitable events asa first step. However, presently, no algorithm exists that gives a generic prediction of an event’sunderlying interaction type. One possible solution to this is the use of deep neural networkssimilar to the ones commonly used for 2D image recognition. The classifier that we present hereis based on the modern InceptionResNet architecture and includes multi-task learning in orderto broaden the field of application and increase the overall accuracy of the result. We provide adetailed discussion of the network’s architecture, examine the performance of the classifier forevent type classification and explain possible applications in IceCube.@en