The Optimal Deployment of the Entry and Exit Gates of Electric Vehicles Wireless Charging Transmitters on Highways

Abstract

Dynamic wireless charging (DWC) facilitates the travel of electric vehicles (EVs) on highways because it can charge EVs without contact and it does not have a recharging time as it can charge vehicles in motion by a set of power transmitters on the road. This work considers a highway road with DWC and a fleet of electric vehicles with heterogeneous batteries to begin a trip from the origin of the highway noted by O to the destination noted by S. As the usage of DWC is not free, this study seeks to install entry gates to the DWC if the vehicles need to charge their batteries and exit gates to the main road if the vehicles wish to stop the recharge. For this purpose, the first objective is to minimize the usage cost paid by each vehicle type to use the DWC during the trip on the highway. The second objective is to find the lower installation cost of the gates on the road. This work proposes to model the problem as a mathematical problem and validate it with the CPLEX optimizer using limited instances and, finally, solves the problem using the non-dominated sorting genetic algorithm (NSGA-II).

1. Introduction

Nowadays, the use of combustion vehicles is expensive due to the increased fuel prices; for this reason, the world is orienting towards using electric vehicles (EVs).

An electric vehicle is a type of vehicle that operates on electricity by exploiting the technology of a battery or fuel cell. It is not a new technology, as the first experimental electric car was produced in 1935. However, it did not return to the market until 2000. This return was motivated by the political will to combat global warming and preserve the environment. Since then, several types of electric cars have emerged: hybrid vehicles, equipped with an internal combustion engine, and 100% electric vehicles, with a fuel cell or battery. They are environmentally friendly, offer a wide range of battery lives, and can be recharged.

The charging rate, the discharging rate, and the autonomy are characteristics that differ from one vehicle to another depending on the type of battery used, so we are discussing heterogeneous vehicles in terms of batteries. In this context, the most batteries used in electric vehicles are:

-

Lead–acid batteries: lead–acid batteries offer limited capacity, despite their large size and weight, but they are economical and straightforward to produce or recycle. Used as a primary storage device for electric vehicles until the 1980s, it quickly gave way to other, more efficient technologies;

-

Nickel–cadmium batteries: Ni–Cd batteries, used in the production of electric vehicles in the 1990s, are now banned due to the toxicity of cadmium;

-

Nickel–metal hydride batteries: these portable rechargeable batteries were the most economical in the early 2000s: this is why they largely dominated the hybrid vehicle market until the advent of lithium-ion technology;

-

Lithium-ion batteries: developed in the early 1990s, lithium-ion batteries have gradually become the leading technology in the world of transport and consumer electronics. With a long lifetime, they offer a much higher energy density than all competing technologies and have no memory effect.

Charging electric vehicles has become more straightforward due to the dynamic wireless charging system (DWCS). This technology eliminates the charging time, as it can recharge vehicles in motion.

The major components of a DWCS are power transmitters (Figure 1) and receiving coils, which the power-distribution network uses to transmit power to EVs. Each power transmitter is composed of an inverter installed beneath roads that converts the DC power into high-frequency AC for wireless transmission and an inductive cable that has the potential to recharge the electric vehicle’s batteries. EVs use the receiving coil connected to their batteries to obtain power from the inductive cable; therefore, electric vehicles can be charged by the DWCS during their trip [1].

The advantage would be to recharge vehicles on highways at high speed, where electric vehicles drain their batteries very quickly; therefore, this would have the effect of drawing a line under one of the disadvantages of electric vehicles. Travelling over long distances would be possible here without stopping to recharge.

Through the DWCS, electric vehicles can use highways without fear of remaining uncharged, as it has the potential to recharge them in motion. Due to the high cost of DWCSs, researchers have thought of determining the minimum infrastructure cost for electric vehicles; in general, they used two methods to obtain it. In the first method, they took the origin road as the reference; then, each power transmitter’s start point and endpoint were described by the travel distance from the reference point; JANG et al. used this method to develop the DWCS infrastructure for electric buses [2]. The second method was used by Bourzik and EL Hilali Aaloui [3]. The principle is to divide the road into potential segments with the same length and determine by vehicle load constraints which segments will be occupied by a DWCS. The two methods mentioned include building a DWCS infrastructure for electric vehicles (Figure 2).

To build a highway road with a DWCS for electric vehicles with heterogeneous batteries (Figure 2) at the least cost, this study considers the work of Bourzik and EL Hilali Aaloui [3] and consists of dividing the road into two zones (Figure 3), the main road without the DWCS and the second road with the DWCS.

Bourzik and EL Hilali Aaloui subdivided the second road into congruent segments; they considered each segment as a potential transmitter and defined two types of segments. The active segment is the part of the road equipped with the DWCS; the vehicles can use this segment type to charge their batteries. The inactive segment is the part of the road without DWCS; this type of segment is not used. They determined the location of the active and the inactive segments according to the vehicle’s load; if at least one vehicle needs to charge its battery, the segment will be active, or inactive if not. The highway road with a DWCS proposed in [3] is shown in Figure 4. If a vehicle needs to charge, it can enter the DWCS road by the doorway at the beginning of the active segment and not leave this road until the next doorway at the end of the active segment.

On the other hand, the usage of a DWCS road would not be free; each vehicle type must pay the service cost, which depends on the vehicle type and the usage duration. This factor was not considered in [3], because they focused on minimizing the infrastructure cost. For this purpose, this work focuses on installing a set of gates on the road to organize the payment and the usage of the DWCS by the vehicles. The usage cost of the DWCS depends on the vehicle type and the usage duration; for this, the road has to contain special gates, which can determine the usage duration of each vehicle type. This paper assumes that the entry gate would provide a ticket for each vehicle that needs to use the DWCS road to localize it, and the exit gate would have the potential to calculate the usage duration from the ticket provided at the entry gate and have a payment system to retrieve the usage cost from the vehicles. Figure 5 shows an example of the entry and exit gates.

To determine the location of the entry and exit gates on the road, the successive active (inactive) segments were assumed to form an active (inactive) charging lane. Each active lane would have a principal entry gate to the DWCS at the beginning and an exit gate at the end of the main road (Figure 6). Between each main entry and exit gate, the goal would be to install a set of gates to ensure a suitable trip for each vehicle type without remaining out of charge based on the minimum total usage cost (T.U.C), which is the first objective of this work.

Due to the heterogeneity of vehicles, the use of the DWCS would differ from one vehicle to another; therefore, each vehicle type needs a set of gates to minimize its T.U.C, which would increase the number of gates; for this purpose, the second objective is to minimize the total number of gates on the road.

The main objective of this paper is to find the optimal location for a power transmitter’s gates on a highway to ensure the trip of a fleet of heterogeneous vehicles with the minimum T.U.C for each type. The first section presents some previous work related to the topic. The next part transforms the problem into a mathematical model with constraints and presents the different notations, data, constraints, and objective functions of the proposed model. The third section proposes solving the problem with the CPLEX optimizer for limited instances to validate the mathematical model. The next part presents the resolution of the problem using the NSGA-II metaheuristic. Finally, the results are analysed and discussed in order to demonstrate the efficiency of the proposed model and methods used.

2. Literature Review

The electric vehicle (EV) is the future mode of transport globally because it is economical and safe for the environment. Inductive charging has the advantage of charging EVs without contact; for this reason, inductive charging and electric vehicles are widely studied by researchers.

Induction charging is composed of three types of charging systems. The first is stationary wireless charging (SWC), which can supply an EV by induction in the stop mode. Many companies around the world have developed their SWC systems, such as the Waseda Electric Bus in Japan, with a power ranging from 30 kW to 150 KW for a distance between transmitter and receiver coils of 105 mm. The vehicle is recharged at each bus stop [4]. Alwesabi et al. [5] developed a mixed-integer mathematical model to simultaneously select the optimal location of DWC facilities and find the optimal battery sizes of electric buses (EBs) for the system based on data obtained from the transportation centre at Binghamton University.

The second type of charging is quasi-dynamic wireless charging (QWC), with which an EV can be charged when it is moving slowly or in the stop-and-go mode. The last type is called dynamic wireless charging (DWC), where the vehicle is charged while running in this charging mode. The DWC is conducted by a specially equipped track where coils are placed that only activate when the vehicle passes over them, resulting in electric roads. This solution can reduce the required capacity and thus the weight and price of vehicle batteries. In 2010, the Korea Institute of Science and Technology (KAIST) designed a contactless bus with an 85% efficiency for a power of 100 kW operating at a frequency of 20 kHz [2].

For the former category, researchers at the Korea Advanced Institute of Science and Technology (KAIST), such as Young [2], sought to ensure the displacement of electric buses with homogeneous batteries during their services using the dynamic wireless charging system. They produced a mathematical model to find a compromise between the infrastructure and battery costs. JEONG et al. [6] modelled the same problem, but added the impact of the battery’s degradation. In their work, the battery life of the bus was calculated by its service number in the DWCS lifetime.

Owing to the uncertainty of power consumption and electric bus travel time, Liu et al. [7] developed a robust mathematical model to optimize the system’s recharging deployment plan. They used Utah State University as a case study. Liu and Song [8] extended the charging lane deployment model proposed by Chen et al. [9] for plug-in hybrid electric truck operations. Chen et al. [10] developed analytical models to optimize the deployment of dynamic charging facilities on a transit system to serve the daily operation of electric buses.

Fuller [11] presented a flow-based overall coverage model to minimize the capital cost of deploying dynamic recharging infrastructure for the California highway system to meet the recharging needs of electric vehicles travelling between significant sources and destinations in the state. At the same time, drivers may be motivated to slow down their electric vehicles in the charging lanes to regain more power.

Mouhrim et al. [12] considered several paths between the arrival station and the base station of electric buses. They sought a compromise between the infrastructure cost of the induction charge and the cost of the batteries. In this work, the battery cost was proportional to the battery capacity. Elbaz et al. [13] considered a multi-path network between the base station and the arrival station to model the problem of determining the minimum infrastructure cost of electric buses with homogeneous batteries. They added the back-and-forth impact to Mouhrim’s work. Xiaotong Sun et al. [14] investigated the optimal deployment of static and dynamic charging infrastructure considering the interdependency between transportation and power networks.

Yung et al. [15] proposed a mathematical study to find the minimum number of power transmitters on the road that could ensure the trips of a set of homogenous electric trams based on the minimum battery capacity.

Bourzik and EL Hilali Alaoui [3] presented the optimal location of the wireless charging infrastructure for EVs with heterogeneous batteries; they conducted their study on a highway. To build the infrastructure, they considered a road subdivided into segments with the same length to determine which segment would be occupied by the DWCS.

Most of the research cited focused on allocating dynamic wireless charging infrastructure. Although these researchers developed the infrastructure for electric vehicles, they considered the cost of the infrastructure, which they sought to optimize. This study considers a case where the electric vehicle’s infrastructure is predefined, and seeks to organize the use and the payment for the use of the DWCS by the vehicles. Due to the heterogeneity of the batteries, it was assumed that the infrastructure was built by Bourzik and EL Hilali Alaoui’s method [3] because they took into account the heterogeneity of the vehicles’ batteries in their work. To organize the use and the payment of the DWCS by the vehicles, the goal is to create the minimum number of entry and exit gates to the DWCS road and to minimize the usage cost of each vehicle type during their trip. This work conducts this study on a highway because electric vehicles’ batteries drain very quickly due to the high speed and the long distance between the origin and the destination, which increases the usage cost.

3. Problem and Modelling

3.1. Problem Description and Objective

This work considers a highway road with a DWCS. The induction charging transmitter system was constructed by Bourzik and EL Hilali Aloui’s method [3]. As noted previously, the location of the active and inactive segments was predefined, and the segments with the same status formed a series of segments. The active series (active lane) had an entry gate at the beginning and an exit gate at the end, and the inactive series were inaccessible. The active series of segments were placed next to the main road as charging lanes (Figure 5).

The fleet of heterogeneous battery vehicles was placed at the origin of the highway, noted by O, to begin the trip to the destination noted by S. The vehicles would use the charging lanes of the highway to not remain out of charge. As access to charging lanes would not be free, this study seeks to minimize the T.U.C of DWCS for each vehicle. To achieve this goal, the aim was to create new entry and exit gates for each charging lane. Owing to the heterogeneity of vehicle batteries, the usage of the charging lanes’ gates differs from one vehicle to another, which would increase the number of gates on the road; for this reason, the goal was to minimize the number of gates on the highway, automatically minimizing the infrastructure cost.

3.2. Problem Formulation, Data, and Decision Variables

In this subsection, the objective is to transform the problem into a mathematical model with constraints. Let $O$ be the origin of the highway and $S$ be the destination. The set of vehicles is denoted by $\phi$, and each type is indexed by α ϵ φ. Moreover, a vehicle of each type begins the trip from $O$ to $S$.

As mentioned previously, the successive segments with the same status (active or inactive) formed a charging lane (series of segments). The first series of segments is denoted by 1, the last series is denoted by $N$, and the other lanes are denoted by $g=1\dots N$. The location of the active lanes (segments series with the DWCS) is predefined; let $U_g$ be a binary variable defined by:

$$U_g=\{\begin{array}{ll}1& if the lane g is active\\ 0& otherwise\end{array}$$

(1)

Let $N^A$ be the set of active lanes, with $N^A=\left\{g/U_g=1\right\}$.

To create new entry and exit gates, the access road of each active lane is discretized into potential gates (PG) indexed by $i=1,\dots , N_g$, with $1$ as the index of the principal entry gate and $N_g$ as the principal exit gate ($N_g$ being the number of potential gates on lane $g$) (Figure 7). Each inactive lane is inaccessible; for this reason, it will not have any gates. In addition, each active lane has a principal entry gate at the beginning, noted by $1$, and a principal exit gate at the end, noted by $N_g$; both gates must be open.

Each gate is associated with a decision variable $P_i^g$, with $i=1,\dots , N_g$ defined by:

$$P_i^g=\{\begin{array}{l}1 if the i{ }^{th} gate of the lane g is open\\ 0 \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}otherwise \end{array}$$

(2)

In the model, each gate can be used to enter or exit the charging lane, and $\rho$ is the necessary distance between two consecutive open gates. Distance $\rho$ is the required number of closed gates between two consecutive open gates. Let $C$ be the installation cost of one gate on the road.

As each vehicle type has its own characteristics, $E_{low}^{\alpha }$ and $E_{up}^{\alpha }$ are the minimum charge and the maximum charge of vehicle $\alpha$. Let $T^{\alpha } \left(t\right)$ and $D^{\alpha }\left(t\right)$ be the charging rate and the discharging rate of vehicle $\alpha$, respectively. $UU{C}^{\alpha }$is the unit usage cost of the DWCS of vehicle $\alpha$.

To determine the open gates in each charging lane, each type of vehicle makes one trip from O to S. The vehicles will pass through each lane’s potential gates; let $t_{g,i}^{\alpha }$ be the arrival time of vehicle $\alpha$ at the $i^{th}$ gate of lane$g$. Let $t_O^{\alpha }$ be the arrival time of vehicle α at the origin $O$ of the highway. The vehicles may slow down on the DWCS road to charge more energy; and ${\delta }_{g,\left(ij\right)}^{\alpha }$ is the maximum allowable travel time between two consecutive gates, $i$ and $j$, when vehicle $\alpha$ uses the DWCS of lane $g$.

Let $I^{\alpha }\left(t\right)$be the amount of energy in the battery $\alpha$ at time$t$; this quantity is described as:

$$\frac{d{I}^{\alpha }\left(t\right) }{dt}=\{\begin{array}{c} T^{\alpha } \left(t\right) if the vehicle \alpha is in charging mode on the DWCS \\ -D^{\alpha } \left(t\right) if the vehicle \alpha is in the main road \end{array}$$

During the trip, the vehicles decide to use the gates to enter or leave the charging lanes; therefore, to determine the gates used for each vehicle type, the decision variable$y_{g,i}^{\alpha }$ is defined as follows:

$$y_{g,i}^{\alpha }=\{\begin{array}{l}1 if \mathrm{the} \mathrm{vehicle} \mathrm{type} \alpha use the i{ }^{th}gate of the charging lane g\\ 0\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em} otherwise \end{array}$$

(3)

To determine the charging cost of each vehicle type, the decision variable$w_{g,\left(i,i+1\right)}^{\alpha }$ is defined as follows:

$$w_{g,\left(i,\mathrm{i}+1\right)}^{\alpha }=\{\begin{array}{l}1 if the \mathrm{vehicle} \mathrm{type} \alpha uses the charging lane g between the gates i and i+1\\ 0\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em} otherwise\end{array}$$

(4)

Variables $w_{g,\left(i,i+1\right)}^{\alpha }$ and $y_{g,i}^{\alpha }$ depend on the vehicle type, because the usage of the charging lanes differs from one type to another due to the heterogeneity of the batteries.

3.3. Constraints

The mathematical model constraints are constructed in this section. As mentioned previously, each vehicle type makes one trip from O to S, and each battery type has a full charge at the origin of the road:

$$I^{\alpha }\left(t_O^{\alpha }\right)=E_{up}^{\alpha } \forall \alpha ϵ\phi$$

(5)

To ensure the trip of each vehicle type without remaining out of charge in the active charging lanes, the following constraints must be verified:

$$I^{\alpha }\left(t_{g,i}^{\alpha }\right)+{{\displaystyle \int }}_{t_{g,i}^{\alpha }}^{t_{g,i+1}^{\alpha }}(D^{\alpha }\left(t\right)\times \left(w_{g,\left(i,i+1\right)}^{\alpha }-1\right)+T^{\alpha }\left(t\right)\times w_{g,\left(i,i+1\right)}^{\alpha })dt\ge E_{low}^{\alpha }$$

$$\forall \alpha ϵ\phi , \forall gϵN^A; \forall i=1,\dots ,N_g-1$$

(6)

The first term of the constraint presents the battery charge of vehicle $\alpha$ at its arrival time at the $i^{\mathrm{th}}$ gate of lane $g$. The second term presents the load consumption of vehicle $\alpha$ during its travel between gates $i$ and $i+1$ of lane $g$; the vehicle loses this energy if it has not used the charging lane $g$ between gates $i$ and $i+1$ $\left(w_{g,\left(i,i+1\right) }^{\alpha }=0\right)$. If the vehicle uses the charging lane between gates $i$ and $i+1$ $\left(w{ }_{g,\left(i,i+1\right)}^{\alpha }=1\right)$, the second term will be cancelled because the battery is in the recharge mode, and the third term represents the amount of energy recharged. Then, constraint (6) presents the battery level of the vehicle α at its arrival time at gate $i+1$ of the charging lane $g$, which must always be greater than the battery’s minimum load. In other words, each type of vehicle uses the recharge track so that the energy level is greater than the minimum load of the vehicle.

To ensure the trip of each vehicle type without remaining out of charge in the inactive charging lanes, the following constraints must be verified:

$$I^{\alpha }\left(t_{g,N_g}^{\alpha }\right)+{{\displaystyle \int }}_{t_{g,N_g}^{\alpha }}^{t_{g+1,1}^{\alpha }}(D^{\alpha }\left(t\right)dt\ge E_{low}^{\alpha }) \forall \alpha ϵ\phi , \forall gϵN^A$$

(7)

The first term of (7) presents the amount of energy of vehicle $\alpha$ at the last gate of the active charging lane $g$, and the second term is the energy consumption due to the travel between the last gate of active charging lane $g$ and the first gate of charging lane $g+1$. Then, constraint (7) presents the variation in the battery charge during the trip in an inactive charging lane, which must be greater than the minimum load of the vehicle.

The vehicle batteries are operated in such a way that the level of charge does not exceed its maximum charge; for this, the following constraints must be verified:

$$I^{\alpha }\left(t_{g,i+1}^{\alpha }\right)=\min \left(E_{up}^{\alpha }, I^{\alpha }\left(t_{g,i}^{\alpha }\right)+{{\displaystyle \int }}_{t_{g,i}^{\alpha }}^{t_{g,i+1}^{\alpha }}(D^{\alpha }\left(t\right)\times \left(w_{g,\left(i,i+1\right)}^{\alpha }-1\right)+T^{\alpha }\left(t\right)\times w_{g,\left(i,i+1\right)}^{\alpha })dt\right)$$

$$\forall \alpha ϵ\phi , \forall g=1,\dots ,N; \forall i=1,\dots ,N_g-1$$

(8)

Constraint (8) updates the remaining charge at each ${\left(i+1\right)}^{th}$ gate. The battery energy level of each vehicle $\alpha$ should be lower than the upper limit of the battery $E_{up}^{\alpha }$. If the energy amount is higher than the upper limit, then the energy level would be $E_{up}^{\alpha }$.

Constraint (9) updates the remaining charge of vehicles at the first gate of each active charging lane:

$$I^{\alpha }\left(t_{g+1,1}^{\alpha }\right)=I^{\alpha }\left(t_{g,N_g}^{\alpha }\right)+{{\displaystyle \int }}_{t_{g,N_g}^{\alpha }}^{t_{g+1,1}^{\alpha }}(D^{\alpha }\left(t\right)dt) \forall \alpha ϵ\phi , \forall gϵN^A$$

(9)

The usage of the segment gates differs from one type to another due to the heterogeneity of batteries. The following constraints determine the usage of gates for each vehicle:

$$y_{g,i}^{\alpha }=\left(1-w_{g,\left(i-1,i\right)}^{\alpha }\right)\times w_{g,\left(i,i+1\right)}^{\alpha }+\left(1-w_{g,\left(i,i+1\right)}^{\alpha }\right)\times w_{g,\left(i-1,i\right)}^{\alpha }$$

$$\forall \alpha ϵ\phi , \forall gϵN^A, \forall i=2,\dots ,N_g-1$$

(10)

$$y_{g,1}^{\alpha }=w_{g,\left(12\right)}^{\alpha } \forall \alpha ϵ\phi , \forall g=1,\dots ,N$$

(11)

$$y_{g,N_g}^{\alpha }=w_{g,\left(N_g-1,N_g\right)}^{\alpha } \forall \alpha ϵ\phi , \forall g=1,\dots ,N$$

(12)

For constraint$\left(10\right)$:

• If $w_{g,\left(i-1,i\right)}^{\alpha }=0$, the vehicle $\alpha$ has not used lane $g$ between gates $i-1$ and $i$; this means that vehicle $\alpha$ is on the main road, so if $w_{g,\left(i,i+1\right)}^{\alpha }=1$, the vehicle decides to use lane $g$ between gates $i$and $i+1$; in this case, it enters the lane by the $i^{th}$ gate, found with the constraint $y_{g,i}^{\alpha }=1$;
• If $w_{g,\left(i-1,i\right)}^{\alpha }=1$, vehicle $\alpha$ uses lane $g$ between gates $i-1$ and $i$, so if $w_{g,\left(i,i+1\right)}^{\alpha }=0$, the vehicle does not need to use lane $g$ between gates $i$ and $i+1$ and decides to leave the lane by the $i^{th}$ gate, found with the constraint $y_{g,i}^{\alpha }=1$;
• If $w_{g,\left(i-1,i\right)}^{\alpha }=w_{g,\left(i,i+1\right)}^{\alpha }=0$, vehicle α is on the main road between gates $i-1$ and $i$ and it stays on the main road between gates $i$ and $i+1$, so vehicle $\alpha$ does not use gate $i$ and involves $y_{g,i}^{\alpha }=0$. The same case $\left(y_{g,i}^{\alpha }=0\right)$ if $w_{g,\left(i-1,i\right)}^{\alpha }=w_{g,\left(i,i+1\right)}^{\alpha }=1$.

Constraints (11) and (12) replace constraints (10) at the first and the last gates of each active charging lane.

To determine the open gates of each lane, constraints (13) and (14) are used:

$$y_{g,i}^{\alpha }\le P_i^g \forall \alpha ϵ\phi , \forall g ϵ N^A, \forall i=1,\dots ,N_{g }$$

(13)

$$P_i^g\le {\displaystyle \sum }_{\alpha =0}^{\left|\phi \right|}{y}_{g,i}^{\alpha } \forall g ϵ N^A , \forall i=1,\dots ,N_{g }$$

(14)

If there is at least one $\alpha ϵ \phi$, such that$y_{g,i}^{\alpha }=1$, there is at least one vehicle type that uses the $i^{th}$ gate of lane $g$; this implies that gate $i$ must be open, according to constraint (13) $\left(1\le P_i^g\right)$.

In the same context, if $y_{g,i}^{\alpha }=0$ for all $\alpha ϵ \phi$, no one vehicle type uses the $i^{th}$ gate of lane $g$; this implies that gate $i$ must be closed, found with constraint (14) $\left(P_i^g\le 0\right)$. Then, constraints (13) and (14) ensure that the $i^{th}$ gate of lane $g$ is opened if, and only if, at least one type of vehicle $\alpha$ uses it.

In order to avoid the opening of two successive potential gates on the same charging lane, a necessary number of gates to be closed between two successive gates is chosen, and the open gates must satisfy the following constraint:

$${\displaystyle \sum }_{i=k}^{\rho +k}{P}_i^g\le 1 \forall g ϵ N^A; \forall k=1,\dots ,N_g-\rho$$

(15)

Vehicles can slow down to gain additional charging time; constraint (16) ensures that the travel time between two successive gates of each vehicle type on the active lane is no greater than the maximum allowable travel time ${\delta }_{g,\left(i,j\right)}^{\alpha }$:

$$\begin{gathered} (t_{g,i+1}^{\alpha }-t_{g,i}^{\alpha }) w_{g,\left(i,i+1\right)}^{\alpha }\le {\delta }_{g,\left(i,i+1\right)}^{\alpha } \forall \alpha ϵ\phi , \forall g=1,\dots ,N, \\ \forall i=1,\dots ,N_g-1 \end{gathered}$$

(16)

In this case, the recharge duration is limited to a maximum duration to avoid the issue of overload, which results in an additional recharge cost; i.e., each vehicle has a maximum recharging time in the recharging lane.

3.4. Objective Function

The first objective in this paper is to minimize the total usage cost of charging lanes for each vehicle type, which is represented by:

$$\min {\displaystyle \sum }_{\alpha ϵ\phi }UU{C}^{\alpha }\times {\displaystyle \sum }_{g=1}^N{\displaystyle \sum }_{i=1}^{N_g-1}{w}_{g,\left(i,i+1\right)}^{\alpha }\times \left(t_{g,i+1}^{\alpha }-t_{g,i}^{\alpha }\right)$$

(17)

where $UU{C}^{\alpha }$ is the unit usage cost of vehicle $\alpha$ for using an active charging lane. $t_{g,i+1}^{\alpha }-t_{g,i}^{\alpha }$ represents the charging time of vehicle $\alpha$ while using the $g^{th}$charging lane between gates $i$ and $i+1$ if $w_{g,\left(i,i+1\right)}^{\alpha }=1$. If not $(w_{g,\left(i,i+1\right)}^{\alpha }=0)$, the vehicle has not used the charging lane $g$ between gates $i$ and $i+1$; in this case, the objective function (17) will be zero for rank $i$.

The second objective is to minimize the total number of open gates in each active charging lane, which is obtained by the following function:

$$\min C\times {\displaystyle \sum }_{g=1}^N{\displaystyle \sum }_{i=1}^{N_g}{P}_i^g$$

(18)

where $C$ is the unit cost of opening a new gate; then, function (18) represents the total cost of the open gates on the road.

4. Problem Solving

In this work, the aim is to minimize the usage cost of the charging lanes for a fleet of heterogeneous vehicles during their trip on the highway. For this purpose, the goal is to create new entry and exit gates for each charging lane of the highway at the lowest cost. In this section, the problem is solved using the CPLEX optimizer for limited instances to validate the proposed mathematical model. The resolution approach to the problem using the NSGA-II metaheuristic is presented.

4.1. Problem Validation

CPLEX optimizer [16] provides flexible, high-performance mathematical programming solvers for linear programming, mixed integer programming, constraint programming, and quadratic constraint programming problems. These solvers include a distributed parallel algorithm for mixed-integer programming to take advantage of multiple computers to solve complex problems. Validating the model with data and constraints makes it possible to verify the operation of the constraints. Once a solution is found, the formulation checks whose constraints have been modelled so they can be alerted in case of error. To validate the mathematical model by CPLEX, some constraints are modified as follows:

Constraint (8) is replaced by the following constraints:

$$I^{\alpha }\left(t_{g,i}^{\alpha }\right)+{{\displaystyle \int }}_{t_{g,i}^{\alpha }}^{t_{g,i+1}^{\alpha }}(D^{\alpha }\left(t\right)\times \left(w_{g,\left(i,i+1\right)}^{\alpha }-1\right)+T^{\alpha }\left(t\right)\times w_{g,\left(i,i+1\right)}^{\alpha })dt\ge E_{up}^{\alpha } \Rightarrow I^{\alpha }\left(t_{g,i+1}^{\alpha }\right)=E_{up}^{\alpha }$$

(19a)

$$I^{\alpha }\left(t_{g,i}^{\alpha }\right)+{{\displaystyle \int }}_{t_{g,i}^{\alpha }}^{t_{g,i+1}^{\alpha }}(D^{\alpha }\left(t\right)\times \left(w_{g,\left(i,i+1\right)}^{\alpha }-1\right)+T^{\alpha }\left(t\right)\times w_{g,\left(i,i+1\right)}^{\alpha })dt<E_{up}^{\alpha } \Rightarrow$$

$$I^{\alpha }\left(t_{g,i+1}^{\alpha }\right)=I^{\alpha }\left(t_{g,i}^{\alpha }\right)+{{\displaystyle \int }}_{t_{g,i}^{\alpha }}^{t_{g,i+1}^{\alpha }}(D^{\alpha }\left(t\right)\times \left(w_{g,\left(i,i+1\right)}^{\alpha }-1\right)+T^{\alpha }\left(t\right)\times w_{g,\left(i,i+1\right)}^{\alpha })dt$$

(19b)

To complete the linearization process, constraint (12) is replaced with the equivalent following constraints:

$$w_{g,\left(i-1,i\right)}^{\alpha }\ne w_{g,\left(i,i+1\right)}^{\alpha } \Rightarrow y_{g,i}^{\alpha }=1$$

(20a)

$$w_{g,\left(i-1,i\right)}^{\alpha }=w_{g,\left(i,i+1\right)}^{\alpha } \Rightarrow y_{g,i}^{\alpha }=0$$

(20b)

The other constraints remain the same.

4.1.1. Transport Network Data

To solve the problem by the CPLEX optimizer, the road between the origin O and destination S is 7500 m, and four types of vehicles need to travel from O to S without remaining out of charge by the minimum infrastructure cost. The segment of length 100 m is a reference unit and the necessary data relative to each segmentation used during the resolution are deducted.

Table 1. Vehicle data.

	Vehicle 1	Vehicle 2	Vehicle 3	Vehicle 4
$\mathrm{Energy} \mathrm{supply} \mathrm{rate} \mathrm{in} \mathrm{each} \mathrm{segment} (\mathrm{k}\mathrm{w})$	4.2	3	5	5.5
$\mathrm{Energy} \mathrm{consumption} \mathrm{rate} \left(\mathrm{k}\mathrm{w}\mathrm{h}/100 \mathrm{k}\mathrm{m}\right)$	25.2	19.6	19.5	34.7
$E_{up}^{\alpha }$	8	17.8	13.8	20
$E_{low}^{\alpha }$	2.7	3.8	5.7	4
Unit cost for using the DWCS road	12.5	8.5	10	14

and

Table 2. Lane data.

Lane Number	Length	Lane Status	Potential Gates Number
1	500	Inactive	0
2	750	Active	4
3	500	Inactive	0
4	500	Active	4
5	500	Inactive	0
6	1000	Active	4
7	750	Inactive	0
8	500	Active	4
9	500	Inactive	0
10	1000	Active	4
11	250	Inactive	0
12	250	Active	4
13	500	Inactive	0

contain the energy supply rate, the energy consumption rate of each vehicle type, and the other data.

The validation of the proposed mathematical model with the CPLEX optimizer was based on the same example used by Bourzik and EL Hilali Aaloui [3]. They considered a road between the origin O and destination S to be 7500 m, and four vehicle types that needed to travel from O to S.

To ensure the trip of the four vehicles without remaining out of charge by the minimum infrastructure cost, they discretized the road into a segment length of 200 m and determined the active and inactive segments according to vehicle load constraints. The results found in [3] were used to produce the active and the inactive charging lanes of the example. Table 1 and Table 2 contain the energy supply rate, the energy consumption rate of each vehicle type, the unit cost for using the charging lanes, the lane’s status, and other data.

Each active charging lane has principal entry and exit gates, and the access road of each active lane is discretized into potential gates. As the example has four vehicle types, four potential gates in each active charging lane are used to allow each vehicle type to exit the charging lane before the principal exit gate if it minimizes its T.U.C. Let $C=1000$ be the unit cost of opening a new gate.

4.1.2. Results

The problem is solved for each of the objectives, because CPLEX can only solve mono-objective problems. The first objective is to minimize the total usage cost (T.U.C) of each vehicle type, and the second objective is to minimize the number of open gates on the road.

The blue column in

Table 3. Results for each objective.

	Minimizing the T.U.C	Minimizing the Open Gates
Total cost of open gates on the road	19,000	0
T.U.C of vehicle 1	137.5	312.5
T.U.C of vehicle 2	127.5	212.5
T.U.C of vehicle 3	150	250
T.U.C of vehicle 4	126	294

presents the total cost of open gates on the road, and the T.U.C of each vehicle type of the solution found with the objective of minimizing the T.U.C for vehicles. In this case, the total cost of open gates is equal to 19,000, and the T.U.Cs for vehicles 1, 2, 3, and 4 equal 137.5, 127.5, 150, and 126, respectively. The green column provides the results, with the main objective being minimizing the number of open gates on the road. In this solution, the total cost of an open gate on the road is equal to zero, and the T.U.Cs for vehicles 1, 2, 3, and 4 equal 137.5, 127.5, 150, and 126, respectively.

To ensure the trip of each vehicle type without remaining out of charge and based on the minimum usage cost, the gate cost is 19,000, which is the cost to create 19 gates on the road. On the other hand, each vehicle type uses the gates depending on the battery state. Due to the heterogeneity of batteries, each vehicle type uses a set of gates to minimize its T.U.C; for this reason, the number of gates on the road increases.

In the case of minimizing the set of gates on the road, the number of gates found was 0 on the road because the main entry and the exit gates of each charging lane can ensure the trip of the vehicles without remaining out of charge. The T.U.C of each vehicle type increases in this case because the vehicles will have to use the full active charging lanes.

4.2. Approach to Solving the Problem

In the previous section, the problem was solved for limited instances and for each one of the objectives using the CPLEX optimizer. In this section, the non-dominated sorting genetic algorithm NSGA-II is adopted to solve the problem, and the main steps of the method and its application to the problem are described.

4.2.1. NSGA-II

NSGA-II is a modified version of the NSGA algorithm [17]. The crossover, recombination, and mutation operators (see [18] and [19] for more details) allow the creation of a daughter population Q0 with the same size as the parent population P0. Moreover, the ranking of equally dominant individuals is based on a dispersion measure called crowding distance [20]. Algorithm 1 represents the main steps of NSGA-II (more details in [21]).

Algorithm 1: NSGA-II

1. $\mathrm{t} \leftarrow 0$   2. While $t<$$\mathrm{M} \mathbf{do}$   3. ${\mathit{R}}_{\mathit{t}}\leftarrow {\mathit{P}}_{\mathit{t}} {\displaystyle \cup } {\mathit{Q}}_{\mathit{t}}$   4. $\mathit{F} \leftarrow$$\mathrm{fast}-\mathrm{non}-\mathrm{dominated}-\mathrm{sort} ({\mathit{R}}_{\mathit{t}})$   5. ${\mathit{P}}_{\mathit{t}+\mathbf{1}}\leftarrow \varnothing$   6.$\mathrm{i} \leftarrow \mathbf{0}$   7.$\mathbf{While} \left|{\mathit{P}}_{\mathit{t}+\mathbf{1}}\right|$$+\left|{\mathit{F}}_{\mathit{i}}\right|$$\ge \mathit{N}$$\mathit{do}$   8.${\mathit{P}}_{\mathit{t}+\mathbf{1}}\leftarrow {\mathit{P}}_{\mathit{t}+\mathbf{1}}{\displaystyle \cup } {\mathit{F}}_{\mathit{i}}$   9. Apply crowding-distance-assignment ${\mathit{F}}_{\mathit{i}}$   10.$\mathrm{i} \leftarrow \mathit{i}+\mathbf{1}$   11.$\mathbf{end} \mathbf{while}$   12.$\mathrm{sort} ({\mathit{F}}_{\mathit{i}},<\mathit{n})$   13.${\mathit{P}}_{\mathit{t}+\mathbf{1}}\leftarrow {\mathit{P}}_{\mathit{t}+\mathbf{1}}{\displaystyle \cup }{\mathit{F}}_{\mathit{i}}\left[\mathbf{1}:\left(\mathit{N}-\left|{\mathit{P}}_{\mathit{t}+\mathbf{1}}\right|\right)\right]$   14.${\mathit{Q}}_{\mathit{t}+\mathbf{1}}\leftarrow$$\mathrm{create} \mathrm{new} \mathrm{population} ({\mathit{P}}_{\mathit{t}+\mathbf{1}})$   15. $\mathrm{t}\leftarrow \mathit{t}+\mathbf{1}$   16. end while

The population Pt necessarily converges to a set of points on the Pareto front, as non-dominated solutions are preserved across generations. Furthermore, the dispersion criterion (crowding distance) guarantees good population diversity [22].

4.2.2. Crowding Distance (CD)

The crowding distance operator [23] guides the selection process to a uniformly expanding Pareto optimal front at various stages of the algorithm. This subroutine was used to compare other members of the United Front. In other words, the CD was for sorting a specific front end. According to Formula (21), calculate the number of CDs of each member compared with the next and previous members and the first and last members (illustrated in Figure 8) [24].

$$d_{ij}=\frac{\left|f_1^i-f_1^j\right|}{f_1^{max}-f_1^{min}}, d_{ik}=\frac{\left|f_2^i-f_2^k\right|}{f_2^{max}-f_2^{min}}, C{D}_i=d_{ij}+d_{ik}$$

(21)

It is worth noting that, to obtain the best answer, the answer needs to be placed and distributed regularly on the Pareto front. The higher the magnitude of CD, the more regular the order of responses in the Pareto front. Therefore, a higher CD amount means a priority standard for each member compared with others on the same front. When calculating the CD of the first and last members [25], it is worth noting that the CD of the previous member to the first member is assumed to be ∞, and the CD of the next member is assumed to be +∞. Therefore, the CD of these points is ∞: this means that, between two chromosomes with different non-dominant ranks, the lower-rank answer is selected. Otherwise, if both answers belong to the same frontier, the answer in the region with the lower number of answers is selected.

4.3. Application of the NSGA-II

This section presents the application of the NSGA-II algorithm to the problem. For this, different steps of NSGA-II are defined in this case:

4.3.1. Encoding Strategy

To adopt the approximated methods, this work considers that a solution to the problem is described as follows:

• Open gates in each charging lane of the road are coded in the form of a chromosome with a matrix$\left(N\times N_i\right)$, noted $A={\left(a_{ij}\right)}_{i=1\dots N}^{j=1\dots N_i}$ with:

  $$a_{ij}=\{\begin{array}{l}1 if the j{ }^{th} gate of the lane i is open \\ 0 otherwise \end{array}$$

  where $N$ is the number of charging lanes on the road and $N_g$ is the number of gates on charging lane $i$. The number of columns of $A$ depends on$N_g$, which differs from one charging lane to another; so, to generate $A$, let $N{N}_i$ be the number of columns of the matrix $A$, with $N{N}_i=\underset{1\le i\le 1}{\mathit{max}}{N}_g$, so $A={\left(a_{ij}\right)}_{i=1\dots N}^{j=1\dots N{N}_i}$ and $a_{ij}=0 \forall N_i<N{N}_i$.

As mentioned previously, each active charging lane has principal entry and exit gates, which must open; for this, $a_{i1}=U_i$ and $a_{i{N}_i}=U_i \forall i=1\dots N$. Figure 9 shows an example of the open gate matrix with six charging lanes and five potential gates, $U_2=1$, $U_4=1$, and $U_6=1$.

• The used gates of each vehicle type is a table noted by B =${\left(b_{kij}\right)}_{j=1\dots N_i}^{\begin{array}{c}k=1\dots \left|\phi \right|\\ i=1\dots N\end{array}}$, with:

  $$b_{kij}=\{\begin{array}{l}1 if the vehicle k use the j^{th} gate of the lane i\\ 0 otherwise\end{array}$$

This part of the solution is feasible if each type of vehicle leaves the DWCS road after using the active charging lane. As the vehicles begin the trip from the main road, the first use of each potential gate means that the vehicle enters the DWCS road, and the second use of the following potential gate means that the vehicle uses the gate to exit the DWCS road. For this, this part of the solution is feasible if, and only if, ${\displaystyle \sum }_{j=1}^{N_i}{b}_{kij}$ is an even number for all $k ϵ \phi$ and $i=1,\dots , N$.

4.3.2. Initial Population

Before generating a population, it is necessary to generate an individual. In this case, a vehicle type is randomly selected and ensures its trip on the road while respecting the model’s constraints. For the second iteration, another vehicle type is randomly selected and verified if the last type’s open gates ensure the selected vehicle’s trip without remaining out of charge; if not, the procedure opens another gate for the vehicle until the model constraints are met. The procedure stops when all of the vehicles can complete the trip without remaining out of charge.

The procedure consists of testing at each iteration whether the gates used by the last vehicles can ensure the travel of the selected vehicle without remaining out of load in order to minimize the number of open gates for each individual using Algorithm 2.

Let:

• $S$ be the set of selected vehicles;
• $\phi$ be the set of vehicles indexed by $\alpha$;
• $X$ be the set of open gates;
• $P$ be the set of the potential gates indexed by $i$ and $p$;
• $G$ be the set of the charging lane indexed by $g$.

Algorithm 2: Generation of an individual

17.$\mathit{S}=\varnothing$$, \mathbf{X}=\varnothing$   18. for each vehicle $\mathbf{\alpha }$   19.$\mathbf{While} \mathit{S}=\varnothing$ do:   20. $\mathbf{Choose} \mathbf{randomly} \mathbf{a} \mathbf{vehicle} \mathit{\alpha } \mathit{ϵ} \mathit{\phi }$$\mathbf{and} \mathit{\alpha }\mathbf{\notin } \mathit{S}$   21. If the $\mathit{X}$ ensures the trip of the $\mathit{\alpha }$ without remaining out of charge   22. $\mathit{S}=\mathit{S} {\displaystyle \cup }\left\{\mathit{\alpha }\right\}$   23. Else   24. for each charging lane $\mathit{g}$   25. for each potential gate $\mathit{i}$   26. $\mathbf{If} {\mathit{I}}^{\mathit{\alpha }}\left({\mathit{t}}_{\mathit{g},\mathit{i}}^{\mathit{\alpha }}\right)<$${\mathit{I}}_{\mathit{l}\mathit{o}\mathit{w}}^{\mathit{\alpha }}$ and $\mathit{g}$ is active   27. Make the gate $\mathit{i}$$\mathbf{open} \mathbf{and} \mathit{X}=\mathit{X}{\displaystyle \cup }\left\{ \mathit{i} \right\}$   28. end if   29. else if $\mathit{g}$ is inactive   30. $\mathbf{do}: \mathit{p}=\mathbf{1}$   31. $\mathbf{If} \mathbf{the} \mathbf{gate} \mathit{p}$$\mathbf{of} \mathbf{the} \mathbf{lane} \mathit{g}-\mathbf{1}$ is closed   32. Make $\mathit{p}$$\mathbf{open} \mathbf{and} \mathit{X}=\mathit{X}{\displaystyle \cup }\left\{ \mathit{p} \right\}$$\mathbf{and} \mathit{p}=\mathit{p}+\mathbf{1}$   33. end if   34. $\mathbf{while} ({\mathit{I}}^{\alpha }\left({\mathit{t}}_{\mathit{g},\mathit{i}}^{\alpha }\right)<$ ${\mathit{I}}_{\mathit{l}\mathit{o}\mathit{w}}^{\mathit{\alpha }})$   35. end if   36. else Make $\mathit{i}$ closed   37. end for   38. end for   39. end while   40. end for

4.3.3. Crossover Procedure

The open gates in each charging lane and the usage gates of each vehicle type represent the individual in the problem; for this purpose, the crossover used in this work is conducted in two parts. The first part is a crossing for two matrices of the open gates of charging lanes $A_1$ and $A_2$ of two individuals’ parents $P_1$ and $P_2$. The second part is a crossing of two tables of the usage gates of vehicles T₁ and T₂; the proposed crossing procedure is described below:

-

For the first part of the crossover:

A crossing point $h$ is randomly chosen for each charging lane in the interval $\left[0,Ni\right]$, and then exchange the first $h$ boxes of the gates between the two parents to generate the matrices $CxA1$ and $CxA2$ of two children, C1 and C2, respectively (see Figure 10).

The table $CxB1$ (resp. $CxB2)$ of the usage gates of the vehicles of each child C1 (resp. C2) is generated so that each vehicle type uses the necessary open gates in the matrices $CxA1$ (resp. $CxA2$) to not remain out of charge. The part colored in blue in$CxA1$ generated from A2 of P2 and the part colored in white generated from A1 of P1, and the same for $CxA2$.

To verify the feasibility of these new individuals, C1 and C2, the heuristic illustrated in the following algorithm is used:

-

For the second part of the crossover:

For each vehicle type $\alpha$, a crossing point $k$ is randomly chosen for each charging lane in the interval $\left[0,Ni\right]$, and then the first $h$ boxes of the matrices $B$ are exchanged between the two parents to generate the matrices $CxB1$ and $CxB2$ of children C1 and C2, respectively.

Table $CxA1$ (resp. $CxA2)$ of the open gates in each charging lane of child C1 (resp. C2) is generated so that each potential gate is open if it is used by at least one vehicle.

To verify the feasibility of these new individuals, C1 and C2, the heuristic illustrated in algorithm 3 is used.

Algorithm 3: Correction Algorithm

1. for each vehicle $\alpha$   2. for each charging line $\mathit{g}$   3. for each potential gate $\mathit{i}$   4. If ${\mathit{I}}^{\mathit{\alpha }}\left({\mathit{t}}_{\mathit{g},\mathit{i}}^{\mathit{\alpha }}\right)<$ ${\mathit{I}}_{\mathit{l}\mathit{o}\mathit{w}}^{\mathit{\alpha }}$ and $\mathit{g}$ is active   5. Make the gate $\mathit{i}$ open   6. end if   7. else   8. if $\mathit{g}$ is inactive   9. $\mathbf{do}: \mathit{p}=\mathsf{1}$   10. $\mathbf{If} \mathbf{the} \mathbf{gate} \mathit{p}$$\mathbf{of} \mathbf{the} \mathbf{lane} \mathit{g}-\mathbf{1}$ is closed   11. Make $\mathit{p}$$\mathbf{open} \mathbf{and} \mathit{p}=\mathit{p}+\mathsf{1}$   12. end if   13. $\mathbf{while} ({\mathit{I}}^{\mathit{\alpha }}\left({\mathit{t}}_{\mathit{g},\mathit{i}}^{\mathit{\alpha }}\right)<$${\mathit{I}}_{\mathit{l}\mathit{o}\mathit{w}}^{\mathit{\alpha }})$   14. end if   15. end for   16. end for   17. end for

4.3.4. Mutation Procedure

The principle of crossing consists of changing two parts of two individuals to create two other children, and the reproduction using only this operator can produce a local optimum solution. The mutation operator is applied in this work to explore the search space. This makes it possible to obtain another very different solution and therefore diversifies the search space. The choice of genes is conducted randomly in each charging lane of matrix A, and the open gates of the selected lanes are modified to keep the remaining charge of each vehicle type between the minimum charge $I_{low}^{\alpha }$ and the maximum charge $I_{up}^{\alpha }$. In the example of Figure 11 the modified genes are colored in sky blue

4.3.5. Case Study

Morocco highway (Meknes–Fez) (see Figure 12) is used in this study as a case study. Five vehicle types are chosen to begin the journey from Meknes to Fez. This study focuses on determining the minimum gates on the road to ensure the trip of each vehicle type by the minimum usage cost:

4.3.6. Transport Network Data

The objective in this paragraph is to install a set of gates on the DWCS road to organize the use and the payment of the use of charging lanes by the vehicles. The first step to achieving the goal is to build the DWCS infrastructure for the electric vehicles with the minimum cost using the model of Bourzik and EL Hilali Aaloui [3]. As mentioned previously, their method consists of discretizing the road into segments with the same length, then determining, according to the battery state of each vehicle, the active and the inactive segments. The length of the Morocco highway A-B is 60 km. The road was discretized into segments of 250 m, the first segment noted by 1 and the last noted by 240. As mentioned, successive active (inactive) segments form an active (inactive) charging lane.

Table 4. Active and inactive lanes.

Seg. No	Seg. Status	Lane No.	Lane Status	Seg. No	Seg. Status	Lane No.	Lane Status
1-2	Inactive	$1$	Inactive	144	Inactive	57	Inactive
3-4-5-6-7-8-9-10	Active	2	Active	145-146-147-148-149	Active	58	Active
11-12	Inactive	3	Inactive	150	Inactive	59	Inactive
13-14	Active	4	Active	151	Active	60	Active
15	Inactive	5	Inactive	152	Inactive	61	Inactive
16	Active	6	Active	153	Active	62	Active
17	Inactive	7	Inactive	154	Inactive	63	Inactive
18-19-20-21	Active	8	Active	155-156-157	Active	64	Active
22	Inactive	9	Inactive	158	Inactive	65	Inactive
23	Active	10	Active	159-160-161	Active	66	Active
24	Inactive	11	Inactive	162	Inactive	67	Inactive
25-26	Active	12	Active	163-164-165-166-167-168	Active	68	Active
27	Inactive	13	Inactive	169	Inactive	69	Inactive
28	Active	14	Active	170	Active	70	Active
29	Inactive	15	Inactive	171	Inactive	71	Inactive
30	Active	16	Active	172-173	Active	72	Active
31	Inactive	17	Inactive	174	Inactive	73	Inactive
32	Active	18	Active	175	Active	74	Active
33	Inactive	19	Inactive	176	Inactive	75	Inactive
34-35-36-37-38-39-40	Active	20	Active	177	Active	76	Active
41	Inactive	21	Inactive	178	Inactive	77	Inactive
42-43	Active	22	Active	179-180	Active	78	Active
44-45	Inactive	23	Inactive	181	Inactive	79	Inactive
46-47-48-49	Active	24	Active	182-183	Active	80	Active
50	Inactive	25	Inactive	184	Inactive	81	Inactive
60-70-71-72	Active	26	Active	185	Active	82	Active
73-74	Inactive	27	Inactive	186	Inactive	83	Inactive
75-76	Active	28	Active	187	Active	84	Active
77-78-79	Inactive	29	Inactive	188	Inactive	85	Inactive
80-81-82-83	Active	30	Active	189-190-191-192	Active	86	Active
84-85	Inactive	31	Inactive	193-194	Inactive	87	Inactive
86-87	Active	32	Active	195-196-197	Active	88	Active
88	Inactive	33	Inactive	189-190	Inactive	89	Inactive
89-90-91-92-93-94	Active	34	Active	191-192-193-194	Active	90	Active
95	Inactive	35	Inactive	195-196	Inactive	91	Inactive
96-97-98-99	Active	36	Active	197-198-199-200-201-202-203-204-205	Active	92	Active
100	Inactive	37	Inactive	206-207	Inactive	93	Inactive
101-102-103	Active	38	Active	208-209-210	Active	94	Active
104	Inactive	39	Inactive	211	Inactive	95	Inactive
105-106-107-108-109-110-111-112-113	Active	40	Active	212-213	Active	96	Active
114-115	Inactive	41	Inactive	214	Inactive	97	Inactive
116-117-118	Active	42	Active	215-216-217	Active	98	Active
119	Inactive	43	Inactive	218	Inactive	99	Inactive
120-121-122-123-124-125	Active	44	Active	219-220-221-222-223-224-225	Active	100	Active
126	Inactive	45	Inactive	226-227	Inactive	101	Inactive
127	Active	46	Active	228-229-230-231	Active	102	Active
128	Inactive	47	Inactive	232	Inactive	103	Inactive
129-130	Active	48	Active	233-234	Active	104	Active
131-132	Inactive	49	Inactive	235	Inactive	105	Inactive
133-134	Active	50	Active	236-237-238-139	Active	106	Active
135	Inactive	51	Inactive	240	Inactive	107	Inactive
136	Active	52	Active
137	Inactive	53	Inactive
138-139-140	Active	54	Active
141	Inactive	55	Inactive
142-143	Active	56	Active

shows the active and inactive segments found by Bourzik and EL Hilali Aaloui’s model and the status of each charging lane of the used instances.

Each active charging lane has a principal entry and exit gate, and the access road of each active lane is discretized into potential gates. It is assumed that each charging lane has five potential gates, because the case study uses five vehicle types on the road.

Table 5. Vehicle data.

	Battery Capacity ${\mathit{I}}_{\mathit{b}\mathit{a}\mathit{t}}^{\mathit{\alpha }}\left(\mathbf{k}\mathbf{w}\right)$	Energy Supply Rate	Energy Consumption Rate $\left(\mathbf{k}\mathbf{w}\mathbf{h}/100 \mathbf{k}\mathbf{m}\right)$	Unit Cost for Using the DWCS Road
Vehicle 1	7.6	1.1	29.5	13.5
Vehicle 2	42.2	0.9	17.8	11
Vehicle 3	11.6	1.3	30.6	17
Vehicle 4	18.4	0.4	19.5	9
Vehicle 5	16	1.2	25.8	15

and

Table 6. Number of open gates in each charging lane for solution 1.

Lane No.	PG Number	Open Gates Number	Lane No.	PG Number	Number of Open Gates
2	40	6	56	10	2
4	10	2	58	25	3
6	5	0	60	5	0
8	20	3	62	5	0
10	5	1	64	15	2
12	10	2	66	15	2
14	5	0	68	30	4
16	5	0	70	5	0
18	5	1	72	10	2
20	35	5	74	5	0
22	10	2	76	5	0
24	20	5	78	10	2
26	20	3	80	5	0
28	10	3	82	5	0
30	20	6	84	5	1
32	10	1	86	20	3
34	30	6	88	15	2
36	20	5	90	20	5
38	15	4	92	45	5
40	45	7	94	15	2
42	15	5	96	10	1
44	30	4	98	15	2
46	5	0	100	35	4
48	10	1	102	20	3
50	10	2	104	10	1
52	5	0	106	20	4
54	15	3

contain the energy supply rate, the energy consumption rate of each vehicle type, and the other data.

4.3.7. Experimental Results

Before generating the results presented in this section, the paper began by explaining the problem of finding the optimal location of the power transmitter’s gates on the highway to ensure the trip of a fleet of heterogeneous vehicles with the minimum total usage cost (T.U.C) for each type. The objectives considered are minimizing the usage cost paid by each vehicle type to use the DWC during the trip on the highway and finding the lowest installation cost of the gates on the road. Then, the work presented the mathematical modelling of the problem and the validation using the Cplex optimizer with limited instances. This study applied the non-dominated sorting genetic algorithm (NSGA-II) for real large instances. NSGA-II was implemented using C++ language on a Windows 10 Professional Intel(R) Xeon(R) W 2155 CPU (20 CPUs) at 2.5 GHz, with 8 G.B. of RAM.

The solutions provided by NSGA-II are Pareto solutions. During the resolution of the problem, the best front of NSGA-II provides six solutions shown in Figure 13, where F1 represents the cost of the open gates on the road and F2 represents the T.U.C. Two solutions were used for the discussion; solution 1 had the minimum cost of the open gates on the road, and solution 2 had the minimum T.U.C. of each vehicle type. Table 6 and

Table 7. Number of open gates in each charging lane for solution 2.

Lane No.	PG Number	Number of Open Gates	Lane No.	PG Number	Number of Open Gates
2	40	8	56	10	4
4	10	4	58	25	2
6	5	0	60	5	1
8	20	4	62	5	0
10	5	1	64	15	2
12	10	2	66	15	3
14	5	0	68	30	4
16	5	0	70	5	1
18	5	1	72	10	3
20	35	7	74	5	1
22	10	3	76	5	0
24	20	6	78	10	2
26	20	3	80	5	1
28	10	4	82	5	0
30	20	7	84	5	1
32	10	3	86	20	2
34	30	6	88	15	2
36	20	6	90	20	6
38	15	3	92	45	7
40	45	8	94	15	1
42	15	3	96	10	1
44	30	5	98	15	1
46	5	1	100	35	5
48	10	1	102	20	2
50	10	3	104	10	2
52	5	1	106	20	3
54	15	3

present the numbers of open gates provided by the first and the second solutions, respectively, and

Table 8. T.U.C of each vehicle type.

	T.U.C of Solution 1	T.U.C of Solution 2
Vehicle 1	7020	6001
Vehicle 2	4129	4059
Vehicle 3	7803	6038
Vehicle 4	3960	3010
Vehicle 5	7425	6393

presents the T.U.C. of each vehicle type in the first and the second solutions.

Table 6 and Table 7 present the number of open gates in each active charging lane for the first and the second solutions, respectively. Table 8 shows the cost of the open gates and T.U.Cs of each vehicle type for the selected solutions (solutions 1 and 2).

The total number of open gates in the first solution was 226 with the main entry and exit gates, and the total cost was 226,000. Compared with the second solution, which gave 249,000 as the cost of the open gates, the first solution found the best case for the open gates on the road. However, the second solution had the minimum T.U.C of the vehicles compared with the first. It is remarked that, when the T.U.C decreased in the second solution, the total number of open gates in the road increased compared with the first solution. This phenomenon is logical, because if the T.U.C is reduced in the second solution, each vehicle type uses a set of gates to minimize its T.U.C. Owing to the heterogeneity of the vehicles, the set of gates used by each vehicle type differed from one vehicle to another. For this purpose, the number of gates increased in this case (second solution), which improved the reality of the results. On the other hand, when the number of open gates on the road decreased (solution 1), the search space for gates to be used for each vehicle decreased; because of this, the T.U.C of some vehicles increased (solution 2).

Table 9. T.U.Cs of the vehicles and the open gates cost in solution 0.

	T.U.C	Open Gate Cost
Vehicle 1	12,920	215,000
Vehicle 2	8514
Vehicle 3	15,096
Vehicle 4	6960
Vehicle 5	13,230

presents the cost of the total gates on the road and the T.U.C of each vehicle if the gates are installed only at the beginning and the end of each active segment in the infrastructure found in [3] (Table 5), which is noted as solution 0.

The open gate cost in solution 0 was 215,000, which was a little lower than the costs found for solutions 1 and 2. This result was expected, because solution 0 was developed in a way to minimize the number of active segments, which minimized the number of open gates placed at the beginning and end of the active segments, demonstrating the reality of the results found by the NSGA-II. On the other hand, there was a significant rise in the T.U.C in solution 0, demonstrating the efficacy of the results. The T.U.C increased in solution 0 because the vehicles in this solution would be required to use the active segments completely, even if their battery saturated before the principal exit gate at the end of the segment.

Figure 14 shows the use of the open gates according to the number of vehicles in solutions 1 and 2. In solution 1, 69 gates were used by four vehicles, 60 gates were used by three vehicles, 41 gates were used by five vehicles, and the other gates were used by two or one vehicle. Most of the open gates were used by at least three or four vehicles, which corresponds to reality because, if a gate is open, the best case to minimize the number of gates on the road is to have them be usable by all or the maximum number of types of vehicles. In solution 2, 40 gates were used by one vehicle and 52 gates were used by two vehicles; compared with the first solution, the number of gates used by one or two vehicles was higher in the second solution. For this purpose, the second solution provided a lower T.U.C of vehicles because it allowed a somewhat significant number of vehicles to use the gates to minimize their T.U.C; however, the number of open gates comparatively increased in this solution.

5. Conclusions

This work treats the problem of the optimal deployment of the entry and exit gates of wireless electric vehicle charging transmitters on highways. The study considered the T.U.C as a new factor in the problem as electric vehicles’ batteries drain very quickly on highways due to the high speed and the long distance between the origin and the destination, which increases the usage cost of DWCSs for vehicles. The heterogeneity of the battery vehicles adds more difficulty to finding the optimal locations of gates because each has its characteristics. For this purpose, the study introduced a mathematical model with constraints, which aimed to find the best location of a set of gates in the wireless power transmitters that allowed a heterogeneous fleet of vehicles to travel on the highway at the minimum usage cost. The non-dominated sorting genetic algorithm was adopted to solve the problem and demonstrate the model’s application; the paper considered the Morocco highway (Meknes–Fez) as a case study. This work used static data; for example, it was assumed that there was no heavy traffic in the charging lanes, which would influence the time required for a full battery recharge. Therefore, integrating random factors in a stochastic study will be a continuation of this study. Additionally, building mixed wireless charging infrastructure, static and dynamic, would be more challenging, ensuring a vehicle trip with the minimum usage cost.