Bi-Objective Battery Electric Truck Dispatching Problem with Backhauls and Time Windows

Abstract

The battery electric truck (BET) has emerged as a promising solution to reduce greenhouse gas emissions in urban logistics, given the current strict environmental regulations. This research explores the formulation and solution of the bi-objective BET dispatching problem with backhauls and time windows, aiming to simultaneously reduce environmental impacts and enhance the efficiency of urban logistics. From the sustainability perspective, one of the objectives is to minimize total energy costs, which include energy consumption and battery replacement expenses. On the other hand, from an economic perspective, the other objective is the minimization of labor costs. To solve this bi-objective BET dispatching problem, we propose an innovative approach, integrating an adaptive large neighborhood search-based metaheuristics algorithm with a multi-objective optimization strategy. This integration enables the exploration of the trade-off between fleet energy expenses and labor costs, optimizing the dispatching decisions for BETs. To validate the proposed dispatching strategy, extensive experiments were conducted using real-world fleet operations data from a logistics fleet in Southern California. The results demonstrated that the proposed approach yields a set of Pareto solutions, showcasing its effectiveness in finding a balance between energy efficiency and labor costs in urban logistics systems. The findings of this research contribute to advancing sustainable urban logistics practices and provide valuable insights for fleet operators in effectively managing BET fleets to reduce environmental impacts while maintaining economic efficiency.

Keywords

freight operations trucking industry research city logistics and last mile strategies sustainability and resilience transportation and sustainability electric and hybrid-electric vehicles

Urban freight transportation plays an important role in fostering economic development and sustainability within cities, garnering attention from stakeholders in both the public and the private sectors. For example, the U.S.A. has set a goal to achieve a 50%–52% reduction in greenhouse gas (GHG) emissions below 2005 levels economy-wide, including from the transportation sector, by 2030 ( 1 ). As another example, the European Environment Agency has planned to reduce GHG emissions from transportation to a level of 6% below 1990 levels by 2030 ( 2 ). These ambitious goals have led to the implementation of diverse policies and measures, particularly promoting low-carbon fuels and electric vehicles (EVs). Among others, battery EVs have emerged as a promising and viable option to achieve sustainable urban freight transportation and contribute toward reaching these environmental targets.

In recent years, there has been a surge in the adoption of EVs such as battery electric trucks (BETs) within the logistics and transportation network planning domain. Notably, this trend is evident in various applications, such as EV routing ( 3 – 8 ), BET fleet dispatching ( 9 – 12 ), and electric bus scheduling ( 13 , 14 ). Those efforts have been made to reduce GHG emissions through efficient routing and scheduling of EVs. This is especially important for heavy-duty (i.e., Classes 7 and 8) BETs, which are subject to limitations such as short range of travel, high vehicle purchase and battery replacement costs, scarcity of recharging stations, and long recharging time.

Our study is motivated by the pressing need to curb transportation-related GHG emissions and establish a sustainable urban freight dispatching strategy. However, we recognize the inherent conflict between two essential perspectives when developing such a strategy—the need to address environmental concerns while also meeting economic goals. On the one hand, from a sustainability point of view, an energy-efficient dispatching approach is desired to minimize total energy consumption. On the other hand, a time-efficient routing strategy is crucial to ensure the optimal level of service and customer satisfaction.

For instance, cargo weight is one of the key factors influencing heavy-duty BET energy consumption, especially for Class 8 BETs. During a route, more energy is consumed when a BET travels long distances with a full or heavy load. Consequently, decision-makers may adjust the service sequences of BETs to achieve an energy-efficient dispatching solution for the truck fleet. In that case, customers who require heavy cargo may have priority. The BET can visit them first to reduce the cargo weight, and then visit the remaining customers. Thus, this adjustment may lead to an increase in the total travel time, potentially causing delays for other customers and reducing the level of service.

Researchers have applied techniques from multi-objective optimization (MOO) to solve multi-objective vehicle routing problems. For example, Demir et al. ( 15 ) extended the traditional pollution routing problem (PRP) and proposed a bi-objective PRP model for an internal combustion engine vehicle fleet. The first objective is minimizing fuel consumption while the second objective is minimizing the total travel time. To address this problem, the authors incorporated MOO techniques with an adaptive large neighborhood search (ALNS) metaheuristic, where the ALNS is a search engine to find a set of Pareto solutions. Muñoz-Villamizar et al. ( 16 ) introduced a bi-objective urban transport network model aimed at improving the efficiency of urban logistics while simultaneously reducing environmental impacts and maintaining service levels. Specifically, the authors investigated the efficient trade-off between potential economic impacts and GHG emission reduction when implementing an EV fleet. A weighted method was introduced to find the efficient frontier of the problem. Recently, Amiri et al. ( 17 ) introduced a green vehicle routing problem (G-VRP) variant and considered a heterogenous truck fleet, which includes heavy-duty diesel trucks and BETs. The authors first investigated the economic impact as one objective when deploying the mixed truck fleet. To address environmental concerns, they also considered GHG emissions as the second objective.

Contrary to the traditional PRP ( 15 ), developing a dispatching strategy for a BET fleet poses greater challenges. Since BETs have limited battery capacity (and thus, range), decision-makers need to consider an optimal recharging scheme at both the tactical and operational levels when necessary. Firstly, an en route partial recharging policy ( 18 ) should be taken into account. This policy has the potential to reduce idle time and improve dispatching efficiency. Secondly, because of the scarcity of charging stations, BETs may need to make a detour to reach a suitable recharging station. In this study, we incorporate these practical considerations in the design of BET dispatching strategies.

In addition, the proposed BET dispatching problem considers a backhaul strategy, where the BET routes follow a last-in, first-out rule ( 19 ). It has been demonstrated as a sustainable way to improve the dispatching efficiency in urban logistics ( 20 ). To do this, customers are categorized into linehaul customers, who require deliveries, and backhaul customers, who require pickups. The pickup orders are only initiated once all deliveries are completed. This strategy is commonly known as the vehicle routing problem with backhauls (VRPB) ( 21 ). Over the years, various approaches have been proposed to solve the VPRB, including exact methods ( 21 , 22 ) and metaheuristics approaches ( 23 – 25 ).

Major contributions of this paper to the research field are summarized as follows.

Formulation of a bi-objective BET dispatching problem: A novel bi-objective dispatching problem is proposed for BET fleets, considering important factors such as backhauling, en route partial recharging policy, limited range and capacity, and time window constraints. This extended formulation of the classic G-VRP incorporates two objective functions, total BET fleet energy cost and total labor cost, addressing both environmental and economic concerns.

Development of an efficient dispatching strategy: An advanced dispatching algorithm is developed to solve the bi-objective BET dispatching problem. The algorithm combines the ALNS metaheuristics with a MOO approach. By leveraging the ALNS framework, the algorithm searches for a set of Pareto solutions that provide versatile dispatching guidance for fleet operators.

Validation with benchmark and real-world fleet dispatching data: To assess the performance of the proposed dispatching algorithm with respect to solution quality and computation time, we apply our dispatching algorithm to a VRPB benchmark dataset ( 21 ) and find that it achieves the best-known solution (BKS) in 16 instances (out of 62). The deviation between our best solution and the BKS is less than 1% for more than half of the problem instances, demonstrating the efficacy of our algorithm. In addition, the ALNS framework is extensively validated using real-world fleet dispatching data, confirming the effectiveness of the dispatching algorithm in practical applications.

Overall, this research significantly contributes to advancing the field of sustainable urban logistics and BET fleet management, providing valuable insights and practical tools for optimizing dispatching decisions while considering energy efficiency and cost-effectiveness.

The remainder of this paper is organized as follows. The second section presents a mixed-integer linear programming (MILP) model of the bi-objective BET dispatching problem. The third section describes the methodology of the ALNS-based metaheuristics algorithm, integrated with a MOO approach to effectively solve the proposed problem. The fourth section is dedicated to the evaluation of the solution performance based on a VRPB benchmark dataset as well as a real-world case study. Finally, the fifth section concludes the paper and outlines potential directions for future work.

Problem Description and Formulation

The proposed bi-objective BET dispatching problem considers a set of customers with known delivery type (pickup or delivery), appointment time windows, service time, demand, and address. The dispatcher should make a dispatching decision for a fleet of BETs with limited cargo payload and battery capacity, following the last-in and first-out strategy. The goal is to construct optimal routes that start from the depot, visit all customers exactly once following a first-out and last-in rule, and return to the same depot within the predefined operation time. Specifically, a possible en route recharging scheme is considered during the route planning when the BET route is energy infeasible.

There are two conflicting objectives during the decision-making stage: fleet energy cost (i.e., battery electricity and depletion cost) and labor cost. The first objective is to minimize the fleet energy cost related to battery energy consumption, recharging cost, and battery replacement cost in urban distribution. The second objective is minimizing the labor cost, which is a linear combination of travel and recharging time. Considering a realistic energy consumption model (detailed in the BET Fleet Energy Cost of Transportation section), the cargo weight and travel distance can influence the total energy consumption. So, the BET may detour to avoid a full truckload with long trips. Therefore, the total travel time could be increased because of the detour.

A bi-objective evaluation is recommended to estimate the efficient frontier between fleet energy and labor costs. The detailed mathematical formulation of those objectives is described in the BET Fleet Energy Cost of Transportation and Travel Time Cost of Transportation sections, following the Problem Description section.

Problem Description

The proposed BET dispatching problem requires decision-making at two levels: (1) the strategic level, where an en route recharging schedule needs to be located during dispatching; and (2) the tactical level, which determines the energy-efficient routing strategy of the BET fleet considering the backhauling strategy, time windows, and partial recharging policy.

To formulate the BET dispatching problem, we define it on a complete directed graph $G = (N'_{O, D} \cup R, A)$ , where $N'_{O, D}$ is the set of nodes including customer nodes $N$ and depot node $(O, D)$ , and $R$ represents a set of recharging stations. The customers $N$ can be partitioned into two sets, that is, $N = {L, B}$ , where the sets $L = (1, 2, \dots, n)$ and $B = (n + 1, n + 2, \dots, n + m)$ represent the linehaul customers and the backhaul customers, respectively. Each customer $i \in N$ has a specific service type, a service time $s$ , a time window $[e, l]$ , and a demand $q$ (negative if delivery and positive if pickup).

The arc set is defined by $A = A_{1} \cup A_{2} \cup A_{3}$ , where $A_{1} = {(i, j) \in A : i \in L \cup O, j \in L \cup R}$ to connect all forward flows, $A_{2} = {(i, j) \in A : i \in B \cup R, j \in B \cup D}$ to represent the backward flows, and the interface arc is represented by $A_{3} = {(i, j) \in A : i \in L \cup R, j \in B \cup D}$ . To simplify the flow degrees in the mathematical formulation, we define $Δ_{i}^{+} = {j : (i, j) \in A, i \in N'_{O, D}}$ , which denotes the forward of $i$ , and $Δ_{i}^{-} = {j : (j, i) \in A, i \in N'_{O, D}}$ , which denotes the backward of $i$ . Each arc $(i, j)$ has an associated travel distance $d_{ij}$ , energy consumption $E_{ij}$ , and travel time $t_{ij}$ .

BET Fleet Energy Cost of Transportation

The first objective function of the bi-objective BET dispatching problem is to minimize the total energy cost, which consists of total energy consumption, recharging, and battery replacement costs. In addition, we consider the microscopic energy consumption models presented by Wang et al. ( 26 ) and Goeke and Schneider ( 3 ) to estimate BET energy consumption in each arc.

Figure 1 illustrates the calculation of required energy consumption for the BET. We first determine the mechanical power applied to fulfill its acceleration and overcome the air and rolling resistance. Then, electric power output ${W_{E}}_{ij}$ from the battery can be estimated by the efficiencies of the electric motors based on the tractive power. In addition, similar to the energy consumption model in Wang et al. ( 26 ), the accessory load $P_{acc}$ is considered in our model. Finally, the required electric power and accessory load are converted into the amount of power generated from the battery, which depends on the battery discharge efficiency.

Figure 1.

Calculation of required energy on an arc.

The rolling resistance $F_{r}$ of the BET is calculated by Equation 1, which is required to overcome the rolling, aerodynamic resistance, and gravitational force. In this equation, $c_{r}$ denotes the rolling resistance factor, $g$ stands for the gravitational constant, and $θ$ represents the gradient angle. We assume the total weight $M = w + C_{ij}$ , where $w$ and $C_{ij}$ represent the curb weight (i.e., the weight of empty truck) and load carried by the BET, respectively:

F_{r} = c_{r} \cdot M \cdot g \cdot \cos (θ) .

(1)

Considering the speed $v$ , the aerodynamic drag coefficient $c_{d}$ , the air density $ρ_{a}$ , and the frontal area $A$ , the aerodynamic resistance $F_{a}$ can be calculated by the following:

F_{a} = \frac{1}{2} \cdot ρ_{a} \cdot A \cdot c_{d} \cdot v^{2} .

(2)

Therefore, the total mechanical power $P_{M}$ is as follows:

\begin{matrix} P_{M} = \\ (M \cdot a + \frac{1}{2} \cdot c_{d} \cdot ρ \cdot A \cdot v^{2} + M \cdot g \cdot \sin (θ) + c_{r} \cdot M \cdot g \cdot \cos (θ)) \cdot ν . \end{matrix}

(3)

The mechanical and accessory energy required by the BET is estimated by the following:

{W_{E}}_{ij} \approx (P_{M} + P_{acc}) \frac{d_{ij}}{v_{ij}} = α (w + C_{ij}) d_{ij} + β v_{ij}^{2} d_{ij} + P_{acc} \frac{d_{ij}}{v_{ij}},

(4)

where $α = a + g \sin θ + g C_{r} \cos θ$ is an arc specific constant and $β = 0.5 C_{d} A ρ$ is a vehicle specific constant.

Therefore, the motor efficiency $(ef f_{m})$ and battery discharging efficiency $(ef f_{d})$ of a BET are taken into consideration in the model. The electric energy consumption $E_{ij}$ for traveling this arc can be calculated as follows:

\begin{matrix} E_{ij} = & \frac{{W_{E}}_{ij}}{ef f_{d} \cdot ef f_{m}} = \frac{(P_{M} + P_{acc})}{ef f_{d} \cdot ef f_{m}} \cdot \frac{d_{ij}}{v_{ij}} = \frac{1}{ef f_{d} \cdot ef f_{m}} \cdot \\ {[α_{ij} (w + C_{ij}) d_{ij} + β v_{ij}^{2} d_{ij}] + P_{acc} \frac{d_{ij}}{v_{ij}}} . \end{matrix}

(5)

In this study, minimizing the total fleet energy cost $(Z_{1})$ can be formulated as a mixed-integer programming problem, as shown in Equation 6. The first term is the total energy consumption cost for the BET fleet, while the second term is the battery replacement cost. The battery replacement cost is generated by the distance traveled by the BETs. We assume the BET fleet has to have replacement batteries after 150,000 mi, and the cost factor of replacement $C^{B}$ is given by Goeke and Schneider ( 3 ). A binary variable $x_{ij}$ is used to determine if the BET has traveled on the arcs:

min Z_{1} = \sum_{i \in {N^{'}}_{O} \cup R, j \in {N^{'}}_{D} \cup R, i \neq j} (C^{E} E_{ij} + C^{B} d_{ij}) x_{ij} .

(6)

Travel Time Cost of Transportation

The second objective function of the bi-objective BET dispatching problem is to minimize the total labor cost of transportation with respect to travel time. It consists of travel times, loading/unloading service times at each customer, and idling time at the recharging station. Table 1 summarizes the variable definitions in our model:

min Z_{2} = \sum_{i \in {N^{'}}_{O} \cup R, j \in {N^{'}}_{D} \cup R, i \neq j} C^{T} (t_{ij} + s_{i} + \frac{(Y_{i} - y_{i})}{r} k_{ij}) x_{ij}

(7)

Table 1.

Notations and Vehicle Parameters of the Mathematical Model

Notation	Description
Problem parameters
$C^{E}$	Cost factor of energy consumption
$C^{B}$	Cost factor of battery replacement
$C^{T}$	Cost factor of travel time
$m_{B}$	Set of BETs available at the depot
$K$	Total number of BETs in operation
$N$	Sets of customer vertices
$L$	Sets of linehaul customer vertices
$B$	Sets of backhaul customer vertices
$R$	Recharging station(s)
$r$	Recharging rate
$d_{ij}$	Distance between vertices i and j
$E_{ij}$	Energy consumption between vertices i and j
$t_{ij}$	Travel time between vertices i and j
$T_{O}$	Earliest departure time
$T_{D}$	Latest return time
$C$	Cargo payload capacity
$Q$	BET maximum battery capacity
$q_{i}$	Demand at vertex (positive if pickup, negative if drop-off)
$e_{i}$	Earliest start of service time at vertex i
$l_{i}$	Latest start of service time at vertex i
$s_{i}$	Service time at vertex i
Decision variables
$τ_{i}$	Decision variable specifying the time of arrival at vertex i
$k_{i}$	Decision variable specifying the visit to recharging station vertex i. 0 if customer, 1 if charging station.
$u_{i}$	Decision variable specifying the remain cargo on arrival at vertex i
$y_{i}$	Current SOC for BET $v_{B}$ when arriving at vertex i
$Y_{i}$	Finish charging SOC for BET $v_{B}$ at vertex i
$x_{ij}$	Binary decision variable. 0 if the route from i to j is not visited by BET $v_{B}$ , 1 otherwise

Note: BET = battery electric truck; SOC = state of charge.

Multi-Objective Evaluation and Constraints

The multi-objective evaluation is used to evaluate the impact of the fleet energy cost and the labor cost of transportation by identifying a set of non-dominated solutions (i.e., Pareto optimal solutions). When searching for the Pareto optimal solutions, it attempts to improve one of the objective functions without compromising the other. Thereby, one way is to use the weighted method, which minimizes the weighted sum of the objective functions. This method transfers a multi-objective function to a single objective function by multiplying a weighted sum of factors. The mixed-integer programming formulation of our problem is shown in Equation 8. We define non-negative weighting factors $w_{a}$ and $(1 - w_{a})$ for the fleet energy cost and labor cost, respectively:

\begin{matrix} min Z_{3} & = w_{a} \sum_{i \in {N^{'}}_{O} \cup R, j \in {N^{'}}_{D} \cup R, i \neq j} (C^{E} E_{ij} + C^{B} d_{ij}) x_{ij} \\ + (1 - w_{a}) \sum_{i \in {N^{'}}_{O} \cup R, j \in {N^{'}}_{D} \cup R, i \neq j} C^{T} (t_{ij} + s_{i} + \frac{(Y_{i} - y_{i})}{r} k_{ij}) x_{ij}, \end{matrix}

(8)

subject to the following.

Demand and flow balance constraints:

\sum_{i \in Δ_{i}^{-}} x_{ij} = 1, j \in N \cup R,

(9)

\sum_{j \in Δ_{j}^{+}} x_{ij} = 1, i \in N \cup R,

(10)

\sum_{j \in N'_{D} \cup R, i \neq j} x_{ij} - x_{ji} = 0, \forall i \in N'_{O} \cup R,

(11)

\sum_{i \in Δ_{O}^{-}} x_{ij} = K,

(12)

\sum_{i \in Δ_{O}^{+}} x_{ij} = K .

(13)

Vehicle constraints:

y_{O} = Q .

(14)

Recharging constraints:

\sum_{j \in (D \cup N \cup R)} x_{ij} \leq 1, \forall i \in R,

(15)

{\begin{matrix} \sum_{i, j \in (D \cup N \cup R)} (t_{ij} + (1 - k_{i}) s_{i} + k_{i} \cdot \frac{Y_{i} - y_{i}}{r}) \\ x_{ij} \leq T_{D} - T_{O}, \\ \forall i \in O \cup N \cup R, j \in (D \cup N \cup R), i \neq j, \end{matrix}

(16)

0 < Y_{i} \leq Min {60 \cdot r, 80 % \cdot Q} \forall i \in R,

(17)

\begin{matrix} 0 \leq ((1 - k_{i}) \cdot y_{i} + k_{i} \cdot Y_{i} - E_{ij}) x_{ij} \leq Q, \\ \forall i \in {N^{'}}_{O} \cup R, j \in {N^{'}}_{D} \cup R, i \neq j . \end{matrix}

(18)

Time window constraints:

\begin{matrix} τ_{i} + (s_{i} + t_{ij}) x_{ij} - l_{0} (1 - x_{ij}) \leq τ_{j} \\ \forall i \in O \cup N \cup R, \forall j \in D \cup N \cup R i \neq j, \end{matrix}

(19)

e_{i} \leq τ_{i} \leq l_{i}, \forall i \in N'_{O, D} .

(20)

Demand constraints:

0 \leq u_{o} \leq C,

(21)

\begin{matrix} 0 \leq u_{j} \leq (u_{i} - q_{i}) x_{ij} + C (1 - x_{ij}) \\ \forall i \in O \cup N \cup R, \forall j \in D \cup N \cup R, i \neq j . \end{matrix}

(22)

Binary decision variable:

x_{ij} \in {0, 1}, \forall i, j \in N'_{O, D}, i \neq j .

(23)

Constraints 9–11 define the forward and backward flow conservation constraints. Constraints 12 and 13 ensure that the number of routes equals the number of operating BETs. Constraint 14 defines that the BET fleet is fully recharged with battery capacity $Q$ when departing the depot. Constraint 15 guarantees a recharging visit occurs at most once during dispatching. Constraints 16–18 state the recharging time window and the maximum charging volume. The maximum charging time is limited to 1 h. Constraints 19 and 20 force the BET to visit the customers within the scheduled time windows. Constraints 21 and 22 guarantee the cargo load does not exceed the payload capacity for either linehauls or backhauls. Finally, condition 23 defines the binary decision variables.

Methodology

In this section, an ALNS metaheuristic is proposed to solve the bi-objective BET dispatching problem. There are two main goals for the developed ALNS framework. One on hand, the ALNS is used as a searching engine to find a set of Pareto solutions for the proposed bi-objective BET dispatching problem. On the other hand, an en route partial recharging schedule is scheduled for the BET fleet. An overview of the ALNS framework is described in Algorithm 1.

Algorithm 1.

Overview of the ALNS framework.

Input: An initial feasible solution $S$ generated by initialization phase;
Output: Best solution $S^{b}$
1: $S^{init} \leftarrow generate_inital_solution ()$
2: $S^{b} = S^{init}; ω^{-} = (1, \dots, 1); ω^{+} = (1, \dots, 1)$
3: while iterations $η$ is not reached do
4: {select a destroy operator $ζ^{-} \in Π^{-}$ by $P (ω_{i}^{-})$ }
5: Remove $n$ vertex from current solution $S^{c}$ ( $S^{c} = S^{init} at the first iteration$ ) with $ζ^{-}$
6: $S^{c'} \leftarrow$ ApplyDestroyedOperator( $S^{c}$ )
7: {select a repair operator $ζ^{+} \in Π^{+}$ by $P (ω_{i}^{+})$ }}
8: $S^{c'} \leftarrow$ ApplyRepairOperator( $S^{c'}$ )
9: if accept_SA( $S^{c'}$ , $S^{b}$ ) then
10: $S^{c} \leftarrow S^{c'}$
11: if $S^{c'}$ is better than $S^{b}$ then
12: $S^{b} \leftarrow S^{c'}$
13: end if
14: end if
15: Update: the weight for $ω^{-}$ and $ω^{+}$
16: end while
17: return $S^{b}$

Generation of the Initial Solution

The initial solution for ALNS is generated by a greedy constructive heuristic. At the beginning, unvisited customers are first sorted in a non-decreasing order according to the cost function $Z_{3}$ , then iteratively inserted into the BET routes. During each iteration, a candidate customer $i$ is randomly selected and insert to the current solution $S^{init}$ , which leads to a minimum increase in the total cost, that is, $c_{i} = Z_{3} (S^{init}) - Z_{3} (S_{- i}^{init})$ , where $S_{- i}^{init}$ is the solution with the candidate customer $i$ and $S^{init}$ is the solution with customer $i$ . Once the BET route is energy infeasible, we try to insert a possible recharging schedule from a set of available recharging stations $R$ . Therefore, more unvisited customers are allowed to insert the solution $S^{init}$ until the energy violation, truck cargo capacity violation, or total working time limitation occurs. Subsequently, if there are customers who are not visited, a new BET route starts following the aforementioned processes.

Destroy and Repair Operators

Our ALNS framework uses five destroy operators for removing $n = ϵ \cdot N$ vertices from the current solution, where the number of customers/vertices $n$ is predefined by the destroy rate $ϵ$ . The removal heuristics are detailed as follows.

Random removal randomly removes $n$ customers/vertices from the BET routes. It can randomly remove customers and the recharging schedule.

Random path removal destroys an entire consecutive sub-path with $n$ vertices.

Simplified Shaw removal identifies and removes customers according to their geographical positions. Firstly, we randomly choose a customer from the route and find the closest customer that has not been chosen to be removed. This pair of customers is identified and removed to subset $L_{removal}$ . Next, the new request is selected from this route that has not been touched by the removal operator, and a new pair is identified by their distance. This process continues several times until the desired number of customers has been removed to the subset $L_{removal}$ .

Worst removal iteratively removes $n$ vertices that contribute the largest insertion cost. It first sorts the insertion cost of all vertices in descending order by calculating $c_{i} = Z_{3} (s) - Z_{3} (s_{- i})$ , where $s_{- i}$ is the route without customer $i$ and $s$ is the route with customer $i$ .

Shaw removal ( 27 ) removes a set of $n$ similar customers. A relatedness function is used to check the similarity for customers $i$ and $j$ , which can be calculated by $Λ (i, j) = ϕ_{1} \frac{d_{ij}}{{max}_{i, j \in N} (d_{ij})} + ϕ_{2} | e_{i} - e_{j} | + ϕ_{3} \frac{| q_{i} - q_{j} |}{{max}_{i \in N} (q_{i}) - {min}_{i \in N} (q_{i})}$ . The weight vector $ϕ = (ϕ_{1}, ϕ_{2}, ϕ_{3})$ is applied to normalize the relatedness function. At the beginning, a customer $i \in N$ is randomly selected as a candidate customer who needs to be removed. Next, the most related customer $j \in N \ i$ is chosen by calculating the similarity function with the smallest value $Λ (i, j)$ . The operator continues to remove the related customer with $j$ . Finally, the Shaw removal operator terminates once $n$ customers have been removed.

Our ALNS framework applies four repair operators to reconstruct all unvisited customers such that the new solution is feasible. Figure 2 shows an example of the repairing process.

Figure 2.

An example of the repairing process.

Greedy insertion iteratively reinserts unvisited customers to construct a route by selecting the feasible cost-minimizing position of each customer. The greedy insertion process terminates when all unvisited customers have been inserted.

Greedy insertion with charging stations is employed to construct routes and determine a recharging schedule. For the insertion of customers, it follows the greedy insertion process. If a BET route is energy infeasible, an appropriate charging station (CS) visit is inserted, considering the detour cost and recharging constraints described in the Multi-Objective Evaluation and Constraints section. If the current BET route has a possible en route recharging visit, more customers are allowed to be visited. When no more customers can be inserted into the current route because of the constraints, a new BET route should be started. However, there is an exception: once a recharging visit has been assigned, no additional customers can be inserted. In this case, the recharging visit will be removed since recharging is unnecessary.

Regret insertion was described by Ropke and Pisinger ( 23 ) and Goeke and Schneider ( 3 ), and aims to estimate the future effect of an insertion operation. The idea is to find the insertion position that maximizes the difference between the best insertion position and the kth best insertion position. Let $re g_{i, k}$ represents the regret value, which can be calculated by $re g_{i, k} = Δ f (i, po s_{i, 1}) - Δ f (i, po s_{i, k})$ , where $Δ f (i, po s_{i, 1})$ indicates the cost improvement with the best insertion and $Δ f (i, po s_{i, k})$ denotes the cost improvement generated by the kth best insertion. In this paper, we use Regret-2 insertion method.

ALNS Improvement

The ALNS algorithm iteratively uses the removal and repair operators described above to construct new solution $S^{c'}$ from the input solution $S^{c}$ . Let $Π^{-} = {ζ_{1}^{-}, ζ_{2}^{-}, \dots, ζ_{ND}^{-}}$ denote a set of removal operators and $Π^{+} = {ζ_{1}^{+}, ζ_{2}^{+}, \dots, ζ_{NR}^{+}}$ represent the repair operators. The number of removal and repair operators is denoted by $ND$ and $NR$ , respectively. We define two weight vectors, $ω^{-} = [ω_{1}^{-}, ω_{2}^{-}, \dots, ω_{ND}^{-}]$ and $ω^{+} = [ω_{1}^{+}, ω_{2}^{+}, \dots, ω_{NR}^{+}]$ , to store the weight of a set of destroy and repair operators, consecutively. In the first iteration, the operator is randomly selected, and the weight of each operator is initialized to 1. Then, during each iteration, the operator can be selected following the roulette wheel principle by calculating their probability $\Pr (selecti) = ω_{i} / (\sum_{j = 1}^{| Γ |} ω_{j})$ . The termination criterion is when the ALNS reaches the maximum iteration $η$ .

In our ALNS framework, a simulated annealing (SA) heuristic is used to accept or reject the new solution $S^{c'}$ . The SA algorithm can diversify the solution by accepting a worse solution $S^{c'}$ with probability $e^{- (f (S^{c'}) - f (S^{c})) / T}$ , where $f (\cdot)$ is the cost function and $T$ is the current temperature of a SA heuristic. We predefine an initial temperature $T_{init}$ , which can be decreased at every iteration by $T = δ T_{init}$ , where the deterioration rate is $δ \in (0, 1)$ .

An adaptive mechanism is used to update the weight of the removal and repair operators with respect to their performance. In each iteration, there are four possible outcomes of the new solution $S^{c'}$ : (1) the new best solution is found, (2) an improved solution is found but it is worse than the global best solution $S^{B}$ , (3) a worse solution is accepted by the SA algorithm, and (4) a worse solution is rejected. We set a score vector $ψ = [φ_{1}, φ_{2}, φ_{3}, φ_{4}]$ to evaluate each outcome. Therefore, the operator in each iteration can be updated by the function $ω_{i} = λ ω_{i} + (1 - λ) ψ$ , where $λ \in (0, 1)$ is a decay variable to control the sensitivity of the weight vector.

Numerical Studies

To evaluate the proposed BET dispatching strategy in the real-world scenario, this section presents numerical tests using real data from a full-service supply chain company. The section is structured as follows. The Experiment Design and Parameter Setting section presents the characteristics of the real-world data and the parameter settings used in our study. In the Experiments on Standard VRPB Instances section, we assess the solution quality of the proposed ALNS algorithm by testing it on the standard VRPB benchmark dataset ( 21 ) and comparing the results with the BKSs in the literature. The Bi-Objective Model Results Analysis section analyzes the results of the bi-objective BET dispatching problem.

The mathematical models described in our study are programmed in Python 3.9 language. The experiments of the bi-objective BET dispatching problem are conducted on an online server with 32 GB RAM. The test performed on the benchmark instances is conducted on a desktop computer with an Intel Core i7 CPU 3.6 GHz processor and 16 GB RAM. The data and detailed routes are open access via GitHub (https://github.com/CurtisPeng123/Results-for-the-standard-VRPB-dataset-GJ89-).

Experiment Design and Parameter Setting

The experimental data is obtained from a logistics company that operates in Riverside and San Bernardino Counties, California. It contains one-day historical itineraries of a heavy-duty diesel truck fleet, including customer IDs, locations, service types (delivery or pickup), required demands, service times, and required time windows. Three BET dispatching instances are sampled from the historical data with different customer sizes to assess the performance of the proposed dispatching approach. In each instance, five customers are randomly selected where a charging station is equipped in their parking lot. A BET can be recharged immediately when arriving at the charging stations. Table 2 summarizes the characteristics of the generated instances.

Table 2.

Summary of Dataset Characteristics

Instance	No. of customers	No. of linehauls	No. of backhauls	CSs
BETVRPB1	47	33	14	5
BETVRPB2	58	26	32	5
BETVRPB3	71	39	32	5

Note: BET = battery electric truck; CS = charging station.

Based on the customer’s location information, the Direction Service Application Programming Interface (DSAPI) provided by OpenRouteService ( 28 ) is used to generate geographical travel distance and travel time matrices for the truck routes. Those matrices consider the urban transport network, speed limitation, and restricted zones for the heavy-duty trucks.

In the numerical study, we use the properties and coefficients of a Class 8 BET model that is commercially available in the current U.S. market ( 29 ). To safely use the battery and extend its life, this study assumes the usable battery capacity of the BET to be 300 kWh, which is 80% of its nominal value (i.e., 375 kWh) as given in VNR Electric Specifications ( 29 ). The accessory power of the BET is set to 5.6 kWh, as described by Wang et al. ( 26 ). For the energy cost, the recharging cost is set to 0.5 dollars per kWh at high peak times ( 30 ) using 250 kW DC fast chargers. Table 3 summarizes the problem parameter settings.

Table 3.

Summary of the Problem Parameters

Notation	Description	Value
Vehicle properties
A	Frontal surface area of a BET $(m^{2}$ )	10
C	Maximum BET cargo capacity (lb) ( 29 )	37,000
Q	Maximum BET usable battery capacity (kWh)	300
$ef f_{m}$	Motor efficiency ( 5 )	0.7
$ef f_{d}$	Discharging efficiency ( 31 )	0.91
$c_{r}$	Rolling resistance coefficient ( 26 )	0.008
$c_{d}$	Coefficient of rolling drag ( 15 )	0.7
$w$	Vehicle curb weight (lb)	8,000
$g$	Gravitational constant $(m / s^{2})$	9.81
$ρ_{a}$	Air density $(km / m^{3})$	1.2041
$θ$	Road angle	$0^{°}$
$a$	Acceleration $(m / s^{2})$	0
$ν$	Vehicle speed (mph)	20
$P_{acc}$	Accessory power (kW) ( 26 )	5.6
Problem variables
$s$	Loading/unloading time (hours)	(0, 2]
$[T_{O}, T_{D}]$	Working hours	[8 a.m., 4 p.m.]
$r$	Recharging rate (kWh/min)	3.96
$C^{E}$	Recharging cost (USD per kWh) ( 30 )	0.5
$C^{B}$	Battery replacement cost (USD per kilometer)	0.1989
$C^{T}$	Labor cost (USD per hour) ( 32 )	62

Note: BET = battery electric truck.

We used the instance BETVRPB1 with 47 customers to find appropriate parameter values. The first objective function is used to tune the parameters. Similar to the parameter tunning process in Ropke and Pisinger ( 33 ), a preliminary analysis was conducted to initialize the parameters. We predefine a set of candidate parameter values in Table 4 that have a stronger influence on the performance of the ALNS framework. Next, we vary one parameter value while holding the rest the same, and then run the algorithm 10 times. A preferred parameter value is defined by observing the minimum cost. Therefore, the bold values in Table 4 are the fine-tuned parameters used in the experiment. The average deviation (in percentage) between the results for the tested settings for each parameter and the best results we obtained is reported as $Δ_{d}$ in the table.

Table 4.

Summary of Parameters in the Experiment

Variable	Value
Score vector $ψ = [φ_{1}, φ_{2}, φ_{3}, φ_{4}]$	[15, 9, 8, 5]	[18, 10, 4, 3]	[15, 9, 4, 3]
$Δ_{d}$ (%)	0.86	1.00	0.95
Decay parameter $λ$	0.8	0.83	0.85
$Δ_{d}$ (%)	0.79	0.92	0.87
Destroy rate $ϵ$	35%	38%	40%
$Δ_{d}$ (%)	0.97	0.77	0.81

Note: Bold values represent the final parameter setting.

The complete parameter tuning leads to the parameter vector $(ϕ_{1}, ϕ_{2}, ϕ_{3}, φ_{1}, φ_{2}, φ_{3}, φ_{4}, λ, ϵ, T_{init}, δ)$ = $(0.5, 0.25, 0.25, 15, 9, 8, 5, 0.8, 0.38, 20, 0.9998)$ , which is used for all of the following experiments. To balance the solution quality and computation time of the developed ALNS framework, we set the maximum iteration $η = 2000$ .

Experiments on Standard VRPB Instances

To assess the performance of our BET dispatching strategy with respect to the solution quality and solution time, we implement the proposed ALNS framework on the standard VRPB instance set of Goetschalckx and Jacobs-Blecha ( 21 ) (GJ89). The GJ89 instance set contains a total of 14 groups that include 62 problem instances with customer size ranging from 25 to 150. It has been used to evaluate the performance of algorithms for solving standard VRPB by Toth and Vigo ( 22 ), Ropke and Pisinger ( 23 ), and Brandão ( 24 ).

Using the parameter settings in Table 4, the ALNS framework aims to minimize the total travel distance objective in the standard VRPB instances. We use the double precision method ( 23 ) to compute the Euclidian distance. The results are rounded to the nearest integer value. Table 5 summarizes the results for the standard VRPB instances with 14 groups. Columns L and B represent the number of linehaul and backhaul customers, respectively. The average results demonstrate that our dispatching strategy generally performs well for the problem instances with fewer than 90 customers, where the average deviation is less than 1% compared to the BKS cost.

Table 5.

Average Comparison of the Proposed Adaptive Large Neighborhood Search Framework on the Standard Vehicle Routing Problem with Backhauls

Instances group	L	B	Avg. BKS cost	Avg. best cost	Dev (%)	Time (s)
A	20	5	182,301	183,589	0.71	5
B	20	10	202,167	202,167	0.00	8
C	20	10	214,795	215,072	0.13	18
D	30	8	271,138	272,027	0.33	17
E	30	15	219,267	219,993	0.33	26
F	30	30	250,842	252,151	0.52	51
G	45	12	241,494	242,878	0.57	52
H	45	23	252,537	253,648	0.44	86
I	45	45	310,382	313,001	0.84	158
J	75	19	305,294	309,841	1.49	220
K	75	38	367,711	376,878	2.49	293
L	75	75	398,801	418,237	4.87	629
M	100	25	379,836	389,506	2.55	441
N	100	50	392,088	408,146	4.10	646

Note: BKS = best-known solution; Avg. = average; Dev = deviation.

In the Appendix, we present detailed results obtained by our ALNS algorithm and compare them with the BKS reported by Koç and Laporte ( 34 ) as well as the solutions obtained by other metaheuristic algorithms in the literature. The abbreviations of the papers that we use for comparison are as follows: RP06 for Ropke and Pisinger ( 23 ) and B16 for Brandão ( 24 ). Our proposed ALNS algorithm can obtain the BKS in 16 of the 62 instances. The results indicate that our proposed ALNS algorithm performs well within a moderate computational time.

Bi-Objective Model Results Analysis

Real-world truck dispatching data is used to validate the proposed bi-objective model. The bi-objective model is solved by the proposed BET dispatching strategy to gain insight into the relative efficient frontier. As discussed in the second section, the first objective $Z_{1}$ indicates the total BET energy cost (in USD), the second objective $Z_{2}$ denotes the labor cost (in USD), which is linearly related to the total travel time, and $Z_{3}$ is the weighted-sum function to find the trade-off between those two objective values. For the weight factor $w_{a}$ of the total BET energy cost, it is set to 0 in the first iteration and increases by 0.1 when the ALNS framework terminates. The maximum value of $w_{a}$ is set to 1. Therefore, we can obtain 11 results and compare each result to find the non-dominated solutions, that is, Pareto solutions. To ensure the solution quality, the ALNS metaheuristic algorithm is restarted 10 times for each iteration and the best results are selected. Table 6 shows the computational results of the bi-objective model for the instances. The columns E(S), T(S), and D(S) represent the BET energy consumption (in kWh), total travel time (in minutes), and total travel distance (in miles) of solution S, respectively. The column Time shows the CPU computational time.

Table 6.

Computational Results of the Real-World Problem Instances

$w_{a}$	$Z_{3} (S)$	$Z_{1} (S)$	$Z_{2} (S)$	$E (S)$	$T (S)$	$D (S)$	Time (s)
BETVRPB1
0.0	652	376	652	501	631	392	712
0.1	624	376	652	501	631	392	726
0.2	590	368	645	497	624	375	756
0.3	562	365	646	488	625	381	843
0.4	539	369	653	493	632	386	768
0.5	506	364	647	485	626	391	823
0.6	482	368	654	491	633	384	828
0.7	452	361	665	479	644	382	857
0.8	422	361	665	479	644	382	723
0.9	392	361	665	479	644	382	780
1.0	361	361	665	479	644	382	831
BETVRPB2
0.0	626	345	626	468	606	350	1657
0.1	600	345	628	468	608	350	1455
0.2	574	343	631	457	611	359	1346
0.3	545	343	631	457	611	359	1325
0.4	517	343	633	456	613	359	1722
0.5	487	343	631	457	611	359	1664
0.6	458	339	637	458	617	347	1662
0.7	427	339	632	458	611	345	1327
0.8	398	337	642	454	622	346	1351
0.9	368	337	644	456	623	345	1614
1.0	337	337	643	454	623	345	1668
BETVRPB3
0.0	720	415	720	548	697	443	2004
0.1	690	414	720	545	697	443	1810
0.2	666	417	728	549	704	449	1682
0.3	628	414	720	545	697	443	1933
0.4	599	415	722	548	698	443	2228
0.5	568	414	722	546	699	443	1814
0.6	536	413	721	545	698	442	1632
0.7	505	413	722	544	698	442	1961
0.8	475	412	726	543	703	441	2152
0.9	446	413	737	543	713	445	2716
1.0	407	407	733	537	709	435	1744

Note: BET = battery electric truck.

As demonstrated in Table 6, the proposed BET dispatching strategy can find four Pareto solutions for each problem instance, and the efficient frontier shows the possible best trade-off between the labor cost and the total energy cost for the BET fleet. The decision-makers can choose a dispatching strategy based on one of these solutions. Taking the instance BETVRPB1 as an example, Figure 3a shows the Pareto solutions where the total travel time cost ranges from $645 to $665 USD, while the total BET energy cost ranges from $361 to $368 USD. Figure 3b illustrates how the total travel time changes under the obtained solutions. Comparing between solutions A and B, the BET fleet can save 20 min of travel time if the fleet owner spends $3 USD more on the BET energy cost.

Figure 3.

(a) The Pareto frontier of instance BETVRPB1. (b) Total battery electric truck (BET) energy cost (USD) versus total travel time for the Pareto solutions of instance BETVRPB1.

Conclusion and Future Work

This paper presents a bi-objective BET dispatching problem encompassing backhauls and time windows within a MOO framework, aimed at devising an efficient dispatching strategy for urban freight transportation. By accounting for both environmental and economic factors, the proposed model offers a comprehensive approach to address the complexities of BET fleet operations. Striking the right balance between the multiple objectives is vital to create an effective and harmonious BET dispatching strategy that achieves both environmental and economic goals. Our ALNS-based metaheuristic algorithm, integrated with a MOO approach, effectively finds an efficient set of optimal dispatching strategies for fleet operators.

As avenues for further research, this study opens possibilities to expand the proposed model by incorporating additional constraints related to BET fleets, such as charging station density or charging power. By considering these factors, future studies can refine the dispatching strategy further and foster sustainable practices in urban logistics. This research contributes valuable insights into optimizing BET fleet operations and lays the groundwork for ongoing investigations in advancing sustainable transportation solutions.

Supplemental Material

sj-docx-1-trr-10.1177_03611981241246270 – Supplemental material for Bi-Objective Battery Electric Truck Dispatching Problem with Backhauls and Time Windows

Supplemental material, sj-docx-1-trr-10.1177_03611981241246270 for Bi-Objective Battery Electric Truck Dispatching Problem with Backhauls and Time Windows by Dongbo Peng, Guoyuan Wu and Kanok Boriboonsomsin in Transportation Research Record

Footnotes

Acknowledgements

The authors are thankful to Mr. Troy Musgrave of Dependable Highway Express for sharing sample fleet operations data for use in this study.

Author Contributions

The authors confirm contribution to the paper as follows: study conception and design: D. Peng, G. Wu, K. Boriboonsomsin; data collection: D. Peng; analysis and interpretation of results: D. Peng, G. Wu, K. Boriboonsomsin; draft manuscript preparation: D. Peng, G. Wu, K. Boriboonsomsin. 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: This study was funded by a grant from the National Center for Sustainable Transportation (NCST), supported by the U.S. Department of Transportation’s University Transportation Centers Program.

ORCID iDs

Dongbo Peng

Guoyuan Wu

Kanok Boriboonsomsin

Supplemental Material

Supplemental material for this article is available online.

The contents of this paper reflect the views of the authors who are responsible for the facts and the accuracy of the information presented here. These contents are disseminated in the interest of information exchange and do not necessarily reflect the official views or policies of the U.S. Government. The U.S. Government assumes no liability for the contents or use thereof.

References

US Department of Transportation. Climate Action. https://www.transportation.gov/priorities/climate-and-sustainability/climate-action#The%20Department%20of%20Transportation%20Is%20Taking%20Action%20on%20Climate. Accessed July 24, 2023.

European Environment Agency. Greenhouse Gas Emissions from Transport in Europe. https://www.eea.europa.eu/ims/greenhouse-gas-emissions-from-transport. Accessed May 23, 2023.

Goeke

Schneider

Routing a Mixed Fleet of Electric and Conventional Vehicles. European Journal of Operational Research, Vol. 245, No. 1, 2015, pp. 81–99.

Zhang

Gajpal

Appadoo

S. S.

Abdulkader

M. M. S.

Electric Vehicle Routing Problem with Recharging Stations for Minimizing Energy Consumption. International Journal of Production Economics, Vol. 203, 2018, pp. 404–413. https://doi.org/10.1016/j.ijpe.2018.07.016.

Lin

Zhou

Wolfson

Electric Vehicle Routing Problem. Transportation Research Procedia, Vol. 12, 2016, pp. 508–521.

Felipe

Á.

Ortuño

M. T.

Righini

Tirado

A Heuristic Approach for the Green Vehicle Routing Problem with Multiple Technologies and Partial Recharges. Transportation Research Part E: Logistics and Transportation Review, Vol. 71, 2014, pp. 111–128.

Schneider

Stenger

Goeke

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

Macrina

Laporte

Guerriero

Pugliese

L. D. P.

An Energy-Efficient Green-Vehicle Routing Problem with Mixed Vehicle Fleet, Partial Battery Recharging and Time Windows. European Journal of Operational Research, Vol. 276, No. 3, 2019, pp. 971–982.

Tanvir

Un-Noor

Boriboonsomsin

Gao

Feasibility of Operating a Heavy-Duty Battery Electric Truck Fleet for Drayage Applications. Transportation Research Record: Journal of the Transportation Research Board, 2021. 2675: 258–268.

10.

Peng

Zhao

Boriboonsomsin

Bi-Level Fleet Dispatching Strategy for Battery-Electric Trucks: A Real-World Case Study. Sustainability, Vol. 15, No. 2, 2023, p. 925. https://doi.org/10.3390/su15020925.

11.

Zhao

Boriboonsomsin

Kailas

Vehicle Dispatching and Scheduling Algorithms for Battery Electric Heavy-Duty Truck Fleets Considering En-Route Opportunity Charging. Proc., IEEE Conference on Technologies for Sustainability (SusTech), Irvine, CA, April 22–24, 2021, IEEE, New York, pp. 1–8. https://doi.org/10.1109/SusTech51236.2021.9467476.

12.

Garrido

Hidalgo

Barth

Boriboonsomsin

En-Route Opportunity Charging for Heavy-Duty Battery Electric Trucks in Drayage Operations: Case Study at the Southern California Ports. Proc., IEEE Vehicle Power and Propulsion Conference (VPPC), Merced, CA, November 1–4, 2022, IEEE, New York, pp. 1–6. https://doi.org/10.1109/VPPC55846.2022.10003273.

13.

Hulagu

Celikoglu

H. B.

A Multiple Objective Formulation of An Electric Vehicle Routing Problem For Shuttle Bus Fleet at A University Campus. Proc., 6th International Conference on Models and Technologies for Intelligent Transportation Systems (MT-ITS), Cracow, Poland, June 5–7, 2019, IEEE, New York, pp. 1–5. https://doi.org/10.1109/MTITS.2019.8883344.

14.

Wen

Linde

Ropke

Mirchandani

Larsen

An Adaptive Large Neighborhood Search Heuristic for the Electric Vehicle Scheduling Problem. Computers & Operations Research, Vol. 76, 2016, pp. 73–83. https://doi.org/10.1016/j.cor.2016.06.013.

15.

Demir

Bektaş

Laporte

An Adaptive Large Neighborhood Search Heuristic for the Pollution-Routing Problem. European Journal of Operational Research, Vol. 223, No. 2, 2012, pp. 346–359.

16.

Muñoz-Villamizar

Montoya-Torres

J. R.

Faulin

Impact of the Use of Electric Vehicles in Collaborative Urban Transport Networks: A Case Study. Transportation Research Part D: Transport and Environment, Vol. 50, 2017, pp. 40–54. https://doi.org/10.1016/j.trd.2016.10.018.

17.

Amiri

Amin

S. H.

Zolfagharinia

A Bi-Objective Green Vehicle Routing Problem with a Mixed Fleet of Conventional and Electric Trucks: Considering Charging Power and Density of Stations. Expert Systems with Applications, Vol. 213, 2023, p. 119228. https://doi.org/10.1016/j.eswa.2022.119228.

18.

Keskin

Çatay

Partial Recharge Strategies for the Electric Vehicle Routing Problem with Time Windows. Transportation Research Part C: Emerging Technologies, Vol. 65, 2016, pp. 111–127.

19.

Lin

Bard

J. F.

Jarrah

A. I.

Zhang

Novoa

L. J.

Route Design for Last-In, First-Out Deliveries with Backhauling. Transportation Research Part C: Emerging Technologies, Vol. 76, 2017, pp. 90–117.

20.

Pradenas

Oportus

Parada

Mitigation of Greenhouse Gas Emissions in Vehicle Routing Problems with Backhauling. Expert Systems with Applications, Vol. 40, No. 8, 2013, pp. 2985–2991.

21.

Goetschalckx

Jacobs-Blecha

The Vehicle Routing Problem with Backhauls. European Journal of Operational Research, Vol. 42, No. 1, 1989, pp. 39–51. https://doi.org/10.1016/0377-2217(89)90057-X.

22.

Toth

Vigo

An Exact Algorithm for the Vehicle Routing Problem with Backhauls. Transportation Science, Vol. 31, No. 4, 1997, pp. 372–385. https://doi.org/10.1287/trsc.31.4.372.

23.

Ropke

Pisinger

A Unified Heuristic for a Large Class of Vehicle Routing Problems with Backhauls. European Journal of Operational Research, Vol. 171, No. 3, 2006, pp. 750–775. https://doi.org/10.1016/j.ejor.2004.09.004.

24.

Brandão

A Deterministic Iterated Local Search Algorithm for the Vehicle Routing Problem with Backhauls. Top, Vol. 24, No. 2, 2016, pp. 445–465.

25.

Belloso

Juan

A. A.

Martinez

Faulin

A Biased-Randomized Metaheuristic for the Vehicle Routing Problem with Clustered and Mixed Backhauls. Networks, Vol. 69, No. 3, 2017, pp. 241–255. https://doi.org/10.1002/net.21734.

26.

Wang

Hao

Boriboonsomsin

Barth

Developing a Mesoscopic Energy Consumption Model for Battery Electric Trucks Using Real-World Diesel Truck Driving Data. Proc., IEEE Vehicle Power and Propulsion Conference (VPPC), Merced, CA, November 1–4, 2022, IEEE, New York, pp. 1–6. https://doi.org/10.1109/VPPC55846.2022.10003335.

27.

Shaw

Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems. In Principles and Practice of Constraint Programming — CP98 ( Maher

Puget

J.-F.

, eds.), Lecture Notes in Computer Science, Springer, Berlin, Heidelberg, 1998, pp. 417–431. https://doi.org/10.1007/3-540-49481-2_30.

28.

Openrouteservice. https://openrouteservice.org/. Accessed March 15, 2022.

29.

VNR Electric Specifications. https://www.volvotrucks.us/trucks/vnr-electric/specifications/. Accessed December 16, 2022.

30.

Lambert

Tesla Hikes Supercharger Prices in California. Electrek. https://electrek.co/2022/09/28/tesla-hikes-supercharger-prices-california/. Accessed July 23, 2023.

31.

Fiori

Ahn

Rakha

H. A.

Power-Based Electric Vehicle Energy Consumption Model: Model Development and Validation. Applied Energy, Vol. 168, 2016, pp. 257–268. https://doi.org/10.1016/j.apenergy.2016.01.097.

32.

ZipRecruiter. Semi Truck Driver Salary in California: Hourly Rate (Jun 23). ZipRecruiter. https://www.ziprecruiter.com/Salaries/SEMI-Truck-Driver-Salary—in-California. Accessed July 19, 2023.

33.

Ropke

Pisinger

An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows. Transportation Science, Vol. 40, No. 4, 2006, pp. 455–472.

34.

Koç

Ç.

Laporte

Vehicle Routing with Backhauls: Review and Research Perspectives. Computers & Operations Research, Vol. 91, 2018, pp. 79–91.

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