Data-driven Optimization for Drone Delivery Service Planning
with Online Demand

It is common in optimization that a solution algorithm is tuned to a specific problem scenario by refining its parameters or policy to that scenario. Such tuning (or adaptation) need not come from research expertise and intuition. ML can assist an optimization algorithm to this end (Bengio et al., 2021). This direct assistance provided by ML can be analysed based on its motivation or on its structure. In terms of motivation, ML can either: (a) replace some heavy computation with a fast, reliable approximation or (b) explore the decision space (defined by the optimization model) and discover better policies. As for structure, the collaboration between ML and optimization can be sequential, whereby the ML model supports the optimization algorithm with valuable information. Or it can be parallel, wherein the ML and MP components work alongside each other. If one of the components works within the framework of the other, then the solutions of the nested component help the external one make better decisions.

Kruber et al. (2017) provide an illustration of the sequential implementation. They use supervised ML to decide if a given Dantzig-Wolf decomposition will be effective in solving instances of a mixed-integer linear programming (MILP) problem. Bonami et al. (2018) address a similar question. They employ supervised ML to determine if linearizing a given instance of a mixed integer quadratic programming problem will reduce solve time. An example of parallel implementation is found in Lodi and Zarpellon (2017). The ML model works within a branch-and-bound framework, and is used to make decisions about branching. Specifically, the goal of the ML component is to learn an efficient policy for selecting the branching variable and branching direction. Yilmaz and Büyüktahtakın (2024) address sequential combinatorial optimization problems in industrial contexts, where problem instances arise with slight parameter variations. A neural network generates a relaxed problem instance by predicting binding constraints, then uses this relaxed instance to eliminate infeasible predictions of decision variables through rapid feasibility checks. This reduces solution time by up to three orders of magnitude, while maintaining an optimality gap below 0.1%. Larsen et al. (2022) introduce a supervised ML model to quickly predict expected tactical descriptions of operational solutions in stochastic optimization. This addresses a common challenge in two-stage stochastic programming, where the second stage is computationally demanding. Their approach aids in solving the overall two-stage problem by circumventing the need for online generation of multiple second stage scenarios and solutions. Another implementation possibility is to leverage a MP formulation to aid an ML algorithm in the solution process. Tran-Thanh et al. (2012) employ an unbounded knapsack formulation to improve the performance of the $\epsilon$-greedy algorithm for multi-armed bandits, where the knapsack solution governs the probability of pulling a given arm of the bandit. A comprehensive overview of ML-enabled optimization methods is reported in Bengio et al. (2021).

Many decision-making problems deal with both prediction and optimization (or decision). These two tasks are complex on their own and are hence often treated separately and sequentially. The prediction model predicts the unknown parameters of the optimization model, which the latter uses to perform the optimization. ML has been a popular candidate for the prediction task in recent times. But the conventional approach is to train the ML prediction model to minimize the prediction error. This does not consider the nature and attributes of the successive optimization problem and may result in sub-optimal decisions (Elmachtoub and Grigas, 2022). As a brief but standard example, consider two possible paths between an origin O and a destination D. Travel times for both paths are unknown to the decision-maker, but may be predicted with contextual data (weather, congestion, etc.). Suppose the actual travel times are 10 and 20 minutes each, respectively. ML model 1 predicts travel times on the two paths to be 15 and 13 minutes (respectively), while ML model 2 predicts the same to be 30 and 40 minutes. Although model 1 has better accuracy, it causes a worse decision.

Two frameworks have been proposed which integrate prediction with optimization by taking the downstream optimization model into account (Yan and Wang, 2022). The first framework is called smart “predict, then optimize” (SPO), and it evaluates the performance of the ML prediction model based on the final decision error induced by the prediction made, not on the initial prediction error (Elmachtoub and Grigas, 2022). The authors propose a design which applies to the optimization of a linear objective functions over a convex feasible region. They introduce the SPO loss function which captures the decision error of a prediction by utilizing the objective function of the downstream optimization model. Since training with the SPO loss function can be cumbersome, a more manageable surrogate loss function called SPO+ loss is also introduced, which is equivalent to the original loss under specific conditions. The second framework, predictive prescriptions, aims to harness the joint distributions between decision variables and auxiliary data, both of which are uncertain (Bertsimas and Kallus, 2020). The principle of predictive prescriptions is to simulate various scenarios in which the values of the unknown parameters are estimated by the ML prediction model. These estimations lead to a cost in the optimization process, and the costs are weighted by the data-driven exploration of the scenarios. The optimal decision policy then minimizes the weighted sum costs thus generated. Both SPO and predictive prescriptions framework have been increasingly adopted by the scientific community and a survey of contextual optimization methods for decision-making under uncertainty is available in Sadana et al. (2023).

The benefits of e-commerce come with the challenges of online demand. By its dynamic and uncertain nature, online demand is difficult to fulfill. Failed first deliveries can account for up to $60\%$ of all orders for a service provider (Song et al., 2009), the primary reason being the absence of the customer during package handover. This is partially due to modern lifestyle changes such as increase in single person households and flexible (but demanding) work patterns. But a major contributing factor also is that no delivery time slot is explicitly agreed upon between the customer and the e-commerce retailer. This leads to several detrimental effects. If packages are left unattended then lack of security is a concern. Repeated deliveries or customers personally travelling to collection points result in economic losses as well as excess carbon emissions (Edwards et al., 2010). A high rate of unsatisfied or partially satisfied demand also strains driver-customer relationships (Masorgo et al., 2023). However, if a delivery time window is agreed upon through some form of online demand management, then the success of last mile deliveries is shown to increase (Van Duin et al., 2016).

Many studies dealing with online demand employ some form of heuristic approach to modify routes as and when new demand requests emerge. Hong et al. (2019) consider a shipping company that faces online demand, but delivers products to pre-determined collection centres that the customer must visit on their own. They implement an ant colony based heuristic which changes the previously decided collection centre for a particular customer in light of incoming demand requests. Mobility services also fall under stochastic and online demand, where the commodity sold is the route itself. Bertsimas et al. (2019) analyse online taxi ride-sharing with time windows for pickups. They employ a cost metric to measure waiting or empty driving time between customers. The network is pruned by keeping, for each customer, the top $k$ subsequent customers with the lowest costs. A maxflow heuristic is applied by reducing pickup time windows to a single randomly selected time instant. The resulting route arcs are retained, and the process is iteratively repeated until a specified number of arcs is reached. Finally, a mixed-integer formulation is applied to the modified network for obtaining results. Consolidation of delivery requests can also save costs by revealing efficient routes. Muñoz-Villamizar et al. (2024) explore stochastic demand where customer requests arrive daily. The city of operation is divided into regions, each with an expected customer density, estimated average velocity and travel distance per order. A region-specific postponement cost function is proposed for quantifying the delay of a request in a given region to a later date. A tabu-search metaheuristic modifies vehicle routes by identifying better (lower cost) routes in their local neighbourhood. The neighbourhood is traversed by applying insertion, swap and inversion operators that transform the customer sequence of a vehicle route.

Using ML to assist optimization was given much attention in the transport literature. The same-day delivery problem is a rich base for such joint implementations as mentioned in Section 2.1.1. Chen et al. (2023) study same-day delivery under fairness, dividing the service area into regions. Service availability is defined as the ratio of expected accepted requests per day to the expected overall number of requests. The objective is to maximize both the service availability in the entire area and the minimum service availability across all regions. The learning agent receives rewards for each fulfilled request, guiding it to improve its policy by considering changes in both components of the objective function. Feng et al. (2022) apply reinforcement learning to the real-time ride-sourcing problem with incorporation of public transport services. For every customer ride request, feasible routes are heuristically generated. For every driver capable of responding to the request, the learning agent estimates the perceived value of the route-driver pairs. Finally an integer linear program is solved to determine the optimal allocation of drivers to routes. If electric vehicles are involved, then charge depletion adds an additional factor of uncertainty. Basso et al. (2022) study the electric vehicle routing problem where both arrival of customer requests and energy consumption per unit road length are stochastic. Charging locations are deterministic. At each state of the MDP formulation, the reinforcement learning agent estimates the energy cost of moving to possible subsequent states and, in doing so, the probability of battery charge falling below a safety threshold.

The predict-then-optimize frameworks discussed in Section 2.1.2 have also been applied in stochastic transport optimization. Chu et al. (2021) implement the SPO method to solve the last-mile problem for an online food delivery service. They consider driver behaviour, traffic conditions and route lengths as input features to predict travel times. Simulated annealing is used to generate feasible routes, which are further updated with customer exchange operators to derive new routes. Baty et al. (2024) design a machine learning pipeline which relies on a downstream optimization component to improve predictions. The authors study the dynamic vehicle routing problem with time windows (VRPTW), where all requests must be fulfilled and fleet size is unlimited. They demonstrate that solving an equivalent prize-collecting VRPTW, where each unfulfilled customer is assigned a prize or profit, addresses this version of the VRP. An ML model determines the optimal allocation of prizes, yielding a near-optimal solution for the original problem. A hybrid genetic search algorithm solves the prize-collecting VRPTW based on input from the ML component. The ML model refines itself through a loss function, which measures the disparity between the target and acquired objective function values. The target objective value is derived by solving a static VRPTW from historical data, utilizing the same hybrid genetic search algorithm.

UAVs are cheaper to maintain, reduce labour and delay costs and have a lower carbon footprint compared to trucks. Amazon and Alibaba have been frontrunners in adopting UAVs for logistics, in moderate density urban regions and to deliver time-sensitive packages respectively. Many other companies across the world are following suit (Han et al., 2022). Additionally, a majority of customers in urban locations live close to a supermarket, and most delivery packages are relatively light-weight (Moshref-Javadi and Winkenbach, 2021). This includes food, beverages, groceries and also medical and pharmaceutical supplies, all of which have a perishability constraint which makes UAVs an attractive choice.

Levin and Rey (2023) explore the drone delivery service planning problem and propose a novel branch-and-price algorithm for its solution. They also design a reservation heuristic to generate feasible solutions expediently. Vlahovic et al. (2017) perform a case study of a UAV delivery model for pharmaceutical supplies, exhibiting cost reductions and improvements in service responsiveness. Retail facility placements can be improved when network design is conducted under the availability of a UAV delivery service (Baloch and Gzara, 2020). Liu (2019) propose a mixed integer programming formulation for online meal delivery using UAVs. The objective function penalizes excess battery depletion, motivates fast delivery and minimizes unnecessary movement for re-routing. The model is executed in a progressive rolling fashion across discrete time-steps. Chen et al. (2021) explore key strategic and tactical decisions for retailers implementing drone-based delivery operations, focusing on when to offer drone delivery and the appropriate pricing. Using a Markov decision process (MDP) framework, they introduce heuristic procedures to obtain near-optimal closed-form solutions efficiently. The aim is to assist online retailers in real-time decision-making regarding the feasibility and extent of offering drone-based delivery for specific product categories in various service zones. Additionally, they identify effective pricing strategies for drone-based deliveries. Payload delivery expands outside the realm of delivery to consumers. For example, UAVs can be used in precision agriculture, to simultaneously monitor crop sites and perform spraying tasks. This increases the efficiency of both pesticide and fertiliser use (Radoglou-Grammatikis et al., 2020).

The study of drone-only logistics also attracts ML-enriched solution strategies. Asadi et al. (2022) study drone delivery of medical supplies to hospitals, categorizing demand based on hospital distance from the drone hub. Each demand class includes a demand distribution and the required battery charge for successful delivery. The problem is formulated as a MDP where the system state is a vector containing the number of batteries at specific charge levels within the hub. The concise state expression allows reinforcement learning where a lookup table suffices for value function approximation. The action space involves charging batteries from lower to higher levels within decision epochs. This model optimizes battery usage, preserving charge for future deliveries and reducing replacement and charging costs. UAVs also have potential as a supplementary resource in two-echelon logistics networks. Li et al. (2024) study the last-mile delivery problem, where trucks transport goods from a primary depot to satellite depots, and UAVs complete the delivery to customers. Note that we categorize this study as drone-only logistics since trucks are treated as a stochastic externality. The stochastic nature of parcel arrival times at satellites is handled through Bayesian estimation, converting continuous arrival scenarios into discrete expected arrival intervals. A two-stage stochastic model is applied: parcel consolidation is first performed to release a subset for immediate delivery, and the remaining parcels are reserved for routing with future arrivals. Next, the route is treated as a particle in a particle swarm optimization problem. Reinforcement learning using search operators incrementally permutes the route in each iteration to discover better routes in the local neighbourhood.

The integration of UAVs into the logistic service fleet (together with conventional vehicles) can result in considerable benefits (Rejeb et al., 2023). Such a multi-modal delivery model decreases delivery times, overcomes traffic congestion and minimises human participation in the delivery process. Dayarian et al. (2020) investigate a same-day delivery model where a fleet of trucks is assisted by UAVs (through commodity resupply) at mutually determined meeting locations, allowing trucks to make longer trips before returning to the depot. Gu et al. (2023) investigate a single truck-and-drone scenario for online demand, consisting of deterministic delivery requests along with online pickup requests. The drone revisits the truck for resupply when needed, such revisits dividing the route into segments. An insertion heuristic compares the costs of placing pickup customers at various segments of the initial route. A $15\%$ increase in profits is reported, with UAVs contributing a $50\%$ increase in the acceptance rate of online requests. Yang et al. (2023) study a robust drone-truck delivery problem with customer time windows. They leverage the precision of drone routes to mitigate uncertainties in truck travel times caused by ground traffic congestion. Unlike Gu et al. (2023), here the truck remains at a customer location until the drone serves other customers and returns. Numerical experiments show that the drone-truck combination can safe-guard against the risk of failed deliveries due to unmet time windows. Rave et al. (2023) broaden the truck-drone route planning framework by introducing deployable drone launching stations known as microdepots. In this setup, trucks leave a central distribution centre equipped with both onboard drones and microdepots. The authors address a truck-drone fleet planning problem for a single logistics service provider using adaptive large neighbourhood search. Experiments demonstrate that mixed fleets provide cost-savings over a truck-only fleet, and that the cost-optimal choice of fleet composition and delivery method involves considering all possible combinations.

Heterogeneous fleets logistics, such as truck and drone models, also welcome ML-supported solutions. Chen et al. (2022) handle a mixed fleet of vehicles and UAVs to handle online requests. Network evolution is modelled as a MDP. Routing heuristics determine route feasibility by vehicle or drone, and deep reinforcement learning is then used to determine if a vehicle or a drone should be dispatched. Ghiasvand et al. (2024) tackle a two-echelon multi-trip truck-drone routing problem with uncertainty. Trucks make multiple trips from the depot to local distribution centres (LDCs), while UAVs make single trips from LDCs to customers. The research formulates a mixed-integer linear programming model to minimize total customer waiting times, managing uncertain customer demand through kernel-function based machine learning algorithms.

In an urban scenario, the operation environment of UAVs can mimic the road network. Buildings and other infrastructure can impede flight paths or require excessive energy to overcome aerially. But the airspace above roadways is generally free of obstructions. A possible drone flight network can be a map of the road traffic network itself, where links are above roads and nodes are above traffic intersections and several flight levels may be considered (Levin and Rey, 2023). We adopt this problem and context for the online DDSP.

The evolution of drone traffic in the network is represented as a sequential MDP moving through states. The state of the network captures all relevant information about its current structure. The state $s_{r}$ is constructed with the following components:

1. 1.

   $t_{r}$: The time step at which a new request arrives. This triggers the creation of a new state. Note that two successive requests may arrive several time steps apart i.e., $t_{r+1}-t_{r}\geq 1$.

2. 2.

   $\vec{r}$: The request vector contains details of the request. These are: the request sequence number, origin node, destination node, earliest departure time, time window of arrival at the destination, and request profit. We write $\vec{r}=(r,o_{r},d_{r},e_{r},[l_{r},u_{r}],p_{r})$.

3. 3.

   $\vec{\Theta}_{r}^{pre}$: The route vector $\vec{\theta}_{r}$ contains details of the drone route assigned to request $r$. The collection of all route vectors in state $s_{r}$ is $\vec{\Theta}_{r}^{pre}$. The composition of $\vec{\theta}_{r}$ reveals the request sequence number, the time of drone departure, and sequence of nodes in the route $(r,t_{o_{r}},[o_{r},\ldots,d_{r}])$. For sake of brevity, the sequence of nodes in the route is also denoted by $\mu_{r}=[o_{r},\ldots,d_{r}]$. It can be known if the request $r$ is active or idle based on whether $t_{o_{r}}$ lies within the current interval or without. If a request becomes active, its route vector is immune to any further change. If a request is fulfilled by the time the new state is triggered, its corresponding $\vec{\theta}_{r}$ is removed from $\vec{\Theta}_{r}^{pre}$.

Hence the state $s_{r}$ is represented as the tuple $s_{r}=(t_{r},\vec{r},\vec{\Theta}_{r}^{pre})$. Every interval witnesses the creation of as many states as there are request arrivals in that interval. Between the acceptance (and subsequent routing) or rejection of a request and the arrival of the successive request, the only change in the network is the movement of active drones as per their routes. Since this is a deterministic change (the routes of active drones are known and fixed), a new state need not be declared until the arrival of the next request.

After the arrival of a new request $r$ triggers the creation of state $s_{r}$, the agent must take an action $a_{r}$ from the feasible action space $\mathcal{A}(s_{r})$. The action space allows the rejection of request $r$, but also contains all possible ways in which request $r$ can be routed through the network, provided four conditions are met:

1. 1.

   The drone must not exceed the capacity of a link pre-occupied by other active drones.

2. 2.

   The drone must not, at any time-step, utilize a turn junction which is already utilized by an active drone at that time-step.

3. 3.

   The drone must not depart the request origin before $e_{r}$.

4. 4.

   The drone must reach the request destination within the time window $[l_{r},u_{r}]$.

The action space $\mathcal{A}(s_{r})$ also permits re-routing idle requests from previous intervals in order to accommodate request $r$ or to achieve a better objective value. The action taken is then represented as the tuple $a_{r}=(z_{r},\vec{\Theta}_{r}^{post})$ where $z_{r}$ is a binary decision regarding request $r$ and $\vec{\Theta}_{r}^{post}$ is the $updated$ collective route vector, which would include a route $\vec{\theta}_{r}$ for request $r$ if $z_{r}=1$. At a given state, action selection is done by the agent’s policy, which maps states to actions. Conventionally, a policy is represented as $\pi(a_{r}|s_{r})$, and governs the probability of taking action $a_{r}$ when in state $s_{r}$.

Accepting a request increases the value of the objective function and should therefore indicate a reward. The reward received in state $s_{r}=(t_{r},\vec{r},\vec{\Theta}_{r}^{pre})$ with action $a_{r}=(z_{r},\vec{\Theta}_{r}^{post})$ is simply:

This gives a reward of $p_{r}$ for accepting a request and a reward of 0 for rejecting it. Consequently, the reward accumulated over the course of interval $i\in I$ is given by $\sum\limits_{r\in\mathcal{R}_{C}^{i}}R(s_{r},a_{r})=\sum\limits_{r\in\mathcal{R}_{C}^{i}}z_{r}p_{r}$. The overall cumulative reward is $\sum\limits_{t_{r}\in[0,T]}z_{r}p_{r}$, which is equivalent to $\sum\limits_{r\in\mathcal{R}}z_{r}p_{r}$.

The state-action pair $(s_{r},a_{r})$ captures the process of taking an action $a_{r}$ while in a state $s_{r}$. In the application of ML under the MDP framework, every state-action pair is assigned a relative value in comparison to all other pairs. This value indicates the expected final objective (or reward) that can be achieved given that the agent occupies state $s_{r}$ and takes action $a_{r}$. The learning model presented in this study seeks to estimate the value of taking a certain action while occupying a certain state. In other words, it seeks to discover and exploit the action value function $Q(s_{r},a_{r})$. Thus “learning” is equivalent to improving the accuracy of the value estimations of $Q(s_{r},a_{r})$ to a satisfactory degree.

The transition to the next state occurs under transition probabilities $P^{a_{r}}_{s_{r}\rightarrow s_{r}^{\prime}}$. The transition probability determines which state the environment jumps to once the agent undertakes a specific action in the current state. There are many application scenarios where the transition probability matrix is either unknown to the agent, or the size of the state space prohibits its use. In such scenarios the agent can only control its policy, and has no prior knowledge of how the environment will react to its actions. The drone delivery network with online demand falls under this scenario.

As mentioned, the density of request arrival across the time horizon is due to a Poisson process with rate $\lambda$. The origins and destinations of the requests are generated via spatial distributions, the time windows of arrival at the destinations are governed by a temporal distribution, and the request profits are sourced from a profit distribution. However, the agent or network manager has no prior information about any of these distributions or the Poisson process. This makes the problem online and the nature of request arrival becomes exogenous to the agent.

The objective is to maximize the cumulative profit earned from requests served over the entire horizon. This is identical to maximizing the cumulative reward acquired in the MDP formulation. In MP terminology, this becomes:

This is equivalent to stating that the policy, out of the set of all policies $\Pi$, that maximizes the objective function, i.e. the expected total reward gained over the course of the time horizon, is $\pi^{*}$:

Here $A_{r}^{\pi}(s_{r})$ is the action taken by policy $\pi$ in state $s_{r}$. The state $s_{0}$ depicts the initial empty network where no request has yet arrived. Note that the limits of summation in (3) and (5) are slightly different because, unlike in (3), in (5) we emphasize operating upon requests sequentially to demonstrate the evolution of the MDP.

We use lookahead simulations to synthesize training data that will be used to train a predictive model which itself will be queried during the execution of the Surrogate ILP policy.

The priority of a link can be correlated to the frequency of link traversal by drones in a suitable span of time. Given a duration of network operation (e.g. $\delta$ intervals), crucial high priority links will experience large throughput and are likely to create bottlenecks which impede request acceptance. The link priority $\beta_{i,l}$ is therefore formally defined as the number of times link $l$ is traversed by incoming requests between the beginning of interval $i$ and the end of interval $i+\delta$.

Here $\chi^{r\uparrow,sol}_{l}(t)$ represents the routing solution value of the upstream-link variable $\chi^{r\uparrow}_{l}(t)$ for link $l$ and time $t$ at the end of each interval. We also define a vector $\bm{\vec{B}}$ to store link priority values for all intervals.

Link priority values as defined above are a function of drone traffic evolution in the network, which in turn depends on customer demand. From a snapshot of the network state at a certain time-step, the short-term future of the network may be estimated, provided historical patterns of customer demand are known. The introduction of the ML framework serves this purpose. We develop a supervised ML model which takes as input a snapshot of the network (number of drones occupying each link) and returns as output an estimate of link priorities for the near future. This input snapshot of link occupation is captured for the beginning of every time interval and is denoted by:

where $\Delta=\frac{\rho_{l}}{v}$ is the time taken by a drone to traverse link $l$. Eq. (10) increments the value of $s_{i,l}$ for every active drone occupying link $l$ at the beginning of interval $i$ (i.e., $t=(i-1)D$). We define a collection vector to store link occupancy values for all intervals.

$\bm{\vec{S}}$ serves as the input feature vector dataset and $\bm{\vec{B}}$ as the target output vector dataset while training the ML model. Once trained, it is deployed in the Surrogate ILP to estimate the values of $\beta_{i,l}$ which are subsequently used in the surrogate objective function (7). Note that in the training phase, all $\beta_{i,l}$ – and hence $\bm{\vec{B}}$ – are calculated via Eq. (8) to produce the output targets of the training dataset. In the testing and execution of the Surrogate ILP, however, the values of $\beta_{i,l}$ are predicted by the ML model.

In the training scheme, the number of training intervals is designed to be much larger than that in a test instance ($I_{training}>>I$). This is equivalent to processing several test instances successively without emptying the network between two consecutive test instances. At the beginning of each training interval $i$, the link occupancy on each link $l$ by currently active requests is calculated and stored in $s_{i,l}$. For this we define the function LinkActivity which computes $s_{i,l}$ as per Eq. (10). This function takes two inputs – the route $\mu_{r}$ of an active request and the link occupancy vector $\vec{\bm{s_{i}}}$ for the current interval. It iterates through the route to determine which link the UAV occupied at the beginning of the interval ($t=(i-1)D$) and increments the corresponding $s_{i,l}$ in $\vec{\bm{s_{i}}}$. Next, a lookahead is performed by virtually simulating the future of the network for the next $I_{virtual}$ number of intervals. For these intervals, virtual requests $\mathcal{R}_{V}$ are created, imitating historical data. These virtual requests are then routed through the network, obeying link capacity and conflict resolution constraints in the presence of active requests. The routes of successfully serviced virtual requests then contribute to the values of $\beta_{i,l}$ for interval $i$. For a link $l$, $\beta_{i,l}$ is equal to the number of times link $l$ was traversed by virtual requests in the lookahead simulation. This captures the perceived priority of link $l$ in the foreseeable near future, from the perspective of the network at interval $i$, in accordance with Eq. (8), with $\delta=I_{virtual}$. We define the function BetaUpdate, which takes two inputs: the route $\mu_{r}$ of a virtual request and the link priority vector $\vec{\bm{\beta_{i}}}$ for the current interval, and updates $\beta_{i,l}$ for all the links that this request traverses according to $\mu_{r}$ .

Once the virtual lookahead is complete, all virtual request paths are erased from the network. Thereafter, the process resembles the Myopic ILP. Idle requests from previous intervals and incoming requests of current interval $i$ are routed. Successfully accepted requests are stored in $\mathcal{R}_{\checkmark}$. Successful paths $\mu_{r}$ for a given request $r$ are also stored in a route vector $\theta_{r}=(r,t_{o_{r}},\mu_{r})$ and added to the collective route vector $\vec{\Theta}$. Then the next interval $i+1$ is initiated.

We use $k$-Nearest Neighbors ($k$NN) regression to train a predictive model for estimating relative link priority based on network snapshots. The $k$NN regressor is a supervised ML algorithm used for prediction tasks. It predicts the output target value of a new data point by considering the average or weighted average of its $k$ nearest neighbors in the input feature space. The $k$NN algorithm utilizes a defined distance metric, such as the Euclidean distance, to measure the similarity between data points in the input feature space. By identifying the $k$ training feature vectors closest to a new data point, the algorithm establishes the nearest neighbors of the given data point. The prediction of the target value of the new data point is made by averaging or weighting the target values associated with its $k$ nearest neighbors, leveraging the assumption that closer points in the feature space exhibit similar target values. The $k$NN multi-output regressor extends the concept of the $k$NN regressor to handle multiple target values for each data point. Notably, the $k$NN regressor is non-parametric and makes minimal assumptions about the underlying data distribution, making it more versatile in handling diverse datasets. It can also capture non-linear relationships between input features and output targets. We use the training data synthesized using the lookahead simulation procedure described in Section 4.3.1 to train the $k$NN regressor.

In practice, the training phase has an associated time budget, implying that link priority values must be estimated expediently. Solving the Myopic ILP for $I_{training}$ intervals demands excessive time and memory. Levin and Rey (2023) propose a reservation heuristic which routes incoming customer requests quickly. This heuristic is used within the training phase. We illustrate the reservation heuristic and formalize the training scheme in Algorithm 3.

The original spatial network $G=(N,A)$ can be converted into a spatio-temporal network $G^{T}$ as demonstrated in Figure 3. $G^{T}$ is the time-expanded dual graph of $G$. To construct $G^{T}$, the nodes and links are extended across time through discrete time levels and connections are made on the basis of link travel times. Suppose a link in $G$ connects node $n_{1}$ to node $n_{2}$ and can be traversed in $\Delta t$ time steps. Then it connects two nodes $\Delta t$ time levels apart in $G^{T}$. The graph $G^{T}$ can be viewed as a network of node-time tuples ($n,t$), where $n$ denotes the node and $t$ is the time level on which it is located. The reservation heuristic works by routing customer requests on $G^{T}$ using a shortest-path finding algorithm. The route is then “reserved” for that request by securing link capacity in space-time, making that capacity unavailable for other requests. Since turn conflict constraints must also be respected in $G^{T}$, the heuristic removes connectivity between node-time tuples whenever constraints (1e)–(1f) and (1h)–(1l) are violated. Algorithm 2 defines the function NewReservation which discovers a path $\mu_{r}^{T}$ for request $r$, makes the relevant reservations in $G^{T}$ and deduces the corresponding path $\mu_{r}$ in $G$. Two additional functions are also required in the training phase. A request may already have a path, but reservations for this path may either need to be made or erased. We use functions Reserve($\mu_{r}^{T},G^{T}$) and EmptyReservation($\mu_{r}^{T},G^{T}$) for these purposes respectively. They follow a similar procedure to NewReservation and are hence not illustrated.