## Fleet-mix Electric Vehicle Routing Problem for the E-commerce Delivery with Limited Off-Hour Delivery Implementation

Hyun-Seop Uhm 1,* , Abdelrahman Ismael 1 , Natalia Zuniga-Garcia 1 , Olcay Sahin 1 , James Cook 1 , Joshua Auld 1 , Monique Stinson 2

## ABSTRACT

Freight truck electrification for last-mile delivery is one of the most important research topics to reduce the dependency  on  fossil  fuel  operations.  Although  a  battery  electric  truck  still  has  limitations  on  daily operations with lower driving ranges and higher purchasing cost than a conventional truck, operations with electrified trucks reduce total energy usage and driving noise on routes. In this paper, we propose a fleetmix and multi-shift electric vehicle routing problem for joint implementation of fleet electrification and offhour delivery in urban e-commerce delivery systems. Every electrified truck is assumed to have two shifts for both daytime and nighttime delivery operations while conventional trucks can operate during daytime only because of municipal restrictions on nighttime deliveries, which are related to  engine noise. Also, every  electrified  truck  must  recharge  between  shifts  at  its  depot.  A  fleet  owner  decides  the  best electrification ratio of the fleet and the proper number of chargers which gives the minimum total cost. The optimization  problem  is  described  as  a  mixed-integer  linear  programming  model  including  common constraints for vehicle routing problem, recharging constraints, and two-shift operation of electrified trucks. A bi-level VNS-TS heuristic is also suggested for efficient solution search. The upper-level problem assigns trucks with engine type and brief route information using variable neighborhood search heuristic, and the lower-level problem finds the best route of each assigned truck using a tabu search heuristic. Scenarios with different EV driving ranges and nighttime operation availabilities are developed and evaluated with the POLARIS transportation simulation framework, and results are reported.

Keywords: Freight Decarbonization, Vehicle Fleet Electrification, Battery Electric Truck Deployment, Urban E-commerce Deliveries, Off-hour Delivery Implementation, Multi-shift Delivery Operations, Vehicle Routing Problem, Mixed-integer Linear Programming, Bi-level Heuristic.

TPS Transportation Systems &amp; Mobility, Argonne National Laboratory, Lemont, IL, 60439

1 * Corresponding author: huhm@anl.gov

2 U.S. Department of Transportation, Bureau of Transportation Statistics, Washington, DC, 20590 Work conducted while Dr. Stinson was at Argonne National Laboratory

## 1. INTRODUCTION

The widespread use of fossil fuels has caused greenhouse gas (GHG) emissions, which have a negative impact on climate and environment (1). The transportation sector is the largest contributor to GHG emissions in the United States, accounting for 27% of the total GHG emissions in 2020, of which 26% are from  heavy-duty  (HD)  and  medium-duty  (MD)  trucks (2). Several  research  studies  have  proposed alternative methods to reduce truck emissions, such as: mechanical improvement of internal combustion engine  (ICE)  trucks,  modal  shift  from  trucks  to  more  energy-efficient  modes  (e.g.,  rail),  and  truck electrification (3) .  Promoting  battery  electric  trucks  can  reduce  GHG  emissions  significantly  when  the electricity is generated from a variety of clean and renewable sources (4,5). Many conventional trucks that operate daily more than 100 miles, 10 hours, and 120 stops in urban areas for e-commerce deliveries could also reduce overall energy usage if they are electrified.

Fleet owners are facing pressure to electrify their trucks due to regulations on carbon-emission and the energy efficiency of electrified trucks, however, truck electrification currently faces three implementation barriers, including (a) low driving range, (b) high purchasing price of electrified trucks and electric vehicle supply equipment (EVSE), and (c) lack of public recharging infrastructure. Electric truck manufacturers aim for a driving range of 200-240 miles for their MD electric models, which is about 43% of the average driving range of current conventional trucks. A number of EV charging plugs for passenger cars have been recently installed at malls, marts, and other public parking spaces, however, these EVSEs are not suitable for truck recharging due to their larger size and their different trip characteristics. Therefore, a step-by-step approach is required to increase the feasibility and make proper investments for the initial deployment of electric trucks in the current systems.

Recent  research  papers  have  suggested  optimization  problems  for  truck  routing  with  battery recharging/swapping infrastructure to overcome the low driving range of battery electric trucks. (6,7) have supported the deployment of electric trucks for delivery, which is usually known as electric vehicle routing problem (EVRP) or location and vehicle routing problem (LVRP). Mathematical models of the EVRPs find the best routing and recharging decision under the assumption that every electric truck can be recharged at the public truck recharging/swapping stations during its operation. Variables for purchasing battery electric truck, locating recharging/swapping stations, and routing each truck with enroute recharging are optimized to minimize the total cost, including purchasing, energy, and daily operational costs (8).

The number of studies on the EVRP increased recently (8), however, truck routing problems with enroute recharging/swapping assumptions still have limitations for real-world last-mile deliveries. First, the number of truck recharging stations in the real-world is too few to support enroute recharging. It is also difficult to increase the number of recharging stations in the near future because of the expensive purchasing cost for fast chargers (level 3), grid constraints, and difficulties to locate truck recharging stations in urban

areas.  Second,  battery  swapping  technology  is  still  in  the  early  development  stage,  therefore,  it  needs various verification steps and improvements before it can be applied to real-world systems. Finally, fleet owners are hesitant to implement enroute recharging/swapping because it may increase the total operating time of drivers, which is strictly regulated.

Although freight truck electrification requires government subsidies, legal support, and technological improvements, the high energy efficiency of battery electric vehicles (BEVs) could reduce the burden of carriers in the long-term. Fleet electrification can also be an effective way to increase the number of locations allowing off-hour delivery (OHD) in urban areas since electric trucks offer much quieter and cleaner operations. OHD has been proposed as a way to reduce vehicle hours traveled (VHT) and  traffic  congestion  by  shifting  some  daytime  delivery  operations  to  nighttime.  However,  nighttime deliveries have a limitation due to emission, noise, and constraints on curb space (9-11). Therefore, we suggest  two-shift  operations  (daytime  and  nighttime  deliveries)  of  electric  trucks  for  the  simultaneous implementation of both truck electrification and OHD in the e-commerce last-mile delivery. Nighttime operation is limited only to visiting locations that accept OHD, and every electric truck which has two routes per day should be recharged during break time between shifts at the depot. This multi-shift operation of electric trucks can be a low-hanging fruit for both fleet electrification and OHD implementations by overcoming the biggest hurdles for deployment: lack of public recharging facilities and low acceptance rate for OHD. This study will also make up for the current inefficiency of electric truck operations with lower driving range and higher purchasing cost, which will encourage fleet owners to have electric trucks for their last-mile deliveries.

In this paper, we propose an optimization model for the fleet-mix electric vehicle routing problem with multi-shift operations. The model (a) finds the best combination of trucks with heterogeneous engine types, (b) decides the best routes to deliver packages to several demand locations, (c) schedules two-shift operations for electric trucks including recharging between daytime and nighttime routes, and (d) allocates the proper number of EVSEs at the depot. The mathematical problem is described as mixed-integer linear programming (MILP) model to minimize the total operational cost, including total cost of ownership (TCO) of trucks, purchasing cost for EVSEs at the depot, and daily transportation cost. Also, a bi-level heuristic is suggested for efficient solution search, which consists of variable neighborhood search (VNS) at the upperlevel and tabu search (TS) at the lower-level. The VNS heuristic finds the best combination of electric and conventional trucks by assigning pickup and delivery locations to each truck, while TS heuristic computes the shortest route to visit all the allocated locations of every truck and feeds the objective function value to the upper-level part.

All  the  solution  algorithms  are  implemented  in  the  POLARIS  framework  and  evaluated  with realistic  simulations  in  Austin,  Texas  metropolitan  area.  POLARIS  is  an  agent-  and  activity-based

transportation simulation framework that provides, synthesizes, and simulates daily travel demands on the regional road network with links, traffic signs, and household locations (12). We can get travel time and energy cost for every origin-destination pair at both daytime and nighttime and simulate the truck tours with background traffic on the POLARIS network. Based on synthesized e-commerce demand (13), the proposed algorithm computes the optimal fleet composition, including the EV ratio, the number of EVSEs, and daily routes, with given OHD acceptance ratio. We also analyze the cost efficiency, implementation feasibility, and the additional impact on the regional traffic network including total VHT, vehicle hours traveled (VMT), and traffic congestion.

The rest  of  this  paper  is  organized  as  follows:  related  literature  is  reviewed  in  Section  2.  The notation, assumptions, and MILP model are described in Section 3. In Section 4, the two-stage VNS-TS heuristic  is  proposed.  Numerical  experiments  and  simulated  results  are  reported  in  Section  5,  and conclusion and future studies are suggested in Section 6.

## 2. LITERATURE REVIEW

## 2.1. Electric Vehicle Routing Problems

Studies of the EVRP, LVRP for electric trucks, and green vehicle routing problem (GVRP) have been extended to cover cutting-edge technologies such as rapid charging (7, 14, and 15), battery swapping (16-20), and the powertrain mode selection for hybrid electric vehicles (21). Realistic representation of parameters and variables for non-linear recharging time (22-24) , waiting time at stations (25-28]), partial recharging strategy (7, 29-31), and energy consumption function during operations (24, 32-35) have also been suggested. Other research papers in (31, 32, 36-39) have considered mixed-fleet operation, including diesel-based and electrified trucks, and suggested mathematical problems to optimize the electrification ratio  with  minimum  purchasing cost  and  operation  cost.  Common  variables  of  proposed  mathematical problems in this paragraph are: (a) locating recharging facilities, (b) finding routes with minimum travel time, and (c) recharging/swapping at public stations during operation.

Other research topics related to fleet electrification can be found in the strategic planning of EVSE allocation. Studies in (40-46) aim to locate recharging stations to maximize demand coverage, optimize the utilization of deployed recharging facilities, and suggest recharging strategies. Since these studies have usually not considered routing decisions and only focused on light-duty trucks or long-haul transport, it is limited for application to urban e-commerce delivery systems.

## 2.2. Routing Problems for Nighttime Deliveries

Only a few studies (47-49) have developed routing decisions for OHD implementation to analyze the traffic impact. Truck tours were synthesized using simple and constructive heuristic methods, and some

routes were allocated to deliver during nighttime using iterative and scoring-based algorithms. Other related research  topics  can  be  found  in  multi-shift  vehicle  routing  problems  (VRPs)  and  pickup  and  delivery problems (PDPs) (50-53). Because drayage operations are the target application of these research papers, long-haul transportation and full-truckload shipments are usually assumed. Therefore, it is also difficult to apply these models to the last-mile delivery with OHD.

The time window constraint is one of the common operational assumptions in VRPs and PDPs, which limits the arrival time at every delivery location to be within a feasible time range. This constraint can be used to represent a certain delivery location accepting OHD by setting the time window of the location  to  include  nighttime.  However,  time  window  constraints  usually make  VRPs  and  PDPs  much harder to solve since there are additional variables and inequalities that check the arrival time feasibility of all combinations of trucks and delivery locations (54). Time window constraints were originally suggested to  capture  the  passengers'  inconvenience  such  as  dial-a-ride  services  for  patient  transportation (55) , therefore,  they  may  not  be  the  best  approach  for  modeling  multi-shift  operations,  including  nighttime deliveries. As a result, EVRPs with time windows (6, 15, 28-31, 34-36) do not consider the multi-shift operations  and  OHD.  Finally, (56) studied  the  cost  efficiency  of  OHD  implementation  in  the  urban business-to-business delivery system.

The most similar research has been suggested in (57), which finds the best routes of electric trucks with depot recharging decisions. Every customer has multiple delivery locations, and each delivery location must be visited within a predetermined time window. The mathematical model finds the best routes of electric trucks to cover all customers' demand including recharging at depots. However, the model doesn't consider  the  break  time  and  package  sorting  and  loading  during  truck  recharging  at  the  depot,  which represents every truck route as a single operation per day. To the best of our knowledge, no similar research topic has been reported in recent review papers (8, 58, and 59).

## 2.3. Solution Search Methods

Recent studies on VRPs have focused on heuristic approaches because of their NP-hard nature (54). Meta-heuristic  algorithms  are  preferred  to  find  near-optimal  solutions  for  PDPs  in  a  relatively  short computational time, as reported by (58, 59) . We refer the reader to recent research papers (15-17, 19-39) for an extensive review about meta-heuristic approaches in PDPs and EVRPs: adaptive large neighborhood search (ALNS), tabu search (TS), genetic algorithm (GA), variable neighborhood search (VNS), iterative local search (ILS), and other hybrid meta-heuristics.

It  is  more  challenging  to  implement  meta-heuristics when  heterogeneous fleets  are assumed  in VRPs and PDPs (60) because each truck type has different capabilities for routing and delivery. It is difficult to find better solutions with simple inter-route moves, and it is easy to be stuck in the local optima, therefore,

more detailed procedures for assigning and/or swapping vehicles are required for mixed-fleet VRPs and PDPs. Inter-route reconstruction in ILS (31) and destroying and repairing procedures in ALNS or VNS (31, 32, 36, 37, 60) have been suggested to capture the heterogeneity of truck types.

## 3. PROBLEM DESCRIPTION

In this section, we  introduce assumptions  and  the notation used throughout the paper. Consequently,  we  present  a  mathematical  model  of  the  electric  vehicle  routing  problem  with  off-hour delivery (EVRP-OHD).

## 3.1. Assumptions

The EVRP-OHD assumes that every fleet owner can operate both conventional and electric trucks. Every  diesel  truck  can  have  significantly  longer  route  than  an  electrified  truck  to  capture  the  current limitation on the driving range of electric trucks. On the other hand, each electrified truck can have two routes per day, visit demand locations allowing OHD at night, and recharge at its depot during the break time to overcome shorter driving range.

Figure 1 (a and b) are illustration of truck tours on a two-dimensional network with different truck types; a conventional truck can visit more demand locations with a single tour in Figure 1 (a) and an electric truck can visit all locations along two routes at both daytime and nighttime in Figure 1 (b) .

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00663v1-figure-5507ff42-5806-4f49-8545-b31bdfb5dd3d.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00663v1-figure-b48728c3-48da-40bf-8dc0-8c613aa6d038.jpg)

- Consumer (OHD not allowed)
- Consumer (OHD possible)

(a) Example of conventional truck tour

(b) Example of electric truck tours

Figure 1. Illustrations of the EVRP-OHD

Although the freight truck electrification may enable fleet owners to reduce the number of trucks, sufficient purchasing of EVSEs at the depot is required for the recharging between daytime and nighttime operations. A static recharging assumption is proposed to compute the minimum number of EVSEs. As a result, fleet electrification has a trade-off between reducing the number of trucks and the high purchasing costs of both electric trucks and EVSEs.

We apply common assumptions and constraints for VRPs, such as (a) every demand location must be visited by a single truck, (b) each truck tour should operate within maximum driving hours and loading capacity, and (c) each tour must be a closed loop.

## 3.2. Mathematical Formulation

We define the EVRP-OHD on a directed graph 𝒢 = (𝒩,𝒜) with location set 𝒩=𝒩 𝐶 ∪𝒩 𝐷 ∪ 𝒩 𝑂 and arc set 𝒜 . Subset 𝒩 𝐶 represents the depot location of every fleet owner. Two subsets for customer locations  are  suggested, 𝒩 𝐷 is  a  subset  of  demand  locations  not  allowing  nighttime  delivery,  and 𝒩 𝑂 consists of locations allowing OHD. We also assume that all locations in 𝒩 𝑂 can be visited by electrified trucks only because they produce far less noise. Let 𝒦 denote the set of trucks, and two types of trucks are defined: conventional trucks ( 𝑘 ∈ 𝒦 𝐶 ) and electrified trucks ( 𝑘 ∈ 𝒦 𝐸 ).

We assume different purchasing costs for conventional ( 𝐶 𝐶 ),  electric  trucks  ( 𝐶 𝐸 ),  and  EVSEs ( 𝐶 𝐸𝑉𝑆𝐸 ).  Travel  time from location   to   during daytime ( 𝑖 𝑗 𝑇 𝑖𝑗 𝐷 )  and  nighttime ( 𝑇 𝑖𝑗 𝑂 )  are  obtained  through POLARIS simulation. E-commerce demand at location   ( 𝑖 𝑉𝑖 ) is estimated based on the model developed in (13) , where the e-commerce model attributes are obtained though the population synthesizer of POLARIS. Drop-off time at location   ( 𝑖 𝑆𝑖 ) is proportional to the demand volume at the location, as 𝑆𝑖 = 𝑉 𝑖 × unit dropoff  time.  Heterogeneous truck capacity ( 𝑄 𝐶 and 𝑄 𝐸 )  and  driving  range  ( 𝐷 𝐶 and 𝐷 𝐸 )  are  considered for conventional  trucks  and  electric  trucks  respectively. 𝐻 𝐸𝑉𝑆𝐸 is  unit  recharging  speed, 𝐵 is  break  time between daytime and nighttime operations, and 𝑏𝑖𝑔𝑀 is a big number.

Let 𝑢𝑖 be  the  number  of  EVSEs  at  the  depot  of  carrier  establishment 𝑖 for  every 𝑖 ∈ 𝒩 𝐶 ,  and variable 𝑟 𝑖𝑘 is recharging time for every 𝑘 ∈ 𝒦 𝐸 and 𝑖 ∈ 𝒩 𝐶 . The binary variable 𝑤𝑘 indicates whether the truck 𝑘 is assigned for the operation ( 𝑤𝑘 = 1 ) or not ( 𝑤𝑘 = 0 ) for every truck 𝑘 ∈ 𝒦 . Finally, variables 𝑥𝑖𝑗𝑘 and 𝑦𝑖𝑗𝑘 be a binary variable equal to 1 if and only if the truck 𝑘 visits arc (𝑖, 𝑗) during daytime and nighttime, respectively, for every (𝑖, 𝑗) ∈ 𝒜 and 𝑘 ∈ 𝒦 .

Table 1 shows sets, parameters, and variables in the EVRP-OHD.

Table 1. Notations

| Sets                                                                  |
|-----------------------------------------------------------------------|
| 𝒩 : the set of locations ( 𝒩=𝒩 𝐶 ∪𝒩 𝐷 ∪𝒩 𝑂 )                          |
| 𝒩 𝐶 : the subset of depots                                            |
| 𝒩 𝐷 : the subset of customer locations not allowing off-hour delivery |
| 𝒩 𝑂 : the subset of customer locations allowing off-hour delivery     |
| 𝒜 : the set of arcs                                                   |
| 𝒦 : the set of trucks ( 𝒦 = 𝒦 𝐶 ∪𝒦 𝐸 )                                |
| 𝒦 𝐶 : the subset of conventional trucks                               |
| 𝒦 𝐸 : the subset of electrified trucks                                |

## Parameters

𝐶 𝐶

- : the TCO of a conventional truck
- 𝐶 𝐸 : the TCO of an electrified truck
- 𝐶 𝐸𝑉𝑆𝐸 : the purchasing cost of an EVSE
- 𝑇 𝑖𝑗 𝐷 : travel time from location   to   during daytime 𝑖 𝑗
- 𝑇 𝑖𝑗 𝑂 : travel time from location   to   during nighttime 𝑖 𝑗
- 𝑄 𝐶 : transportation capacity of a conventional truck
- 𝑄 𝐸 : transportation capacity of an electrified truck
- 𝐷 𝐶 : driving range of a conventional truck
- 𝐷 𝐸 : driving range of an electrified truck
- 𝑉𝑖 : demand volume at the location 𝑖
- 𝑆𝑖 : service time for drop-off at the location 𝑖
- 𝐻 𝐸𝑉𝑆𝐸 : unit recharging speed (traveling time / recharging time)
- 𝐵 : break time between daytime and off-hour deliveries
- 𝑏𝑖𝑔𝑀 : a big number

## Variables

| 𝑤 𝑘 : = 1 if the truck 𝑘 is assigned for delivery, = 0 otherwise                             |
|----------------------------------------------------------------------------------------------|
| 𝑥 𝑖𝑗𝑘 : = 1 if the truck 𝑘 departs from the location 𝑖 to 𝑗 at daytime, = 0 otherwise        |
| 𝑦 𝑖𝑗𝑘 : = 1 if the truck 𝑘 departs from the location 𝑖 to 𝑗 at nighttime, = 0 otherwise      |
| 𝑧 𝑖𝑘 : total volume of packages when the truck 𝑘 at the location 𝑖                           |
| 𝑢 𝑖 : the number of EVSEs at the location 𝑖                                                  |
| 𝑟 𝑖𝑘 : the total recharging time of the electrified truck 𝑘 during break time at the depot 𝑖 |

Every carrier establishment minimizes the total cost, which is the sum of TCO of both conventional and electrified trucks, EVSE purchasing cost, and daily operation cost. The EVRP-OHD can be formulated as the multi-objective MILP model, as follows:

| Minimize ∑ 𝐶 𝐶 𝑤 𝑘 + ∑ 𝐶 𝐸 𝑤 𝑘 + ∑ 𝐶 𝐸𝑉𝑆𝐸 𝑢 𝑖                                                 | (1-1)       |
|-----------------------------------------------------------------------------------------------|-------------|
| Minimize ∑ ∑(𝑇 𝑖𝑗 𝐷 𝑥 𝑖𝑗𝑘 +𝑇 𝑖𝑗 𝑂 𝑦 𝑖𝑗𝑘 ) 𝐸                                                   | (1-2)       |
| 𝑖,𝑗∈𝒩 𝑘∈𝒦 subject to ∑𝑥 𝑖𝑗𝑘 𝑗∈𝒩 ≤ 𝑤 𝑘 ∀𝑖 ∈ 𝒩 𝐶 , 𝑘 ∈ 𝒦                                        | (2) (3) (4) |
| ∑𝑥 𝑖𝑗𝑘 𝑗∈𝒩 = ∑𝑥 𝑗𝑖𝑘 𝑗∈𝒩 ∀𝑖 ∈ 𝒩,𝑘 ∈ 𝒦                                                          |             |
| ∑∑𝑥𝑖𝑗𝑘 𝑘∈𝒦 𝑗∈𝒩 = 1 ∀𝑖 ∈ 𝒩 𝐷                                                                   |             |
| ∑ 𝑇 𝑖𝑗 𝐷 𝑥 𝑖𝑗𝑘 𝑖,𝑗∈𝒩 ≤ 𝐷 𝐶 ∀𝑘 ∈ 𝒦 𝐶                                                           | (5)         |
| 𝑧 𝑗𝑘 ≥ 𝑧 𝑖𝑘 +𝑉 𝑗 -𝑏𝑖𝑔𝑀(1 -𝑥 𝑖𝑗𝑘 ) ∀𝑖 ∈ 𝒩,𝑗 ∈ 𝒩 𝐶 , 𝑘 ∈ 𝒦                                      | (6)         |
| 𝑧 𝑖𝑘 ≤ 𝑄 𝐶 ∀𝑖 ∈ 𝒩,𝑘 ∈ 𝒦 𝐶                                                                     | (7)         |
| ∑𝑦 𝑖𝑗𝑘 𝑗∈𝒩 ≤ ∑𝑥 𝑖𝑗𝑘 𝑗∈𝒩 ∀𝑖 ∈ 𝒩 𝐶 , 𝑘 ∈ 𝒦 𝐸                                                    | (8)         |
| ∑𝑦 𝑖𝑗𝑘 𝑗∈𝒩 = ∑𝑦 𝑗𝑖𝑘 𝑗∈𝒩 ∀𝑖 ∈ 𝒩 𝑂 , 𝑘 ∈ 𝒦 𝐸                                                    | (9)         |
| ∑(∑𝑥 𝑖𝑗𝑘 𝑘∈𝒦 + ∑ 𝑦 𝑖𝑗𝑘 𝑘∈𝒦 𝐸 ) 𝑗∈𝒩 = 1 ∀𝑖 ∈ 𝒩 𝑂                                               | (10)        |
| ∑ 𝑇 𝑖𝑗 𝐷 𝑥 𝑖𝑗𝑘 𝑖,𝑗∈𝒩 ≤ 𝐷 𝐸 ∀𝑘 ∈ 𝒦 𝐸                                                           | (11)        |
| ∑ 𝑇 𝑖𝑗 𝑂 𝑦 𝑖𝑗𝑘 𝑖,𝑗∈𝒩 ≤ 𝐷 𝐸 ∀𝑘 ∈ 𝒦 𝐸                                                           | (12)        |
| 𝑧 𝑗𝑘 ≥ 𝑧 𝑖𝑘 +𝑉 𝑗 -𝑏𝑖𝑔𝑀(1 -𝑦 𝑖𝑗𝑘 ) ∀𝑖 ∈ 𝒩,𝑗 ∈ 𝒩 𝑂 , 𝑘 ∈ 𝒦 𝐸                                    | (13)        |
| 𝑧 𝑖𝑘 ≤ 𝑄 𝐸 ∀𝑖 ∈ 𝒩,𝑘 ∈ 𝒦 𝐸                                                                     | (14)        |
| 𝐻 𝐸𝑉𝑆𝐸 𝑟 𝑖𝑘 ≥ ∑ 𝐶 𝑖𝑗 𝐸 𝑥 𝑖𝑗𝑘 𝑖,𝑗∈𝒩 -𝑏𝑖𝑔𝑀(1- ∑ 𝑦 𝑖𝑗𝑘 𝑗∈𝒩 𝑂 ) ∀𝑖 ∈ 𝒩 𝐶 , 𝑘 ∈ 𝒦 𝐸                | (15)        |
| ∑𝑟 𝑖𝑘 ≤ 𝐵𝑢 𝑖 ∀𝑖 ∈ 𝒩 𝐶 , 𝑘 ∈ 𝒦 𝐸                                                               | (16)        |
| 𝑢 𝑖 ∈ ℕ + ∀𝑖 ∈ 𝒩 𝐶 𝑤 𝑘 , 𝑥 𝑖𝑗𝑘 , 𝑦 𝑖𝑗𝑘 ∈ {0,1} ∀𝑖, 𝑗 ∈ 𝒩,𝑘 ∈ 𝒦 𝑟 𝑖𝑘 , 𝑧 𝑖𝑘 ∈ ℝ + ∀𝑖 ∈ 𝒩,𝑘 ∈ 𝒦 | (17)        |

Objective function (1-1) minimizes the sum of TCO of trucks and EVSE purchasing cost and (1-2) optimizes each truck's daily route with the minimum total travel time. Constraints (2) and (3) represent the route construction constraints for every assigned truck. Every demand location must be visited by one of the  trucks  by  constraint  (4).  Constraints  (5)  and  (6-7)  are  truck  capacity  and  maximum  driving  range constraints,  respectively.  Constraints  (8-14)  are  only  for  OHDs,  which  shares  similar  structure  with constraints (2-7). Constraint (15) ensures that every electrified truck requires recharging during break time if and only if the truck has deliveries at nighttime. Constraint (16) makes the sum of recharging time be less than break time by assigning proper number of EVSEs. Finally, constraint (17) is a variable constraint.

## 4. BI-LEVEL VNS-TS HEURISTIC

We developed a bi-level VNS-TS heuristic; truck assignment in the upper-level part and route improvement  in  the  lower-level  part.  Truck  assignment,  engine  type,  and  visiting  locations  vector  are updated with VNS heuristic in the upper-level, and the lower-level problem finds the best routes of updated trucks with TS procedures. Figure 2 below shows the structure of the VNS-TS heuristic algorithm.

Figure 2. Bi-level VNS-TS heuristic description

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00663v1-figure-d6c94391-0743-45ec-a367-b5abe0b138b3.jpg)

In the upper-level part of Figure 2 , there is a vector which shows the assignment and type info of each truck; '0' for non-assigned, '1c' for assigned conventional, and '1e' for assigned electrified trucks. Also, it has a location vector to be visited by each assigned truck for the demand covering constraint. Upperlevel solutions are updated using VNS heuristic with several inter-route movements to find the best fleet mix to cover all the demands with the minimum purchasing costs (1-1). Whenever upper-level problem needs to compute objective function of a certain solution, lower-level problem is called to find the best order of visiting locations of a truck and return the value of the objective function (1-2) to the upper-level. TS  heuristic  updates  string-structured  solutions  with  intra-route  movements.  There  are  two  embedded procedures to compute the EVSE purchasing cost and guarantee the feasibility of lower-level solutions.

The bi-level structure offers efficient solution search for large-sized instances of the EVRP-OHD, encompassing the entire e-commerce delivery system in simulated metropolitan cities, by partitioning the

solution space through variable classification. While the bi-level heuristic efficiently manages the number of neighborhood solution, it generally requires more iterations to converge. Further, the size of EVRP-OHD instances is significantly larger than that of typical VRPs, this paper focuses on heuristic development that emphasizes exploration at the upper level with ample randomness, while simplifying the lower level to minimize overall computational demands.

All the parts for both upper-level and lower-level problem are described below.

## 4.1. VNS for Upper-level Problem

The VNS heuristic explores a local optimum with a local search method with several neighborhood structures and perturbs the current solution to escape from the corresponding valley in every iteration. The main local searching steps of the VNS are (1) search more distant neighborhoods of the current solution when it fails to find any improved solutions, (2) jump to the improved solution, and (3) repeat the local search  with  adjacent  neighborhoods.  The  heuristic  also  has  a  shaking  procedure  to  add  randomness. Algorithm 1 is the pseudo-code of the upper-level VNS heuristic.

```
                                                                                                                                                                                                       
                                                                                                                                                                                                       

      Algorithm 1. Variable Neighborhood Search

      start
            sol = InitialSolutionByClustering(|\C|)
             repeat
                    for n in NeighborhoodStructure
                              sol' = Shake(sol, n)
```

We  implement  the  VNS  with  a  simple  initialization  procedure,  which  generates  clusters  of customers by using k-medoid algorithm. The number of clusters is set to be the minimum number of diesel trucks to cover the whole customer volume ( k = |𝒦 𝐶 | ). k medoids are selected randomly among customers,

all  other  customers  are  assigned  to  the  closest  medoid,  and  all  constraints  in  the  EVRP-OHD  are  not considered  in  this  step.  Finally,  a  single  diesel  truck  is  assigned  to  every  cluster,  and  the  lower-level heuristic completes the initial tour of each truck.

Common shaking procedures randomly choose a neighborhood solution to be a current solution at every iteration in previous works (60) , but it is not enough to add sufficient randomness to the problem when the number of locations is greater than several thousands. Therefore, shaking procedure in this paper prioritizes trucks randomly, and the neighborhood solution preferentially changes solution structure with highly prioritized truck. It enables not only to reduce the number of neighborhood solutions efficiently but also to add randomness for preventing solutions stuck in the local optima.

The initial solution is updated with several neighborhood structures, and Figure 3 below is an illustration of the neighborhood generation. Since we sorted neighborhood structures from the smallest to the biggest changes in the current solution as '1-insert', '1-swap', '2-insert', 'type change', 'route insert' and  'route  delete',  the  heuristic  explores  the  solution  space  farther  when  the  previous  neighborhood structure cannot find better solutions. Whenever the location subset of a certain truck is changed, the lowerlevel heuristic is called to find the best route and to return the total travel time of the truck. All lower-level procedures  are  parallelized  with  agent-based  modeling  framework,  which  enables  efficient  solution evaluation.

Current solution is always updated whenever better feasible solutions have found, and the whole procedure is repeated until the termination criteria met.

Figure 3. An illustration for neighborhood structure in VNS heuristic

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00663v1-figure-7d94cc7c-2b85-4673-834b-f5a6be1efc28.jpg)

## 4.2. TS for Lower-level Problem

The TS heuristic uses a trajectory-based search method. The basic idea of the TS heuristic is moving a  current  solution  to  one  of  the  locally  improved  solutions  and  recording  some  elements  of  a  solution movement in the tabu list. The elements in the list cannot be revisited for the next 𝜆 iterations, denoted as the tabu tenure. This process prevents repetition in a sequence of solutions, which may reduce the frequency of getting stuck in the local optima. The TS heuristic finds the best solution until its termination, which is usually the maximum iterations at local optima or the maximum computation time.

In this paper, common features and procedures of the TS heuristic are applied for the lower-level problem.  String-structured  solution  is  suggested  in Figure  2 ,  and  we  add  one  additional  node  for  the recharging  during  breaktime  when  the  truck  is  electrified.  Neighborhood  solutions  are  generated  with 'node-swap', 'insert',  and  '2-opt'  procedures  as  shown  in Figure 4 .  To  prevent  repeated  searches,  we applied the common structure of tabu-list from (25,30) - containing moved location ids - with size = √|ℒ| where |ℒ| is the length of the solution string  Because every lower-level problem only solves a single-truck . EVRP with a few locations already assigned to the truck, only few iterations (= √2 × |ℒ| ) are allowed to reduce the computational requirements at the lower-level.

Figure 4. An illustration for neighborhood structure in TS heuristic

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00663v1-figure-cd614698-ebaa-4b10-9922-0f6b5d2031df.jpg)

## 5. EXPERIMENTAL RESULTS

In  this  section,  the  performance  of  the  suggested  bi-level  VNS-TS  heuristic  is  evaluated  with simulated e-commerce demand of Bloomington, Illinois in POLARIS and compared to the commercial optimization solver. Also, the EVRP-OHD is embedded in the POLARIS framework and simulated to represent the  entire residential e-commerce  deliveries  in  the metropolitan  area of  Austin,  Texas  within POLARIS.  The  efficiency  of  the  joint  implementation  of  fleet  electrification  and  off-hour  delivery operation is analyzed and reported for several scenarios.

## 5.1. Performance Evaluation

A few e-commerce orders in Bloomington were sampled including location-to-location travel time, number of packages, and drop-off time. Also, locations allowing nighttime delivery are randomly selected based on 4 OHD ratios. All other parameters related to truck TCO, EVSE purchasing cost, truck capacity and operation time limitation were simplified to be homogeneous, regardless of truck type. Finally, the proposed bi-level VNS-TS heuristic was compared with IBM ILOG CPLEX 12.10 on the same personal computer (Intel Xeon W-2155 @ 3.30GHz, 20 threads, and 32GB ram).

Simplified parameters are assumed for clearer comparison of performance between CPLEX solver and the suggested heuristic. The TCO, driving range, and delivery capacity of electric trucks are assumed to be same to those of diesel trucks. Also, EVSE purchasing cost and recharging time are not considered to simplify the recharging decisions. Customer locations accepting OHD are selected randomly with given acceptance ratio and average travel speed during nighttime is 30% higher than that during daytime to force trucks operate during nighttime. Finally, the MILP model and the VNS-TS heuristic minimize the sum of objective functions (1-1) and (1-2) with artificial TCO value ( 𝐶 𝐶 = 𝐶 𝐸 = 1,000 ).

Table 2 shows results of the sampled Bloomington e-commerce deliveries from both CPLEX and the VNS-TS heuristic. The number of sample locations ( |𝒩| ), the fleet size ( |𝒦| ), and the OHD acceptance ratio are reported in the scenario column. The objective function value and computation time are reported in each solution approach section. Since CPLEX is allowed to search solution within 1 hour only, the gap ratio between the best feasible solution and the lower bound is reported as MIP gap. Finally, the difference of the objective function value between CPLEX and the VNS-TS heuristic is reported in the last column.

Bi-level heuristic could report better solution than that from CPLEX in almost every scenario. The total travel time can be reduced with more deliveries during nighttime, and these trends - higher solution value with fewer customers allowing OHD - can be easily observed with the results from the VNS-TS heuristic in Table 2. However, CPLEX usually returned higher solution value even though more customers accept  delivery  during  nighttime.  MIP  gap  also  tends  to  increase  with  higher  OHD  ratio,  and  these computational inefficiencies are because the mathematical model needs to search larger space of decision variable 𝑦𝑖𝑗𝑘 ( |𝑌| ∝ |𝒩| 2 ×OHDratio 2 ).

In general, all scenario tests cannot be finished within a given time limit of 1 hour. CPLEX reported poor gaps between feasible solutions and lower bounds, which show the complexity of the EVRP-OHD. We believe that the EVRP-OHD is much harder to find the optimal solution than the common VRPs because the model has (1) two sets of three-index decision variables for routing at both daytime ( 𝑥𝑖𝑗𝑘 )  and nighttime ( 𝑦𝑖𝑗𝑘 ), (2) objective function with weighted sum of both strategic purchasing cost and daily operational cost, and (3) more constraints with big-M notations to indicate the condition about multi-shift operation and recharging.

Table 2. Result comparison between CPLEX and VNS-TS heuristic

| Scenario   | Scenario      | Commercial solver (CPLEX)   | Commercial solver (CPLEX)   | Commercial solver (CPLEX)   | VNS-TS heuristic   | VNS-TS heuristic       |             |
|------------|---------------|-----------------------------|-----------------------------|-----------------------------|--------------------|------------------------|-------------|
| |𝒩|, |𝒦|   | OHD Ratio (%) | Obj. value (A)              | MIP gap (%)                 | Computation time (sec)      | Obj. value (B)     | Computation time (sec) | gap B-A (%) |
| {20, 4}    | 0.0           | 20,761                      | 85.15                       | 3,600                       | 20,812             | 1                      | 0.25        |
| {20, 4}    | 20.0          | 20,762                      | 82.74                       | 3,600                       | 20,265             | < 1                    | -2.40       |
| {20, 4}    | 40.0          | 20,762                      | 82.77                       | 3,600                       | 18,424             | < 1                    | -11.26      |
| {20, 4}    | 100.0         | 20,959                      | 84.36                       | 3,600                       | 14,539             | < 1                    | -30.63      |
| {33, 10}   | 0.0           | 39,183                      | 86.50                       | 3,600                       | 38,402             | 1                      | -1.99       |
| {33, 10}   | 20.0          | 40,521                      | 84.42                       | 3,600                       | 35,442             | 1                      | -12.54      |
| {33, 10}   | 40.0          | NONE                        | -                           | 3,600                       | 33,139             | 1                      | -           |
| {33, 10}   | 100.0         | NONE                        | -                           | 3,600                       | 27,973             | 1                      | -           |
| {37, 8}    | 0.0           | 33,306                      | 79.81                       | 3,600                       | 31,423             | 1                      | -5.65       |
| {37, 8}    | 20.0          | 34,490                      | 87.00                       | 3,600                       | 31,071             | 13                     | -9.91       |
| {37, 8}    | 40.0          | 34,008                      | 86.91                       | 3,600                       | 30,173             | 2                      | -11.28      |
| {37, 8}    | 100.0         | NONE                        | -                           | 3,600                       | 25,257             | 2                      | -           |
| {46, 10}   | 0.0           | 40,663                      | 86.11                       | 3,600                       | 39,676             | 5                      | -2.43       |
| {46, 10}   | 20.0          | 44,023                      | 85.32                       | 3,600                       | 34,626             | 17                     | -21.35      |
| {46, 10}   | 40.0          | 39,906                      | 85.18                       | 3,600                       | 36,527             | 65                     | -8.47       |
| {46, 10}   | 100.0         | NONE                        | -                           | 3,600                       | 33,372             | 2                      | -           |
| {49, 8}    | 0.0           | 38,730                      | 87.45                       | 3,600                       | 35,703             | 3                      | -7.81       |
| {49, 8}    | 20.0          | 37,857                      | 90.77                       | 3,600                       | 31,555             | 14                     | -16.65      |
| {49, 8}    | 40.0          | 36,662                      | 85.34                       | 3,600                       | 32,056             | 4                      | -12.56      |
| {49, 8}    | 100.0         | NONE                        | -                           | 3,600                       | 29,313             | 1                      | -           |
| {58, 8}    | 0.0           | 38,865                      | 87.39                       | 3,600                       | 35,590             | 8                      | -8.43       |
| {58, 8}    | 20.0          | 37,707                      | 87.45                       | 3,600                       | 35,127             | 31                     | -6.84       |
| {58, 8}    | 40.0          | 37,619                      | 86.58                       | 3,600                       | 33,662             | 71                     | -10.52      |
| {58, 8}    | 100.0         | NONE                        | -                           | 3,600                       | 29,529             | 1                      | -           |

※ NONE: Feasible solutions cannot be found within the max CPU time

## 5.2. Scenario Evaluation

Demand  locations  and  all  other  details  for  e-commerce  delivery  are  synthesized  using  the  ecommerce choice model based on the synthesized population within POLARIS. Below, Figure 5 is  the target  study  area  in  POLARIS,  which  represents  the  Austin  metropolitan  area  in  Texas  with  39,638 aggregated household locations of residential land-uses, 15,833 links, and 2,161 zones. Also, the major four e-commerce companies are emulated in the POLARIS-Austin, operating out of 20 different depots. There are an average of 280,000 orders among 830,000 households. Each company partitions Austin into several sub-zone clusters and each depot serves customers in a cluster as shown in Figure 5 .  As  a  result,  we implemented bi-level heuristic 20 times for solving single-depot EVRP-OHD.

Figure 5. Target network for numerical experiments

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00663v1-figure-3f48783d-5fad-4ab8-a6e9-fd0db31a5ffd.jpg)

The EVRP-OHD used travel time between every pair of origin and destination locations from POLARIS network with  background traffic,  which  enables  getting  reasonable  travel  time  during  both daytime and nighttime. We considered 10 test scenarios with 2 EV ranges for delivery trucks and 5 cases of OHD acceptance ratio. The TCO of an electric truck and purchasing cost of a recharging plug is assumed to be 95% and 20% of the TCO of diesel truck respectively (61) . We set 𝑅 𝐸 = 7 hours based on the current technology of MD electric truck by dividing 210 miles into 30 MPH and 𝑅 𝐸 = 11 hours when EV range becomes 50% longer. Also, locations allowing nighttime delivery are randomly chosen with given OHD ratio. Other parameters are assumed for test experiments such as: 𝑆𝑖 /𝑉 𝑖 (unit drop-off time) = 120 secs, 𝑄 𝐶 = 𝑄 𝐸 = 140 orders, 𝑅 𝐶 = 12 hours, 𝐻 𝐸𝑉𝑆𝐸 = 1 hour recharging after 7 hour driving, and 𝐵 = maximum 4 hours. Finally, the VNS-TS heuristic minimizes the total TCO and EVSE purchasing cost first at the upper-level and then finds the best tours at the lower-level because the actual value of strategic purchasing cost in objective function (1-1) and the daily travel time in (1-2) are not comparable.

Due to the computational intensity of repeatedly solving the single-depot EVRP-OHD problem with many thousands of locations, we conducted all simulations on the Broadwell partition of the BEBOP cluster operated by Laboratory Computing Resource Center at Argonne National Laboratory. The cluster consists of over 650 high-performance compute nodes, each with 36 physical cores and 128GB DDR4 RAM. By integrating our proposed methodology within the highly efficient POLARIS framework, we were able to run all simulations for solving EVRP-OHD using between 5 (OHD=0%) and 12 (OHD=50%) node hours per simulation.

Table 3 shows results of ten scenarios in POLARIS-Austin.

Table 3. Test results

| Scenario         | Scenario      | Fleet composition   | Fleet composition   | Fleet composition     | Simulation results   | Simulation results   | Simulation results   | Simulation results   | Simulation results   | Simulation results   |
|------------------|---------------|---------------------|---------------------|-----------------------|----------------------|----------------------|----------------------|----------------------|----------------------|----------------------|
| EV range (hours) | OHD ratio (%) | Trucks (A)          | Routes (B)          | EV ratio (B-A)/A, (%) | VMTs (miles)         | VHTs (hours)         | Avg MPH              | Avg VMT (miles/B)    | Avg VHT (hours/B)    | Avg OH (hours/A)     |
| 7.0              | 0.0           | 2,210               | 2,210               | 0.0                   | 60,847.7             | 2,032.4              | 29.9                 | 110.1                | 3.7                  | 7.9                  |
| 7.0              | 10.0          | 2,531               | 2,980               | 17.7                  | 68,989.8             | 2,306.3              | 29.9                 | 92.6                 | 3.1                  | 7.4                  |
| 7.0              | 20.0          | 2,471               | 3,373               | 36.5                  | 71,263.0             | 2,373.6              | 30.0                 | 84.6                 | 2.8                  | 7.7                  |
| 7.0              | 30.0          | 2,354               | 3,650               | 55.1                  | 73,700.3             | 2,428.2              | 30.4                 | 80.8                 | 2.7                  | 8.1                  |
| 7.0              | 50.0          | 2,186               | 3,992               | 82.7                  | 76,604.9             | 2,493.1              | 30.7                 | 76.8                 | 2.5                  | 8.9                  |
| 11.0             | 0.0           | 2,221               | 2,221               | 0.0                   | 61,066.6             | 2,051.6              | 29.8                 | 110.0                | 3.7                  | 7.9                  |
| 11.0             | 10.0          | 2,240               | 2,828               | 26.3                  | 65,799.5             | 2,192.9              | 30.0                 | 93.1                 | 3.1                  | 8.1                  |
| 11.0             | 20.0          | 2,045               | 3,051               | 49.2                  | 68,679.3             | 2,254.1              | 30.5                 | 90.1                 | 3.0                  | 9.0                  |
| 11.0             | 30.0          | 1,856               | 3,107               | 67.4                  | 69,934.9             | 2,286.9              | 30.6                 | 90.1                 | 2.9                  | 10.0                 |
| 11.0             | 50.0          | 1,734               | 3,086               | 78.1                  | 69,973.4             | 2,250.8              | 31.1                 | 90.8                 | 2.9                  | 10.6                 |

※ Average number of demand packages = 282,257

※ OH: operation hours = total travel time + total drop-off time

As shown in Figure 6 (a) and (b) , a higher household ratio accepting OHD requires more electric trucks and increases delivery stops during nighttime. These values monotonically increase with higher OHD acceptance ratio whether the EV driving range is short or long. Also, about 40% of the household locations accepting OHD are actually delivered during nighttime from the EVRP-OHD heuristic results.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00663v1-figure-99d07856-bfad-442c-b08f-ac96f921d965.jpg)

(a) Required EV ratio

(b) Houscholds delivered during nighttime operations

Figure 6. Fleet composition and size

One of the benefits of OHD implementation is avoiding traffic by moving some delivery trips into nighttime. In Table 3 , average truck speed increased with higher OHD acceptance ratio because of fewer traffic on the network, which also makes shorter average vehicle hour traveled (not including drop off times) as shown in Figure 7 (a) . Average VMTs in Figure 7 (b) have also been decreased with more frequent nighttime operations, which implies that electric trucks can not only avoid traffic congestion during daytime but also find shorter paths during nighttime. Since the average miles and hours decrease significantly with

relatively low OHD acceptance ratios of 10-20%, joint implementation of fleet electrification and nighttime delivery to limited demand locations could be an initial approach to reduce energy consumption in realworld e-commerce delivery systems.

Figure 7. Average truck speed and VHTs

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00663v1-figure-a8880cc9-4e3d-41ae-b1e8-36315d808d00.jpg)

Although  electric  truck  is  preferred  with  higher  OHD  acceptance  ratio,  more  trucks  could  be required. In Figure 8 (a) , we compared the overall fleet size, and shorter EV range scenario increased the fleet size when OHD acceptance ratio is 10-30%. On the other hand, long EV range could reduce the fleet size  from 2,221 to 1,734. Also, Figure 8 (b) shows that  average  operation  hours of  every  truck  could increase  because  the  electrified  trucks  need  more  trips  departing  from  and  returning  to  its  depot  for recharging. In Table 3 ,  total  number  of  tours,  VMTs,  and  VHTs  also  increased  with  the same  reason. Therefore, locating depots closer to demand locations is important to resolve these issues, and pairing the EVRP-OHD with micro-hub operations could be an option to reduce the overall traveling distance from depots to demand locations.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00663v1-figure-054f56f9-5f15-41fb-81e4-850540b54d92.jpg)

(a) Total number of trucks

(b) Average operation hours per truck

Figure 8. Fleet composition and size

## 6. CONCLUSION

In  this  paper,  we  proposed the fleet-mix electric vehicle routing problem with limited off-hour delivery implementation (EVRP-OHD) to initiate fleet electrification decisions in e-commerce delivery systems. The EVRP-OHD considered the fleet electrification under current limitation of EV technologies, such as lack of public recharging stations, shorter driving ranges than conventional diesel trucks, and more expensive purchasing costs for EV and EVSE. We also applied limited off-hour delivery implementation to the model based on the strengths of electric trucks, including clean and quiet operations. Every electric truck can have more flexible routes and visit demand locations accepting OHD during nighttime delivery. We suggested a mathematical formulation to minimize both purchasing cost of trucks and EVSEs and daily operation costs and designed a bi-level VNS-TS heuristic for efficient solution search.

Test  experiments  with  several  EV  driving  ranges  and  OHD  acceptance  ratio  scenarios  were performed  in  the  POLARIS  framework.  The  results  demonstrated  the  efficiency  of  deploying  freight electric  trucks  for  OHD  implementations.  In  general,  a  low  OHD  acceptance  ratio  (10-20%  of  total demand) was enough to get the benefit of multi-shift operations. Applying the EVRP-OHD led to decreases of more than 20% of average VMT and VHT, indicating that this may also reduce energy usage for ecommerce delivery operations. Also, the EV ratio required to support the optimal strategy also increased with higher OHD acceptance ratio even though we applied limited operational ranges for electric trucks. Results were highly dependent on the driving range of EVs, therefore, fleet electrification can be boosted with higher EV ranges.

In this study, we limited nighttime deliveries to being operated by electric trucks only. In the future this constraint could be relaxed allow conventional truck types to deliver overnight where municipality policies accept nighttime operations. Also, the EVRP-OHD could be extended to include delivery lockers, micro-hubs, and other technologies to improve drivers' safety during nighttime operations and reduce the overall traveling distance between depots to demand locations in future studies.

## ACKNOWLEDGMENTS

This report and the work described were sponsored by the U.S. Department of Energy (DOE) Vehicle Technologies Office (VTO) under the Systems and Modeling for Accelerated Research in Transportation (SMART) Mobility Laboratory Consortium, an initiative of the Energy Efficient Mobility Systems (EEMS) Program. The submitted manuscript has been created by the UChicago Argonne, LLC, Operator of Argonne National Laboratory (Argonne). Argonne, a U.S. Department of Energy Office of Science laboratory, is operated under Contract No. DE-AC02-06CH11357. The U.S. Government retains for itself, and others acting on its behalf, a paid-up nonexclusive, irrevocable worldwide license in said article to reproduce, prepare derivative works, distribute copies to the public, and perform publicly and display publicly, by or on behalf of the Government.

## REFERENCES 1

| 2 3 4       | 1. Metz, B., Davidson, O., Bosch, P., Dave, R., and Meyer, L. Climate change 2007-mitigation of climate change. Intergovernmental Panel on Climate Change Working Group III, Geneva, Switzerland, 2007.                                                                                   |
|-------------|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| 5 6         | 2. US Environmental Protection Agency, Sources of Greenhouse Gas Emissions, US EPA , 2020.                                                                                                                                                                                                |
| 7           | 3. Hovland Consulting LLC, Zero-Emissions Road Freight Strategy, 2020.                                                                                                                                                                                                                    |
| 9 10 11     | 4. Talebian, H., Herrera, O. E., Tran, M., and Mérida, W. Electrification of road freight transport: Policy implications in British Columbia. Energy policy , 2018. 115:109-118.                                                                                                          |
| 12 13 14    | 5. Xie, F., Liu, C., Li, S., Lin, Z., and Huang, Y. Long-term strategic planning of inter-city fast charging infrastructure for battery electric vehicles. Transportation Research Part E: Logistics and Transportation Review , 2018. 109:261-276.                                       |
| 16 17 18    | 6. Schneider, M., Stenger, A., and Goeke, D. The electric vehicle-routing problem with time windows and recharging stations. Transportation science , 2014. 48(4):500-520.                                                                                                                |
| 19 20 21    | 7. Felipe, Á., Ortuño, M. T., Righini, G., and Tirado, G. A heuristic approach for the green vehicle routing problem with multiple technologies and partial recharges. Transportation Research Part E: Logistics and Transportation Review, 2014. 71:111-128.                             |
| 23 24       | 8. Kucukoglu, I., Dewil, R., and Cattrysse, D. The electric vehicle routing problem and its variations: A literature review. Computers and Industrial Engineering , 2021. 161:107650.                                                                                                     |
| 25 26 27    | 9. Sahin, O., and Stinson, M. Off-Hours Delivery: Simulated Systemwide Results for the Chicago Region. Presented at METRANS - 9th International Urban Freight Conference, Long Beach, CA, 2022.                                                                                           |
| 29 30 31    | 10. Silas, M. A., and Holguín-Veras, J. Behavioral microsimulation formulation for analysis and design of off-hour delivery policies in urban areas. Transportation research record , 2009. 2097(1):43-50.                                                                                |
| 32 33 34    | 11. Holguín-Veras, J., Encarnación, T., González-Calderón, C. A., Winebrake, J., Wang, C., Kyle, S., ... and Garrido, R. Direct impacts of off-hour deliveries on urban freight emissions. Transportation Research Part D: Transport and Environment, 2018. 61:84-103.                    |
| 35 36 37 38 | 12. Auld, J., Hope, M., Ley, H., Sokolov, V., Xu, B., and Zhang, K. POLARIS: Agent-based modeling framework development and implementation for integrated travel demand and network and operations simulations. Transportation Research Part C: Emerging Technologies , 2016. 64:101-116. |
| 40 41 42    | 13. Stinson, M., Enam, A., Moore, A., &Auld, J. Citywide impacts of E-commerce: Does parcel delivery travel outweigh household shopping travel reductions?. In Proceedings of the 2nd ACM/EIGSCC Symposium on Smart Cities and Communities, 2019. 1-7.                                    |
| 43 44 45    | 14. Çatay, B., and Keskin, M. The impact of quick charging stations on the route planning of electric vehicles. In 2017 IEEE Symposium on Computers and Communications (ISCC), 2017. 152-157.                                                                                             |
| 46 47 48    | 15. Keskin, M., and Çatay, B. A matheuristic method for the electric vehicle routing problem with time windows and fast chargers. Computers and operations research , 2018. 100:172-188.                                                                                                  |

49

| 1 2 3    | 16. Yang, J., and Sun, H. Battery swap station location-routing problem with capacitated electric vehicles. Computers and operations research , 2015. 55:217-232.                                                                                                                       |
|----------|-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| 4 5 6 7  | 17. Hof, J., Schneider, M., and Goeke, D. Solving the battery swap station location-routing problem with capacitated electric vehicles using an AVNS algorithm for vehicle-routing problems with intermediate stops. Transportation research part B: methodological , 2017. 97:102-112. |
| 8 9      | 18. Wang, Y. W., Lin, C. C., and Lee, T. J. Electric vehicle tour planning. Transportation Research Part D: Transport and Environment , 2018. 63:121-136.                                                                                                                               |
| 11 12 13 | 19. Masmoudi, M. A., Hosny, M., Demir, E., Genikomsakis, K. N., and Cheikhrouhou, N. The dial-a-ride problem with electric vehicles and battery swapping stations. Transportation research part E: logistics and transportation review , 2018. 118:392-420.                             |
| 15 16 17 | 20. Jie, W., Yang, J., Zhang, M., and Huang, Y. The two-echelon capacitated electric vehicle routing problem with battery swapping stations: Formulation and efficient methodology. European Journal of Operational Research , 2019. 272(3) :879-904.                                   |
| 19 20    | 21. Zhen, L., Xu, Z., Ma, C., and Xiao, L. Hybrid electric vehicle routing problem with mode selection. International Journal of Production Research , 2020. 58(2):562-576.                                                                                                             |
| 22 23    | 22. Montoya, A., Guéret, C., Mendoza, J. E., and Villegas, J. G. The electric vehicle routing problem with nonlinear charging function. Transportation Research Part B: Methodological , 2017. 103:87-110.                                                                              |
| 25 26 27 | 23. Froger, A., Mendoza, J. E., Jabali, O., and Laporte, G. Improved formulations and algorithmic components for the electric vehicle routing problem with nonlinear charging functions. Computers and Operations Research , 2019. 104:256-294.                                         |
| 29 30    | 24. Kancharla, S. R., and Ramadurai, G. Electric vehicle routing problem with non-linear charging and load-dependent discharging. Expert Systems with Applications , 2020. 160:113714.                                                                                                  |
| 31 32 33 | 25. Sweda, T. M., Dolinskaya, I. S., and Klabjan, D. Adaptive routing and recharging policies for electric vehicles. Transportation Science , 2017. 51(4):1326-1348.                                                                                                                    |
| 35 36    | 26. Keskin, M., Laporte, G., and Çatay, B. Electric vehicle routing problem with time-dependent waiting times at recharging stations. Computers and Operations Research , 2019. 107:77-94.                                                                                              |
| 37 38 39 | 27. Kullman, N. D., Goodson, J. C., and Mendoza, J. E. Electric vehicle routing with public charging stations. Transportation Science , 2021. 55(3):637-659.                                                                                                                            |
| 41 42 43 | 28. Keskin, M., Çatay, B., and Laporte, G. A simulation-based heuristic for the electric vehicle routing problem with time windows and stochastic waiting times at recharging stations. Computers and Operations Research , 2021. 125:105060.                                           |
| 44 45 46 | 29. Keskin, M., and Çatay, B. Partial recharge strategies for the electric vehicle routing problem with time windows. Transportation research part C: emerging technologies , 2016. 65:111-127.                                                                                         |
| 48 49    | 30. Schiffer, M., and Walther, G. The electric location routing problem with time windows and partial recharging. European journal of operational research , 2017. 260(3):995-1013.                                                                                                     |

50

| 1 2 3       | 31. Macrina, G., Pugliese, L. D. P., Guerriero, F., and Laporte, G. The green mixed fleet vehicle routing problem with partial battery recharging and time windows. Computers and Operations Research , 2019. 101:183-199.                                                                                              |
|-------------|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| 4 5 6       | 32. Goeke, D., and Schneider, M. Routing a mixed fleet of electric and conventional vehicles. European Journal of Operational Research , 2015. 245(1):81-99.                                                                                                                                                            |
| 8 9 10      | 33. Rastani, S., Yüksel, T., and Çatay, B. Effects of ambient temperature on the route planning of electric freight vehicles. Transportation Research Part D: Transport and Environment , 2019. 74:124-141.                                                                                                             |
| 11 12 13    | 34. Rastani, S., Yüksel, T., and Çatay, B. Electric vehicle routing problem with time windows and cargo weight. Smart and Sustainable Supply Chain and Logistics-Trends, Challenges, Methods and Best Practices , 2020. 1:175-190.                                                                                      |
| 15 16 17    | 35. Rastani, S., and Çatay, B. A large neighborhood search-based matheuristic for the load-dependent electric vehicle routing problem with time windows. Annals of Operations Research , 2021. 1-33.                                                                                                                    |
| 18 19 20    | 36. Hiermann, G., Puchinger, J., Ropke, S., and Hartl, R. F. The electric fleet size and mix vehicle routing problem with time windows and recharging stations. European Journal of Operational Research , 2016. 252(3):995-1018.                                                                                       |
| 22 23       | 37. Mancini, S. The hybrid vehicle routing problem. Transportation Research Part C: Emerging Technologies , 2017. 78:1-12.                                                                                                                                                                                              |
| 25 26       | 38. Sassi, O., and Oulamara, A. Electric vehicle scheduling and optimal charging problem: complexity, exact and heuristic approaches. International Journal of Production Research , 2017. 55(2):519-535.                                                                                                               |
| 27 28 29    | 39. Hiermann, G., Hartl, R. F., Puchinger, J., and Vidal, T. Routing a mix of conventional, plug-in hybrid, and electric vehicles. European Journal of Operational Research , 2019. 272(1):235-248.                                                                                                                     |
| 31 32       | 40. Schiffer, M., Schneider, M., and Laporte, G. Designing sustainable mid-haul logistics networks with intra-route multi-resource facilities. European Journal of Operational Research , 2018. 265(2):517-532.                                                                                                         |
| 33 34 35    | 41. Schiffer, M., and Walther, G. An adaptive large neighborhood search for the location-routing problem with intra-route facilities. Transportation Science , 2018. 52(2):331-352.                                                                                                                                     |
| 37 38 39 40 | 42. Ghamami, M., Kavianipour, M., Zockaie, A., Hohnstadt, L. R., and Ouyang, Y. Refueling infrastructure planning in intercity networks considering route choice and travel time delay for mixed fleet of electric and conventional vehicles. Transportation Research Part C: Emerging Technologies , 2020. 120:102802. |
| 42 43 44    | 43. Zhu, Z. H., Gao, Z. Y., Zheng, J. F., and Du, H. M. Charging station location problem of plug-in electric vehicles. Journal of Transport Geography , 2016. 52:11-22.                                                                                                                                                |
| 45 46 47    | 44. Ghamami, M., Zockaie, A., and Nie, Y. M. A general corridor model for designing plug-in electric vehicle charging infrastructure to support intercity travel. Transportation Research Part C: Emerging Technologies , 2016. 68:389-402.                                                                             |
| 49 50       | 45. Wang, I. L., Wang, Y., and Lin, P. C. Optimal recharging strategies for electric vehicle fleets with duration constraints. Transportation Research Part C: Emerging Technologies , 2016. 69:242-254.                                                                                                                |

51

| 1 2         | 46. Liu, Z., and Song, Z. Dynamic charging infrastructure deployment for plug-in hybrid electric trucks. Transportation Research Part C: Emerging Technologies , 2018. 95:748-772.                                                                              |
|-------------|-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| 3 4 5 6     | 47. Wang, Y., Wei, S., and Chen, Y. Optimal Routing for Off-Hour Delivery Trucks with Noise- Reduction and Transport Costs Objectives. J. Comput. , 2019. 14(10):615-623.                                                                                       |
| 7 8 9       | 48. Ukkusuri, S. V., Ozbay, K., Yushimito, W. F., Iyer, S., Morgul, E. F., and Holguín-Veras, J. Assessing the impact of urban off-hour delivery program using city scale simulation models. EURO Journal on Transportation and Logistics , 2016. 5(2):205-230. |
| 11 12 13    | 49. Mommens, K., Lebeau, P., Verlinde, S., Van Lier, T., and Macharis, C. Evaluating the impact of off- hour deliveries: An application of the TRansport Agent-BAsed model. Transportation Research Part D: Transport and Environment , 2018. 62:102-111.       |
| 14 15 16 17 | 50. Ren, Y., Dessouky, M., and Ordóñez, F. The multi-shift vehicle routing problem with overtime. Computers and Operations Research , 2010. 37(11):1987-1998.                                                                                                   |
| 18 19 20    | 51. Bai, R., Xue, N., Chen, J., and Roberts, G. W. A set-covering model for a bidirectional multi-shift full truckload vehicle routing problem. Transportation Research Part B: Methodological , 2015. 79:134-148.                                              |
| 21 22       | 52. Zangeneh-Khamooshi, S., Zabinsky, Z. B., and Heim, J. A. A multi-shift vehicle routing problem with windows and cycle times. Optimization Letters , 2013. 7:1215-1225.                                                                                      |
| 24 25 26    | 53. Xue, N., Bai, R., Qu, R., and Aickelin, U. A hybrid pricing and cutting approach for the multi-shift full truckload vehicle routing problem. European Journal of Operational Research , 2021. 292(2):500- 514.                                              |
| 27 28 29    | 54. Li, H., and Lim, A. Ametaheuristic for the pickup and delivery problem with time windows. International Journal on Artificial Intelligence Tools , 2003. 12(02):173-186.                                                                                    |
| 30 31 32    | 55. Melachrinoudis, E., Ilhan, A. B., and Min, H. A dial-a-ride problem for client transportation in a health-care organization. Computers and Operations Research , 2007. 34(3):742-759.                                                                       |
| 33 34 35 36 | 56. Suzuki, Y., and Lan, B. Reducing the cost of B2B logistics via night deliveries: Does it really work?. Decision Sciences . 2021.                                                                                                                            |
| 37 38       | 57. Sadati, M. E. H., Akbari, V., and Çatay, B. Electric vehicle routing problem with flexible deliveries. International Journal of Production Research , 2022. 60(13):4268-4294.                                                                               |
| 40 41       | 58. Parragh, S. N., Doerner, K. F., and Hartl, R. F. A survey on pickup and delivery problems. Part II: Transportation between pickup and delivery locations, Journal für Betriebswirtschaft , 2007. 58:81-117.                                                 |
| 42 43 44    | 59. Koç, Ç., Laporte, G., and Tükenmez, İ. A review of vehicle routing with simultaneous pickup and delivery. Computers and Operations Research , 2020. 122:104987.                                                                                             |
| 45 46 47 48 | 60. Salhi, S., Imran, A., and Wassan, N. A. The multi-depot vehicle routing problem with heterogeneous vehicle fleet: Formulation and a variable neighborhood search implementation. Computers and Operations Research , 2014. 52:315-325.                      |
| 49 50 51    | 61. Vijayagopal, R., and Rousseau, A. Electric truck economic feasibility analysis. World Electric Vehicle Journal , 2021. 12(2):75.                                                                                                                            |
Hyun-Seop Uhm Abdelrahman Ismael Natalia Zuniga-Garcia Olcay Sahin James Cook Joshua Auld Monique Stinson
Fleet-mix Electric Vehicle Routing Problem for the E-commerce Delivery with Limited Off-Hour Delivery Implementation
Freight truck electrification for last-mile delivery is one of the most
important research topics to reduce the dependency on fossil fuel operations.
Although a battery electric truck still has limitations on daily operations
with lower driving ranges and higher purchasing cost than a conventional truck,
operations with electrified trucks reduce total energy usage and driving noise
on routes. In this paper, we propose a fleet-mix and multi-shift electric
vehicle routing problem for joint implementation of fleet electrification and
off-hour delivery in urban e-commerce delivery systems. Every electrified truck
is assumed to have two shifts for both daytime and nighttime delivery
operations while conventional trucks can operate during daytime only because of
municipal restrictions on nighttime deliveries, which are related to engine
noise. Also, every electrified truck must recharge between shifts at its depot.
A fleet owner decides the best electrification ratio of the fleet and the
proper number of chargers which gives the minimum total cost. The optimization
problem is described as a mixed-integer linear programming model including
common constraints for vehicle routing problem, recharging constraints, and
two-shift operation of electrified trucks. A bi-level VNS-TS heuristic is also
suggested for efficient solution search. The upper-level problem assigns trucks
with engine type and brief route information using variable neighborhood search
heuristic, and the lower-level problem finds the best route of each assigned
truck using a tabu search heuristic. Scenarios with different EV driving ranges
and nighttime operation availabilities are developed and evaluated with the
POLARIS transportation simulation framework, and results are reported.