# A Hierarchical Network Approach for Long-Haul Parcel Transportation

Camille Gras, Van-Dat Cung, Nathalie Herr, Alantha Newman

► To cite this version:

Camille Gras, Van-Dat Cung, Nathalie Herr, Alantha Newman. A Hierarchical Network Approach for Long-Haul Parcel Transportation. IFIP International Conference on Advances in Production Management Systems (APMS), Sep 2021, Nantes, France. pp.168-178, 10.1007/978-3-030-85914-5_18. hal-03442808

HAL Id: hal-03442808

https://hal.science/hal-03442808

Submitted on 23 Nov 2021

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# A Hierarchical Network Approach for Long-Haul Parcel Transportation

Camille Gras¹², Van-Dat Cung<fnref n="1" />, Nathalie Herr<fnref n="2" />, Alantha Newman<fnref n="1" />

**Abstract.** In this work, we study the long-haul stage of parcel trans-
portation, which involves the integration of the sorting operation allow-
ing better consolidation of parcels in containers. The transportation is
optimized over a complex two-level hybrid hub-and-spoke network and
is conducted with a heterogeneous fleet; there are two types of vehicles
which are balanced over the network on a daily basis with the manage-
ment of empty trucks. We are not aware of a framework for long-haul
parcel transportation in the literature that is sufficient to handle all as-
pects of the industrial problem we address. In terms of finding a solution,
we propose a hierarchical algorithm with aggregate demands whose per-
formance is related to the value of a truck filling rate threshold. Roughly
speaking, the demands above this threshold can be routed directly while
the ones below this threshold follow the hierarchical structure of the net-
work. The routing of the two types of demands is optimized, first sepa-
rately and then together in a multi-step process in which the subproblems
are solved via Mixed Integer Linear Programs. Numerical experiments
are carried out on datasets provided by a postal company (225 sites with
2500 demands). Various threshold values are tested to find out which one
is the best, in terms of solution quality obtained and computational time.

**Keywords:** Operations Research, Network Design, Long-haul Trans-
portation, Parcel Delivery, Hierarchical Network

# 1 Introduction

E-commerce has experienced sustained growth over the last two decades. In 2019, an estimated 1.92 billion people purchased goods or services online <fnref n="3" />. This provides motivation for parcel delivery companies to constantly adapt and optimize their transportation networks. The parcel delivery process is composed of four steps: collection, long-haul transportation, distribution and delivery [10]. The optimization of the long-haul transportation (defined as intercity transportation [4]) on a road network is addressed in this work. This means that neither how parcels reach an initial sorting center (the first-mile collection problem), nor how

<footnote n="1">¹ Univ. Grenoble Alpes, CNRS, Grenoble INP**, G-SCOP, 38000 Grenoble, France
{camille.gras,van-dat.cung,alantha.newman}@grenoble-inp.fr</footnote>

<footnote n="2">² Probayes, 38330, Montbonnot, France
{camille.gras,nathalie.herr}@probayes.com</footnote>

<footnote>** Institute of Engineering Univ. Grenoble Alpes</footnote>

<footnote n="3">³ Statista: E-commerce worldwide - Statistics & Facts Feb. 2021</footnote>
parcels are delivered from depots to final clients (the last-mile delivery and distribution problems) are considered. As long-haul parcel transportation addresses transportation of large volumes of parcels over long distances, a better use of vehicles and logistics operations such as sorting results in economies of scale.

In this paper, we define the Long-Haul Parcel Transportation Problem (LH-PTP) in which the input is made of transportation demands expressed by the triple (origin, destination, number of parcels), and the road network composed of possible origin, destination and intermediate sites and links between them. The objective of the LHPTP is to minimize the costs for the postal company while delivering all of the demands. The predesigned road network has two sets of sites, sorting centers and delivery depots within a two-level (inner and outer level) hierarchical structure presented in Section 2.1. Over this hierarchical network, demands must be routed from sorting centers to delivery depots directly or through at most two other sorting centers. The transportation of parcels is made via two types of vehicles: trucks with one or two containers. As a daily transportation plan is designed, the vehicles have to be balanced over the course of a day for each site: empty vehicles need to be returned to appropriate locations.

## 1.1 Background and Previous Works

Hierarchical networks are composed of sites which are of different types of varying importance. The sites of a same type (inner-hubs, sorting centers, depots) form a **layer** [5]. Each pair of layers constitutes one **level** of the hierarchical network (and is sometimes referred to as an echelon). In the LHPTP, a two-level hierarchical network is given as input as there are three types of sites.

In our network, we have a **hub-and-spoke** configuration on each level. In a hub-and-spoke network, all links either begin or end at a hub, the other extremities of the links being the spokes [2]. A hub-and-spoke network in which there are possibilities to bypass the hubs with direct links is called **hybrid hub-and-spoke network**. Lin and Chen [8] define a hierarchical hub-and-spoke network in which each site is assigned to exactly one hub. It corresponds to our network without inner-hubs. Baumung and Gunduz [1] propose a heuristic for parcel transportation. They send fully filled trucks with parcels for the same destination (sorting center) until there are not enough parcels in the origin sites to fill a truck. The parcels which remain (called **residual volumes**) are consolidated into trucks. These residual volumes routing is optimized with an MILP. This method cannot be used to solve the LHPTP as it uses only one vehicle type, has one level of network (our inner level) and empty vehicle balancing is not considered.

Other work related to the LHPTP can be found in [6, 11, 12, 13] although none of these works exactly captures our problem formulation. Briefly, the LHPTP has more than one vehicle type and a two-level network in which the costs of parcel long-haul transportation are minimized on both levels simultaneously. A key feature of LHPTP is that there is no tour between sorting centers and delivery depots, while in previous work, this transportation stage often involves a tour [11]. We do not consider sorting capacity, as each sorting center has appropriately-sized sorting capacity. We simultaneously optimize the long-haul
transportation and the balance of vehicles in the course of day on a two-level
network which seems to be a unique aspect in the scope of parcel transportation.

## 1.2 Contributions

The LHPTP is really a family of problems based on various parameters (e.g., allowed logistic operations, limited fleet versus unlimited fleet, arc capacity, vehicle balancing constraints, vehicle types, etc.). None of the problems modeled in the literature is sufficient to model the specific problem that we want to solve nor to solve the variations that could arise based on the various parameters that we consider. For example, other works treat the long-haul stage of parcel delivery as a single level; there is very little treatment of two-level networks with logistics operations on parcels permitted between the levels. Moreover, in a two-level network, certain issues arise that do not apply to a simpler model; for example, balancing vehicles between intermediate sites (i.e., not origin/destination sites).

In this work, we take advantage of the hierarchical structure of our network to design good transportation plans by dividing the whole problem into tractable subproblems. We directly send large demands and consolidate residual demands. Indeed, it seems natural to maximize the truck filling rate and minimize the number of parcels sorted. Therefore, we do not impose a sorting (as in [6]) on all the demands, which incurs extra costs. Instead, we require a sorting for a subset of the demands while sending the other demands directly. We send directly (bypassing all sorting operations) trucks filled more than a **truck filling rate threshold**, rather than only the fully filled ones (like [1]). The LHPTP has two levels which can both be bypassed by direct paths, and a heuristic is used to optimize this decision for bypassing the two sortings. But this heuristic is not used within the inner level as the MILP reaches the optimum for the inner level optimization.

In Section 2, the LHPTP is introduced and an MILP formulation for it is presented. In Section 3, an algorithm which solves the LHPTP via the aggregation of demands and the MILP is presented. Finally, in Section 4, we show that the algorithm with aggregate demands can handle our large real data instances.

# 2 Problem Description

The LHPTP defined in this section is basically a Service Network Design problem [3] with Hub-and-Spoke structure. However, the LHPTP has distinct properties such as demands have both fixed origin and destination, and the sorting operation has a cost per parcel. Moreover, the problem we tackle is an industrial problem containing strong constraints. Thus, after the presentation of the application framework of our problem, we introduce an MILP for the LHPTP, which can be adapted to solve other long-haul parcel transportation problems.

## 2.1 Application Framework and Optimization Problem

In our application framework, we are presented with the problem of delivering parcels via trucks with one or two containers in a national postal network composed of sites with around 2500 demands per day being routed between these sites. There are two sets of sites: each site of our network is either a delivery
depot or a sorting center but cannot be both. There are on average 17 sort-
ing centers and 208 delivery depots. Among the sorting centers, some are also
inner-hubs fixed by the transportation managers.

**Parcels** are physical objects which must be routed from a specified origin sorting center to a designated delivery depot. As each container can transport a significant amount of parcels, all parcels are assumed to be of equal (average) size. Parcels having the same origin and destination are grouped in a **demand**. Demands are represented by the triple (origin, destination, number of parcels). We assume that the demands are known for an average day. Our goal is to design a **transportation plan** to deliver all the demands at a minimum cost. The cost of a solution is composed of transportation costs and logistics operations' costs.

Indeed, only one logistics operation is considered – the **sorting** – which
occurs in sorting centers. When parcels are sorted, all parcels in a container are
grouped according to the next site served on their operational path. When a set
of demands destined for different final sites are put in the same container it is
called **consolidation**. The parcels are shipped in **bulk** in containers. A container
cannot be partially unloaded, thus it carries parcels headed for one site, which
is either an intermediate sorting center or a final delivery depot depending on
the parcel's destination. This means that when there is consolidation between
demands, there is always a sorting operation afterwards.

<figure><img src="image_2.png" /><figcaption>**Fig. 1.** The two levels of the hybrid hub-and-spoke network</figcaption></figure>

The parcels are delivered on a road network composed of two hierarchically
nested **hub-and-spoke networks** (see Figure 1). The inner level of this net-
work is made of sorting centers. A sorting center on a path between two sorting
centers is called inner-hub. The outer level of the network is composed of sorting
centers and delivery depots. Indeed, each delivery depot is assigned to a sort-
ing center (an outer-hub), usually the closest (with respect to travel time). The
area which contains the delivery depots affiliated to a sorting center, including
this sorting center, is called a **catchment area**. The mapping of the catchment
areas, created with the experience of transportation managers, is used in the
current operational strategy in which the parcels are handled regionally. They
are sent to the catchment area containing their delivery depot, sorted in their
corresponding outer-hub and sent to their delivery depot.

The **inner network** connects the sorting centers (see Figure 1a). It is a hy-
brid hub-and-spoke network as the sorting centers either send parcels directly
to other sorting centers or they can use an inner-hub to sort and/or consolidate
demands. The **outer network** arises when the final destinations of parcels, are
the delivery depots (see Figure 1b) are added. They are the spokes in a hybrid hub-and-spoke network in which the outer-hubs are the corresponding sorting centers. Indeed, parcels can either be sent directly from their origin sorting center or consolidated and then sorted before reaching their delivery depots.

There are two types of **vehicles**: trucks with one container and trucks with two containers (also called twin trailers). The number of vehicles or containers is not limited and can be adapted appropriately in the optimization process. Note that the performance standard is the same for all the vehicles and does not depend on the vehicle type. The vehicle type changes only the capacity and the cost.

An **operational path** is a set of consecutive physical links between sites. Each of the links on the operational path is associated with a schedule and each site is associated with an operation (sorting or delivery) performed on a parcel flow at a time slot. Moreover, each link is served with a vehicle type (i.e., a vehicle with one or two containers). Each parcel is either (i) sent on a direct path from a sorting center to a delivery depot, or (ii) it undergoes a single sorting at a sorting center (not mandatorily an inner-hub), or (iii) it undergoes two sortings, one at an inner-hub and one at the corresponding sorting center of the destination. Each demand can be split over multiple operational paths in the transportation plan: this is **disaggregate shipping** [7].

As a daily transportation plan is designed, there is a need to balance vehicles to ensure that enough **vehicles and containers** are available each day on each site to send all the parcels. This is achieved by vehicle balancing: sending **empty trucks** back from sites in which there were too many vehicles.

In summary, the LHPTP is composed of three types of constraints: the delivery constraints, the capacity constraints and the design-balance constraints. The delivery constraints (1b) state that all the parcels have to be delivered. The link capacity constraints (1c) associate the number of parcels and the number of vehicles on each link. There are such constraints for each vehicle type and each link in the network. Finally, the design-balance constraints (1d) balance both containers and trucks between sites on a daily basis.

## 2.2 MILP Formulation

The MILP formulation for the LHPTP is a path-based model; the number of possible operational paths for each demand is bounded. Indeed, each operational path is allowed to have at most two sorting operations after the initial sorting (done immediately upon collection), which limits each path's length and thus the number of possible paths. The notations in our model are: $D$ is the set of demands, $V$ the set of vehicle types, $S$ the set of sites composed of $S_{s,c}$ the set of sorting centers and $S_{d,d}$ the set of delivery depots. $L$ is the set of links between sites whose element $l_{i,j}$ is the link between site $i$ and site $j$, $P_d$ is the set of possible operational paths for the demand $d$ in $D$, $P_d^l$ is the set of possible operational paths using the link $l$ in $L$ for demand $d$ in $D$.

The variables are of two types: (1) $x_p^d \in [0,1]$, with $d \in D$ and $p \in P_d$, represent **parcel flows**. It is the percentage of a demand $d$ using an operational path $p$; (2) $y_l^{veh} \in \mathbb{N}$, with $l \in L$ and $veh \in V$, represent **vehicle flows**. They are integers which represent the number of vehicles of type $veh$ on each link $l$.
The cost of the operational path $p$ is denoted $c_p$. $c_l^{veh}$ is the cost of the link $l$ with vehicle $veh$, $v_d$ the number of parcels of demand $d$, and $C_{veh}$ the capacity of vehicle $veh$.

$$ \min \sum_{d \in D} \sum_{p \in P_d} c_p x_p^d + \sum_{veh \in V} \sum_{l \in L} c_l^{veh} y_l^{veh} \quad (1a) $$

s.t.:

$$ \forall d \in D, \sum_{p \in P_d} x_p^d = 1 \quad (1b) $$

$$ \forall l \in L, \forall veh \in V, \sum_{d \in D} \sum_{p \in P_d^l} v_d x_p^d \leq y_l^{veh} \cdot C_{veh} \quad (1c) $$

$$ \forall s \in S, \sum_{i \in S} y_{l_{i,s}}^{veh} = \sum_{j \in S} y_{l_{s,j}}^{veh} \quad (1d) $$

$$ \text{with: } x_p^d \in [0, 1] \quad (1e) $$

$$ y_l^{veh} \in \mathbb{N} \quad (1f) $$

## LHPTP-MILP

Due to the usage of consolidation, a container can carry parcels with different origins and destinations; a demand might not be routed on its shortest path. Indeed, consolidation is a crucial strategy used to reduce costs, but its usage makes the problem computationally difficult (since it is not simply a shortest path problem). Different sorting centers and different time slots can be used for the sorting operations. Moreover as the possibility of disaggregate shipping is added, there is a combinatorial explosion on the number of possible operational paths, which prevent the MILP from giving an optimal solution on realistic sized datasets (with around 225 sites and 2500 demands) in reasonable time.

## 3 Hierarchical Algorithm with Aggregate Demands

The LHPTP can be formulated as an MILP which does work well on small instances. Therefore, the Hierarchical Algorithm with Aggregate Demands (henceforth HAAD) divides the problem into smaller subproblems, each of which can be solved optimally via an MILP or other means, and then adds these solutions together to obtain a final solution of good quality, although it can be suboptimal.

<figure><img src="image_3.png" /><figcaption>Fig. 2. Hierarchical Algorithm with Aggregate Demands (HAAD)</figcaption></figure>
We first find an optimal transportation plan on the inner level (see Figure 1), which involves choosing the inner-hubs. We allow all sorting centers to be candidate inner-hubs in order to test whether or not the inner-hubs proposed by the transportation managers are actually the best ones. Then the extension of this transportation plan is optimized on the outer level. Finally, in the last steps of the algorithm, these solutions are combined and refined to obtain a transportation plan for the whole network (see Figure 2). Recall that the original demands of the LHPTP are from sorting centers to delivery depots. For the inner problem, we create aggregate demands which are demands from sorting centers to sorting centers (in order to separate the two levels). The last sorting is required to be done in the corresponding sorting center of the delivery depot of destination. An aggregate demand is the sum of demands from a sorting center to all the corresponding delivery depots of another (destination) sorting center.

<table><caption>**Algorithm 1:** Hierarchical Algorithm with Aggregate Demands (HAAD)</caption><thead><tr><th></th><th></th></tr></thead><tbody><tr><td>1</td><td>a) Split demands</td></tr><tr><td>2</td><td>for each demand d do</td></tr><tr><td>3</td><td>&nbsp;&nbsp;&nbsp;&nbsp;if $v_d < \sigma \cdot C_{veh}$ then Add d to the set of residual demands</td></tr><tr><td>4</td><td>&nbsp;&nbsp;&nbsp;&nbsp;else $k = \lceil v_d/C_{veh} \rceil$</td></tr><tr><td>5</td><td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if $k \cdot \sigma \cdot C_{veh} \le v_d \le k \cdot C_{veh}$ then Add d to the set of large demands</td></tr><tr><td>6</td><td>&nbsp;&nbsp;&nbsp;&nbsp;else Split d into a large demand of volume $(k-1)C_{veh}$ and a residual demand (twin demands)</td></tr><tr><td>7</td><td>b) Aggregate demands</td></tr><tr><td>8</td><td>for each residual demand d do</td></tr><tr><td>9</td><td>&nbsp;&nbsp;&nbsp;&nbsp;Aggregate it with the demands with the same corresponding sorting center as destination</td></tr><tr><td>10</td><td>c) Solve the aggregate subproblem (inner level)</td></tr><tr><td>11</td><td>Solve the MILP which is made only of links between sorting centers</td></tr><tr><td>12</td><td>d) Extend for each catchment area (outer level)</td></tr><tr><td>13</td><td>for each one of the n catchment areas do</td></tr><tr><td>14</td><td>&nbsp;&nbsp;&nbsp;&nbsp;Solve the MILP without constraints (1d) to route the demands towards their catchment area</td></tr><tr><td>15</td><td>e) Add the solutions for residual demands, large demands (on direct paths) and the balance of trucks</td></tr><tr><td>16</td><td>Solve the MILP with all the residual demands and with only the chosen operational paths to optimize the vehicle flow. The large demands are enforced to use a direct paths (for up to 1h).</td></tr><tr><td>17</td><td>f) Add the large demands</td></tr><tr><td>18</td><td>Solve the MILP with all the demands, the solution of the previous MILP fixed and the option for the large demands to follow a direct path or an already chosen operational path. (for up to 1h)</td></tr></tbody></table>

The algorithm chooses the links between sorting centers first (plain arcs in Figure 2a), then it chooses the links from sorting centers to delivery depots in each zone around each sorting center (dotted arcs on Figure 2a) and finally it assembles the solutions. But if all the demands are aggregated, we lose the possibility of using direct paths from a sorting center to a delivery depot, which have been proven to be useful [9,11]. Therefore the following approach is considered: if a demand is large enough to nearly fill a truck (above a threshold $\sigma$), then sending a truck with this demand directly from the origin to the destination is considered. Thus the HAAD first splits the demands into large demands, whose operational paths are actually determined in the last step (deferred demands), and residual demands whose operational paths are specified by the transportation plan constructed on the inner and outer levels of the network. These residual demands are either routed through an inner-hub and subject to an additional
sorting, or they are routed directly from their initial sorting center to their final sorting center. This latter determination is made during the single call to the LHPTP-MILP on the set of aggregate residual demands.

This approach gives a solution for the complete instance in reasonable time but might be globally suboptimal because the choice between performing at least one sorting or sending the parcel on a direct path is handled in a heuristic way. Thus, for a parcel sent directly, it could be the case that some possible operational paths that could be chosen in a global optimal solution are not considered.

## 4 Numerical Experiments and Results Analysis

Simulations are run on a Linux server with 32 CPU and 150 Gbytes of RAM using CPLEX 12.8 solver. The data, provided by a postal company, contains six datasets which represent six different configurations of the network with logistics sites spread across mainland France. A dataset is made of: (1) a set of sites with their type, location and the travel times between each pair of sites; (2) a set of demands (origin, destination, number of parcels) between these sites; (3) costs: kilometric cost and the costs of all the logistics operations (sorting, entering sites, leaving sites etc.). The number of sites varies from 154 sites to 292 and the number of demands varies from 2312 to 3627. Note that the kilometric cost for a vehicle is thrice the cost to sort one parcel in a sorting center.

In the network on which the parcel transportation is optimized, there are from two to four inner-hubs fixed by the transportation managers. In this section, we ignore this constraint and assume that all the sorting centers can be inner-hubs in order to enhance the possibilities of consolidation and to confirm if the four inner-hubs chosen by the transportation managers are the right ones.

<table><caption>Table 1. Comparison of the thresholds (NEV = No Empty Vehicles)</caption><thead><tr><th>σ (%)</th><th>Time (h) min|avg|max</th><th>Sol fix. dir e) min|avg|max</th><th>Built sol f) min|avg|max</th><th>Gap (%) min|avg|max</th><th>Fill. rate (NEV) min|avg|max</th><th>Global fill. rate min|avg|max</th></tr></thead><tbody><tr><td>none</td><td>6</td><td>—</td><td>377</td><td>406</td><td>426</td><td>10.2</td></tr><tr><td>100</td><td>1.0|1.1|1.3</td><td>376</td><td>415</td><td>376</td><td>414</td><td>13.4</td></tr><tr><td>80</td><td>1.0|1.2|1.2</td><td>374</td><td>406</td><td>429</td><td>374</td><td>12.2</td></tr><tr><td>60</td><td>1.0|1.1|1.2</td><td>367</td><td>399</td><td>367</td><td>399</td><td>10.1</td></tr><tr><td>40</td><td>1.1|1.2|1.5</td><td>374</td><td>406</td><td>426</td><td>406</td><td>11.5</td></tr><tr><td>20</td><td>1.0|1.3|1.5</td><td>436</td><td>463</td><td>480</td><td>436</td><td>19.9</td></tr></tbody></table>

We first compare results obtained with several thresholds ($\sigma$ in Algorithm 1) for splitting demand volumes into large and residual demands. In this algorithm, each MILP is solved with 1h time limit and all sorting centers are considered as inner-hubs. The gap presented in Table 1 is with respect to the best lower bound computed by the solver (after a 6h run).

The results in Table 1 show that compared to the LHPTP-MILP when run without any heuristic for 6 hours (line with threshold none), the HAAD can provide better solution values in 5 to 6 times less computational time for the appropriate thresholds. The threshold which provides the best results is 60% ±10%. The solutions obtained in step e) and step f) are nearly the same and in these steps the optimal solution is reached most of the time (with respect to the
variables fixed as inputs). If a large demand does not have any twin demand, it
cannot use a non-direct path. For these demands, there is no difference between
the solutions of steps e) and f). And the lower the threshold is, the less there are
demands which are split into twin large and residual demands. Note that steps
e) and f) are run for much less than one dedicated hour.

In the solutions presented in Table 1, nearly all the sorting centers are used as
inner-hubs. It is because the demands are small compared to the vehicle capacity
and because the sorting costs are not very high compared to the kilometric cost.
Consolidation of demands is then interesting as it reduces the number of vehicles
used, even if this leads to more sortings. This might not be the case with much
higher sorting costs. To check this we compare results obtained with several sort-
ing costs with a threshold of 60% for the activation of direct paths. The number
of inner-hubs used decreases when the sorting cost increases. Moreover, the inner-
hubs selected by the HAAD are not the one selected by transportation managers
and this results in better solutions. Thus the HAAD can be an interesting deci-
sion support tool for the managers. With σ = 60%, the vehicle filling rates with
and without considering returns of empty vehicles are respectively 50,9% and
81,8%. Slightly higher vehicle filling rates (like 84%) can be obtained with higher
filling rate thresholds but at the expense of sorting cost for more consolidation.

The simulations show that in parcel transportation, due to sorting costs and
empty balancing of vehicles, greater truck filling does not obviously result in
lower cost. Indeed, the cheaper solutions are not the ones in which the trucks
have the highest filling rate. The best threshold to decide if a demand should
use a direct path is when it fills 60% of a container, not 100%. This result seems
counter-intuitive for someone on the ground with only a local point of view, as
they do not have a global perspective, which leads to a different conclusion. But
it allows to optimize the network globally and to minimize the total cost.

We also show that the advantages of consolidation in inner-hubs depends
strongly on the sorting costs and kilometric costs. Thus the optimal threshold
found empirically depends on the datasets and would need to be recomputed if
the algorithm were to be applied on another dataset.

With the data we used, greater truck filling rates do not correspond to the
cheapest solution. It means, in general, that in long-haul parcel transportation,
it is not always better to send fully-filled trucks.

5 Conclusion

In this work, the Long-Haul Parcel Transportation Problem (LHPTP) is defined.
It consists of optimizing the long-haul transportation of parcels on a two-level
hybrid hub-and-spoke network with three types of sites. We present a new hier-
archical algorithm which exploits the two-level structure of the network to solve
this problem which contains strong industrial constraints. As the hybrid hub-
and-spoke network offers the possibility to use direct paths, we offer this option
for large demands (over a threshold). The residual demands (lower than the
threshold) are gathered into aggregate demands which stay on the inner-level of
the network. The HAAD divides the problem into subproblems solved through
MILPs. It has been tested with success on real data instances at the scale of a country (around 225 sites and 2500 demands) which are too large to be solved efficiently with a single global MILP.

We have tested various thresholds of truck filling rate to divide the demands to find which one suits our datasets the best. This constitutes a tailored heuristic which permits us to have better quality solutions for the LHPTP that can be obtained more efficiently. One perspective for future work is to investigate the impact of using different thresholds on different network areas or/and for different demands. These thresholds can integrate other criteria than the truck filling rate such as distances and transportation costs.

**Acknowledgments** This work is funded by ANRT, CIFRE n°2019/0351. We thank Nicolas Teypaz and Sylvain Ducomman (Probayes) for their comments.

## References

1. Baumung, M.N., Gündüz, H.I.: Consolidation of residual volumes in a parcel service provider's long-haul transportation network. Computational Logistics pp. 437–450 (2015)

2. Bryan, D.L., O’Kelly, M.E.: Hub-and-spoke networks in air transportation: an analytical review. Journal of regional science **39**(2), 275–295 (1999)

3. Crainic, T.G.: Service network design in freight transportation. European Journal of Operational Research **122**(2), 272–288 (2000)

4. Crainic, T.G.: Long-haul freight transportation. In: Handbook of transportation science, pp. 451–516. Springer (2003)

5. Cuda, R., Guastaroba, G., Speranza, M.G.: A survey on two-echelon routing problems. Computers & Operations Research **55**, 185–199 (2015)

6. Lee, J.H., Moon, I.: A hybrid hub-and-spoke postal logistics network with realistic restrictions: A case study of korea post. Expert systems with applications **41**(11), 5509–5519 (2014)

7. Leung, J.M.Y., Magnanti, T.L., Singhal, V.: Routing in point-to-point delivery systems: Formulations and solution heuristics. Transportation Science **24**(4), 245–260 (1990)

8. Lin, C.C., Chen, S.H.: The hierarchical network design problem for time-definite express common carriers. Transportation research part B: methodological **38**(3), 271–283 (2004)

9. O’Kelly, M.E.: A geographer’s analysis of hub-and-spoke networks. Journal of transport Geography **6**(3), 171–186 (1998)

10. Sebastian, H.J.: Optimization approaches in the strategic and tactical planning of networks for letter, parcel and freight mail. In: Modeling for Decision Support in Network-Based Services, pp. 36–61. Springer (2012)

11. Zäpfel, G., Wasner, M.: Planning and optimization of hub-and-spoke transportation networks of cooperative third-party logistics providers. International Journal of Production Economics **78**(2), 207–220 (2002)

12. Zhang, J., Wu, Y., Liu, P.: Routing problem for hybrid hub-and-spoke transportation network: a case study of a ltl carrier. In: 2007 IEEE International Conference on Automation and Logistics. pp. 170–175. IEEE (2007)

13. Zhang, W., Payan, A.P., Mavris, D.N.: Improving courier service network efficiency through consolidations. In: AIAA Scitech 2021 Forum. p. 1233 (2021)