Speed-Aware Network Design: A Parametric Optimization Approach

Expedite delivery services are becoming increasingly important for e-commerce supply chains such as Amazon, Alibaba and Walmart as they improve directly customer experience and can indirectly contribute to attaining key sustainability goals. Indeed, the option of expedite delivery increases naturally the range of items customers are willing to purchase from e-commerce platforms instead of visiting physical retail (brick-and-mortar) shops, and this has been found to reduce transportation-based carbon emissions in many scenarios [23, 21]. These reasons contribute to a growing volume of research aiming to improve expedite delivery by means of last-mile routing optimization [17], vehicle dispatch scheduling [16], or innovative crowd-shipping models [8], among others.

Nevertheless, the above works overlook the role of the middle-mile network connecting warehouses (origins) to distribution centers (destinations) in the efficacy and feasibility of such expedite delivery services. As the demand grows, items have to be stored at out-of-city warehouses, and therefore, the possibility of offering expedite delivery for these items is shaped by the network connections. This situation creates an unavoidable tension between cost and speed when designing the transportation network. To reduce costs we need to minimize the number of trucks used to ship orders to customers. Such a goal can be achieved by leveraging intermediate consolidation hubs between origin and destination nodes. Consider the example from Figure 1, where we have nine commodities – one for each origin-destination pair – requiring one-third of truck’s capacity. By utilizing intermediate consolidation hubs, the network configuration from Figure 1 requires only seven trucks to route packages. In contrast, serving these same nine commodities through speed-paths – i.e., paths directly connecting origins to destinations – would require nine trucks, one for each origin-destination pair. To tackle the tradeoff between volume consolidation and opening speed-paths, many studies formulate the middle-mile network design problem as a minimum-cost flow problem with maximum path-length constraints, or aim to balance transit times with path costs (see Sec. 1.2).

Yet, a key factor that has been largely overlooked is the effect of the network connectivity on the share of inventory for which we can offer expedite deliver services. In this paper, we propose to measure such an effect by evaluating the network’s speed-coverage, which we define as the number of unique items that can be delivered in 1-day. Speed-coverage is a function of ($a$) the network topology which determines the transit time from origins to destinations and ($b$) the inventory stored at origin nodes. We recognize an inherent tradeoff: connecting an origin to a destination via a short route (speed-path) increases the speed-coverage, but may increase routing cost by making volume consolidation more difficult. Additionally, the benefit of speed-paths to speed-coverage exhibits diminishing returns. The more speed-paths we introduce, the less their differential impact to the overall speed-coverage objective. In this work, we formulate a problem that captures exactly these tradeoffs and then propose a technique to solve for the jointly optimal routing costs and speed-coverage for the general case when origins have partially overlapping inventory. To the best of our knowledge, this paper is the first to introduce a mathematical formulation of these tradeoffs, and a scalable methodology for solving the optimization problem.

As the importance of, and demand for, expedite delivery services grows, the design of speed-aware middle-mile networks becomes an increasing priority for service providers. Prior works on network design that cater for delivery speed include the hub-network design problem with time-definite delivery. In this setting, the objective is to decide hub locations together with routing paths, and speed deadlines are captured through path-eligibility constraints, see e.g., [7]. Similarly, [27] optimizes the location of hubs, assignment of demand centers to hubs, and the vehicle routing. Expanding on these ideas, [25] considers additionally hub capacity constraints; [3] studies a single-hub overnight delivery system and optimizes routing subject to timing constraints; and [28] focuses on express air-service and decides which routes to operate with the company-owned cargo planes and how much capacity to purchase on commercial flights. Finally, [14] studies the middle-mile consolidation problem with delivery deadlines while accounting for consolidation delays. Similar models have been studied in the context of scheduled service network design that optimizes small (less-than-truckload) inter-city shipments with timing constraints for the delivery or intermediate hops, see [15] and references therein. All the above works model the delivery time requirements through path-length constraints, e.g., a subset of origin-destination nodes are forced to be connected via paths that have transit time smaller than a predefined threshold. In contrast to this binary approach of enforcing time constraints, our work explicitly optimizes the tradeoff between speed and cost, providing a flexible framework for network design decisions.

Time-expanded graphs are one of the most common tools for capturing such timing restrictions but increase the problem’s dimension and compound their solution, cf. [19]. This modeling approach augments the dimension of the problem and therefore its complexity. For this reason, several approaches based on decomposition methods [26, 11], adaptive discretization techniques [5], and model condensation strategies [19] have been proposed. The key difference of our approach from these prior works is that we explicitly consider the overlap of inventory at origins to determine the number of unique items that are eligible for a 1-day delivery option. We do not assume to have an analytical model that captures how the delivery speed affects the inventory, but instead we provide a practical methodology for directly incorporating data-sets and look-up tables in the optimization problem. A key element of our strategy is a parametric linear model [2] which allows to express the inventory function in a compact and tractable form. Parametric optimization has been particularly successful for a range of applications, see [22], but, to the best of the authors knowledge has not been employed for expedite delivery optimization in middle-mile networks.

Jointly optimizing network design decisions and speed-coverage is a challenging problem. First of all, the network design problem, even without the speed-coverage objective, is already NP-hard to solve optimally when one has to ($a$) use unsplittable paths, ($b$) add integer link capacities (trucks), and ($c$) consider a large number of multi-hop path variables, [9, 10]. Secondly, the inventory effect of each new speed-path depends on which other origins are connected to a desination. In other words, speed-path assignment decisions are coupled across all origins serving a certain destination, but also across origins that use intersecting (at one or more edges) paths due to the edge capacities. Third, the inventory coverage function – i.e., the function mapping a set of origins to the number of unique items stored at these nodes – does not admit a convenient analytical expression. In fact, this function depends on the inventory overlap at origins, and in practice can be calculated using inventory datasets and look-up tables. This function format, unfortunately, does not facilitate – actually prohibits – its direct inclusion in the network optimization program, as it renders the problem highly nonlinear – see equation (4) from Section 2 for further details.

Our method relies on multi-parametric optimization [12, 22] to create a continuous (concave) approximation of the inventory function. This uses as input the available inventory data-points – i.e., the number of unique items stored at a set of origin nodes – and creates a continuous piecewise affine interpolation over the convex combination of the input data-points. We prove that this approximation is exact at the input data-points, and hence can serve as a meaningful proxy for maximizing this metric of interest. This, in turn, enables the inclusion of the inventory function in the network design problem, without inflating it with new discrete variables. The result of this new joint formulation is a speed-aware middle-mile network, where the designer can tradeoff network costs with the number of unique items that can be delivered to customers in 1-day. Finally, we take an extra step to reduce the dimension of this problem through a sampling process, namely a low-complexity practical algorithm for selecting the approximation data-points used to approximate inventory overlap at origin nodes.

In summary, the main contributions of this paper are as follows: $(i)$ We introduce the speed-aware network design problem of jointly optimizing network costs and speed-coverage, which we define as the share of unique items for which we can offer a 1-day delivery option. $(ii)$ We introduce a parametric-based modeling approach for enabling this joint optimization, overcoming the lack of a tractable analytical expressions for the number of unique items stored at a set of origin nodes. $(iii)$ We further propose a simple and practical sampling algorithm for reducing the size of the approximation problem, trading off interpolation accuracy in a systematic fashion. $(iv)$ The proposed joint model and approximation strategy are evaluated numerically in extensive tests on representatives scenarios.

The rest of this paper is organized as follows. Section 2 introduces the speed-aware minimum cost Multicommodity Capacitated Network Design problem under study. Section 3 describes the proposed reformulation based on a parametric interpolation, and the related approximation strategy; and Section 4 presents a series of numerical experiments with representative scenarios and different network sizes. We conclude and present future works in Section 5.

Throughout the paper we define the sets of (non-negative) reals and integers as (${ℝ}_{+}^n$)${ℝ}^n$ and (${\mathbb{Z}}_{+}^n$)${\mathbb{Z}}^n$, respectively. Vectors are denoted by boldface lowercase letters and sets by uppercase italic letters, e.g., $𝒗\in {ℝ}^n$ and $𝒞$. Given a set of vectors $𝒞=\{{𝒗}_1,{𝒗}_2\}$, we denote the cardinality of $𝒞$ as $|𝒞|$ and its convex hull as $\text{Cvx}(𝒞)$. Finally, we define the vectors of zeros ${\mathrm{𝟎}}_n\in {ℝ}^n$, ones ${\mathrm{𝟏}}_n\in {ℝ}^n$, and the unit base vector of zeros having one only in the $i$th component as ${𝒆}_n^i={[0,\mathrm{\dots },0,1,0,\mathrm{\dots },0]}^{\top }\in {ℝ}^n$.

We first introduce the standard minimum cost Multicommodity Capacitated Network Design with Unsplittable demands (MCND-U) problem, which aims to assign one path to each commodity and open trucks on links to transport orders at minimum cost. Our network is modeled with a directed graph $𝒢=(𝒱,ℰ)$, where $𝒱=𝒪\cup 𝒟\cup \mathscr{H}$ is the set of nodes, consisting of the set $𝒪$ of $n_O$ origins, the set $𝒟$ of $n_D$ destinations and the set $\mathscr{H}$ of $n_H$ other interim nodes (or hubs), and $ℰ$ is the set of directed links. We are given a set $𝒦$ of $K$ commodities, where each commodity $k=(o_k,d_k)$ originates from an origin $o_k\in 𝒪$ towards a destination $d_k\in 𝒟$, and has volume $v_k\ge 0$. We are also given a set of active network paths $𝒫$, where ${𝒫}_k$ is used to denote the active paths of commodity $k$ and ${𝒫}_{k\ni e}\subseteq {𝒫}_k$ the active commodity $k$ paths that traverse link $e\in ℰ$. Our goal is to assign exactly one path to each commodity and we do so using the path selection vector $\text{x}=\left(x_p\in \{0,1\},p\in 𝒫\right)$.¹¹1We do not need to index variables $x$ with commodities because each path $p$ can only be used by a single commodity, the one that corresponds to the origin-destination pair of the path. Furthermore, the links have capacities that depend on our choice of opened trucks, where opening a truck costs $c_e$ on link $e\in ℰ$ and adds capacity $V_e\in {ℝ}_{+}^n$. We use the truck deployment vector $\text{y}=\left(y_e\in {𝐙}_{+},e\in ℰ\right)$ to decide how many trucks are opened on each link. The minimum cost MCND-U problem is to assign paths to commodities with x and open trucks with y in order to transport the volumes at a minimum cost:

Problem ${\mathbb{P}}_1$ is the standard MCND-U problem studied in the literature, for instance see [13], which is known to be NP–hard [9, 10] – See Section 1.3 for details.

In this work we augment the MCND-U problem with a novel speed model, that captures the number of customer orders that can be delivered within a day, a service that is called Next Day Delivery (NDD), see [4]. Let us consider a destination node $d$, which serves a number of customers in a given area. Whenever a customer in that area makes an order, we say that the order is covered (with NDD service) if the ordered item is stored in any of the origins that are connected to $d$ with a short path, where a path is said to be short if its total transit time is less than an input parameter; if path $p$ is short we will write $w_p=1$, else it is long and we write $w_p=0$. Notice, we require two conditions for NDD: (i) the ordered item is in the storage of some origin node, and (ii) that origin node is connected to $d$ with a path that is short. First, let us study how we measure NDD coverage in a scenario where (ii) is always satisfied, i.e., for now, we consider networks where all paths are short. We introduce the coverage function $I_d$ which counts the number of covered orders at a destination $d$. It is typically impossible to derive the analytical form of $I_d$, but it is reasonable to estimate $I_d$ from available large datasets; using these datasets, one can compute an estimate of the number of covered unique NDD orders.

For example, see Figure 2. Assuming both origins of Figure 2 are connected to $d$ with short paths, $I_d$ would evaluate to 90 items in this example, and we may imagine that in more complicated scenarios, the computation of $I_d$ would boil down into counting unique orders in large datasets of requests and inventories. The model, however, becomes more interesting when we study networks that include long paths, where condition (ii) is not always satisfied. In such a case, depending on our path assignment decisions x, an origin-destination pair $(o,d)$ may not be able to transport items eligible for NDD. For instance, if $(o,d)$ commodity is assigned a long path, the contribution of $o$-inventory to $I_d$ should not be counted because although the inventory is available, its delivery takes more than one day. We should then adjust the coverage function $I_d$ to reflect this. A naive approach would be to adjust it to $I_d(\text{x})$ to denote the dependence on path assignment, but instead we use an alternative approach that reduces significantly the dimensions, and hence the complexity of computing this function: we use the dependent speed variables

where $z_{od}=1$ if the path selected to connect $o$ to $d$ is short. Since we have only one assigned path per commodity (i.e., it holds ${\sum }_{p\in {𝒫}_k}{x}_p=1$) it follows that

where recall that $w_p=1$ if $p$ is short, and $0$ otherwise. Using variables z we can write down the form of $I_d$ for the toy scenario of Figure 2:

More broadly, the function will have the form:

where $𝒫𝒮(.)$ is the power set, ${𝒪}_d$ is the set of origins that form a commodity with $d$, and ${\beta }_s$ is the unique item count of subset $s$ of origins – we may obtain parameters ${\beta }_s$ by performing counting operations on our large datasets. Note, that this function would need to have many more terms if we were to use path assignment variables x (one additive term for each element in the powerset of active paths), hence we have effectively reduced the number of times we need to count parameters in large datasets by an exponential factor. Also, observe that the form of (4) demonstrates well how deeply intertwined is the speed objective $I_d(\text{z})$ with the cost optimization of the MCND-U problem (1), both depending on our choice of x. Some paths may offer better consolidation by mixing volume in consolidation hubs, but because they are longer, they result in smaller NDD coverage. In the next subsection we augment the standard MCND-U problem with our newly introduced speed model.

The NDD coverage impacts customer satisfaction and shapes long-term revenues. We model this effect with a customer conversion factor $\gamma >0$; in practice, this factor can be estimated by analyzing customer behaviors via A/B testing. Therefore, our focus in this paper is to minimize the transportation costs and maximize long-term revenues from NDD coverage, which is formalized in the following optimization program:

Problem ${\mathbb{P}}_2$ is extremely difficult to solve. Evidently, it is a generalization of the NP–hard MCND-U, but a major additional complexity factor is function $I_d$. This coverage function is known to be submodular [4], i.e., the more short paths we assign (by switching $𝒛$ to ${𝒛}^{\mathbf{\prime }}$), the smaller is the benefit $I_d({𝒛}^{\mathbf{\prime }})-I_d(𝒛)$ per added short path, due to overlapping inventory between origins. The domain of function $I_d(𝒛)$ has $2^{n_O}$ points, each one of which requires a full computation on the large dataset. In fact, it is known that even finding the maximum point of such a function is an NP–hard problem [20, 18], let alone considering it inside a broader optimization problem as in ${\mathbb{P}}_2$. Last, observe that the objective of ${\mathbb{P}}_2$ is non-linear, see for example (4). From previous studies in the space of maximum coverage problem [1] we know that the non-linear components of (4) would make even the continuous relaxation of ${\mathbb{P}}_2$ NP–hard. For realistic e-commerce scenarios with multiple origins serving each destination, and a network with many destinations, solving ${\mathbb{P}}_2$ or even obtaining a lower bound via its continuous relaxation is intractable.

In this paper, we overcome this challenge by leveraging multi-parametric programming [12, 22] to create an interpolation (or continuous extension) of integer functions $I_d,d\in 𝒟$, which in turn allows us to propose a solution methodology for the speed-aware MCND-U.

We will interpolate between the integer points of function $I_d$, which are denoted with z and introduced in (2). For reasons that will become clear below when we present our approximation technique, we will introduce additional notation ${\text{z}}_d^i$ to enumerate the vector pointing to the $i^{\text{th}}$ integer point of $I_d(𝒛)$. Hence,

is another way to express the domain of $I_d(\text{z})$ and we have $n_{\text{comb}}=2^{n_O}$. See for example Figure 3(a).

For any vector ${\text{z}}_d^i$, we can use inventory data to compute the number of unique items $I_d({\text{z}}_d^i)$ for which we can offer NDD at $d\in 𝒟$. Then, for a vector ${\text{z}}_d$ in the convex hull of ${𝒵}_d$, we can use the following optimization problem to interpolate $I_d({\text{z}}_d^i)$:

Notice that problem (7) is a linear parametric program and therefore ${\tilde{I}}_d$ is a concave piecewise linear function [6, Chapter 6]; we may think of ${\tilde{I}}_d$ as an extension of $I_d$, referred to in the literature as the concave closure [24]. We will leverage the concavity of the extended function ${\tilde{I}}_d$ to reformulate (5) as a MILP. Note, that submodular functions may also be approximated by their convex closure, which is achieved by replacing the min operator with the max in (7). In this work, we have used the concave closure as this allows us to reformulate the speed-aware network design problem (5) as mixed-integer linear minimization problem, whereas using the convex closure would have resulted in a min-max mixed integer optimization problem.

We highlight that the interpolation from (7) is exact at all integer points ${\text{z}}_d\in {𝒵}_d$, since for each integer point ${\text{z}}_d^j\in {𝒵}_d$ we must have that ${\text{z}}_d^j={\sum }_{i=1}^{n_{\text{comb}}}{\alpha }_d^i{\text{z}}_d^i$, hence ${\alpha }_d^j=1$ and ${\tilde{I}}_d({\text{z}}_d^j)={\alpha }_d^j{I}_d({\text{z}}_d^j)=I_d({\text{z}}_d^j)$. Note that ${\tilde{I}}_d$ is exact at the integer points only when each ${\text{z}}_d^i\in {𝒵}_d$ is an extreme point, i.e., it cannot be expressed as a convex combination of the vectors in $\{{𝒵}_d\setminus {\text{z}}_d^i$}. This condition holds in our case, and yields the following proposition:

Next, we reformulate the speed-aware MCND-U presented in (5) replacing the term $I_d(𝒛)$ with its parametric interpolation ${\tilde{I}}_d(𝒛)$ from (7):

The above MILP is equivalent to the original problem (5), as the interpolation from (7) is exact at integer points, as discussed in Proposition 1. The main advantage of our reformulation is that it can be solved with off-the-shelf solvers. Unfortunately, for each destination $d\in 𝒟$ there are up to $2^{n_{\text{comb}}}$ pre-computed vectors ${\text{z}}_d^i$ that make the reformulation intractable for real-world problems. Thus, in the next section, we propose an algorithm to select only a subset of assignments to reduce the problem dimensionality.

Estimating the coverage function $I_d(\text{z})$ at all integer points $\text{z}\in {𝒵}_d$ from (6) and then solving (8) are both intractable due to the very large number of such points. In this section, we provide heuristics to select a subset of such vectors ${\widetilde{𝒵}}_d\subset {𝒵}_d$, to simplify (8). While this approximation introduces some loss in accuracy, we aim to select points that maintain a reasonable balance between computational efficiency and solution quality. Dropping vectors from ${𝒵}_d$ means that certain paths will always be chosen to be long, and hence, our heuristics attempt to drop the origins that are expected to have the smallest contributions to coverage.

The first step is to rank all origins in terms of individual coverage achieved by taking the short path from this origin and long paths from all others, denoted with $I_d({\mathrm{𝟏}}_o)$ for origin $o\in 𝒪$. Calculating individual coverage is a cheap operation (only $n_O$ calculations per destination), and intuitively helps us prioritize origins with large inventory capabilities – notice, however, that due to inventory overlap, choosing the top origins in this regard does not guarantee maximal coverage. Below we use the notation ${𝒯}_d(\kappa )\subseteq 𝒪$ to denote the top $\kappa$ origins with individual coverage. Note, that $\kappa$ is a user-defined hyper-parameter, which controls the complexity/performance tradeoff of our heuristic.

Our strategy employs four sets of vectors, ${\widetilde{𝒵}}_d=\{{\mathscr{H}}_0,{\mathscr{H}}_1,{\mathscr{H}}_2,{\mathscr{H}}_3\}$ that contain a subset of all possible speed variable assignments. We use the terms “short” and “long” to refer to the speed variable assignments: when we say an origin has a “short” path to a destination ($z_{od}=1$), it means that origin $o$ can offer next-day delivery to destination $d$. Conversely, a “long” path ($z_{od}=0$) indicates that origin $o$ cannot provide next-day delivery to destination $d$. Based on this terminology we define the following sets:

1. 1.

   ${\mathscr{H}}_0$: all short/long combinations of origins in ${𝒯}_d(\kappa )$ ($2^{\kappa }$ cases).

2. 2.

   ${\mathscr{H}}_1$: all origins in ${𝒯}_d(\kappa )$ are short, and one of the remaining origins short ($n_o-\kappa$ cases).

3. 3.

   ${\mathscr{H}}_2$: all origins in ${𝒯}_d(\kappa )$ are long, and one of the remaining origins short ($n_o-\kappa$ cases).

4. 4.

   ${\mathscr{H}}_3$: all origins in ${𝒯}_d(i),i=\kappa +1,\mathrm{\dots },n_o$ are short and the rest long ($n_o-\kappa$ cases).

Note that our heuristic strategy has reduced significantly the amount of vectors for which we need to calculate coverage and add to (8), from $2^{n_O}$ down to $2^{\kappa }+3(n_O-\kappa )$, and we can use $\kappa$ to control how small this number is, trading off with the achieved accuracy of the optimization. We provide an illustrative example for $\kappa =2$ and $n_o=5$:

Given ${\widetilde{𝒵}}_d$, we use the below program to approximate coverage:

In the next section, we empirically analyze the effect of our approximation technique on run-time and solution quality.

In this section, we demonstrate through empirical experiments how the parameter $\gamma$ controls the trade-off between transportation costs and speed-coverage in the network design. Higher values of $\gamma$ result in networks that provide speed-paths for a broader range of unique items, while lower values prioritize cost minimization by encouraging consolidation through intermediate hubs. Table 1 shows results for five randomly generated networks. For each network, we solve three optimization problems: in the first problem, we optimize only for transportation costs – i.e., we set $\gamma =0$; in the second problem we set $\gamma =0.1$; and in the third we use $\gamma =1$. The solver terminates either when the gap is below $0.1\%$ or the solution time exceeds two hours. As expected, for larger values of $\gamma$ both transportation costs and the average number of unique items eligible for NDD increase, i.e., the optimizer decides to open more expensive connections to gain revenues from NDD. Note that the number of direct paths (not crossing any intermediate hub) increases with $\gamma$, as they have lower transit time and thus are more likely to offer NDD. In all experiments, we set the parameter $\kappa$ from Algorithm 1 equal to $10$, meaning that the approximation from (9) is exact for the unique items delivered by the top $10$ origins for each destination – see Section 4.2 for an empirical analysis on the effect of $\kappa$ on the solution. Indeed, we notice from Table 1 that for $n_O=10$ the approximate average number of unique items eligible for NDD (column Avg. Items App.) matches the exact number (column Avg. Items). On the other hand, for $n_O=100$, the proposed strategy only computes a lower bound to the average number of unique items eligible for NDD at a destination $d\in 𝒟$.

In this section, we test how the parameter $\kappa$ from Algorithm 1 affects the solution quality. Table 2 shows results for five different networks and parameter $\kappa \in \{1,5,10\}$. The table reports also results for the baseline cost-optimal network (in blue) that is obtained minimizing only the transportation costs, i.e., the optimizer does not approximate revenues from NDD and therefore the parameter $\kappa$ is not required to run the baseline. For all cases we report the total cost defined as the difference between the transportation costs and revenues from speed-paths²²2As in Problem 5, revenues from speed-paths are computed by summing all unique items eligible for NDD at each destination and using the conversion factor $\gamma$. (column Cost-Rev.). For $\kappa =1$, in Algorithm 1 we do not consider different combinations of origins offering NDD at a destination, but we simply sort origins by number of unique items eligible for NDD and we use the heuristic described in Section 3.3. This strategy allows us to prune the origins combinations used to construct the approximation from (9). On the other hand for $\kappa \in \{5,10\}$, after sorting the origins by the number of unique items eligible for NDD, we consider all possible combination for the top $\kappa$ origins and for the remaining we leverage the heuristic from Algorithm 1. As discussed in Section 3.3, this approximation allows us to reduce the number of constraints needed to build function (7). However when $\kappa$ is smaller than the number of origins $n_O$, the number of unique items computed using (9) is only an approximation. This fact is shown in Table 2, where we compare the true revenues (column Rev.) and the approximated revenues (column App. Rev.) obtained by multiplying the number of unique items eligible for NDD by the coefficient $\gamma$. Finally, we notice that the total cost (column Cost-Rev.) defined as the difference between the transportation cost and the revenues from NDD decreases for larger value of $\kappa$. Note that for $\kappa =1$, the approximation from (9) is constructed using $n_{\text{app}}=59$ data points, while for $\kappa =10$ the approximation is constructed with $n_{\text{app}}=1081$, i.e., for $\kappa =10$ we increase by $94.5\%$ the number of data points used compared with the approximation with $\kappa =1$. From the experiments in Table 2, we notice that using $94.5\%$ more data points in the approximation from (9) improves on average the network cost by $1.79\%$, i.e., as expected a more accurate approximation of revenues from NDD allows us to design a better network by trading off transportation costs and from NDD services. It is also interesting to notice that even for $\kappa =1$, our approach is able to reduce the overall cost – i.e., the cost defined as the difference between transportation cost and revenues from speed-paths – by 8.36% compared to the baseline (in blue).

Finally, we investigate the effect of the parameter $\kappa$ on the computation time. Table 3 shows both solver times and pre-processing times needed to compute the data points $n_{\text{app}}$ used to construct the approximation from (9). We notice that increasing $\kappa$ leads to higher pre-processing and solver time, as more data points are used for approximating the number of unique items eligible for NDD. However, we notice that increasing $\kappa$ from $10$ to $16$ results in only a $0.57\%$ cost improvement, while the computation cost increases by $1.9$x. This result highlights the effectiveness of the approximation from Algorithm 1, where we ranked origins by the number of unique items eligible for NDD and considered all possible combination for a subset of them.