New Mobility-Assist E-Grocery Delivery Network: a Load-Dependent Two-Echelon Vehicle Routing Problem With Mixed Vehicles

Abstract

New forms of transport, such as autonomous delivery robots (ADRs), have attracted considerable attention in recent years for their potential use as green last-mile delivery alternatives because of their flexibility in some areas unreachable by van. However, their low efficiency, delivering a limited number of orders each trip, limits their application in the last mile. Also, the cost and emission impact of new forms of transport on the last-mile delivery network is still not clear. To address these issues, we developed a new two-echelon delivery system that combines traditional vans and ADRs, making use of their individual advantages to overcome their drawbacks and enhance efficiency in the deliveries. The objective of this study was to develop a new approach based on a metaheuristics methodology to minimize transport and emission costs through modeling and to solve the extension of two-echelon load-dependent vehicle routing problems with mixed vehicles (2E-LDVRP-MV). The complicated 2E-LDVRP-MV problem was formulated as a mixed-integer programming (MIP) model and solved efficiently with a cluster-based artificial immune algorithm (C-AIA) in which clustering was employed to allocate customers. We performed a set of numerical experiments with a solver and the proposed C-AIA heuristics. C-AIS highlights the operational implications of four parameters: ratios between load and the empty vehicle weight; vehicle types; emission levels; and customer densities. Our results provide a unique perspective on tactical planning for a sustainable urban logistics system, and this new two-echelon system could be applied in e-grocery last-mile delivery networks where vans and ADRs are combined.

Keywords

freight systems city logistics and last-mile strategies street use delivery logistics

The growth of online grocery shopping has accelerated significantly in recent years, especially during the pandemic. According to a report on US grocery sales, in 2021, online grocery sales passed $100 billion. Online shopping behavior is changing from trial to habit for many shoppers ( 1 ). However, although these e-grocery delivery services boost the growth of the economy, they put tremendous pressure on the environment ( 2 ). As many facilities, roads, and vehicles overlap and intersect in urban transportation and logistics systems, the advantages of fast deliveries of e-grocery services are compromised. On-demand and instant delivery services lead to many short round-tours with low consolidation levels, generating operational and economic inefficiencies, multiplying greenhouse gas emissions, and affecting the living conditions for residents ( 3 ).

To address these problems, many companies are looking for new technologies and operational strategies to obtain high-efficiency and sustainable delivery systems. Autonomous delivery robots (ADRs) have received much attention. ADRs can move flexibly with low emissions in dense areas. However, the speed, capacity, and travel range of ADRs limit their scope to scale deliveries. A sensitivity analysis study from Sonneberg et al. ( 4 ) proved that there is a strong relationship between total costs and ADR capacity. Increasing the number of compartments in an ADR could reduce the overall cost. However, the overall capacity is still limited. Compared with the limited capacity of ADRs, a traditional van has a relatively large volume, and it can move fast. However, vans produce fossil-fuel emissions and have a negative effect on environment. To overcome the individual shortcomings of vans and ADRs, one efficient form of freight delivery is to combine an ADR with a conventional van. Such a combined delivery system (V-ADR) designed for the last-mile delivery enables seamless flow consolidation ( 5 ). Through cooperation and consolidation, the advantages of both conventional vans (low cost and large volume) and the ADRs (low emissions and flexibility) can be functionally maximized in planning an e-grocery network to achieve efficient last-mile delivery.

This van-ADR two-echelon delivery system shares similarities with a robot-assisted delivery system ( 6 ). However, this system does not need a “mothership” van ( 7 ) for the ADRs. ADRs use an infrastructure of micro hubs to transship the groceries. This makes the two-echelon van-ADR system in this study more flexible but also complex, especially if it is subject to various constraints such as allocation of mixed vehicles in the two echelons, load allocation to the facilities, and routing decisions in both echelons.

To evaluate the performance of this two-echelon delivery network and to optimize the transport and emission costs of this network, a model was established for the study. This model considered the load-dependent objective and parcel consolidation in the two echelons. As the problem needs to achieve optimal flow assignments and route choices for the van and ADR, it belongs in the domain of two-echelon vehicle routing problems (2E-VRP). However, this van-ADR two-echelon system differs from the conventional 2E-VRP because, in this new van-ADR two-echelon system, more variables and constraints are involved to address the key considerations of: (i) allocating vans and ADRs in the two echelons based on the load-dependent costs and emissions; and (ii) the travel range limitation of the ADRs. Our literature review below reveals very few models available to solve this new complex 2E-VRP. The objective of this study is, therefore, to fill these gaps by developing a novel formulation and solution method to solve the problem efficiently and then to assess the performance of the van-ADR delivery system. We approached the model as a load-dependent 2E-VRP with mixed vehicles (2E-LDVRP-MV). We then developed a clustering-based artificial immune algorithm (C-AIA) to address the 2E-LDVRP-MV. This model thus helps transportation managers and operators to understand clearly the related planning issues and future economic and environmental benefits when new ways are adopted and load-dependent costs and emissions need to be considered. Therefore, this study contributes to the 2E-VRP in the following three ways:

Synchronization of van and ADR: A two-echelon van-ADR delivery network was designed for the e-grocery delivery setting. A mixed-integer programming (MIP) model was developed to model the 2E-LDVRP-MV, where synchronization of the two-echelon vehicles was considered. In this model, flow-based and arc-based variables were combined to make flow assignments and vehicle route decisions.

Load-dependent costs and emissions: Real-life emissions and costs are not a linear function of delivery distance (as assumed in the models of Schneider et al. [ 8 ] and Liu et al. [ 9 ]). We formulated the 2E-LDVRP-MV with load-dependent cost and emissions.

Clustering-based hybrid heuristics: A clustering-based artificial immune algorithm (C-AIA) was proposed to improve the solution quality.

Literature Review

In recent years, with the application of the new forms of transport, the VRP of new delivery methods has received much attention. Dolati Neghabadi et al. ( 10 ) reviewed systematically a comprehensive view of different aspects of city logistics. Integrated delivery ways that have been widely discussed include electric vehicle -based freight transport ( 11 ), delivery packages into car trucks ( 12 ), drone-based goods delivery ( 13 ), and autonomous ground vehicles with lockers ( 14 ). Recently, an autonomous delivery robot company Nuro obtained federal safety permission for grocery delivery robots in the USA. This kind of robot navigates on a road at a low speed and can deliver groceries with a weight that is limited compared with traditional vehicles. Some preliminary results recognized certain sensitive factors related to the adoption of ADRs, such as density of the customers, capacity of the ADRs, and so on. Simoni ( 6 ), Jennings and Figliozzi ( 15 ), and Boysen et al. ( 14 ) also reported these sensitive factors in their studies. In their studies, current regulations on ADRs in the United States were discussed, and existing delivery vehicles and the capabilities of vehicles were also summarized ( 15 ). Furthermore, delivery time and the number of customers managed by an ADR and a van were estimated. Boysen et al. ( 14 ) proposed a method that can schedule the drop-off locations of the robots and then determine the route of a truck. They modeled this as a VRP with synchronization where the number of late deliveries to customers was minimized. To minimize the transport cost, a robot delivery system dispatching from a truck was studied, which was also formulated as a VRP ( 6 ). Although the above-mentioned delivery systems are similar to the multi-echelon or two-echelon VRP (2E-VRP), they did use micro hubs. 2E-VRP was initially proposed by Gonzalez-Feliu ( 16 ), and their newly published outcomes in Perboli et al. ( 17 ) showed that 2E-VRP can be used to model delivery system involving a micro hub. The 2E-VRP is attributed to a VRP of two-echelon delivery connected by micro hubs ( 18 ) with unitary mode vehicles or mixed vehicles. For example, vans and cargo bikes ( 19 ), cargo bikes, and parcel lockers ( 20 ) are integrated into a two-echelon system to achieve a sustainable delivery. Recent studies have also started to evaluate the impact of vehicle load on the VRP ( 21 , 22 ). Zachariadis et al. ( 23 ) investigated a load-dependent VRP (LDVRP) which aimed to produce sustainable routing plans that take into account the variation of the cargo weight along the vehicle trips. However, the impact of load variation of ADRs, and the resulting cost and emission change on the two-echelon delivery network have not yet been addressed.

To address the LDVRP, a clustering-based method was used (18, 24, 25). The reported studies found that, if the distance was the only component to be considered when customers were clustered, the optimal clustering results might not be achieved. This is because smaller orders from customers might first be allocated to a cluster, while larger orders would not be allocated, generating other clusters that increase delivery vehicles. However, a key issue is how to handle customer clustering with multiple variables and the degradation raised by a random iteration without guidance for the initialized clustering. Further, the 2E-VRP is a long-standing NP-hard (non-deterministic polynomial-time hardness) problem. Therefore, it is difficult to obtain an optimal solution by pure exact methods for realistically sized instances within a reasonable time (26, 27). The metaheuristics method was the choice used in most cases ( 28 ). The branch-and-cut algorithm as an exact solution algorithm was used to solve the 2E-VRP (16, 29). For realistically sized instances, the metaheuristics method was adopted as a rule ( 30 ), for example, in the cases of iterated local search ( 31 ), the adaptive large neighborhood search (32 –34), the variable neighborhood search ( 35 ), a hybrid bat algorithm heuristic algorithm ( 36 ). Heuristic algorithms are powerful tools that can get a solution in an acceptable time for realistically sized data. However, all operators iterating randomly without guidance inevitably bring degradation to individuals in a group for most of the heuristics. On the other hand, the crossover and mutation operators are relatively fixed, which ignores auxiliary information in the problem, because every practical problem to be solved has discrete information or knowledge. This kind of “neglect,” especially in solving some complex problems, will produce low-quality solutions. In recent years, one of the soft computing paradigm-artificial immune systems (AIS) has been widely used in various domain areas. It is a heuristic algorithm with a random search, which combines deterministic and stochastic selections and has the ability to “explore” and “mine” ( 37 ). Shukla and Jharkharia ( 38 ) presented a vehicle routing problem (VRP) that was solved by an AIS-based algorithm. Results showed better performance by AIS, compared with the results produced by simulated annealing (SA) and genetic algorithm (GA). To date, there has been no research bringing this computational intelligence paradigms-based AIS to the clustering-based VRP. Taking into consideration various constraints, an efficient technique to optimally solve the load-dependent 2E-VRP with mixed vehicles urgently needs to be developed.

From the status of current models in existing literature, there is no model available to our proposed 2E-LDVRP-MV problem. A new model and algorithm are needed to help better understand the e-grocery delivery network and its potential benefits. A clustering-based artificial immune algorithm (C-AIA) was, therefore, proposed to improve the solution quality. In the following section, the developed model and algorithm are discussed in detail.

Methodology

Problem Definition

In this e-grocery delivery setting, conventional vans travel in the first echelon starting from a depot, visit all the assigned micro hubs, and unload the parcels. ADRs then depart from these micro hubs carrying the packages to all the assigned customers in the second echelon. Compared with the basic 2E-VRP that aims to minimize the distance-based cost in the two echelons, the objective of the 2E-LDVRP-MV in this study is to minimize the total load-distance-based cost that considers the gross weight of the two echelons. Thus, it could produce a reasonable routing plan that considers the variation of the cargo weight. The objective of the 2E-LDVRP-MV is related to the emissions of the vans and ADRs, making it an alternative when the emissions of the delivery are examined and optimized. We do not consider any time window constraints.

Figure 1 illustrates a two-echelon network where groceries are delivered from depot d₁ to customers. We assume that there are two alternative ways to deliver the customer’s request in Figure 1, a and b . The number of the depot, satellite, and customer is chosen as an illustration example. In Figure 1a, customers $f_{1}$ , $f_{2}$ , $f_{3}$ , $f_{4}$ , and $f_{5}$ are served via micro hubs $s_{1}$ , $s_{2}$ , and $s_{3}$ , and the ADR is half loaded. When the micro hub $s_{3}$ is not assigned any customer, customers $f_{1}$ , $f_{2}$ , $f_{3}$ , $f_{4}$ , and $f_{5}$ are served via micro hubs $s_{1}$ and $s_{2}$ . Accordingly, the load assigned to the ADR would increase (fully loaded, not violating the capacity constraint of the ADR) if the vehicle number is fixed. In turn, route decisions for the first and second echelons will be changed (shown in Figure 1b). We can see that by serving five customers with a different route in Figure 1, a and b , the distance traveled and the load carried by each ADR are different, which will directly affect the load-dependent transportation and emission costs.

Figure 1.

Schematic graphs showing a two-echelon delivery network with varied loads: (a) three micro hubs; and (b) two micro hubs.

To find solutions for the two-echelon delivery network, 2E-LDVRP-MV is first presented as a graph W = (N, L), where N is the set of nodes, and L is the set of arcs. Furthermore, three subsets of nodes are represented as depots ( $O$ ), customers ( $F$ ), and micropubs ( $S$ ). We have N = $O \cup F \cup S, N_{1} = O \cup S, N_{2} = S \cup F .$ Accordingly, the 2E-VRP are identified: the first-echelon route is presented by ( $i, j$ ), $(i, j) \in N_{1},$ and the second-echelon route is represented by ( $i$ , $j$ ), $(i, j) \in N_{2}$ . In the first echelon, a limited fleet of vans with capacity $Q_{va n}$ start from a depot ( $O$ ) to visit all of the assigned micro hubs (S) and return to the origin depot. In the second echelon, a limited number of ADRs with a capacity $Q_{ADR}$ ( $Q_{va n} > Q_{ADR}) start$ from micro hubs and visit assigned customers. The groceries are unloaded and loaded in the micro hub $s$ with capacity $P_{s} .$ To solve the 2E-LDVRP-MV, customers are first allocated to the micro hubs in the second echelon, then, routing decisions are made for the ADRs in the second echelon and vans in the first echelon respectively to achieve minimum transport cost and emissions. We made the following assumptions before the model was developed:

Each van and each ADR are assigned to, at most, one route.

Each van in the first echelon can serve indirectly one or more customers.

Each trip in the second echelon must start and terminate at the same micro hub.

In the second echelon, the demand per customer cannot be split among different ADRs. In this way, every customer must be served by one and only one ADR.

In the first echelon, each micro hub’s volume could be allocated to different vehicles and every micro hub could be served by two or more vans.

The total demand assigned to a micro hub from the customers should not be more than the maximum capacity of the micro hub.

The fixed costs of the van and ADR are available in a certain number, which is not considered in the model.

Only one depot serves in the first echelon.

Formulation of the Model

Parameters

$O = {o}$	Depot
$F$ = ${f_{1}, f_{2}, \dots, f_{i}}$	Set of customers
$S$ = ${s_{1}, s_{2}, \dots, s_{i}}$	Set of micro hubs
v	Vehicle types v, v $\in V {van, ADR}$
$Q^{van}$	Capacity of a van
$Q^{ADR}$	Capacity of an ADR
$m^{van}$	Num. of vans
$m^{ADR}$	Num. of ADRs
$m_{s}^{ADR}$	Maximum num. of tours starting from micro hub $s, s \in S$ in the second echelon
$n_{s}$	Num. of micro hubs
$n_{f}$	Num. of customers
$P_{s}$	Micro hub capacity, $s \in S$
${TW}^{van}$	Tare weight of van
${TW}^{ADR}$	Tare weight of ADR
$d_{k}$	Order requested by customer $k$ , $k \in F$
$C_{ij}^{van}$	Unit delivery cost (per package, per mile) between (i, j), (i, j) $\in N_{1}$
$C_{ij}^{ADR}$	Unit delivery cost (per package, per mile) between (i, j), (i, j) $\in N_{2}$
$φ_{ij}^{van}$	Ratio of emission cost between (i, j) $\in N_{1}$
$φ_{ij}^{ADR}$	Ratio of emission cost between (i, j) $\in N_{2}$
$H_{s}$	Unit handling cost per package in micro hub $s, s \in S$
$τ_{s}$	Unit emission cost per package in micro hub $s, s \in S$
$l_{ij}^{van}$	Delivery distance between $(i, j) \in N_{1}$
$l_{ij}^{ADR}$	Delivery distance between $(i, j) \in N_{2}$
$β^{range}$	Maximum battery electric range of an ADR
$σ^{rang}$	Safety buffer of the battery
$u^{v}$	Average speed for vehicle type $v \in V$
$q_{v}$	Maximum capacity of vehicle type v $\in V$

Auxiliary variables

$μ_{ij}^{van}$	Flow delivered $on arc (i, j) \in N_{1}$
$μ_{ijs}^{ADR}$	Flow $delivered on arc (i, j) \in N_{2}$ coming from micro hub $s, s \in S$

Decision Variables

$x_{ij}$	Vehicle number $travels on arc (i, j) \in N_{1}$
$y_{ijs}^{ADR}$	${\begin{matrix} 1, if an ADR travels on arc (i, j) \in N_{2} and starting from micro hub s, s \in S \\ 0, otherwise \end{matrix}$
$z_{sj}$	${\begin{matrix} 1, if micro hub s serves customer j, s \in S \\ 0, otherwise \end{matrix}$

2E-LDVRP-MV model

\begin{matrix} Min \sum_{i \in N_{1}} \sum_{j \in N_{1}} C_{ij}^{van} l_{ij}^{van} x_{ij} \\ + \sum_{s \in S} \sum_{i \in N_{2}} \sum_{j \in N_{2}} C_{ij}^{ADR} l_{ij}^{ADR} y_{ijs}^{ADR} \\ + \sum_{i \in N_{1}} {\sum_{j \in N_{1}} φ}_{ij}^{van} l_{ij}^{van} x_{ij} \\ + \sum_{s \in S} \sum_{i \in N_{2}} \sum_{j \in N_{2}} φ_{ij}^{ADR} l_{ij}^{ADR} y_{ijs}^{ADR} \\ + \sum_{s \in S} H_{s} \sum_{j \in F} d_{j} z_{sj} + \sum_{s \in S} τ_{s} \sum_{j \in F} d_{j} z_{sj} \end{matrix}

(1)

It should be noted that the unit costs $C_{ij}^{van}, C_{ij}^{ADR}$ are not fixed constants, but the proportional function to the volume of delivery groceries $(μ_{ij}^{van}, μ_{ijs}^{ADR}) .$ The unit emissions are not fixed constants, but the proportional function to the gross vehicle weight ( $μ_{ij}^{van} + {TW}^{van}, μ_{ijs}^{ADR} + {TW}^{ADR})$ and travel speed $u^{v},$ respectively.

Equation 1 minimizes the load-dependent transport cost and emission cost, which is subject to:

(a) Vehicle availability constraints

\sum_{j \in N_{1}} x_{oj} \leq m^{van}, \forall o \in O

(2)

\sum_{j \in F} y_{sjs}^{ADR} \leq m^{ADR}, \forall s \in S

(3)

\sum_{j \in F} y_{sjs}^{ADR} \leq m_{s}^{ADR}, \forall s \in S

(4)

Equation 2 sets a limitation on the number of vans. Equation 3 sets a limitation on the number of ADRs. Equation 4 sets a limitation on the maximum number of routes.

(b) Flow conservation constraints

\sum_{s \in S} x_{si} = \sum_{s \in S} x_{is}, \forall i \in N_{1}

(5)

\sum_{j \in F} y_{sjs}^{ADR} = \sum_{j \in F} y_{jss}^{ADR}, \forall s \in S

(6)

y_{ijs}^{ADR} \leq z_{sj} \forall i \in N_{2}, j \in F, s \in S

(7)

y_{jis}^{ADR} \leq z_{sj} \forall i \in S, j \in F, s \in S

(8)

\sum_{s \in S} z_{sj} = 1 \forall j \in F

(9)

y_{sjs}^{ADR} \leq \sum_{i \in N_{1}} x_{si}, \forall j \in F, s \in S

(10)

Equation 5 guarantees that in each micro hub, the entering and leaving number of vehicles is the same; and in particular when $i \in O,$ the van traveled in the first echelon starts and terminates at the same depot. Equation 6 ensures that each second-echelon route should start and end at the same micro hub. Equations 7 and 8 indicate only if a customer j receives a delivery from a micro hub s, the customer is allocated to that micro hub. Equation 9 sets the limitation that each customer can only be served by one micro hub. Equation 10 ensures only if a first-echelon route contains micro hub s, s is the starting point of a second-echelon route.

\sum_{i \in N_{1}} μ_{ij}^{van} - \sum_{i \in N_{1}} μ_{ji}^{van} = {\begin{matrix} \sum_{k \in F} d_{k} z_{jk} if j is not a depot \\ \sum_{k \in F} - d_{k} otherwise \end{matrix} \forall j \in N_{1}, i \neq j

(11)

\sum_{i \in N_{2}} μ_{ijs}^{ADR} - \sum_{i \in N_{2}} μ_{jis}^{ADR} = {\begin{matrix} z_{sj} d_{j} if j is not a micro hub \\ - \sum_{k \in F} d_{k} z_{jk} otherwise \end{matrix} \forall j \in N_{2}, s \in S, i \neq j

(12)

Equation 11 ensures that the volume of groceries delivered in the first echelon via a micro hub comprises the order of the micro hub, except for depots that the delivery volume consists of all the orders from the customers. Equation 12 ensures that the volume of delivery in the second echelon consists of the orders (unknown) assigned to the micro hubs. Besides, Equations 11 and 12 restrict sub-tours navigating in the two echelons, respectively.

(d) Capacity restrictions

μ_{ij}^{van} \leq Q^{van} x_{ij} \forall i, j \in N_{1}, i \neq j

(13)

μ_{ijs}^{ADR} \leq Q^{ADR} y_{ijs}^{ADR} \forall i, j \in N_{2}, s \in, i \neq j

(14)

z_{sj} = \sum_{i \in N_{2}} y_{ijs}^{ADR} \forall j \in F, s \in S

(15)

z_{sj} = \sum_{i \in S} y_{jis}^{ADR} \forall j \in F, s \in S

(16)

\sum_{s \in S} z_{sj} d_{j} \leq P_{s} \forall j \in F, s \in S

(17)

Equations 13 and 14 set capacity limitations on delivering vehicles. Equations 15 and 16 show that each customer can only be served by one ADR. Furthermore, Equation 16 sets the constraint that an ADR departs from micro hub s and serves customer j only if the customer is assigned to the micro hub. Equation 17 ensures that the capacity of a micro hub should be more than the total demand assigned to the micro hub.

(e) Battery life limit constraints

\sum_{i \in N_{2}} \sum_{j \in N_{2}} l_{ij}^{ADR} y_{ijs}^{ADR} \leq β^{range} - σ^{range} \forall s \in S

(18)

Equation 18 guarantees that each tour in the second echelon should be less than the maximum operating life of a battery. Besides, the right side of the inequality ensures the reserved safety buffer for unforeseen circumstances during one navigation.

(f) Variable definition

x_{ij} \in Z^{+}, \forall i, j \in N_{1}

(19)

y_{ijs}^{ADR} \in {0, 1} \forall i, j \in F, s \in N_{2}

(20)

z_{sj} \in {0, 1} \forall j \in F, s \in N_{2}

(21)

μ_{ij}^{van} \geq 0 \forall i, j \in N_{1}

(22)

μ_{ijs}^{ADR} \geq 0 \forall i, j \in N_{2}, s \in S

(23)

The variable constraints were defined in Equations 19 to 23.

Discussion of the Model

To illustrate the impact of the vehicle type on the transport cost and emission, we introduced parameter $σ$ = $\frac{Q^{v}}{T W^{v}},$ which represents the ratio between the maximum load of the vehicle and the empty vehicle weight: for a high $σ,$ the weight of grocery contributes more to the gross weight carried. On the contrary, for a low $σ,$ the weight of empty vehicle contributes more to the gross weight carried. We present this quantifying characteristic in Figure 2. Let $Q^{ADR} = 76$ , the demand of customers $f_{1}$ , $f_{2}, f_{3}$ are 29, 19, and 42, respectively, the tare vehicle weight of ADR is $\frac{Q^{A D R}}{σ}$ .

Figure 2.

The example network of one micro hub and three customer locations.

Let $C_{distance}$ = $\sum_{(i, j) \in N_{2}} l_{ij}$ represent the distance-based transport objective without considering the load of the vehicles. $C_{load - distance}$ = $\sum_{(i, j) \in N_{2}} (\frac{Q^{A D R}}{σ} + d_{i j}) l_{i j}$ represents the load-distance-based transport objective.

C_{distance} (s_{1}, f_{1}, f_{2}, f_{3}, s_{1}) = 7 + 17 + 24 + 29 = 67

\begin{matrix} C_{load - distance} (s_{1}, f_{1}, f_{2}, f_{3}, s_{1}) \\ = 7 (\frac{90}{σ} + 90) + 17 (\frac{90}{σ} + 29) + 24 (\frac{90}{σ} + 19) + 29 (\frac{90}{σ}) = \frac{6930}{σ} + 1580 \end{matrix}

\begin{matrix} C_{distance} (s_{1}, f_{1}, f_{3}, f_{2}, s_{1}) = 7 + 10 + 25 + 18 = 60 \\ C_{load - distance} (s_{1}, f_{1}, f_{3}, f_{2}, s_{1}) \\ \frac{= 7 (\frac{90}{σ} + 90) + 10 (\frac{90}{σ} + 29) + 25 (\frac{90}{σ} + 42) + 18 (\frac{90}{σ}) = 5400}{σ} + 3720 \end{matrix}

Compare the solution results of the distance-based and load-distance-based VRP,

$r_{d i s t a n c e} = \frac{C_{d i s t a n c e} (s_{1}, f_{1}, f_{2}, f_{3}, s_{1})}{C_{d i s t a n c e} (s_{1}, f_{1}, f_{3}, f_{2}, s_{1})} = 1.12,$ indicating that the route of ${s_{1}, f_{1}, f_{3}, f_{2}, s_{1}}$ is shorter than ${s_{1}, f_{1}, f_{2}, f_{3}, s_{1}}$ .

r_{l o a d - d i s t a n c e} = \frac{C_{l o a d - d i s t a n c e} (s_{1}, f_{1}, f_{2}, f_{3}, s_{1})}{C_{l o a d - d i s t a n c e} (s_{1}, f_{1}, f_{3}, f_{2}, s_{1})}

= $(\frac{6930}{σ} + 1580) / (\frac{5400}{σ} + 3270),$ indicating that the preferred route depends on the $σ$ value, as shown in Figure 3. When $σ$ = 0.71, $r_{load - distance}$ = 1, which means that the solutions of route ${s_{1}, f_{1}, f_{3}, f_{2}, s_{1}}$ and ${s_{1}, f_{1}, f_{2}, f_{3}, s_{1}}$ are equal. In addition, we found that when $σ$ = 2, $r_{load - distance} =$ 0.79, which means that the ${s_{1}, f_{1}, f_{3}, f_{2}, s_{1}}$ improved the ${s_{1}, f_{1}, f_{2}, f_{3}, s_{1}}$ by almost 21%.

Figure 3.

Comparison of the objective ratio for distance-based vehicle routing problem (VRP) and load-distance-based VRP.

Considering the significant impact of vehicle load and empty vehicle weight on the route decision, in our model, the transport cost was formulated as Equation 24 ( 39 ),

c_{ij} (μ_{ij}^{v}, l_{ij}, Q^{v}) = \frac{μ_{ij}^{v} C^{v} (l_{ij}^{v})}{σ Q^{v}}

(24)

where $μ_{ij}^{v}$ is the grocery flow between (i, j) using vehicle type v, $C^{v} (l_{ij}^{v})$ is the unit transport cost using vehicle type v, which is described as a function of the distance $l_{ij}^{v}$ between (i, j), and $σ$ is the factor of vehicle weight; and $Q^{v}$ is the capacity of each vehicle.

To formulate the emission cost of vehicles on arc (i, j), the vehicle type v is assumed to deliver at an average speed of $u_{v}$ on (i, j), the travel distance is $l_{ij}^{v}$ , and the total load carried is $T W^{v} + μ_{ij}^{v}$ , where $T W^{v}$ is the empty vehicle weight, and $μ_{ij}^{v}$ is the load carried on the arc (i, j). The resulting approximation yields energy consumption, which directly translates into fuel emissions. The total consumed energy on arc (i, j) can then be approximated in the following formula ( 21 ).

C_{emissions} = φ_{ij}^{v} α_{ij} (T W^{v} + μ_{ij}) l_{ij}^{v} + φ_{ij}^{v} ω u_{v}^{2} l_{ij}^{v}

(25)

where $α_{ij}$ is a specific constant for arcs, $ω$ is a specific constant for vehicles, and $u_{v}$ is assumed to be constant.

Solution Framework

Given the high complexity of the 2E-LDVRP-MV model, a learning-based heuristic consisting of the following three parts was used to solve the 2E-LDVRP-MV. The hybrid algorithm starts from an initial feasible solution generated by k-mean clustering (Algorithm 1). The Clarke and Wright saving method was then used to construct the routes in the two echelons. Eventually, two heuristics operators, vaccination and immune selection, were introduced to improve the final solutions (Algorithm 2).

Customer Clustering with Balance Constraints

To obtain the vehicle routing in the two echelons, we adopted a philosophy of clustering first and routing second. In this study, to better verify the impact of the load-dependent characteristics of ADRs on the vehicle routing, we assumed that there was one depot in the first echelon and that the 2E-LDVRP-MV can be altered to a multi-depot-LDVRP-MV. First, customers were assigned to the micro hubs based on the distance and loads of the customers. The clustered nodes were then assigned vehicles and routes were constructed by connecting the nodes ( 18 ).

Algorithm 1. Customer Clustering with Balance Constraints
Input: Coordinates ( $x_{i}$ , $y_{i}$ ) Demands $d_{k}$ Customer $f_{i}$ Output: k clusters Procedure: Calculate k= $[\frac{\sum_{f_{i} \in F} d_{f_{i}}}{P_{s_{i}}}]$ Select k satellites as the initial centroid while each customer $f_{i}$ ∈ $F is$ not converged while $f_{i}$ is not allocated. Sort the demand of customers from high to low and measure the Euclidean distance to each cluster k. Calculate the priority value for $f_{i}$ using $δ_{f_{i}}$ = $θ (f_{i}, s_{i})$ / $d_{f_{i}}$ ( $θ (f_{i}, s_{i})$ is the Euclidean $distance)$ . Assign the nearest centroid of $f_{i}$ as m using $δ_{f_{i}}$ . Group all unallocated requesters as G with m as their nearest centroid. Assign $f_{i}$ to their nearest centroid based on the priority value without violating the vehicle’s capacity. Update $P_{k_{i}}$ . If $f_{i}$ is not allocated, then the next nearest centroid will be chosen. end if end while end for Update the new centroid based on the clusters generated before using $x_{j} = \frac{\sum_{m = 1}^{j} x_{m}}{n_{j}}$ $and y_{j} = \frac{\sum_{m = 1}^{j} y_{m}}{n_{j}}$ where ( $x_{j}, y_{j}$ ) represents the j^th centroid and $n_{j}$ represents the number of customers in cluster j. end while

Algorithm 1. Customer Clustering with Balance Constraints

Input:
Coordinates (

x_{i}

, $y_{i}$ )
Demands $d_{k}$
Customer

f_{i}

Output:
k clusters
Procedure:
Calculate k=

[\frac{\sum_{f_{i} \in F} d_{f_{i}}}{P_{s_{i}}}]

Select k satellites as the initial centroid
while each customer

f_{i}

∈

F is

not converged
while

f_{i}

is not allocated.
Sort the demand of customers from high to low and measure the Euclidean distance to each cluster k.
Calculate the priority value for

f_{i}

using

δ_{f_{i}}

θ (f_{i}, s_{i})

d_{f_{i}}

(

θ (f_{i}, s_{i})

is the Euclidean

distance)

.
Assign the nearest centroid of $f_{i}$ as m using

δ_{f_{i}}

.
Group all unallocated requesters as G with m as their nearest centroid.
Assign

f_{i}

to their nearest centroid based on the priority value without violating the vehicle’s capacity.
Update

P_{k_{i}}

.
If

f_{i}

is not allocated, then the next nearest centroid will be chosen.
end if
end while
end for
Update the new centroid based on the clusters generated before using

x_{j} = \frac{\sum_{m = 1}^{j} x_{m}}{n_{j}}

and y_{j} = \frac{\sum_{m = 1}^{j} y_{m}}{n_{j}}

where (

x_{j}, y_{j}

) represents the j^th centroid and

n_{j}

represents the number of customers in cluster j.
end while

Routing and Scheduling

The Clarke and Wright saving method was used to route the customers in the second echelon and micro hubs in the first echelon, respectively. We used the nearest neighbor heuristic ( 40 ) to solve the scheduling problem.

Application of the C-AIA to the MDVRP

After initializing the algorithm in the first step, we searched for the solutions to 2E-LDVRP-MV with an artificial immune algorithm, which integrates the vaccination and immune selection with the genetic algorithm ( 41 ). To better present the operator of vaccination and immune selection, we used the following settings: $y_{ψ, j}^{i}$ is the vaccinated individual of j^th antibody $y_{j}^{i}$ in generation g. $P_{I}$ is the probability of vaccination, and $P_{V}$ is the probability of immune selection. Vaccine ( $y_{g}^{i}, ψ_{j})$ represents that $y_{g}^{i}$ is vaccinated in the form of $ψ_{j}$ , n and m is the size of the population and vaccine, respectively.

Algorithm 2. Vaccination and Immune Selection
Begin: g=0, and j=0; while (Conditions = True) if ${P_{V}}$ = Ture, then j= j+1; i=0; for (i $\leq n)$ Vaccination: $y_{ψ, j}^{i} = Vaccin e_{{P_{I}}} {y_{j}^{i}, ψ_{j}}$ Immune test: if $y_{ψ, g}^{i} < y_{g - 1}^{i}, then y_{g}^{i} = y_{g - 1}^{i};$ else $y_{g}^{i} = y_{ψ, g}^{i};$ Immune selection: $Y_{g + 1} = S (Y_{g});$ g=g+1; end

Exprimental Analyses and Results

To test the effectiveness of the 2E-LDVRP-MV, we first tested the model using a small-scale data set on Gurobi 9.1.2. The C-AIA was then coded on an Intel core 2 Duo (2.00 GHz), 6GB RAM PC with MATLAB R2020b.

Parameter Values and Data Set

We evaluated the performance of the 2E-LDVRP-MV using four data sets (Table 1). Data sets 1 and 2 were acquired from Crainic et al. ( 42 ), and the number of micro hubs was set according to the number of customers. The micro hubs were randomly selected from customers. In data sets 1 and 2, the depot was located near the center area of the distribution district (it is marked “near” in the tables). Considering the layout of the micro hubs in practice, in data set 3, the micro hubs selected bordered randomly with the customers with low density, and the depot was located far from the center of the service area (marked “far” in the following tables). The fourth and fifth data sets were generated from Crainic et al. ( 42 ).

Table 1.

Data set Description

Set	Num instances	Depot location	$n_{s}$	$n_{f}$	$m^{van}$	$m^{ADV}$	$Q^{van}$	$Q^{ADV}$	Micro hub distribution
1	3	Near	2	6	2	4	1,320	360	Random
1	4	Near	3	8	3	5	1,320	360	Random
1	3	Near	3	10	4	6	1,320	360	Random
2	6	Near	2	21	2	4	1,320	360	Random
2	6	Near	3	21	2	4	1,320	360	Random
2	6	Near	2	32	3	5	1,320	360	Random
2	6	Near	3	32	4	6	1,320	360	Random
3	6	Far	2	21	3	4	1,320	360	Border random
3	6	Far	3	21	3	4	1,320	360	Border random
3	6	Far	2	32	4	5	1,320	360	Border random
3	6	Far	3	32	4	6	1,320	360	Border random
4	8	Far	2	50	6	8	1,320	360	Random
5	4	Far	5	100	8	10	1,320	360	Random

We chose two kinds of vehicle to compare the operating costs and emissions. Isuzu N-SERIES was selected as the first echelon vehicle because it is a commonly used as a grocery delivery vehicle, and Nuro-R was selected as the second-echelon vehicle as it is more flexible for making the parcel transfer without needing a “mothership” truck to carry it. At the same time, Nuro-R is not restricted to very low speeds and can be applied in grocery delivery scenarios. In Table 2, the rates of vehicle energy consumption and CO₂ emissions for the two types of vehicle are compared. We calculated energy costs and CO₂ emission costs per mile for ADRs and vans based on the formula proposed by Feng and Figliozzi ( 43 ). The unit handling cost refers to Veenstra et al. ( 44 ). It was assumed that if an ADR is fully charged, it can go up to 100 mi before recharging.

Table 2.

Comparison of Vans and Autonomous Delivery Robots (ADR) Characteristics

Vehicle type	Isuzu N-SERIES	Nuro-R1
Energy price	$3.08/gal ( 45 )	$ 0.1048/KW h ( 45 )
CO₂ emissions	8.92 kg/gal ( 46 )	0.69kg/kw h (46, 47)
Energy consumption	13.46 mpg ( 43 )	0.8 mpg ( 48 )
Operating cost	$ 0.23/mi ( 4 )	$ 0.09/mi ( 4 )
Maintenance cost	$ 0.36/mi ( 4 )	$ 0.20/mi ( 4 )
Fixed cost	$2.1/mi ( 4 )	$ 0.5/mi ( 4 )
Speed	80 mph ( 7 )	25 mph ( 7 )
Vehicle weight	3,900 lbs ( 49 )	1,500 lbs ( 49 )
Payload	6,830 lbs	419 lbs ( 49 )

We tested the 2E-LDVRP-MV with Gurobi for small-scale instances at the end of the 1-h time limit. Figure 4 shows the number of no-solutions and non-optimal solutions as well as the optimal solutions for data set 1. We found that Gurobi generated solutions for up to 10 customers, which took over 3,600 s. When the number of customers increased, the number of no-solutions and non-optimal solutions increased rapidly.

Figure 4.

Results with Gurobi for 2E-LDVRP-MV.

To evaluate the proposed methodology in larger-scale data sets, we compared the performance of the C-AIA with hybrid genetic algorithm 2 (HGA-2, without improved initialization and immune operator) ( 50 ) using up to 100 customers. Table S1 in the Appendix lists the instance name and the number of satellites in Columns 1 and 2. Columns 3, 4, 5, and 6 represent the performance of the C-AIA, and Columns 7, 8, 9, and 10 represent the performance of the HGA-2, providing for each heuristic with the value of the best initial population, the computational time, the final best solution, and the improvement rate. In Figure 5a, we found that the final best solutions produced by C-AIA are superior to those generated by HGA-2, since the percentage of minimal cost and emission produced by C-AIA (16/24) is higher than HGA-2 (8/24). This phenomenon proves that the initialization step and immune operators adopted significantly improved the solution results. The running time of C-AIA was slightly longer than that of HGA-2 (as shown in Table S1). However, the improvement rates of C-AIA (13/24) are superior to HGA-2(11/24), as shown in Figure 5b.

Figure 5.

Performance comparision between C-AIA and HGA-2: (a) comparison of the final best solution for C-AIA and HGA-2 and (b) comparison of the improment rate for C-AIA and HGA-2.

Sensitivity Analysis

In this section, the impact of four sensitive factors of the 2E-LDVRP-MV model were analyzed: (a) the load to tare vehicle weight; (b) unitary mode vehicles (vans) and mixed vehicles (van-ADRs); (c) breakdown of transport cost and emissions; and (d) the customer density. All the data sets together with the proposed methodologies allowed us to reach the conclusions. The execution parameters of the C-AIA were set as follows: size of population = 100; number of iterations = 600; rate of crossover = 0.4; rate of mutation = 0.03; number of memory cell = 10; and suppressor cell number = 5.

The Load to Empty Vehicle Weight

To investigate the impact of $σ,$ data set 1 (n ≤ 10) was selected to ensure high-quality solutions. For instances in data set 1, the σ value is taken from ${0, 0.4, 0.8, 1.2, 1.6, 2.0}$ . Some of these ratios were acquired based on realistic vehicle data, while others were not realistic and were used to show how the model reacts and how the route choice would form in extreme situations such as σ = 2, representing the vehicle being fully loaded. So, it is mostly experimental for us to see what happened in each case, and what would be the best combination of transportation and emission cost for the route choice. When σ = 0, the vehicle is empty. Considering the available ADR (4, 5, or 6), the vehicle number was classified into three types: M-1, M-2, and M-3. Figure 6 represents the percentage gap between the load-distance-based objective and distance-based objective. It shows that the gap between load-distance-based objectives for M-1 is $r_{load - distance}$ = 5.6% when σ = 2, while the gap for M-2 is 6.6% when σ = 2. And it reduces to 6.5% when the type of vehicle is M-3. This observation also shows that the shape of the solutions is defined to a great extent by the capacity of ADRs when the fleet number is small.

Figure 6.

Comparison of the percent gap between load-distance and distance objectives.

Unitary Mode Vehicles (Vans) and Mixed Vehicles (Van-ADRs)

The use of mixed vehicles is a likely reason for the reduction in emission cost and an increase in distance cost. To determine whether the increase in marginal cost was associated with marginal reductions of emissions, we compared the distance cost and load-distance cost for both mixed vehicles and unitary mode vehicles in Table 3. In the case of unitary mode vehicles, the model used Isuzu N-SERIES (σ = 2) whereas, in the case of mixed vehicles, the model used Isuzu N-SERIES in the first echelon and Nuro-R1 (σ = 1.2) in the second echelon. Minimizing the distance did not, therefore, always reduce emissions since the load on the vehicle and its type significantly affect fuel consumption.

Table 3.

Comparison of Distance Cost Savings (%) and Load-Distance Cost Savings (%)

			Mixed vehicles (van-ADR)		Uni-mode (van)
Instances	Distance cost (i)	Load-distance cost (ii)	Distance cost (iii)	Load-distance cost (iv)	Distance cost savings (%) (iii–i)	Load-distance cost savings (%) (iv–ii)
E2-f22-x4-s6-17	465.82	431.35	451.29	451.29	−14.53	19.94
E2-f22-x4-s8-14	85.97	74.80	81.43	81.43	−4.54	6.64
E2-f22-x4-s9-19	518.58	499.16	495.50	495.50	−23.08	3.66
E2-f33-x4-sl-9	822.71	757.01	787.84	787.84	−34.87	3.08
E2-f33-x4-s2-13	744.12	737.07	747.65	747.65	3.53	10.58
E2-f33-x4-s3-17	742.34	740.4	731.92	731.92	−10.42	8.48
E2-50-s2-1	1,490.91	1,442.33	1,490.16	1,490.16	−0.75	47.83
E2-50-s2-2	1,599.97	1,578.89	1,616.27	1,616.27	16.3	37.38
E2-100-5-1	2,860.78	2,457.76	2,908.02	2,908.02	1.45	18.32
E2-100-5-1	2,688.54	2,133.41	2,599.13	2,599.13	−3.44	21.83
Average	1,201.97	1,085.22	1,190.92	1,190.92	−7.03	17.77

Note: ADR = autonomous delivery robots.

Note: ADR = autonomous delivery robots.

Having unitary mode vehicles (Isuzu N-SERIES) without satellites resulted in lower distance-based costs than mixed vehicles (Isuzu N-SERIES – Nuro-R1). The average distance-based cost saving is 7.03%. Fewer detours were generated in unitary mode vehicles compared with the mixed vehicles, and this led to less handling costs being generated. The mode of mixed vehicles resulted in lower load-distance costs than unitary mode vehicles. In two cases, operating van-ADRs resulted in a better load-distance cost, which saved 17.77% of average costs. We attribute these variations in unitary mode and mixed vehicles cases to the reduction in empty and less than truckload trips.

Breakdown of Transport Cost and Emissions

In this subsection, we discuss the impact of σ value and resultant two types of cost ratio on the two-echelon delivery network, namely the cost ratios between load-dependent transport and emission (CRTE), and the transport cost ratios between van and ADR (CTRVA). The numbers for the ratios of both CRTE and CTRVA taken into consideration were estimated based on σ value, which shows how the route choice would form in different situations. Results in Table 4 are the percentages between the minimum cost and all instances from all data sets. It was seen that the minimum and maximum total costs were not reached for different CRTE and CTRVA. For instance, the minimum total cost was reached when CTRVA = 0.7 and CRTE = 0.3, while the maximum total cost was reached when CTRVA = 0.9 and when CRTE = 0.5. The minimum and maximum values in Table 4 are shown in bold. These outcomes show a case of the relationships between cost ratios of vans and ADRs, and ratios between transport cost and emission costs. Obviously, these results lie on the input data, but it proves the need for mathematical modeling to identify the optimal network design.

Table 4.

Percentages of the Minimum Value of all the Instances Under Different CTRVA and CRTE

		CRTE
CTRVA		0.1	0.2	0.3	0.4	0.5
0.5	Total cost*	1.05	1.06	1.11	1.09	1.20
	Transport cost**	1.04	1.08	1.00	1.00	1.02
	Emission cost***	1.15	1.12	1.00	1.32	1.42
0.6	Total cost	1.21	1.14	1.18	1.25	1.26
	Transport cost	1.23	1.13	1.19	1.19	1.19
	Emission cost	1.23	1.26	1.26	1.29	1.34
0.7	Total cost	1.34	1.32	1.00	1.38	1.38
	Transport cost	1.31	1.30	1.30	1.30	1.30
	Emission cost	1.18	1.30	1.24	1.70	1.51
0.8	Total cost	1.67	1.43	1.54	1.56	1.49
	Transport cost	1.97	1.63	1.63	1.63	1.63
	Emission cost	1.29	1.19	1.31	1.52	1.52
0.9	Total cost	1,44	2.08	2.10	1.77	1.71
	Transport cost	1.72	2.51	2.51	2.01	2.63
	Emission cost	1.01	1.14	1.16	1.69	1.40
1.0	Total cost	1.75	2.01	1.69	1.62	1.75
	Transport cost	1.94	1.89	1.81	1.89	1.88
	Emission cost	1.02	1.19	1.27	1.35	1.53

Note: CTRVA = transport cost ratios between van and ADR; CRTE = cost ratios between load-dependent transport and emission.

% of minimum total cost over all instances; **% of minimum transport cost over all instances; ***% of minimum emissions cost over all instances.

Emission Levels and Customer Densities

In addition, we analyzed the solution outcomes for depot–customer layouts and the customer densities when CTRVA and CRTE are fixed in this sub-section.

When customers are located in a dense area [15, 15], and CTRVA = 0.9, CRTE = 0.5, the total cost increases for most of the instances (83%) when the depot moves from the “near the service area” to “far from the service area,” as shown in Table 5. However, when CTRVA = 0.7 and CRTE = 0.3, the percentage reduces to 58%. Generally, we found that when the customer density runs high, the percentage of the lowest cost is higher when CTRVA = 0.7 and CRTE = 0.3.

Table 5.

Customers Located in an Area [15, 15]

Instances*	Depot location	Cost	Depot location	Cost	Instances	Depot location	Cost	Depot location	Cost
CTRVA = 0.9, CRTE = 0.5					CTRVA = 0.7, CRTE = 0.3
E2-f22-x4-s6-17	Near	423.82	Far away	442.33	E2-f22-x4-s6-17	Near	435.9	Far away	431.35
E2-f22-x4-s8-14	Near	69.97	Far away	78.885	E2-f22-x4-s8-14	Near	78.445	Far away	74.795
E2-f22-x4-s9-19	Near	498.58	Far away	501.53	E2-f22-x4-s9-19	Near	485.86	Far away	499.16
E2-f22-x4-sl0-14	Near	439.43	Far away	438.18	E2-f22-x4-sl0-14	Near	424.65	Far away	437.22
E2-f22-x4-sll-12	Near	425.68	Far away	434.57	E2-f22-x4-sll-12	Near	420.63	Far away	432.58
E2-f22-x4-sl2-16	Near	107.20	Far away	113.25	E2-f22-x4-sl2-16	Near	105.93	Far away	105.50
E2-f33-x4-sl-9	Near	752.71	Far away	757.01	E2-f33-x4-sl-9	Near	764.71	Far away	757.01
E2-f33-x4-s2-13	Near	744.12	Far away	739.42	E2-f33-x4-s2-13	Near	744.61	Far away	737.07
E2-f33-x4-s3-17	Near	730.34	Far away	739.60	E2-f33-x4-s3-17	Near	727.20	Far away	740.4
E2-f33-x4-s4-5	Near	831.81	Far away	836.75	E2-f33-x4-s4-5	Near	757.81	Far away	830.82
E2-f33-x4-s7-25	Near	841.25	Far away	859.24	E2-f33-x4-s7-25	Near	836.43	Far away	855.91
E2-f33-x4-sl4-2	Near	623.72	Far away	625.01	E2-f33-x4-sl4-2	Near	601.75	Far away	626.67

Note: CTRVA = transport cost ratios between van and ADR; CRTE = cost ratios between load-dependent transport and emission.

From data sets 2 and 3. The use of bold words represents better results that are achieved comparing the two scenarios.

When customers are located in a sparse area [100, 100], the costs decrease by 62% when the depot moves from “near the service area” to “far from the service area” for both scenarios (CTRVA = 0.9, CRTE = 0.5; CTRVA = 0.7, CRTE = 0.3.) The result in Table 6 shows that the percentage of the minimal cost (88%) is higher when CTRVA = 0.7 and CRTE = 0.3 compared with CTRVA = 0.9 and CRTE = 0.5 (63%). This phenomenon could be explained by the total cost being affected by emission costs and package consolidation costs.

Table 6.

Customers Located in an Area [100, 100]

Instances*	Depot location	Cost	Depot location	Cost	Instances	Depot location	Cost	Depot location	Cost
CTRVA = 0.9, CRTE = 0.5					CTRVA = 0.7, CRTE = 0.3
Instance 50-s2-1	Near	1,489.91	Far away	1,442.33	Instance 50-s2-1	Near	1,499.9	Far away	1,479.32
Instance 50-s2-2	Near	1,669.97	Far away	1,578.89	Instance 50-s2-2	Near	1,578.45	Far away	1,554.80
Instance 50-s2-3	Near	1,518.58	Far away	1,501.53	Instance 50-s2-3	Near	1,485.86	Far away	1,499.16
Instance 50-s2-4	Near	1,529.43	Far away	1,538.18	Instance 50-s2-4	Near	1,524.65	Far away	1,537.93
Instance 50-s2-5	Near	1,625.68	Far away	1,644.57	Instance 50-s2-5	Near	1,640.63	Far away	1,632.58
Instance 50-s2-6	Near	1,612.64	Far away	1,630.60	Instance 50-s2-6	Near	1,565.52	Far away	1,547.33
Instance 50-s2-7	Near	1,712.07	Far away	1,707.29	Instance 50-s2-7	Near	1,589.73	Far away	1,579.32
Instance 50-s2-8	Near	1,850.42	Far away	1,822.10	Instance 50-s2-8	Near	1,744.61	Far away	1,737.07

Note: CTRVA = transport cost ratios between van and ADR; CRTE = cost ratios between load-dependent transport and emission.

From data set 4. The use of bold words represents better results that are achieved comparing the two scenarios.

In addition, we found that the percent deviation of objectives aroused by CTRVA and CRTE in sparse areas is larger than that in the dense areas, as shown in Figure 7.

Figure 7.

The impact of emission levels and customer densities in: (a) a dense area [15, 15]; and (b) a sparse area [100, 100].

Discussion

In this study we present a generalization of the VRP for an ADR-assist e-grocery delivery network which is of major practical importance. We call the problem a two-echelon load-dependent VRP with mixed vehicles (2E-LDVRP-MV), which is very well suited for making low-carbon last-mile deliveries. In the last-mile deliveries, the weight of delivered products contributes significantly to the gross weight of the ADR. Contrary to the traditional two-echelon VRP with a distance-based objective, the 2E-LDVRP-MV calls for the minimization of the load-distance-based objective, which is capable of generating sensitive analysis of the variable rate of load and empty vehicle weight. In addition, the 2E-LDVRP-MV provides a basis for minimizing the total delivery cost and at the same time the emissions from a technical planning view. Except for the basic assumptions of the two-echelon VRP, the present study is the first to introduce the 2E-LDVRP with mixed vehicles requiring synchronization of van and ADR. To capture these characteristics and optimize the routing extensions, a new model was formulated.

To solve the proposed 2E-LDVRP-MV, we proposed a powerful clustering-based artificial immune algorithm (C-AIA) to find solutions. In C-AIA, customer clustering with balance constraints was employed to generate initialization. In addition, two operators, vaccination and immune selection, were integrated into the heuristics. The basic features of our algorithmic design are that the initialization of a solution was performed efficiently by a balanced clustering method, while the search was diversified by the two operators.

The proposed model and algorithm were evaluated through five data sets, which were newly constructed or taken from the literature. The results proved the feasibility of the developed model on a small-scale data set through the business solver Gruobi. In addition, C-AIA was proved to be more efficient in finding high-quality solutions than HGA-2 through comparing the final best solution and improvement rate on larger-scale data sets. Furthermore, extensive computational experiments were conducted in this study to examine the effect of some key sensitive parameters: the load to tare vehicle weight; unitary mode vehicles (vans) and mixed vehicles (van-ADRs); breakdown of transport costs and emissions; and the customer density. Our experiments also revealed that the depot location significantly affects the total transport cost and emission cost when customers are located in the dense area, specifically when the characteristics of mixed vehicles were considered, namely the cost ratios between load-dependent transport and emission (CRTE), and the transport cost ratios between van and ADR (CTRVA). Furthermore, we found that, no matter what the customer density is, a higher percentage of the minimal total costs for the two-echelon delivery system can be obtained in our experiments when CTRVA = 0.7 and CRTE = 0.3, which shed light on the importance of vehicle type selections when planning the low emission ADR-assist two-echelon delivery system.

Although the instances generated in this research presented limited distributions of the depots, micro hubs, and customers in urban delivery settings (on which there is a big gap in actual urban grocery delivery considering the road conditions) this study provides a unique strategy for a sustainable e-grocery delivery network design that integrates mixed vehicles for last-mile delivery. For future research directions, the model and algorithm need to be tested in more real-life data sets. Furthermore, other constraints will be considered in the model. For example, the load-dependent objective should be incorporated into practical two-echelon VRPs with pickup and delivery. More studies are also needed to examine how the shape of the solutions produced may be affected by the synchronization of e-grocery between the two echelons. Special interest should be also given to the heterogeneous robot variants, such as navigation speed, as the selection of vehicle type drastically affects the gross weight traveled along the generated routes. All these potential research directions will further expand the model for the two-echelon VRPs, thus enabling the application of the two-echelon e-grocery delivery network in a real last-mile delivery.

Conclusions

Based on the implementation of the numerical studies, the model’s applicability is demonstrated with test data, and we draw the following conclusions.

C-AIA can be efficient in improving the final best solutions for the 2E-LDVRP-MV compared with the HGA-2, which is attributed to the customer clustering and immune operator.

The total cost of 2E-LDVRP-MV is affected to a great extent by the capacity of ADRs when the fleet number is small.

Minimizing distance does not always reduce emissions since the load on the vehicle and type of vehicle significantly affect fuel consumption. The load-dependent two-echelon e-grocery delivery network with van and ADR can efficiently reduce the emission cost compared with the distance-based objective. The average saving is 17.77%.

The efficiency of the two-echelon e-grocery delivery system is affected by the ratios between load and empty weight, vehicle types, emission levels, and customer densities. The percent deviation of objectives aroused by CTRVA and CRTE in sparse areas is larger than that in the dense areas.

Supplemental Material

sj-docx-1-trr-10.1177_03611981221099277 – Supplemental material for New Mobility-Assist E-Grocery Delivery Network: a Load-Dependent Two-Echelon Vehicle Routing Problem With Mixed Vehicles

Supplemental material, sj-docx-1-trr-10.1177_03611981221099277 for New Mobility-Assist E-Grocery Delivery Network: a Load-Dependent Two-Echelon Vehicle Routing Problem With Mixed Vehicles by Dan Liu, Hao (Frank) Yang, Xinhua Mao, Vasileia Antonoglou and Evangelos I. Kaisar in Transportation Research Record

Footnotes

Author Contributions

The authors confirm contribution to the paper as follows: study conception and design: D. Liu, E. Kaisers; data collection: D. Liu; analysis and interpretation of results: D. Liu, E. Kaisar, V. Antonoglou; draft manuscript preparation: D. Liu, H. (F.) Yang, X. Mao. All authors reviewed the results and approved the final version of the manuscript.

Declaration of Conflicting Interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: The work was supported by the Freight Mobility Research Institute (FMRI), one of the TIER 1 Transportation Centers that were selected by the U.S. Department of Transportation (U.S. DOT); National Natural Science Foundation of China (Grant No. 618060211, 52102374)

ORCID iDs

Hao (Frank) Yang

Xinhua Mao

Vasileia Antonoglou

Evangelos I. Kaisar

Supplemental Material

Supplemental material for this article is available online.

References

eMarketer. In 2021, Online Grocery Sales Will Surpass $100 Billion. https://www.emarketer.com/content/2021-online-grocery-sales-will-surpass-100-billion.

Yang

Liu

Zhuang

Sun

Murthy

Wang

Truck Parking Pattern Aggregation and Availability Prediction by Deep Learning. IEEE Transactions on Intelligent Transportation Systems, 2021, pp. 1–12. https://doi.org/10.1109/TITS.2021.3117290.

Holguín-Veras

Encarnación

González-Calderón

C. A.

Winebrake

Wang

Kyle

Herazo-Padilla

, et al. Direct Impacts of Off-Hour Deliveries on Urban Freight Emissions. Transportation Research Part D: Transport and Environment, Vol. 61, 2018, pp. 84–103.

Sonneberg

M.-O.

Leyerer

Kleinschmidt

Knigge

Breitner

M. H.

Autonomous Unmanned Ground Vehicles for Urban Logistics: Optimization of Last Mile Delivery Operations. Proc., 52nd Hawaii International Conference on System Sciences, Maui, 2019.

Ballot

Montreuil

Zacharia

Z. G.

Physical Internet: First Results and Next Challenges. Journal of Business Logistics, Vol. 42, No. 1, 2021, pp. 101–107.

Simoni

M. D.

Kutanoglu

Claudel

C. G.

Optimization and Analysis of a Robot-Assisted Last Mile Delivery System. Transportation Research Part E: Logistics and Transportation Review, Vol. 142, 2020, p. 102049.

Figliozzi

Jennings

Autonomous Delivery Robots and Their Potential Impacts on Urban Freight Energy Consumption and Emissions. Transportation Research Procedia, Vol. 46, 2020, pp. 21–28.

Schneider

Stenger

Goeke

The Electric Vehicle-Routing Problem With Time Windows and Recharging Stations. Transportation Science, Vol. 48, No. 4, 2014, pp. 500–520.

Liu

Yan

Wang

Kaisar

E. I.

Hybrid Artificial Immune Algorithm for Optimizing a Van-Robot E-Grocery Delivery System. Transportation Research Part E: Logistics and Transportation Review, Vol. 154, 2021, p. 102466.

10.

Dolati Neghabadi

Evrard Samuel

Espinouse

M.-L.

Systematic Literature Review on City Logistics: Overview, Classification and Analysis. International Journal of Production Research, Vol. 57, No. 3, 2019, pp. 865–887.

11.

Hiermann

Puchinger

Ropke

Hartl

R. F.

The Electric Fleet Size and Mix Vehicle Routing Problem With Time Windows and Recharging Stations. European Journal of Operational Research, Vol. 252, No. 3, 2016, pp. 995–1018.

12.

Reyes

Savelsbergh

Toriello

Vehicle Routing With Roaming Delivery Locations. Transportation Research Part C: Emerging Technologies, Vol. 80, 2017, pp. 71–91.

13.

Ulmer

Thomas

Same-Day Delivery With a Heterogeneous Fleet of Drones and Vehicles. Networks, Vol. 72, No. 4, 2018, pp. 475–505.

14.

Boysen

Schwerdfeger

Weidinger

Scheduling Last-Mile Deliveries With Truck-Based Autonomous Robots. European Journal of Operational Research, Vol. 271, No. 3, 2018, pp. 1085–1099.

15.

Jennings

Figliozzi

Study of Sidewalk Autonomous Delivery Robots and Their Potential Impacts on Freight Efficiency and Travel. Transportation Research Record: Journal of the Transportation Research Board, 2019. 2673: 317–326.

16.

Gonzalez-Feliu

Models and Methods for the City Logistics: The Two-Echelon Capacitated Vehicle Routing Problem. Operations Research. Politecnico di Torino, Turin, Italy, 2008.

17.

Perboli

Tadei

Vigo

The Two-Echelon Capacitated Vehicle Routing Problem: Models and Math-Based Heuristics. Transportation Science, Vol. 45, No. 3, 2011, pp. 364–380.

18.

Liu

Deng

Mao

Yang

Kaisar

E. I.

Two-Echelon Vehicle-Routing Problem: Optimization of Autonomous Delivery Vehicle-Assisted E-Grocery Distribution. IEEE Access, Vol. 8, 2020, pp. 108705–108719.

19.

Anderluh

Hemmelmayr

V. C.

Nolz

P. C.

Synchronizing Vans and Cargo Bikes in a City Distribution Network. Central European Journal of Operations Research, Vol. 25, No. 2, 2017, pp. 345–376.

20.

Enthoven

D. L. J. U.

Jargalsaikhan

Roodbergen

K. J.

uit het Broek

M. A. J.

Schrotenboer

A. H.

The Two-Echelon Vehicle Routing Problem With Covering Options: City Logistics With Cargo Bikes and Parcel Lockers. Computers & Operations Research, Vol. 118, 2020, p. 104919.

21.

Bektaş

Laporte

The Pollution-Routing Problem. Transportation Research Part B: Methodological, Vol. 45, No. 8, 2011, pp. 1232–1250.

22.

Demir

Bektaş

Laporte

A Review of Recent Research on Green Road Freight Transportation. European Journal of Operational Research, Vol. 237, No. 3, 2014, pp. 775–793.

23.

Zachariadis

E. E.

Tarantilis

C. D.

Kiranoudis

C. T.

The Load-Dependent Vehicle Routing Problem and its Pick-Up and Delivery Extension. Transportation Research Part B: Methodological, Vol. 71, 2015, pp. 158–181.

24.

Dondo

Cerda

A Cluster-Based Optimization Approach for the Multi-Depot Heterogeneous Fleet Vehicle Routing Problem With Time Windows. European Journal of Operational Research, Vol. 176, No. 3, 2007, pp. 1478–1507.

25.

Geetha

Poonthalir

Vanathi

P. T.

Improved K-Means Algorithm for Capacitated Clustering Problem. INFOCOMP Journal of Computer Science, Vol. 8, 2009, pp. 52–59.

26.

Crainic

T. G.

Mancini

Perboli

Tadei

Multi-Start Heuristics for the Two-Echelon Vehicle Routing Problem. In Evolutionary Computation in Combinatorial Optimization ( Merz

Hao

J. K.

, eds.), Springer, Berlin, Heidelberg, 2011, pp. 179–190.

27.

Lysgaard

Letchford

A. N.

Eglese

R. W.

A New Branch-and-Cut Algorithm for the Capacitated Vehicle Routing Problem. Mathematical Programming, Vol. 100, No. 2, 2004, pp. 423–445.

28.

Crainic

T. G.

Sgalambro

Service Network Design Models for Two-Tier City Logistics. Optimization Letters, Vol. 8, No. 4, 2014, pp. 1375–1387.

29.

Dellaert

Dashty Saridarq

Van Woensel

Crainic

T. G.

Branch-and-Price–Based Algorithms for the Two-Echelon Vehicle Routing Problem With Time Windows. Transportation Science, Vol. 53, No. 2, 2018, pp. 463–479.

30.

Crainic

T. G.

Sforza

Sterle

Tabu Search Heuristic for a Two-Echelon Location-Routing Problem. Proc., CIRRELT Conference, Montréal, Québec, 2011.

31.

Nguyen

V.-P.

Prins

Prodhon

A Multi-Start Iterated Local Search With Tabu List and Path Relinking for the Two-Echelon Location-Routing Problem. Engineering Applications of Artificial Intelligence, Vol. 25, No. 1, 2012, pp. 56–71.

32.

Grangier

Gendreau

Lehuédé

Rousseau

L.-M.

An Adaptive Large Neighborhood Search for the Two-Echelon Multiple-Trip Vehicle Routing Problem With Satellite Synchronization. European Journal of Operational Research, Vol. 254, No. 1, 2016, pp. 80–91.

33.

Hemmelmayr

V. C.

Cordeau

J.-F.

Crainic

T. G.

An Adaptive Large Neighborhood Search Heuristic for Two-Echelon Vehicle Routing Problems Arising in City Logistics. Computers & Operations Research, Vol. 39, No. 12, 2012, pp. 3215–3228.

34.

Wang

Chen

Bai

Two-Echelon Vehicle Routing Problem With Time Windows and Mobile Satellites. Transportation Research Part B: Methodological, Vol. 138, 2020, pp. 179–201.

35.

Schwengerer

Pirkwieser

Raidl

A Variable Neighborhood Search Approach for the Two-Echelon Location-Routing Problem. In Proc., Evolutionary Computation in Combinatorial Optimization: European Conference ( Hao

J. K.

Middendorf

, eds.), Málaga, Spain, April 11, 2012, Springer, Berlin, Heidelberg, pp. 13–24.

36.

Kassem

Korayem

Khorshid

Tharwat

A Hybrid Bat Algorithm to Solve the Capacitated Vehicle Routing Problem. Proc., 2019 Novel Intelligent and Leading Emerging Sciences Conference (NILES), Vol. 1, Giza, Egypt, 2019, pp. 222–225.

37.

Freschi

Repetto

Multiobjective Optimization by a Modified Artificial Immune System Algorithm. Proc., International Conference on Artificial Immune Systems, Alberta, Canada, 2005.

38.

Shukla

Jharkharia

Artificial Immune System-Based Algorithm for Vehicle Routing Problem With Time Window Constraint for the Delivery of Agri-Fresh Produce. Journal of Decision System, Vol. 22, 2013, pp. 224–247.

39.

Liu

Yan

Deng

Wang

Kaisar

E. I.

Collaborative Intermodal Freight Transport Network Design and Vehicle Arrangement With Applications in the Oil and Gas Drilling Equipment Industry. Transportmetrica A: Transport Science, Vol. 16, No. 3, 2020, pp. 1574–1603.

40.

Tomasz

D. G.

Genetic Algorithms Reference. ACM Digital Library, Tomasz Gwiazda, 2006.

41.

Liu

Deng

Zhang

Wang

Kaisar

E. I.

Design of Sustainable Urban Electronic Grocery Distribution Network. Alexandria Engineering Journal, Vol. 60, No. 1, 2020, pp. 145–157.

42.

Crainic

T. G.

Perboli

Mancini

Tadei

Two-Echelon Vehicle Routing Problem: A Satellite Location Analysis. Procedia - Social and Behavioral Sciences, Vol. 2, No. 3, 2010, pp. 5944–5955.

43.

Feng

Figliozzi

An Economic and Technological Analysis of the Key Factors Affecting the Competitiveness of Electric Commercial Vehicles: A Case Study From the USA Market. Transportation Research Part C: Emerging Technologies, Vol. 26, 2013, pp. 135–145.

44.

Veenstra

Roodbergen

K. J.

Vis

I. F. A.

Coelho

L. C.

The Pickup and Delivery Traveling Salesman Problem With Handling Costs. European Journal of Operational Research, Vol. 257, No. 1, 2017, pp. 118–132.

45.

EIA. US Energy Information Administration, 2019. https://www.eia.gov/beta/electricity/data/browser/#/topic/14?agg=2,0,1&fuel=vtvv&sec=g&geo=g&freq=M&tab=overview&pin=&rse=0&maptype=0&ltype=pin&ctype=linechart&end=201710&start=200101.

46.

EPA. The Isuzu N-Series CO2 Emissions is the Average Tailpipe Emissions From a Diesel Truck, While the Nuro-R1emissions is the Average Emissions From Electricity Generation Process. US Environmental Protection Agency. https://www.epa.gov/energy/clean-energy-programs. Accessed September, 2019.

47.

Sherman

. Here Comes Your Latest Unicorn: Nuro, a Billion-Dollar Automated Delivery Vehicle. https://www.inc.com/erik-sherman/here-comes-your-latest-unicorn-nuro-a-billion-dollar-automated-delivery-vehicle.html.

48.

Heinla

Starship Technologies, 2018. https://medium.com/starshiptechnologies/hello-robot-28b9b73787bf.

49.

Figliozzi

M. A.

Carbon Emissions Reductions in Last Mile and Grocery Deliveries Utilizing Air and Ground Autonomous Vehicles. Transportation Research Part D: Transport and Environment, Vol. 85, 2020, p. 102443.

50.

G. T. S.

Lau

H. C. W.

A Hybrid Genetic Algorithm for the Multi-Depot Vehicle Routing Problem. Engineering Applications of Artificial Intelligence, Vol. 21, No. 4, 2008, pp. 548–557.

Supplementary Material

Please find the following supplemental material available below.

For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.

For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.

0.00 MB

0.02 MB