Two-Phase Fuzzy Real-Time Approach for Fuzzy Demand Electric Vehicle Routing Problem with Soft Time Windows

Abstract

Environmental concerns have called for several measures to be taken within the logistics and transportation fields. Among these measures is the adoption of electric vehicles instead of diesel-operated vehicles for personal and commercial-delivery use. The optimized routing of electric vehicles for the commercial delivery of products is the focus of this paper. We study the effect of several practical challenges that are faced when routing electric vehicles. Electric vehicle routing faces the additional challenge of the potential need for recharging while en route, leading to more travel time, and hence cost. Therefore, in this work, we address the issue of electric vehicle routing problem, allowing for partial recharging while en route. In addition, the practical mandate of the time windows set by customers is also considered, where electric vehicle routing problems with soft time windows are studied. Real-life experience shows that the delivery of customers’ demands might be uncertain. In addition, real-time traffic conditions are usually uncertain due to congestion. Therefore, in this work, uncertainties in customers’ demands and traffic conditions are modeled and solved using fuzzy methods. The problems of fuzzy real-time, fuzzy demand, and electric vehicle routing problems with soft time windows are addressed. A mixed-integer programming mathematical model to represent the problem is developed. A novel two-phase solution approach is proposed to solve the problem. In phase I, the classical genetic algorithm (GA) is utilized to obtain an optimum/near-optimum solution for the fuzzy demand electric vehicle routing problem with soft time windows (FD-EVRPSTW). In phase II, a novel fuzzy real-time-adaptive optimizer (FRTAO) is developed to overcome the challenges of recharging and real-time traffic conditions facing FD-EVRPSTW. The proposed solution approach is tested on several modified benchmark instances, and the results show the significance of recharging and congestion challenges for routing costs. In addition, the results show the efficiency of the proposed two-phase approach in overcoming the challenges and reducing the total costs.

1. Introduction

The vehicle routing problem (VRP) is among the most important optimization problems within the field of transportation logistics. The problem was introduced in 1959 [1]. The vehicle routing problem is defined by having a number of available vehicles that start their trips from a central depot loaded with products. The vehicles visit a number of customers to deliver the required products in a certain order that minimizes the total travel cost, and then the vehicles end their trips at the same central depot. Since the first time the VRP was introduced in 1959, it has attracted the attention of numerous researchers and practitioners within the field. Several variants have extended the original problem to reflect real-life situations. For example, the capacitated VRP considers utilizing vehicles with limited capacities [2]. Another variant of the problem considers picking up products as well as delivering them. The VRP with backhauls (VRPB) is one example of deliveries and pickups conducted using vehicles. The VRPB is designed such that all deliveries are performed first, and then pickups take place, as given in [3,4]. Vehicles with different capacities are another practical variant of the VRP, known as the heterogeneous VRP [5]. Usually, customers prefer to be visited within a certain time frame, known as a time window, resulting in the well-studied problem known as the VRP with time windows (VRPTW) [6]. To facilitate the VRPTW, a technique that allows vehicles to arrive outside the time window with a penalty added to the total cost has been developed by several researchers, known as the VRP with soft time windows (VRPSTW), as explained, for example, in [7]. These VRP variants require planning routes for vehicles regardless of real-time traffic conditions. Real-time aspects are significant when practical planning and cost calculations are essential. Therefore, several research papers consider real-time planning for the VRP and its several variants. Examples include that of [8], in which the VRPTW with real-time and time-dependent travel times in addition to real-time demands is formulated and the problem is solved using a heuristic approach. Also, in [9], the real-time VRPTW was solved using a genetic algorithm. In 2021, Gmira et al. [10] solved the real-time VRP with time-dependent travel times on Montreal City’s road network.

Environmental concerns and climate change issues caused the world to re-think diesel-operated vehicles in a more environmentally friendly approach. Among the most significant environmental improvements in this regard is the shift towards electric vehicles to reduce the harmful effects of diesel-operated delivery vehicles. This shift raised several challenges that need to be considered when designing operation strategies for electric vehicles. Among these considerations is the logistics of operating electric vehicles, and naturally the routing of electric delivery trucks with their different sizes, resulting in the electric vehicle routing problem (EVRP). EVRPs face an additional challenge over diesel-operated VRPs, namely the battery-recharging challenge. EVRPs may require the recharging of their batteries while en route during customers’ visits for deliveries and/or pickups. The battery-recharging time may consume large amounts of time, causing lots of delays compared to the re-fueling time of diesel-operated vehicles. Moreover, when the EVRP is restricted by customers’ time windows, the problem of delays adds an additional challenge. Therefore, studying the EVRP and its variants in light of battery-recharging times has acquired a lot of attention recently. Schneider et al.’s 2014 [11] study of the EVRP with time windows considered visits to recharging stations. The EVRP with time windows and recharging has also been studied in [12,13]. Since recharging times may cause significant delays for the EVRP while en route, the flexibility of soft time windows is important to consider. Therefore, several research works solve the EVRP with soft time windows; examples include [14,15,16,17]. Other important variants of the EVRP have been also studied. For example, the heterogeneous EVRP is solved in [18], and the optimization of the heterogeneous EVRP with simultaneous pickups and deliveries is solved in [19]. Real-time traffic conditions are an essential factor in travel-cost calculations, especially for EVRPs, where battery depletion and long recharging times are significant. Nevertheless, studying the real-time effect of the EVRP and its associated travel costs is limited to a few research papers, including that of [17]. Other papers implicitly consider congestion delays in travel times due to traffic conditions but without referring to real time explicitly, for example, [20,21]. Küçükoğlu et al. [22] provide a literature review on the EVRP and its variants.

VRPs and EVRPs often experience uncertainties in real-life applications. Examples of such uncertainties include uncertain customer demands [23,24], uncertain travel times [25], uncertain battery energy consumption for electric vehicles [26] and many others. Fuzzy-based models are among the most efficient techniques for representing and solving problems with uncertainties. Within the field of transportation logistics, especially for VRPs and EVRPs, fuzzy-based techniques have been applied intensely, and numerous successful implementations have been reported. Uncertain demands were modeled and solved using fuzzy techniques, for example, as given in [27,28,29,30,31]. The efficacy of solving the VRP and some of its variants using fuzzy clustering has been proven, as shown in [32,33,34]. Although remarkable success has been reported in studying the VRP with fuzzy theory, the study of the EVRP with fuzzy theory has been limited. A few research papers have considered this topic. For example, Zhang et al. [20] solve the EVRP under fuzzy service times, fuzzy consumption of the battery’s energy, and fuzzy travel times, while Syafrizal and Sugiharti [35] solve the EVRP with fuzzy time windows.

The EVRP is an NP-hard problem, as mentioned in [36]. Therefore, heuristics and metaheuristics were utilized to solve the practical sizes of the problem and several of its variants. For example, Hao [15] used an adaptive large-scale neighborhood search algorithm to solve the EVRP with soft time windows and weight-related discharging. Syafrizal and Sugiharti [35] used a genetic algorithm and tabu search to solve the EVRP with fuzzy time windows. The genetic algorithm reported promising results in solving the EVRPTW, as shown in [37]. Mavrovouniotis et al. [38] used ant colony optimization to successfully solve the EVRP.

In this paper, the EVRP is studied with practical variants to represent real-life challenges of the problem. The time window constraint is addressed in a flexible manner through soft time windows. Due to the uncertain nature of customers’ demands, fuzzy demands of customers are considered. Traffic conditions are accounted for through fuzzy real-time EVRP. Due to the significant impact of charging times on travel costs, partial recharging is permitted and is related to the real-time factor that is addressed in the current research. A mixed-integer programming model is developed to represent the problem at hand. The problem is solved using a novel two-phase solution approach. The proposed approach utilizes a genetic algorithm in phase I, which aims to reach an optimum/near optimum solution in a reasonable time for practical-sized problems, considering a static problem that does not examine real-time traffic conditions. In phase II, a novel fuzzy real-time adaptive optimizer (FRTAO) is developed to overcome the challenges that are faced by electric vehicles due to the necessary recharging while en route, and fuzzy real-time traffic conditions that are represented as congestion. FRTAO aims to make use of traffic delays and permit changing the original vehicles’ routes to go to the nearest charging station. The objective is to re-optimize the solution obtained from phase I by utilizing the real-time traffic delays in partial/full battery recharging. The decision depends on the battery’s state of charge (SoC), the amount of expected delay, and the proximity of the charging station in relation to the soft time windows and travel times of the remaining customers who are assigned to the route.

Accordingly, the contribution of this paper is summarized as follows:

• For the first time, the EVRP is studied considering soft time windows (EVRPSTW), fuzzy demands (FD-EVRPSTW), and partial recharging while en route. The soft time windows are reflected by allowing the vehicles to visit customers outside of their time windows with a cost that is added to the total travel cost of the vehicles. Due to the uncertain nature of the customers’ demands, these demands are represented with fuzzy variables to account for their uncertainties. Due to the limited driving range of electric vehicles resulting from battery depletion and the large amount of time needed for recharging, partial recharging is allowed.
• Traffic conditions that may arise, especially due to congestion, are taken into consideration when planning EVRP routes. Hence, the fuzzy real-time electric vehicle routing problem with soft time windows and fuzzy demand (RT-FD-EVRPSTW) is studied for the first time. Real-time traffic conditions, represented by congestion, are modeled using a novel fuzzy-based model.
• A mixed-integer programming model is developed to represent the problem.
• A novel fuzzy real-time adaptive optimizer (FRTAO) is developed based on the proposed real-time traffic condition fuzzy-based model. FRTAO aims to overcome the challenges faced by electric vehicles due to the necessary recharging and real-time traffic conditions.
• A two-phase approach is developed to solve the above-mentioned problem. In phase I, a genetic algorithm is used for the first time to solve the FD-EVRPSTW with partial recharging. In phase II, FRTAO is utilized to improve the output of the GA that was obtained from phase I.

The rest of this paper is organized as follows: Section 2 explains the problem definition and the proposed mathematical model representing the problem, Section 3 shows the details of the two-phase solution methodology used to solve the problem, Section 4 gives details of the experimental and comparative analysis and the results and discussion, and finally, Section 5 concludes the paper.

2. Problem Definition and Mathematical Model

2.1. Problem Definition

In the current research, EVRP is optimized considering soft time windows, fuzzy demands, partial recharging, and fuzzy real-time traffic conditions. A connected network is considered, where the customers, the central depot, and the electric charging stations are present at the nodes of the network. A fleet of homogeneous electric vehicles is available at the central depot which is filled with products that need to be delivered to spatially dispersed customers. The vehicles have a limited capacity for the amount of products that they can carry to deliver to the customers. The vehicles start their trips at the central depot with their batteries fully charged, carrying the products to be delivered to their assigned customers. The vehicles visit the customers to deliver the products in a scheduled order that minimizes the total cost. After visiting their assigned customers, the vehicles end their trips back at the central depot. Due to the natural restriction set by customers on the times allowed for visits, the EVRP with soft time windows (EVRPSTW) is considered. In this paper, the EVRPSTW is modeled and solved. A schedule for the vehicles to visit the customers is designed such that visits to the customers are performed as much as possible within the time frame, or time windows, set by each customer. However, the vehicles are permitted to visit the customers outside the time windows at a cost that is added as a penalty to the total travel cost. This way, the flexibility of visiting times is incorporated within the model, and, at the same time, the level of violations of the time window constraints is kept as low as possible. Real-life practices show that customers’ demands are not always deterministic. To incorporate uncertainty in the amounts of customers’ demands, this research adopts the fuzzy variable method as it has proven efficient in several applications, as shown in Section 1.

Electric vehicles may require recharging while still more customers need to be visited and/or to return back to the central depot. In such cases, recharging is considered while the vehicles are still en route. Such vehicles are hence allowed to visit recharging stations located at nodes within the proximity of the vehicles while en route. Full recharging of electric vehicles’ batteries is time-consuming, and therefore, partial recharging is adopted to make sure that the vehicles have enough batteries’ state of charge (SoC) to complete their routes and return to the central depot. Real-time traffic conditions have a significant effect on the total travel times and, therefore, are taken into consideration in the current work. Delays due to traffic conditions have a two-fold effect, namely the direct increase in travel time and the late arrival to customers, which may result in arrival after the time windows that are set by the customers, resulting in penalties that are added to the total cost encountered. Real-time traffic conditions should not be expressed as crisp numbers due to the nature of the roads’ situations; hence, a fuzzy model is adopted to reflect the actual effect of real-time conditions on the optimized solution. The objective is to minimize the total travel cost in addition to the penalty costs due to early or late arrivals at customers.

The assumptions of the problem are as follows:

• There are enough vehicles at the central depot to serve all the customers.
• The depot has enough delivery units to satisfy all the customers’ demands.
• Any customer is visited only once with one vehicle.
• All the vehicles are fully charged when they are dispatched from the depot.
• The vehicles are identical.
• There are no time window restrictions on the central depot.

The following mathematical model is developed to represent the defined problem.

2.2. Mathematical Model

• Parameters:
  • τ: A variable holding the current time.
  • ${\mathrm{c}}_{\mathrm{i}\mathrm{j}}$: The distance between nodes i and j.
  • K: Set of vehicles, k = 1, 2, …, $\mathrm{k}$.
  • Q: Maximum capacity of a vehicle.
  • d_i: fuzzy demand of customer i.
  • ${\mathrm{t}}_{\mathrm{i}\mathrm{j}}\left(\mathsf{\tau }\right)$: Fuzzy-based estimation of travel time between nodes i and j at time τ.
  • ${\mathrm{e}}_{\mathrm{i}}$: Earliest allowable time to start service at customer node i.
  • ${\mathrm{l}}_{\mathrm{i}}$: Latest allowable time to start service at customer node i.
  • [${\mathrm{e}}_{\mathrm{i}}$, ${\mathrm{l}}_{\mathrm{i}}$]: Time window of customer i.
  • ${\mathrm{s}}_{\mathrm{i}}$: Service time at customer i;${\mathrm{s}}_0$ = 0, where 0 is the central depot.
  • N: Set of customers: 1, 2, …, n.
  • O: Depot.
  • $\mathrm{A}$: Set of artificial intermediate nodes for vehicles being en route at time τ.
  • $\mathrm{C}\mathrm{S}$: Set of charging stations.
  • NOCS = N $\cup \mathrm{O}\cup \mathrm{C}\mathrm{S}$.
  • ${\mathrm{P}\mathrm{E}\_\mathrm{C}}_{\mathrm{i}}$: Early penalty cost for customer i, if vehicle arrives before ${\mathrm{e}}_{\mathrm{i}}$ i $\in \mathrm{N}$, and ${\mathrm{P}\mathrm{E}\_\mathrm{C}}_0$ = 0 where 0 is a central depot.
  • ${\mathrm{P}\mathrm{L}\_\mathrm{C}}_{\mathrm{i}}$: Late penalty cost for customer i, if vehicle arrives after ${\mathrm{l}}_{\mathrm{i}}$ i $\in \mathrm{N}$, and ${\mathrm{P}\mathrm{L}\_\mathrm{C}}_0$ = 0 where 0 is a central depot.
  • W: Battery capacity.
  • ${\mathrm{A}\mathrm{S}\mathrm{o}\mathrm{C}}_{\mathrm{i}}$: The remaining, i.e., actual, battery state of charge (SoC) on arrival at node i.
  • ${\mathrm{D}\mathrm{S}\mathrm{o}\mathrm{C}}_{\mathrm{i}}$: SoC on departure from node i.
  • h: Constant charge consumption rate.
  • g: Constant recharging rate.
  • M: Large positive number.

In the proposed mathematical model, a customer’s fuzzy demand is defined using triangular fuzzy numbers, such that ${\mathrm{d}}_{\mathrm{i}}=\left({\mathrm{d}}_{\mathrm{i}1},{\mathrm{d}}_{\mathrm{i}2},{\mathrm{d}}_{\mathrm{i}3}\right)$, where ${\mathrm{d}}_{\mathrm{i}2}$ is the deterministic customer demand. The boundaries $\left({\mathrm{d}}_{\mathrm{i}1} \mathrm{a}\mathrm{n}\mathrm{d} {\mathrm{d}}_{\mathrm{i}3}\right)$ are calculated as follows: ${\mathrm{d}}_{\mathrm{i}1}={\mathrm{d}}_{\mathrm{i}2}-{\mathsf{\sigma }}_{\mathrm{d}}$ and ${\mathrm{d}}_{\mathrm{i}3}={\mathrm{d}}_{\mathrm{i}2}+{\mathsf{\sigma }}_{\mathrm{d}}$, where ${\mathsf{\sigma }}_{\mathrm{d}}$ is the standard deviation calculated from the deterministic customer demands’ statistical distribution. In addition, ${\mathrm{t}}_{\mathrm{i}\mathrm{j}}\left(\mathsf{\tau }\right)$ is the fuzzy-based estimation of the travel time between vertices i and j at time τ. ${\mathrm{t}}_{\mathrm{i}\mathrm{j}}\left(\mathsf{\tau }\right)$ is calculated as follows: ${\mathrm{t}}_{\mathrm{i}\mathrm{j}}\left(\mathsf{\tau }\right)=(1+\mathsf{\alpha }(\mathsf{\tau }\left)\right){\mathrm{c}}_{\mathrm{i}\mathrm{j}}$, where $\mathsf{\alpha }\left(\mathsf{\tau }\right)$ is a fuzzy-based coefficient that is calculated from the proposed real-time fuzzy-based model.

• Decision variables:
  • ${\mathrm{x}}_{\mathrm{i}\mathrm{j}\mathrm{k}}^{\mathrm{t}}=1$ if vehicle k visits node j immediately after node i at time t and 0 otherwise; $\mathrm{i},\mathrm{j}\in \mathrm{N}\mathrm{O}\mathrm{C}\mathrm{S}$.
  • ${\mathrm{P}\mathrm{E}\_\mathrm{T}}_{\mathrm{i}\mathrm{k}}$= 1 if service start time for customer i ${\mathrm{T}}_{\mathrm{i}}$ < ${\mathrm{e}}_{\mathrm{i}}$, i $\in \mathrm{N}$, and 0 otherwise.
  • ${\mathrm{P}\mathrm{L}\_\mathrm{T}}_{\mathrm{i}\mathrm{k}}$ = 1 if service start time for customer i ${\mathrm{T}}_{\mathrm{i}}$ > ${\mathrm{l}}_{\mathrm{i}}$, i $\in \mathrm{N}$, and 0 otherwise.
  • ${\mathrm{T}}_{\mathrm{i}}$: Arrival time at node i, i $\in \mathrm{N}\cup \mathrm{S}\mathrm{C}$.
  • ${\mathrm{q}}_{\mathrm{i}}:$ The recharge quantity at recharging station i, i $\in \mathrm{C}\mathrm{S}$.

$$\mathrm{M}\mathrm{i}\mathrm{n}\hspace{1em}\hspace{1em}\sum _{\mathrm{i}\in \mathrm{N}\mathrm{O}\mathrm{C}\mathrm{S}}\sum _{\mathrm{j}\in \mathrm{N}\mathrm{O}\mathrm{C}\mathrm{S}}\sum _{\mathrm{k}\in \mathrm{K}}\sum _{\mathrm{t}\ge \mathsf{\tau }}{\mathrm{t}}_{\mathrm{i}\mathrm{j}}\left(\mathsf{\tau }\right){\mathrm{x}}_{\mathrm{i}\mathrm{j}\mathrm{k}}^{\mathrm{t}}+\sum _{\mathrm{i}\in \mathrm{N}}\sum _{\mathrm{k}\in \mathrm{K}}{\mathrm{P}\mathrm{E}\_\mathrm{C}}_{\mathrm{i}}\ast {\mathrm{P}\mathrm{E}\_\mathrm{T}}_{\mathrm{i}\mathrm{k}}+\sum _{\mathrm{i}\in \mathrm{N}}\sum _{\mathrm{k}\in \mathrm{K}}{\mathrm{P}{\mathrm{L}}_{\mathrm{C}}}_{\mathrm{i}}\ast {\mathrm{P}{\mathrm{L}}_{\mathrm{T}}}_{\mathrm{i}\mathrm{k}}$$

(1)

$$\mathrm{Q}\ge \sum _{\mathrm{i}\in \mathrm{N}}\sum _{\mathrm{j}\in \mathrm{N}}\sum _{\mathrm{t}\ge \mathsf{\tau }}{{\mathrm{d}}_{\mathrm{i}\mathrm{j}}\mathrm{x}}_{\mathrm{i}\mathrm{j}\mathrm{k}}^{\mathrm{t}}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\mathrm{k}\in \mathrm{K}$$

(2)

$$\sum _{\mathrm{i}\in \mathrm{N}}\sum _{\mathrm{k}\in \mathrm{K}}\sum _{\mathrm{t}\ge \mathsf{\tau }}{\mathrm{x}}_{\mathrm{i}\mathrm{j}\mathrm{k}}^{\mathrm{t}}=1\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\mathrm{j}\in \mathrm{N}$$

(3)

$$\sum _{\mathrm{i}\in \mathrm{N}}\sum _{\mathrm{t}\ge \mathsf{\tau }}{\mathrm{x}}_{\mathrm{i}\mathrm{b}\mathrm{k}}^{\mathrm{t}}=\sum _{\mathrm{j}\in \mathrm{N}}\sum _{\mathrm{t}\ge \mathsf{\tau }}{\mathrm{x}}_{\mathrm{b}\mathrm{j}\mathrm{k}}^{\mathrm{t}}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\mathrm{b}\in \mathrm{N},\mathrm{k}\in \mathrm{K}$$

(4)

$$\sum _{\mathrm{j}\in \mathrm{N}}{\mathrm{x}}_{0\mathrm{j}\mathrm{k}}^{\mathrm{t}}=1\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\mathrm{k}\in \mathrm{K},\mathrm{t}=0$$

(5)

$$\sum _{\mathrm{i}\in \mathrm{N}}\sum _{\mathrm{t}\ge \mathsf{\tau }}{\mathrm{x}}_{\mathrm{i}0\mathrm{k}}^{\mathrm{t}}=1\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\mathrm{k}\in \mathrm{K}$$

(6)

$${\mathrm{T}}_{\mathrm{i}}+{\mathrm{t}}_{\mathrm{i}\mathrm{j}}\left(\mathsf{\tau }\right)+{\mathrm{s}}_{\mathrm{i}}-\mathrm{M}\left(1-{\mathrm{x}}_{\mathrm{i}\mathrm{j}\mathrm{k}}^{\mathrm{t}}\right)+\le {\mathrm{T}}_{\mathrm{j}},\hspace{1em}\hspace{1em}\mathrm{i}\ne \mathrm{j},\mathrm{i}\in \mathrm{N}\cup \mathrm{O}\cup \mathrm{A},\hspace{1em}\hspace{1em}\hspace{1em}\mathrm{j}\in \mathrm{N}\cup \mathrm{S}\mathrm{C},\hspace{1em}\mathrm{k}\in \mathrm{K},\mathrm{t}\ge \mathsf{\tau }$$

(7)

$${\mathrm{T}}_{\mathrm{i}}+{\mathrm{t}}_{\mathrm{i}\mathrm{j}}\left(\mathsf{\tau }\right)+\mathrm{g}{\mathrm{q}}_{\mathrm{i}}-\mathrm{M}\left(1-{\mathrm{x}}_{\mathrm{i}\mathrm{j}\mathrm{k}}^{\mathrm{t}}\right)\le {\mathrm{T}}_{\mathrm{j}},\hspace{1em}\hspace{1em}\mathrm{i}\ne \mathrm{j};\mathrm{i}\in \mathrm{C}\mathrm{S},\mathrm{j}\in \mathrm{N},\hspace{1em}\mathrm{k}\in \mathrm{K},\mathrm{t}\ge \mathsf{\tau },$$

(8)

$$\mathrm{M}\ast {\mathrm{P}\mathrm{E}\_\mathrm{T}}_{\mathrm{i}}+{\mathrm{T}}_{\mathrm{i}}\ge {\mathrm{e}}_{\mathrm{i}}$$

(9)

$$-\mathrm{M}\ast (1-{\mathrm{P}\mathrm{E}\_\mathrm{T}}_{\mathrm{i}})+{\mathrm{T}}_{\mathrm{i}}<{\mathrm{e}}_{\mathrm{i}}$$

(10)

$$-\mathrm{M}\ast {\mathrm{P}\mathrm{L}\_\mathrm{T}}_{\mathrm{i}}+{\mathrm{T}}_{\mathrm{i}}\le {\mathrm{l}}_{\mathrm{i}}$$

(11)

$$\mathrm{M}\ast (1-{\mathrm{P}\mathrm{L}\_\mathrm{T}}_{\mathrm{i}})+{\mathrm{T}}_{\mathrm{i}}>{\mathrm{l}}_{\mathrm{i}}$$

(12)

For Equations (13)–(16), $\mathrm{i}\in \mathrm{N}$.

$$0\le {\mathrm{A}\mathrm{S}\mathrm{o}\mathrm{C}}_{\mathrm{j}}\le {\mathrm{A}\mathrm{S}\mathrm{o}\mathrm{C}}_{\mathrm{i}}-\left(\mathrm{h}.{\mathrm{c}}_{\mathrm{i}\mathrm{j}}\right){\mathrm{x}}_{\mathrm{i}\mathrm{j}\mathrm{k}}^{\mathrm{t}}+\mathrm{M}\left(1-{\mathrm{x}}_{\mathrm{i}\mathrm{j}\mathrm{k}}^{\mathrm{t}}\right),\hspace{1em}\mathrm{i}\ne \mathrm{j},\hspace{1em}\mathrm{i}\in \mathrm{N}\cup \mathrm{O},\mathrm{j}\in \mathrm{N}\cup \mathrm{O}\cup \mathrm{C}\mathrm{S},\mathrm{k}\in \mathrm{K},\mathrm{t}\ge \mathsf{\tau }$$

(13)

$${\mathrm{A}\mathrm{S}\mathrm{o}\mathrm{C}}_{\mathrm{j}}\le \mathrm{W}-(\mathrm{h}.{\mathrm{c}}_{\mathrm{i}\mathrm{j}}){\mathrm{x}}_{\mathrm{i}\mathrm{j}\mathrm{k}}^{\mathrm{t}}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\mathrm{i}\ne \mathrm{j},\mathrm{i}\in \mathrm{O},\mathrm{j}\in \mathrm{N},\mathrm{k}\in \mathrm{K},\mathrm{t}\ge \mathsf{\tau }$$

(14)

$${\mathrm{A}\mathrm{S}\mathrm{o}\mathrm{C}}_{\mathrm{i}}\le {\mathrm{D}\mathrm{S}\mathrm{o}\mathrm{C}}_{\mathrm{i}}\le \mathrm{W}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\mathrm{i}\in \mathrm{O}\cup \mathrm{C}\mathrm{S}$$

(15)

$${\mathrm{D}\mathrm{S}\mathrm{o}\mathrm{C}}_{\mathrm{i}}\ge {\mathrm{A}\mathrm{S}\mathrm{o}\mathrm{C}}_{\mathrm{i}}+{\mathrm{q}}_{\mathrm{i}}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\mathrm{i}\in \mathrm{C}\mathrm{S}$$

(16)

$${\mathrm{x}}_{\mathrm{i}\mathrm{j}\mathrm{k}}^{\mathrm{t}}\in \left\{0,1\right\},\hspace{1em}\mathrm{i}\in \mathrm{N}\mathrm{O}\mathrm{C}\mathrm{S},\hspace{1em}\hspace{1em}\mathrm{j}\in \mathrm{N}\mathrm{O}\mathrm{C}\mathrm{S},\hspace{1em}\mathrm{i}\ne \mathrm{j}\mathrm{k}\in \mathrm{K},\hspace{1em}\hspace{1em}\mathrm{t}\ge \mathsf{\tau }$$

(17)

$${\mathrm{P}\mathrm{E}\_\mathrm{T}}_{\mathrm{i}\mathrm{k}}\in \left\{0,1\right\},\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}{\mathrm{P}\mathrm{L}\_\mathrm{T}}_{\mathrm{i}\mathrm{k}}\in \left\{0,1\right\},\hspace{1em}\hspace{1em}\hspace{1em}\mathrm{i}\in \mathrm{N},\hspace{1em}\hspace{1em}\hspace{1em}\mathrm{k}\in \mathrm{K}$$

(18)

$${\mathrm{q}}_{\mathrm{i}}\ge 0,\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\mathrm{i}\in \mathrm{C}\mathrm{S}$$

(19)

$${\mathrm{T}}_{\mathrm{i}}\ge 0,\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\mathrm{i}\in \mathrm{N}\cup \mathrm{C}\mathrm{S}$$

(20)

• Equation (1) is the objective function that aims to minimize the total travel cost for all the routes, including the penalties for arriving earlier or later than the time windows. Travel times are calculated as per real-time traffic conditions.
• Constraint (2) ensures that the total demand of customers who are assigned to a vehicle does not exceed the vehicle’s capacity.
• Constraint (3) ensures that each customer is visited by exactly one vehicle.
• Constraint (4) ensures that a vehicle arrives at and leaves a customer (flow conservation constraint).
• Constraints (5) and (6) ensure that each vehicle starts the trip from the depot at time 0 and ends the trip at the depot, respectively.
• Constraint (7) calculates the arrival time to a customer or a charging station from the depot or from another customer.
• Constraint (8) calculates the arrival time from a charging station (if visited) to the next visited customer.
• Constraints (9) and (10) determine the violation of an early arrival, if it exists, at customer i, i $\in N$
• Constraints (11) and (12) determine the violation of a late arrival, if it exists, at customer i, i $\in N$
• Constraint (13) ensures that the level of a battery’s charge never falls below 0 and calculates the SoC when arriving at a customer, a charging station, or the depot at the end of a trip after leaving from the depot or another customer.
• Constraint (14) calculates the SoC when arriving at the first customer after departing from the depot.
• Constraint (15) states that the vehicles depart from the depot fully charged, and the SoC of a vehicle when departing from the depot is greater than or equal to the SoC when arriving at the depot.
• Constraint (16) determines the SoC after partial/full recharging at a charging station.
• Finally, Constraints (17)–(20) define the nature of the decision variables.

3. Proposed Two-Phase Solution Approach

To solve the problem that has been defined and modeled in the previous section, a novel two-phase solution approach is developed. Phase I solves the FD-EVRPSTW, i.e., the electric VRP with fuzzy demands taking into consideration the penalties of early and late arrivals. In the proposed algorithm, the need for partial recharging of a vehicle’s battery is checked on each visit to a customer based on the state of charge (SoC) of the vehicle’s battery. In phase I, the FD-EVRPSTW problem is solved first using a genetic algorithm (GA) to solve the proposed mathematical model; then, partial recharging decisions are determined as per the best solution provided by the GA. Phase II utilizes a novel fuzzy real-time adaptive optimizer (FRTAO). The FRTAO considers the effect on the total cost resulting from the challenges of daily traffic conditions and the need for recharging batteries while en route. The fuzzy real-time adaptive optimizer makes use of traffic conditions and batteries’ SoC to decide partial/full recharging during delays due to traffic conditions in conjunction with early arrival cases. Therefore, if after partial recharging during congestion an early arrival still exists for the immediate coming customer, the vehicle will keep recharging until either the battery is fully charged, or the early arrival is eliminated and the arrival time is within the customer’s time window. Recharging during congested times has two major advantages: (1) avoiding early arrival penalties since early arrival is utilized in recharging instead of waiting at the customer’s node until the beginning of the customer’s time window, (2) avoiding delays resulting from long recharging times while en route, hence avoiding late arrivals and the penalties associated with them. The overall flow of the proposed two-phase solution approach is described briefly in the following steps:

• Phase I: Optimize FD-EVRPSTW using GA to obtain the initial best routing plan.
• Calculate the corresponding initial solution’s objective function, i.e., the total cost of FD-EVRPSTW after inserting charging stations for partial recharging.
• Phase II: Repeat the following steps for each $\mathsf{\tau }$ of the real-time working hours until all the customers are served.
  • Update the travel times of the best solution generated from phase I, based on traffic congestion conditions using the proposed fuzzy real-time traffic conditions model.
  • Decide re-routing (re-optimizing):
    • At each $\mathsf{\tau }$, check the regions with traffic congestion; then, partially re-route some routes by re-arranging the charging stations’ locations (if any) on each route to eliminate or reduce the early and late penalties as much as possible.
    • If $\mathsf{\tau }$ is within non-congested regions and no early arrival penalties are detected, then there is no need to re-route.
• Provide the final routes and calculate the final real-time-based objective function value (total cost).

3.1. Phase I: Genetic Algorithm for FD-EVRPSTW and Partial Recharging

In the first phase of the proposed two-phase solution approach, a genetic algorithm is used to solve the mathematical model of the FD-EVRPSTW to provide a best-route solution, i.e., a solution with the total cost being minimized. Then, using the provided GA’s best-route solution, the charging stations’ locations within each vehicle’s route are determined. Figure 1 depicts a flowchart of the proposed algorithm used in phase I. As Figure 1 shows, the proposed algorithm randomly generates an initial feasible solution for the FD-EVRPSTW. Then, the fitness function is evaluated for every generated chromosome to calculate the total cost of the chromosome. The total cost is calculated according to Equation (1) and consists of the total travel times in addition to the early or late penalties at customers’ nodes if a vehicle arrives outside the customers’ time windows. At the end of the algorithm, the best fitness value and the corresponding solution are retained. In this work, the selection, crossover, and mutation operators of the GA are adopted from [9]. To select a set of parents for further reproduction, a stochastic tournament-selection operator is employed. This operator takes a population and selects the parents of each child in the new population. At the beginning, five random individuals are selected from the population. Then, a random number is generated. If the random number is less than a pre-defined selection probability, then a parent is chosen from the five selected individuals. Otherwise, the parent with the least cost among the five random individuals is chosen. Afterward, the “Best Cost Route Crossover” operator is implemented within the same chromosome and/or different chromosomes by exchanging the values within its/their genes. Finally, the mutation operator iterates on each individual in the population according to the mutation probability. The mutation operator chooses two random customers and swaps their positions such that a feasible solution is obtained. The GA’s steps are repeated until a stopping condition has been met. In our proposed algorithm, the stopping conditions are either reaching the pre-defined maximum number of iterations (generations) or no improvement being recorded for the total cost in the last twenty generated solutions. The insertion of charging stations for partial recharging is decided based on the SoC of each vehicle’s battery level and the distance to the immediate next customer. Batteries’ SoCs are monitored when vehicles arrive at customers (${\mathrm{A}\mathrm{S}\mathrm{o}\mathrm{C}}_{\mathrm{i}}$). If the remaining SoC (${\mathrm{A}\mathrm{S}\mathrm{o}\mathrm{C}}_{\mathrm{i}}$) is less than 200% of the required SoC to reach the next customer, the vehicle exits its designated route to visit the nearest charging station. Recharging is performed partially or fully such that ${\mathrm{D}\mathrm{S}\mathrm{o}\mathrm{C}}_{\mathrm{i}}$ is raised to be ${\mathrm{A}\mathrm{S}\mathrm{o}\mathrm{C}}_{\mathrm{i}}$+ 200% of the required SoC to reach the next customer. ${\mathrm{D}\mathrm{S}\mathrm{o}\mathrm{C}}_{\mathrm{i}}$ cannot exceed 100% of the battery capacity (W). Finally, the total cost of the best solution after adding the charging stations is calculated to consider the effect of the electric vehicles’ recharging while en route.

Figure 2 shows a representation of the proposed chromosomes that are used in phase I. A chromosome represents all the vehicles with all the routes and their assigned customers in the presented order. Demands are summed up such that when a vehicle’s capacity is reached, the route ends, and a new vehicle is utilized. For example, in Figure 2, route 1 is designed such that a vehicle is dispatched from the depot to visit customer 7, then customer 9, then customer 3. The total demands of customers 7, 9, and 3 do not leave capacity for the vehicle to visit other customers; hence, the route ends at customer 3, and the vehicle returns to the depot after visiting customer 3. Another vehicle is dispatched from the depot to visit customers 8–5–2–1–4–6, and then the vehicle returns to the depot. The demands of customers 8–5–2–1–4–6 are within the limits of the vehicle’s capacity. A feasible chromosome, i.e., a feasible solution, is decided according to the proposed mathematical model’s constraints of the FD-EVRPSTW. As mentioned in Section 2.2, a customer’s fuzzy demand is defined using triangular fuzzy numbers, where $d_i=\left(d_{i1},d_{i2},d_{i3}\right)$, and $d_{i2}$ is the deterministic demand of a customer. The boundaries $\left(d_{i1} \mathrm{a}\mathrm{n}\mathrm{d} {di}_3\right)$ are calculated according to the statistical distribution of the deterministic customer demands.

3.2. Phase II: Fuzzy Real-Time Adaptive Optimizer (FRTAO)

Real-time travel conditions are considered as different congestion levels during a regular working day. Congestion levels are categorized as medium-congestion traffic (i.e., crowded), normal traffic flow, and high-congestion traffic (i.e., congested). Medium-congestion traffic occurs during the morning hours, when people are heading to their workplaces, schools, etc. After the start of a workday, when people are already in their workplaces, study places, etc., the normal traffic flow begins. This is the duration when roads are characterized by a smooth flow of traffic. At the end of a workday, when people are leaving their workplaces, study places, etc., the duration of high-congestion traffic begins. We choose the morning congestion to be medium relative to the end-of-day congestion because it is noticed that work start times may allow some flexibility in employees’ arrivals, leading to lower congestion levels when compared to the typical leaving times at the end of working days. Moreover, some study places naturally have students arriving at different times in the morning, unlike the leaving times which are similar in most cases. Medium and high traffic congestion levels occur gradually, and hence, they are better represented by fuzzy membership functions.

The effect of traffic congestion is reflected in this paper as longer travel times. Travel times due to congestion are re-calculated according to a novel real-time traffic condition fuzzy-based model. In the proposed fuzzy-based model, the three possible traffic conditions, namely normal, crowded, and congested, are represented as given in Figure 3. In the mathematical model, ${\mathrm{t}}_{\mathrm{i}\mathrm{j}}\left(\mathsf{\tau }\right)$ is the fuzzy-based estimation of the travel time between nodes i and j at time τ. ${\mathrm{t}}_{\mathrm{i}\mathrm{j}}\left(\mathsf{\tau }\right)$ is calculated such that ${\mathrm{t}}_{\mathrm{i}\mathrm{j}}\left(\mathsf{\tau }\right)=(1+\mathsf{\alpha }(\mathsf{\tau }\left)\right){\mathrm{c}}_{\mathrm{i}\mathrm{j}}$, where $\mathsf{\alpha }\left(\mathsf{\tau }\right)$ is a fuzzy-based coefficient. $\mathsf{\alpha }\left(\mathsf{\tau }\right)$ is calculated using the proposed real-time fuzzy model that models different traffic conditions. Figure 3 illustrates the proposed fuzzy model of real-time traffic conditions. As Figure 3 shows, for medium congestion (crowded), $\mathsf{\alpha }\left(\mathsf{\tau }\right)$ is in the range of [0, ${\mathrm{C}\mathrm{r}}_{\mathrm{M}\mathrm{a}\mathrm{x}}$]; for normal traffic conditions, $\mathsf{\alpha }\left(\mathsf{\tau }\right)=0$; and for high congestion (congested), $\mathsf{\alpha }\left(\mathsf{\tau }\right)$ is in the range of [0-${\mathrm{C}\mathrm{o}\mathrm{n}}_{\mathrm{M}\mathrm{a}\mathrm{x}}$]. Hence, for the period of normal traffic conditions, ${\mathrm{t}}_{\mathrm{i}\mathrm{j}}\left(\mathsf{\tau }\right)={\mathrm{c}}_{\mathrm{i}\mathrm{j}}$; in other traffic conditions, ${\mathrm{t}}_{\mathrm{i}\mathrm{j}}\left(\mathsf{\tau }\right)$ is larger than ${\mathrm{c}}_{\mathrm{i}\mathrm{j}}$ with a value that is proportional to the degree of real-time congestion that is modeled by $\mathsf{\alpha }\left(\mathsf{\tau }\right)$.

According to the proposed real-time traffic condition fuzzy-based model, a novel, adaptive, optimization algorithm is designed. The output of phase I is re-evaluated in light of the different traffic conditions. Travel times that have been obtained from the solution of phase I are re-adjusted to reflect the traffic congestion category according to the fuzzy-based model calculations explained above. A decision regarding recharging is considered at this stage of the solution as follows: If the SoC is less than W, and a delay due to congestion is expected, then the vehicle exits the designed route and goes to the nearest recharging station to recharge. After recharging, the vehicle resumes its route as planned in phase I. The overall flow of the proposed fuzzy real-time adaptive optimizer is described briefly in the following steps:

Phase II: Fuzzy real-time adaptive optimizer (FRTAO):

• Input:
  • The initial best routing plan from phase I.
  • ${\mathrm{t}}_{\mathrm{s}\mathrm{t}\mathrm{e}\mathrm{p}}$, the time step to be used for real-time updates.
• Initialize $\mathsf{\tau }=0$.
• Repeat the following steps until all the customers are served:
  • $\mathsf{\tau }={\mathsf{\tau }+\mathrm{t}}_{\mathrm{s}\mathrm{t}\mathrm{e}\mathrm{p}}$, update $\mathsf{\alpha }\left(\mathsf{\tau }\right)$ as explained above.
  • For each vehicle k, perform the following steps:
    • Check the vehicle’s current location; if it is between two customers, then create a new artificial, intermediate node on the route.
    • Update the travel times ${\mathrm{t}}_{\mathrm{i}\mathrm{j}}\left(\mathsf{\tau }\right)$ according to the traffic congestion conditions using the proposed fuzzy real-time traffic conditions model.
    • If the remaining portion of the vehicle’s route contains one or more charging stations (from phase I solution), perform the following:
      • If τ is within a congested region (crowded or congested), perform the following:
        • If ASoC_i < W, $\mathrm{i}\in \mathrm{N}\cup \mathrm{A}$, then re-route the vehicle to visit the nearest charging station to make use of the congestion in partial or full recharge, instead of waiting to recharge later en route. The aim is to reduce/remove the late penalties due to the need for future recharging as much as possible.
        • If ASoC_i = W, $\mathrm{i}\in \mathrm{N}\cup \mathrm{A}$, then no re-routing takes place.
      • If $\tau$ is not within a congested region, and there is an early arrival case at the next customer, and the battery’s ASoC_i < W, $\mathrm{i}\in \mathrm{N}\cup \mathrm{A}$, then visit a charging station such that the early penalty is reduced/removed as much as possible.
• Provide the final routes and, hence, calculate the final real-time-based objective function value.

4. Results and Discussion

4.1. Dataset

To examine the efficiency of the proposed two-phase solution approach, benchmark test instances are used after applying modifications to them. The original dataset used is the well-known Solomon’s benchmark test instances. Solomon’s test instances are categorized into six groups, namely C1, C2, R1, R2, RC1, and RC2. The two groups C1 and C2 are designed such that customers are clustered into well-defined clusters. The two groups R1 and R2 are designed such that customers are scattered and do not form clusters. The last two groups, RC1 and RC2, are a combination of some clustered customers and some scattered customers. Groups C1, R1, and RC1 are designed with small vehicle capacities and tight time windows for customers. Accordingly, the number of vehicles required to serve the customers is expected to be large. On the other hand, C2, R2, and RC2 groups of instances are designed such that vehicles’ capacities are large and customers’ time windows are loose. Hence, fewer vehicles are required to serve the customers, and accordingly, each vehicle serves many customers.

Solomon’s test instances were originally designed for conventional diesel-operated vehicles with hard time windows and deterministic customer demands. Accordingly, customers’ fuzzy demands, soft time windows, and the associated penalties were not considered, and electric charging needed for electric vehicles and the charging stations’ locations were also not considered. Therefore, in this paper, the original Solomon’s test instances are modified to be suitable for the problem under study, i.e., the FD-EVRP-STW. First, as explained earlier, a customer’s fuzzy demand is defined using triangular fuzzy numbers ${\mathrm{d}}_{\mathrm{i}}=\left({\mathrm{d}}_{\mathrm{i}1},{\mathrm{d}}_{\mathrm{i}2},{\mathrm{d}}_{\mathrm{i}3}\right)$, where ${\mathrm{d}}_{\mathrm{i}2}$ is the deterministic customer demand. The boundaries $\left({\mathrm{d}}_{\mathrm{i}1} \mathrm{a}\mathrm{n}\mathrm{d} {\mathrm{d}\mathrm{i}}_3\right)$ are calculated as follows: ${\mathrm{d}}_{\mathrm{i}1}={\mathrm{d}}_{\mathrm{i}2}-{\mathsf{\sigma }}_{\mathrm{d}}$ and ${\mathrm{d}}_{\mathrm{i}3}={\mathrm{d}}_{\mathrm{i}2}+{\mathsf{\sigma }}_{\mathrm{d}}$, where ${\mathsf{\sigma }}_{\mathrm{d}}$ is the standard deviation calculated from the statistical distribution of the deterministic customer demands. Hence, during implementation, a customer’s fuzzy demand parameter $d_i$ is calculated using the stochastic simulation algorithm explained in [29]. Second, soft time windows are applied to Solomon’s test instances such that each unit of violation of the time window of a customer is added as one cost unit of penalty in the objective function. For example, if a vehicle arrives at customer i five time units earlier than e_i, then five cost units are added to the objective function. Similarly, late penalty costs are calculated. Finally, we have designed an electrified version of Solomon’s test instances, and we named it E-Solomon. In E-Solomon, each instance of the original Solomon’s dataset is modified by adding a pre-determined set of charging stations. The locations of these charging stations are selected to be uniformly distributed among the customers as given in Figure 4. For each instance, a rectangular area is determined from the coordinates of the depot and the customers’ locations. Hence, nine charging stations are created, as shown in Figure 4. One charging station is at the center of the rectangular area. The remaining eight stations are located midways between the center of the rectangle and the rectangle’s edges and corners. The numbers inside the red ovals in Figure 4 identify each charging station in the E-Solomon test instances. Figure 5 shows the nine charging stations distributed within instance R202 from the E-Solomon dataset.

4.2. Comparative Study and Analysis

The comparative study is performed for phase I considering a static solution that has been obtained using genetic algorithm and for phase II considering fuzzy real-time traffic conditions. The objective of the comparative study of phase I is to examine the effect of replacing diesel-operated vehicles with electric vehicles. There is usually an added cost due to recharging EVs if recharging is required en route. This cost is paid for environmental concerns; however, it is minimized through partial recharging. On the other hand, the objective of the comparative study of phase II is to examine the effect of real-time traffic conditions, represented by congestion, on the total cost. In addition, comparisons of phase II explore the efficiency of the proposed fuzzy real-time adaptive optimizer (FRTAO) in reducing the combined negative effects of batteries’ recharging and traffic congestion on the total cost.

4.2.1. Phase I Comparisons

Phase I of the proposed two-phase solution approach utilizes a GA to obtain a static solution for the fuzzy demand vehicle routing problem with soft time windows (FD-VRPSTW) and for the fuzzy demand electric vehicle routing problem with soft time windows (FD-EVRPSTW). In our implementation of the GA, the population size is selected to be 30, the maximum number of generations is set to 900, and the probabilities of crossover and mutation are 0.6 and 0.01, respectively. For electric vehicles, the battery’s consumption rate is 0.4 km for 1% of the battery charge, and recharging 1% takes 3.6 time units. The output of phase I for the examined test instances is summarized in

Table 1. Results obtained in phase I.

Instance #	# of Vehicles	Total Cost FD-VRPSTW	FD-EVRPSTW
			Total Cost	Average Charging Percentage
C101	13	4938.71	9801.26	42.5%
C102	14	3668.45	5327.85	35.9%
C103	13	3050.61	7143.34	42%
C104	10	2099.26	2105.47	23.1%
C201	4	6196.76	75,698.49	50.1%
C202	5	4797.30	50,579.54	48.42%
C203	6	4437.27	36,470.79	41.15%
C204	9	3448.66	21,304.21	41.34%
R101	22	4052.85	4052.85	0
R102	20	2589.77	2589.77	0
R103	18	2195.92	2195.92	0
R104	15	1623.10	1623.10	0
R201	6	3972.35	10,741.82	32.67%
R202	7	3327.93	12,477.66	34.98%
R203	5	2551.96	6862.29	35.27%
R204	7	2037.93	3607.43	23.6%
RC101	22	3173.91	3173.91	0
RC102	19	2631.14	2631.14	0
RC103	18	2235.19	2235.19	0
RC104	13	1690.46	1690.46	0
RC201	6	3821.62	14,940.31	44.56%
RC202	6	3372.60	11,381.33	39.18%
RC203	6	3083.73	8886.21	44.45%
RC204	5	2251.77	6277.95	42.78%

and Figure 6 and Figure 7. Table 1 shows the total costs, the number of utilized vehicles, and the average charging percentage of the vehicles’ batteries. Figure 6 and Figure 7 show the averages of the total costs and the number of utilized vehicles for every set of test instances. The total cost is calculated as defined in objective function (1), which is the summation of the total travel distance in addition to early or late penalties if they exist.

Table 1 shows that electric vehicles in the examined instances of groups C1, C2, R2, and RC2 need to visit some charging stations, and hence an additional cost is added when electric vehicles are utilized, while in test instances R1 and RC1, the cost of electric vehicles is similar to that of diesel-operated vehicles because no recharging is needed. The average differences and similarities of costs between the test instances belonging to different groups are visualized well in Figure 7. The differences and similarities in costs are explained by the large number of vehicles that are required to serve the customers for instances of groups R1 and RC1, as shown in Figure 6. The utilization of a large number of vehicles means that each vehicle serves a small number of customers, and hence, recharging is not needed, which makes the total travel and penalty costs similar for diesel-operated and electric vehicles since no delay or additional travel cost takes place due to recharging. It is noted from Figure 7 that the increase in the total cost due to utilization of electric vehicles for C2’s instances is large compared to the same increase for C1’s instances. This is due to the difference in the characteristics of the two sets of instances. In C2’s instances, vehicles have large capacities, and customers have wide time windows, which allows a small number of vehicles to serve a large number of customers. In such cases, many customers are assigned to each vehicle, and hence, late penalties are expected to apply. The late penalties are magnified when delays occur due to recharging, and hence, when EVs are utilized, these late penalties increase significantly, leading to a remarkable increase in the total cost. The increase in the amount of late penalties in the case of the utilization of EVs is directly proportional to the average percentage of partial recharging, as shown in Table 1. This is opposite to the cases of C1’s instances, where vehicles have smaller capacities and customers have narrow time windows, forcing a large number of vehicles to be utilized. Hence, each vehicle serves a small number of customers, leading to smaller late penalties. Moreover, the small number of customers per vehicle allows the vehicles to experience less recharging, and accordingly, the delay due to recharging the EVs is not as large as in test instances of the set C2. The same analysis holds when the total cost of electric vehicles in Figure 7 is compared with the total cost of diesel-operated vehicles in instances of sets R2 and RC2 versus those of R1 and RC1, respectively.

It is worth noting that the limiting constraint on the number of required vehicles is the vehicles’ capacities, while the time windows do not pose a limitation since they can be violated with penalties. That is why it is noted in Figure 6 that vehicles with large capacities, namely those in groups C2, R2, and RC2, utilize a small number of vehicles compared to the large number of vehicles that are utilized in groups C1, R1, and RC1, where vehicles have smaller capacities.

4.2.2. Phase II Comparisons

Phase II aims to explore the effect of real-time traffic conditions, namely congestion, on the total cost encountered. Moreover, phase II examines and analyzes the impact of the proposed fuzzy real-time adaptive optimizer (FRTAO) on cost increases that result from the combined effect of recharging and congestion. In this phase, the proposed real-time traffic fuzzy model is assumed to have a working day of 11 time slots, with ${\mathrm{t}}_{\mathrm{s}\mathrm{t}\mathrm{e}\mathrm{p}}=0.5$ of a time slot, such that ${\mathsf{\tau }}_0=0,{\mathsf{\tau }}_{\mathrm{N}\mathrm{S}}=3,$ ${\mathsf{\tau }}_{\mathrm{N}\mathrm{E}}=7,$ ${\mathsf{\tau }}_{\mathrm{M}\mathrm{a}\mathrm{x}}=11,$ ${\mathrm{C}\mathrm{r}}_{\mathrm{M}\mathrm{a}\mathrm{x}}=0.5,$ and ${\mathrm{C}\mathrm{o}\mathrm{n}}_{\mathrm{M}\mathrm{a}\mathrm{x}}=1$. Real-time traffic conditions present a major challenge for vehicle routing problems, especially when time windows are considered as they lead to delays and hence late arrivals at customers. On the other hand, if early arrivals are the challenge facing vehicle routing problems, then real-time traffic conditions lead to a “good” delay that reduces or eliminates early arrivals at customers. Real-time traffic conditions are modeled using fuzzy numbers, as explained in Section 3.

Table 2. Effect of real-time on total cost for FD-VRPSTW.

Instance #	# of Vehicles	Total Cost FD-VRPSTW	Total Cost RT-FD-VRPSTW
C101	13	4938.71	6727.45
C102	14	3668.45	7480.56
C103	13	3050.61	7341.66
C104	10	2099.26	6281.43
C201	4	6196.76	14,634.51
C202	5	4797.30	14,805.14
C203	6	4437.27	13,993.68
C204	9	3448.66	13,766.47
R101	22	4052.85	3308.10
R102	20	2589.77	3004.66
R103	18	2195.92	2642.71
R104	15	1623.10	2445.28
R201	6	3972.35	5716.81
R202	7	3327.93	5503.64
R203	5	2551.96	4531.08
R204	7	2037.93	3913.75
RC101	22	3173.91	3708.49
RC102	19	2631.14	3442.93
RC103	18	2235.19	2579.31
RC104	13	1690.46	2090.32
RC201	6	3821.62	6095.43
RC202	6	3372.60	5804.21
RC203	6	3083.73	5337.07
RC204	5	2251.77	4143.73

presents the number of utilized vehicles and the total costs of the fuzzy demand vehicle routing problem with soft time windows (FD-VRPSTW) and the real-time FD-VRPSTW (RT-FD-VRPSTW). The results presented in Table 2 were obtained using a GA. Figure 8 provides the average total cost for each set of test instances for FD-VRPSTW and RT-FD-VRPSTW.

Table 2 shows that, as expected, in most cases, real-time traffic conditions result in delays that increase the total cost due to the increase in travel times in congested regions, and accordingly, an increase is noticed in the penalty costs due to the late arrivals beyond the time windows of customers. Although some exceptions exist, Figure 8 shows that among the six groups of test instances, the average total cost is larger when real-time traffic conditions, expressed as congestion, are considered.

Figure 8 also shows that the magnitude of the increase in the average total costs due to real-time traffic conditions in C2’s test instances is larger than that in C1’s test instances. This is explained by the number of utilized vehicles due to the different vehicles’ capacities. In the C2 set of test instances, vehicles have large capacities; hence, fewer vehicles are utilized. Accordingly, a large number of customers is assigned to each vehicle. This causes a significant increase in late penalties, especially for those customers who are nearer to the end of the route. The result is a large increase in the total cost. The same analysis applies for the results of the test instances that belong to sets R2 and RC2 when compared to the results of the test instances that belong to sets R1 and RC1, respectively.

Real-time traffic conditions, specifically congestion that is studied in this paper, affect late penalties negatively and affect early penalties positively. Therefore, when early penalties exist, congestion eases, and sometimes eliminates, the effect of the early penalties. This is because congestion delays vehicles, which leads to later arrivals at customers. These delays cause the vehicles to arrive close to or during customers’ time windows, which leads to the early penalties being reduced or eliminated. The opposite is true for late arrivals and their associated late penalties. For any vehicle, real-time traffic conditions may have positive effects on early arrivals for some customers and/or negative effects on late arrivals for other customers. The total magnitude of both penalties, the reduced early plus the increased late penalties, is calculated for all the vehicles and their assigned customers. The total magnitude of the two types of penalties is then added to the total cost. If the positive effects of congestion on early arrivals’ penalties are larger than the negative effects of congestion on late arrivals’ penalties, then the overall total effect of congestion is a total cost decrease. On the other hand, if the negative effects of congestion on late arrivals’ penalties are larger than the positive effects of congestion on early arrivals’ penalties, then the overall total effect of congestion is a total cost increase. The magnitude of the total cost decrease or increase due to congestion depends on the characteristics of the instance that is solved and the values of its parameters. In the majority of the examined test instances, congestion has a large negative effect on the total cost increase, where the values of the added late penalties are larger than the values of the reduced/removed early penalties. The only exception noticed in Table 2 is for test instance R101. By examining the details of that particular instance, it has been noticed that all the penalties for that instance are early penalties, and hence, when the vehicles are delayed due to traffic conditions, the early penalties are eliminated, leading to a decrease in the total cost encountered. The rest of the instances of the R1 group and all the instances of the RC1 group show relatively similar behavior, where all the penalties are early penalties but with small amounts. When real-time travel conditions cause delays, the early penalties are removed; nevertheless, the additional late penalties are added. The added late penalties are larger than the removed early penalties, leading to a small increase in the total cost. It is worth noting here that this behavior for R1 and RC1 groups of test instances is due to the large number of utilized vehicles which results in a small number of customers being assigned to each vehicle. Accordingly, early arrivals at customers’ locations are expected, while late arrivals are small and are not magnified for the customers who are assigned near the end of the route.

The effect of recharging EVs on the total cost is clearly identified in Table 1 and Figure 7. Table 1 and Figure 7 show that the total cost increases when electric vehicles need to recharge before finishing their assigned route. In addition, Table 2 and Figure 8 show that real-time traffic conditions, represented by congestion, usually lead to an increase in the total cost, although some exceptions are noticed. Accordingly, when real-time traffic conditions are combined with recharging for EVs, more increase in the total cost is expected very often.

The proposed fuzzy real-time adaptive optimizer (FRTAO) that is developed in this research aims to overcome both challenges, namely the negative effects of recharging and congestion. To study the effect of the proposed optimizer on the real-time fuzzy demand electric vehicle routing problem with time windows (RT-FD-EVRPSTW), test instances from the modified E-Solomon instances are solved using the proposed two-phase solution approach, where FRTAO is utilized in phase II.

Numerical case example:

To explain the details of the way FRTAO overcomes the combined effect of recharging and real-time traffic conditions on the total cost, a numerical example is explained. This example is one of the routes that are obtained from the solution of test instance R202. The sequence of visits to customers for the chosen instance’s solution route is given in Figure 5. The distribution of the nine charging stations and their ID numbers is given in Figure 5 and Figure 6.

The selected route assigns nine customers to the vehicle. The sequence of customers’ visits and charging stations’ visits, without considering real-time traffic conditions, is given in Figure 9a. The solution illustrated in Figure 9a is the output solution from phase I. The output solution from phase I is the input to phase II, where FRTAO is applied. The resulting output solution from phase II is shown in Figure 9b.

As Figure 9a shows, two visits to two different charging stations are needed. Before the charging stations are visited, one early penalty exists for the third customer (customer ID 62). Late penalties start to appear after the delay at the charging stations. The total late penalties’ value for the customers assigned to the route is 328.1, the early penalty value = 39.9, and the total cost of the route including both the early and the late penalties is 716.9.

The concept of the proposed optimizer FRTAO is to make use of the delay that is naturally present in real-time traffic congestions to recharge the EVs’ batteries. Therefore, during normal traffic flow times, the EV does not need to recharge, and hence, the EV avoids delays during the normal traffic flow time. When FRTAO is applied to the route that is illustrated in Figure 9a, the resulting route that is illustrated in Figure 9b is obtained. Figure 9b shows that FRTAO efficiently utilizes the crowded traffic condition to recharge the EV in station ID 109, immediately after visiting the second customer (ID 26). This newly added visit eliminates the need for recharging after the sixth customer (ID 88) in the original route in Figure 9a. The result is the elimination of the early penalty of customer ID 62; moreover, the total late penalties across the route are reduced to 162.3. The total early and late penalties in the entire route after the application of FRTAO are reduced to nearly half the value, and the new cost of the route is 491.

The results obtained for the FD-EVRPSTW, the RT-FD-VRPSTW, and the results obtained using the two-phase approach employing FRTAO to solve the RT-FD-EVRPSTW are presented in

Table 3. Proposed approach effect on recharging and real-time challenges.

Instance #	# of Vehicles	Total Cost Using GA FD-EVRPSTW	Total Cost Using GA RT-FD-VRPSTW	Total Cost Using GA and FRTAO FD-EVRPSTW
C101	13	9801.26	6727.45	6356.99
C102	14	5327.85	7480.56	6548.37
C103	13	7143.34	7341.66	6537.25
C104	10	2105.47	6281.43	6199.97
C201	4	75,698.49	14,634.51	17,461.16
C202	5	50,579.54	14,805.14	16,063.09
C203	6	36,470.79	13,993.68	15,593.02
C204	9	21,304.21	13,766.47	13,888.57
R101	22	4052.85	3308.10	3308.10
R102	20	2589.77	3004.66	3004.66
R103	18	2195.92	2642.71	2642.71
R104	15	1623.10	2445.28	2445.28
R201	6	10,741.82	5716.81	5532.90
R202	7	12,477.66	5503.64	4956.75
R203	5	6862.29	4531.08	4480.25
R204	7	3607.43	3913.75	3682.90
RC101	22	3173.91	3708.49	3708.49
RC102	19	2631.14	3442.93	3442.93
RC103	18	2235.19	2579.31	2579.31
RC104	13	1690.46	2090.32	2090.32
RC201	6	14,940.31	6095.43	5847.10
RC202	6	11,381.33	5804.21	5237.86
RC203	6	8886.21	5337.07	4765.76
RC204	5	6277.95	4143.73	4049.86

. The averages of the total costs per group of instances are given in Figure 10. Column 3 in Table 3 lists the total cost of the FD-EVRPSTW without real-time considerations. On the other hand, Column 4 in Table 3 lists the total cost values when real-time traffic conditions are considered for diesel-operated vehicles, i.e., RT-FD-VRPSTW. Finally, Column 5 in Table 3 lists the total costs for the RT-FD-EVRPSTW after the application of FRTAO, when real-time traffic conditions and partial/full recharging are considered.

Table 3 and Figure 10 show the ability of FRTAO to overcome the combined effect of real-time traffic congestion and the recharging needed for EVs as explained in the numerical case example illustrated above. Figure 10 shows that, for test instances belonging to sets C1, R2, and RC2, FRTAO generally provides better results. Regarding the test instances belonging to set C2, FRTAO is able to make use of the traffic congestion to significantly reduce the delay resulting from recharging. The effect of applying FRTAO on test instances belonging to set C2 is a remarkable reduction in the total cost of utilizing EVs, such that the EVs’ cost becomes very close to the diesel-operated vehicles’ cost.

Test instances belonging to sets R1 and RC1 do not show improvements after FRTAO is applied. This is due to the design nature of FRTAO which makes use of the delays due to congestion in recharging. Table 1 and Figure 7 show that the test instances that belong to sets R1 and RC1 do not require recharging while en route. Accordingly, no optimization of recharging during congestion can be applied. In such cases, utilizing EVs requires a travel cost that is similar to diesel-operated vehicles’ cost. Accordingly, in such cases, the utilization of EVs is favorable since no additional cost resulting from battery recharging is faced.

5. Conclusions

In this work, the electric vehicle routing problem with fuzzy demands and soft time windows considering fuzzy real-time traffic conditions was studied. A mixed-integer programming model of the problem was developed, and a novel two-phase solution approach was proposed to solve the problem. The proposed solution approach examined the effect of recharging on the FD-EVRPSTW in phase I and obtained optimum/near optimum solutions using a genetic algorithm. The obtained results showed that in most cases, recharging led to a negative effect on the total cost encountered; nevertheless, in some cases, where vehicles were serving only a few customers, recharging had no effect on the total cost. In phase II, fuzzy real-time traffic conditions, namely congestion, were studied. The obtained results showed that real-time traffic conditions, in most cases, led to an increase in the total cost, and in very few cases, delays due to congestion eliminated the early penalties, which caused a reduction in the total travel costs. To overcome the negative effects of recharging and congestion, a novel fuzzy real-time adaptive optimizer (FRTAO) was proposed. A numerical case example on a chosen solution route was illustrated to show the enhancement FRTAO achieved when it was applied to the route and the associated cost reduction. Moreover, FRTAO was tested on several benchmark instances, and the obtained results showed that FRTAO improved the total cost obtained by the genetic algorithm in cases of the RT-FD-EVRPSTW and/or the total cost of the RT-FD-VRPSTW when recharging was needed. The magnitude of improvement was dependent on the characteristics and the parameters of each instance being solved.

Future work includes utilizing metaheuristic techniques other than the genetic algorithm, considering other practical applications like the EVRP with backhauls, and considering the fixed cost of dispatching vehicles to limit the number of utilized vehicles.