# The Energy-Efficient Dynamic Route Planning for Electric Vehicles

Authors: Wenjuan Zhou; Li Wang
Journal: Journal of Advanced Transportation
 (2019)

---

## Abstract

Aiming to provide an approach for finding energy-efficient routes in dynamic and stochastic transportation networks for electric vehicles, this paper addresses the route planning problem in dynamic transportation network where the link travel times are assumed to be random variables to minimize total energy consumption and travel time. The changeable signals are introduced to establish state-space-time network to describe the realistic dynamic traffic network and also used to adjust the travel time according to the signal information (signal cycle, green time, and red time). By adjusting the travel time, the electric vehicle can achieve a nonstop driving mode during the traveling. Further, the nonstop driving mode could avoid frequent acceleration and deceleration at the signal intersections so as to reduce the energy consumption. Therefore, the dynamically adjusted travel time can save the energy and eliminate the waiting time. A multiobjective 0-1 integer programming model is formulated to find the optimal routes. Two methods are presented to transform the multiobjective optimization problem into a single objective problem. To verify the validity of the model, a specific simulation is conducted on a test network. The results indicate that the shortest travel time and the energy consumption of the planning route can be significantly reduced, demonstrating the effectiveness of the proposed approaches.


---

## Body

## 1. Introduction

At present, with the problem of global energy shortage and environment pollution becoming more and more serious, it has gradually become the common choice of the world to improve the traditional high energy consumption and high-polluted development mode. Vigorously promoting energy saving and emission reduction to achieve sustainable development is also a hot spot of social concern (e.g., [1, 2]). Transportation is a series link of energy consumption and environmental pollution. Based on the characteristics of urban vehicle, EV is being popularized and applied in the field of urban traffic with the stimulation of various policy subsidies and demonstration operations (e.g., [3, 4]). Electric vehicle has become an important technical direction to promote the energy saving and emission reduction of vehicles [5].In the urban road network, the dynamic route planning can make full use of the real-time traffic information of the entire network to assist in decision-making (e.g., [6–8]). The intersection signal is an important part to reflect the dynamic of network, which has a periodical variation [9]. The real driving conditions of braking at intersection signals will influence the energy losses. Obviously, more energy is consumed at varying velocities than that at constant velocity. The frequent acceleration and braking process at intersection signals will undoubtedly increase both energy consumption and travel time. Therefore, we shall consider the intersection signals into the route planning problem and propose a nonstop dynamic route planning method to achieve the travel route with the shortest time and the lowest energy consumption.


### 1.1. Literature Review

Based on numerous contributions in route planning and the shortest path problem, this paper focuses on the energy-efficient routing planning problem. There exist various techniques for EV energy-efficient routing problem in literature. Chang et al. [10] proposed a vehicular-ad-hoc-network-based A∗ route planning algorithm to calculate the route with the shortest traveling time or the lowest energy consumption. Sachenbacher et al. [11] introduced a solution of energy-optimal routing for electric vehicles within the framework of A∗ search using heuristic routing algorithm. Schneider et al. [12] proposed the electric vehicle routing problem with time windows and battery charging stations to avoid inefficient vehicle routes with long detours. Fontana [13] developed an optimization formulation based on robust optimization in uncertainty and designed an efficient route searching algorithm for electric vehicles to address range anxiety. Abousleiman and Rawashdeh [14] developed a model to solve the single constraint optimization problem of finding the most energy-efficient route between two points with a particle swarm optimization algorithm. Shao et al. [15] proposed an electric vehicle routing problem with charging time and variable travel time using dynamic Dijkstra algorithm to find the shortest path between any two adjacent nodes along the routes. Lu et al. [16] analyzed the link travel times and speeds by the proposed generic agent-based eco-system optimal dynamic traffic assignment model to effectively generate time-dependent speeds for multiscale emission analysis and derive a formula of marginal emission to find system optimal eco-routing that minimizes total vehicular emission in a congested network.In the last several decades, lots of signal control problem and signal timing optimization have been proposed to provide priority to transit vehicles at signalized intersections. Aziz et al. [17] presented the system optimal approach for dynamic traffic assignment with an embedded traffic flow model and the signal control optimization considering intersection delay and lost time from phase switches in the objective function. Han et al. [18, 19] presented a traffic signal optimization problem to illustrate the unique advantages of applying the continuum signal model instead of the on-and-off model. Feng et al. [20] presented a real-time adaptive signal phase allocation algorithm using connected vehicle data to optimize the phase sequence and duration, which can minimize the total vehicle delay and the queue length. Li et al. [21] presented a new signal timing optimization approach to minimize the vehicles’ fuel consumptions utilizing the Lagrangian Relaxation. Liu et al. [22] presented a dynamical model of green-times (or red-times) in day-to-day rerouting considering a restricted proportional-switch adjustment process. Shi et al. [23] presented an optimization approach for jointly determining tram schedules in a single tram line and modifying signal timings at major controlled intersections, which minimize the total tram travel time and negative impacts of the transit signal priority.The advanced intelligent transportation system can receive real-time traffic information to provide a dynamic traffic environment to assist in decision-making (e.g., [24, 25]). It is obvious to contrast the advantages between the static route guidance and the dynamic route guidance. Besides, the dynamic route planning with variable travel time is closer to the reality. Yang and Zhou [26] addressed a class of two-stage routing models to measure travel time reliability, on-time arrival probability and percentile travel time in time-dependent transportation networks. Zhou et al. [27] and Ma et al. [28] studied a problem of designing trajectories of a platoon of vehicles on a highway segment with advanced connected and automated vehicle technologies that yield the optimum traffic performance measures on mobility, environment, and safety. Mahmassani et al. [29, 30] addressed the departure time and route switching decisions of occupant response to advanced traveler information system using dynamic interactive travel simulators to study user responses under real-time information. A dynamic traffic assignment (DTA) system for advanced traffic network management is also proposed to describe the evolution of traffic flow patterns under specific traffic measures in the network and the route guidance information supply strategy for individual drivers.


### 1.2. The Proposed Method

The literatures above have made great contributions in different fields, which provide inspirations to this paper. The energy-efficient dynamic route planning for electric vehicles is proposed. The main innovative contributions of this study are as follows.(1) Firstly, we introduce intersection signals to the dynamic road network. The intersection signals are changing periodically (in red light or green light), which can control the vehicles’ driving trajectory and influence the results of the dynamic route planning. Further, we establish the state-space-time network to describe the realistic road network. In comparison to traditional strategies, the state-space-time network reflects the dynamic characteristic not only on the link travel time but also on the node state.(2) Secondly, we try to control the travel velocity to achieve the nonstopping driving when the vehicles pass through the intersection signals. When the velocity varies greatly, the energy consumption will increase significantly. Therefore, if the vehicle stops at the intersection signals by the rules, it needs to decelerate from a certain velocity to 0 and then accelerates from 0 to a certain velocity, which will consume massive energy. By using nonstop driving mode, the waiting time at the signalized intersection is allocated to the driving process, which can avoid frequent starting and stopping at signalized intersections. To a certain extent, it will eliminate the drivers’ waiting anxiety and reduce the energy consumption in the driving process.(3) Thirdly, a multiobjective 0-1 integer programming model is formulated to find the optimal nonstop driving route in the state-space-time network. The two objective of travel time and energy consumption are considered in this paper. Then, we adopt two methods of constrained shortest path (CSP) problem and membership functions by using fuzzy theory to transform the multiobjective into a single objective problem. The experiment results indicate that the nonstop driving mode proposed in this paper can save the energy and eliminate the waiting time.The rest of paper is organized as follows. Section2 gives a detailed problem statement, which compares the energy consumption between stop and nonstop driving process and further establishes a state-time-space network to find the shortest route. In Section 3, the mathematical model is formulated to optimize the travel route achieving minimum energy consumption and travel time. The energy consumption model proposed by Haaren [31] is used to calculate the object function. Section 4 provides an example to illustrate the proposed energy-efficient dynamic route planning approach and analyze the results of planning route. Finally, Section 5 concludes with an outline of future work directions.


## 1.1. Literature Review

Based on numerous contributions in route planning and the shortest path problem, this paper focuses on the energy-efficient routing planning problem. There exist various techniques for EV energy-efficient routing problem in literature. Chang et al. [10] proposed a vehicular-ad-hoc-network-based A∗ route planning algorithm to calculate the route with the shortest traveling time or the lowest energy consumption. Sachenbacher et al. [11] introduced a solution of energy-optimal routing for electric vehicles within the framework of A∗ search using heuristic routing algorithm. Schneider et al. [12] proposed the electric vehicle routing problem with time windows and battery charging stations to avoid inefficient vehicle routes with long detours. Fontana [13] developed an optimization formulation based on robust optimization in uncertainty and designed an efficient route searching algorithm for electric vehicles to address range anxiety. Abousleiman and Rawashdeh [14] developed a model to solve the single constraint optimization problem of finding the most energy-efficient route between two points with a particle swarm optimization algorithm. Shao et al. [15] proposed an electric vehicle routing problem with charging time and variable travel time using dynamic Dijkstra algorithm to find the shortest path between any two adjacent nodes along the routes. Lu et al. [16] analyzed the link travel times and speeds by the proposed generic agent-based eco-system optimal dynamic traffic assignment model to effectively generate time-dependent speeds for multiscale emission analysis and derive a formula of marginal emission to find system optimal eco-routing that minimizes total vehicular emission in a congested network.In the last several decades, lots of signal control problem and signal timing optimization have been proposed to provide priority to transit vehicles at signalized intersections. Aziz et al. [17] presented the system optimal approach for dynamic traffic assignment with an embedded traffic flow model and the signal control optimization considering intersection delay and lost time from phase switches in the objective function. Han et al. [18, 19] presented a traffic signal optimization problem to illustrate the unique advantages of applying the continuum signal model instead of the on-and-off model. Feng et al. [20] presented a real-time adaptive signal phase allocation algorithm using connected vehicle data to optimize the phase sequence and duration, which can minimize the total vehicle delay and the queue length. Li et al. [21] presented a new signal timing optimization approach to minimize the vehicles’ fuel consumptions utilizing the Lagrangian Relaxation. Liu et al. [22] presented a dynamical model of green-times (or red-times) in day-to-day rerouting considering a restricted proportional-switch adjustment process. Shi et al. [23] presented an optimization approach for jointly determining tram schedules in a single tram line and modifying signal timings at major controlled intersections, which minimize the total tram travel time and negative impacts of the transit signal priority.The advanced intelligent transportation system can receive real-time traffic information to provide a dynamic traffic environment to assist in decision-making (e.g., [24, 25]). It is obvious to contrast the advantages between the static route guidance and the dynamic route guidance. Besides, the dynamic route planning with variable travel time is closer to the reality. Yang and Zhou [26] addressed a class of two-stage routing models to measure travel time reliability, on-time arrival probability and percentile travel time in time-dependent transportation networks. Zhou et al. [27] and Ma et al. [28] studied a problem of designing trajectories of a platoon of vehicles on a highway segment with advanced connected and automated vehicle technologies that yield the optimum traffic performance measures on mobility, environment, and safety. Mahmassani et al. [29, 30] addressed the departure time and route switching decisions of occupant response to advanced traveler information system using dynamic interactive travel simulators to study user responses under real-time information. A dynamic traffic assignment (DTA) system for advanced traffic network management is also proposed to describe the evolution of traffic flow patterns under specific traffic measures in the network and the route guidance information supply strategy for individual drivers.


## 1.2. The Proposed Method

The literatures above have made great contributions in different fields, which provide inspirations to this paper. The energy-efficient dynamic route planning for electric vehicles is proposed. The main innovative contributions of this study are as follows.(1) Firstly, we introduce intersection signals to the dynamic road network. The intersection signals are changing periodically (in red light or green light), which can control the vehicles’ driving trajectory and influence the results of the dynamic route planning. Further, we establish the state-space-time network to describe the realistic road network. In comparison to traditional strategies, the state-space-time network reflects the dynamic characteristic not only on the link travel time but also on the node state.(2) Secondly, we try to control the travel velocity to achieve the nonstopping driving when the vehicles pass through the intersection signals. When the velocity varies greatly, the energy consumption will increase significantly. Therefore, if the vehicle stops at the intersection signals by the rules, it needs to decelerate from a certain velocity to 0 and then accelerates from 0 to a certain velocity, which will consume massive energy. By using nonstop driving mode, the waiting time at the signalized intersection is allocated to the driving process, which can avoid frequent starting and stopping at signalized intersections. To a certain extent, it will eliminate the drivers’ waiting anxiety and reduce the energy consumption in the driving process.(3) Thirdly, a multiobjective 0-1 integer programming model is formulated to find the optimal nonstop driving route in the state-space-time network. The two objective of travel time and energy consumption are considered in this paper. Then, we adopt two methods of constrained shortest path (CSP) problem and membership functions by using fuzzy theory to transform the multiobjective into a single objective problem. The experiment results indicate that the nonstop driving mode proposed in this paper can save the energy and eliminate the waiting time.The rest of paper is organized as follows. Section2 gives a detailed problem statement, which compares the energy consumption between stop and nonstop driving process and further establishes a state-time-space network to find the shortest route. In Section 3, the mathematical model is formulated to optimize the travel route achieving minimum energy consumption and travel time. The energy consumption model proposed by Haaren [31] is used to calculate the object function. Section 4 provides an example to illustrate the proposed energy-efficient dynamic route planning approach and analyze the results of planning route. Finally, Section 5 concludes with an outline of future work directions.


## 2. Problem Statement

### 2.1. The Energy Consumption Comparison between Stop and Nonstop Driving

The highlight of this paper is to consider the dynamic traffic signals into the route planning, which can reduce energy consumption and eliminate waiting time. The following is a simple example to illustrate this problem.Figure1 shows the driving process of the same trajectory under general circumstance (stop once since the red light) and proposed approach of this paper (nonstop driving). There are three indicator lights in the signals, indicating left turn, go straight, and right turn. Usually, in the traveling process, we may encounter a red light at the signalized intersection. It needs to brake to stop until the signal lights turn green and then starts to accelerate. In this process, additional energy consumption and waiting time are inevitable, as shown in Figure 1(a). In contrast, Figure 1(b) shows the driving situation under our proposed approach, namely, nonstop driving, which is to adjust the driving velocity by the signal information to avoid the deceleration process to stop and the acceleration of starting. Nonstop driving is benefit to save energy and eliminate drivers' waiting anxieties.Figure 1
The driving process of the same trajectory under general circumstance and our proposed approach.
(a) (b)In the following, we will take travel route in the dotted box in Figures1(a) and 1(b) for example to concretely illustrate how to save energy and eliminate drivers' waiting anxieties. In Figure 1(a), we assume that the velocity of vehicle is v1=60km/h and encounters a red light at the signal intersection after t1=1min. At the red light intersection, it decelerates to stop waiting for t2=15s and then accelerates to v3=60km/h (ignoring the acceleration and deceleration time), arriving the next intersection after t3=1min. In Figure 1(b), to achieve nonstop driving, we adjust the velocity of vehicle to v2=48km/h, so that it passes through the second intersection at a constant velocity after t1+t2. Next, it completes the following trip with the same travel state as Figure 1(a).We refer to Haaren [31] to calculate the energy consumption of the two cases above. It considers energy losses at variable velocity and constant velocity. Energy loss at variable velocity is due to change in kinetic energy, as shown in (1)Ekin=1.05·12m·Δv2wherem is the total mass of the vehicle (m=1235kg) andv is the change of velocity (inm/s).During acceleration phase, the electric energy is converted into kinetic energy with about 80% efficiency. During deceleration phase, a part of lost kinetic energy is recuperated as electric energy with efficiency of around 40%. Then, the energy losses are shown in (2) and (3), and the relationship with the velocity is displayed in Figure 2.(2)Eacc=Ekin0.8(3)Edec=-Ekin×0.4Figure 2
The energy loss during acceleration phase and deceleration phase related to velocity.The energy loss at constant velocity is related to the power loss and travel time. The power loss,Pcons, is the sum of the losses due to aerodynamics (Paer), drive-train (Pdr), rolling resistance (Prr), and ancillary losses (Panc) [31]. The power losses from aerodynamics, drive-train, and rolling resistance are related to various factors and are complex expressions of velocity (unit:mph). The power losses from ancillary losses may vary between 0.2-2.2 kW, which includes climate control, external lights, and audio, as well as systems necessary to regulate battery temperature, as shown in (4)-(9). The relationship with the velocity is displayed in Figure 3. Table 1 lists the parameters used in the energy consumption calculation.(4)Ev,t=Pcons·t(5)Pcons=Paer+Pdr+Prr+Panc(6)Paer=aaer·v3(7)Pdr=adr·v3+βdr·v2+γdr·v+cdr(8)Prr=crr·N·v(9)Panc=200Table 1
Parameters of energy consumption model.
Parameters Definition Value a a e r The force of air friction 0.0345 a d r Losses coefficients of the inverter 0.004 β d r Losses coefficients of the AC induction motor, gears 0.5 γ d r Losses coefficients of the gears 29.3 c d r The power usage of the complete drivetrain system in the vehicle without moving 375 c r r The coefficient of rolling resistance 0.0075 N The normal force (weight carried by the tire) 7460Figure 3
The velocity changing of two cases in Figure1.As for the travel process of two cases in Figure1, it can be clearly displayed in Figure 3. The energy consumptions are divided into three parts by time segments t1, t2, and t3. In Figure 1(a), the vehicle’s velocity is 0 during t2; thus the energy consumption is also 0. Then, the energy losses can be calculated as E1=E(v1,t1)+Edec(v1-0)+Eacc(v3-0)+E(v3,t3). The calculation result is 256.13wh. The energy losses in Figure 1(b) can be calculated as E2=E(v2,t1+t2)+E(v3,t3). The calculation result is 202.90wh, saving energy about 53wh. The results show that nonstop driving can save energy and avoid the waiting time.


### 2.2. The Shortest Route in State-Space-Time Network

Since the intersection signals are considered in this network, the different phrases of the signals will lead to different routes. To distinguish the different phrases of the signals at the intersections, we divide the intersection with signals into different phase nodes. Therefore, the set of nodes include physical nodes and signal phase nodes, and the problem of route selection at signal intersection is transformed into the selection of signal phase node. An illustrative network is displayed in Figure4. A physical road network is shown in Figure 4(a) such that the node 2 and node 4 are signal intersections, the phases of which correspond to the connection relationship of adjacent nodes. Thus, the signal intersection is split into a corresponding signal phase node according to its phase, as shown in Figure 4(b). Node 2 connects with nodes 3 and 4, which represents two directions (such as go straight and turn right) controlled by the signal phrases. Node 2 can be split into nodes 2′ and 2′′. As for node 4, it is connected by nodes 2 and 3, which can be split into nodes 4′ and 4′′ in the same way. The number marked on the arrow is the travel time of the link. Then, the network structure is also changed due to the addition of nodes.Figure 4
An illustrative network.
(a) (b)To clearly illustrate the problem of interest, the transportation network is represented by a directed graphG(N,A), where N is the set of nodes and A is the set of directed links. To effectively represent the trajectory with spatial and temporal characteristics, the planning time horizon T is discretized into a set of small-time intervals with the same length, where the set of discretized timestamps is denoted by T=t0,t0+δ,…,t0+Mδ. Parameter t is the timestamp in the discretized time horizon, t∈T. Therefore, each link (i,j) has time-dependent travel time TTijtt′ from node i to node j. The following relevant notions are listed for convenience of formulation, which can be clearly seen in Tables 2 and 3.Table 2
Notations used in formulation.
Notations Definition T A discrete time horizon under consideration,T={t0,t0+δ,…,t0+Mδ} t The timestamp in the discretized time horizon,t∈T. N Set of nodes A Set of direction links ( i , j , t , t ′ ) A time-dependent arc on link(i,j) with departure time t and arrival time t′ T T i j t t ′ m i n The time-dependent travel time of link(i,j,t,t′) without adjusting T T i j t t ′ The adjusted time-dependent travel time of link(i,j,t,t′) t i The departure time from nodei g i t The state of signal phase nodei at time t, which is the 0-1 variable C i The signal cycle at signal phase nodei a i The start time of red light in the first signal cycle of signal phase nodei b i The end time of red light in the first signal cycle of signal phase nodei v i j t t ′ The average travel velocity of link(i,j,t,t′) l i j The length of link(i,j)Table 3
Decision variables used in formulation.
Notations Definition x i j t t ′ =1, if the link(i,j,t,t′) is selected=0, otherwiseWe now use the illustrative network to demonstrate primary modeling features of constructed networks, as shown in Figure5. There are two feasible routes from node 1 to node 5 with node sequence 1-2′-4′-5 (route 1) and 1-2′′-3-4′′-5 (route 2), which are connected by bold arrows marked with the travel time. If the signals are not considered, the travel time of the two routes is equal to 7-time intervals. However, the travel time will increase a part of waiting time when the vehicle stops at the signal intersection because of the red light. As shown in Figure 5, the EV must wait at the signal phase node 2′′ at time t2 if it drives along the route 2 with the unadjusted travel time, similarly in route 1 (see the dotted line in Figure 5). It will spend 8-time intervals on route 2 and 9-time intervals on route 1, which will produce unnecessary waiting time and energy consumption. Therefore, we adjust the travel velocity to reduce the speed properly and waiting time on the road to achieve nonstop driving. As a result, the space-time trajectories of two routes are represented by solid line, and the travel time of route 2 (8-time intervals) is shorter than that of route 1 (9-time intervals).Figure 5
The simplified illustrative example of space-time trajectory.Besides, if the state of signal phase is represented as a state dimension, it can be represented as the state-space-time network, as shown in Figure6. Figure 6 can be seen as a projection of Figure 5 on the time-space dimension.Figure 6
The simplified illustrative example of state-space-time trajectory.By the above description, it is proved that taking the signals into account in the route planning conforms to the reality and can also reduce energy consumption. Therefore, this paper presents an energy-efficient dynamic route planning method for EVs.


## 2.1. The Energy Consumption Comparison between Stop and Nonstop Driving

The highlight of this paper is to consider the dynamic traffic signals into the route planning, which can reduce energy consumption and eliminate waiting time. The following is a simple example to illustrate this problem.Figure1 shows the driving process of the same trajectory under general circumstance (stop once since the red light) and proposed approach of this paper (nonstop driving). There are three indicator lights in the signals, indicating left turn, go straight, and right turn. Usually, in the traveling process, we may encounter a red light at the signalized intersection. It needs to brake to stop until the signal lights turn green and then starts to accelerate. In this process, additional energy consumption and waiting time are inevitable, as shown in Figure 1(a). In contrast, Figure 1(b) shows the driving situation under our proposed approach, namely, nonstop driving, which is to adjust the driving velocity by the signal information to avoid the deceleration process to stop and the acceleration of starting. Nonstop driving is benefit to save energy and eliminate drivers' waiting anxieties.Figure 1
The driving process of the same trajectory under general circumstance and our proposed approach.
(a) (b)In the following, we will take travel route in the dotted box in Figures1(a) and 1(b) for example to concretely illustrate how to save energy and eliminate drivers' waiting anxieties. In Figure 1(a), we assume that the velocity of vehicle is v1=60km/h and encounters a red light at the signal intersection after t1=1min. At the red light intersection, it decelerates to stop waiting for t2=15s and then accelerates to v3=60km/h (ignoring the acceleration and deceleration time), arriving the next intersection after t3=1min. In Figure 1(b), to achieve nonstop driving, we adjust the velocity of vehicle to v2=48km/h, so that it passes through the second intersection at a constant velocity after t1+t2. Next, it completes the following trip with the same travel state as Figure 1(a).We refer to Haaren [31] to calculate the energy consumption of the two cases above. It considers energy losses at variable velocity and constant velocity. Energy loss at variable velocity is due to change in kinetic energy, as shown in (1)Ekin=1.05·12m·Δv2wherem is the total mass of the vehicle (m=1235kg) andv is the change of velocity (inm/s).During acceleration phase, the electric energy is converted into kinetic energy with about 80% efficiency. During deceleration phase, a part of lost kinetic energy is recuperated as electric energy with efficiency of around 40%. Then, the energy losses are shown in (2) and (3), and the relationship with the velocity is displayed in Figure 2.(2)Eacc=Ekin0.8(3)Edec=-Ekin×0.4Figure 2
The energy loss during acceleration phase and deceleration phase related to velocity.The energy loss at constant velocity is related to the power loss and travel time. The power loss,Pcons, is the sum of the losses due to aerodynamics (Paer), drive-train (Pdr), rolling resistance (Prr), and ancillary losses (Panc) [31]. The power losses from aerodynamics, drive-train, and rolling resistance are related to various factors and are complex expressions of velocity (unit:mph). The power losses from ancillary losses may vary between 0.2-2.2 kW, which includes climate control, external lights, and audio, as well as systems necessary to regulate battery temperature, as shown in (4)-(9). The relationship with the velocity is displayed in Figure 3. Table 1 lists the parameters used in the energy consumption calculation.(4)Ev,t=Pcons·t(5)Pcons=Paer+Pdr+Prr+Panc(6)Paer=aaer·v3(7)Pdr=adr·v3+βdr·v2+γdr·v+cdr(8)Prr=crr·N·v(9)Panc=200Table 1
Parameters of energy consumption model.
Parameters Definition Value a a e r The force of air friction 0.0345 a d r Losses coefficients of the inverter 0.004 β d r Losses coefficients of the AC induction motor, gears 0.5 γ d r Losses coefficients of the gears 29.3 c d r The power usage of the complete drivetrain system in the vehicle without moving 375 c r r The coefficient of rolling resistance 0.0075 N The normal force (weight carried by the tire) 7460Figure 3
The velocity changing of two cases in Figure1.As for the travel process of two cases in Figure1, it can be clearly displayed in Figure 3. The energy consumptions are divided into three parts by time segments t1, t2, and t3. In Figure 1(a), the vehicle’s velocity is 0 during t2; thus the energy consumption is also 0. Then, the energy losses can be calculated as E1=E(v1,t1)+Edec(v1-0)+Eacc(v3-0)+E(v3,t3). The calculation result is 256.13wh. The energy losses in Figure 1(b) can be calculated as E2=E(v2,t1+t2)+E(v3,t3). The calculation result is 202.90wh, saving energy about 53wh. The results show that nonstop driving can save energy and avoid the waiting time.


## 2.2. The Shortest Route in State-Space-Time Network

Since the intersection signals are considered in this network, the different phrases of the signals will lead to different routes. To distinguish the different phrases of the signals at the intersections, we divide the intersection with signals into different phase nodes. Therefore, the set of nodes include physical nodes and signal phase nodes, and the problem of route selection at signal intersection is transformed into the selection of signal phase node. An illustrative network is displayed in Figure4. A physical road network is shown in Figure 4(a) such that the node 2 and node 4 are signal intersections, the phases of which correspond to the connection relationship of adjacent nodes. Thus, the signal intersection is split into a corresponding signal phase node according to its phase, as shown in Figure 4(b). Node 2 connects with nodes 3 and 4, which represents two directions (such as go straight and turn right) controlled by the signal phrases. Node 2 can be split into nodes 2′ and 2′′. As for node 4, it is connected by nodes 2 and 3, which can be split into nodes 4′ and 4′′ in the same way. The number marked on the arrow is the travel time of the link. Then, the network structure is also changed due to the addition of nodes.Figure 4
An illustrative network.
(a) (b)To clearly illustrate the problem of interest, the transportation network is represented by a directed graphG(N,A), where N is the set of nodes and A is the set of directed links. To effectively represent the trajectory with spatial and temporal characteristics, the planning time horizon T is discretized into a set of small-time intervals with the same length, where the set of discretized timestamps is denoted by T=t0,t0+δ,…,t0+Mδ. Parameter t is the timestamp in the discretized time horizon, t∈T. Therefore, each link (i,j) has time-dependent travel time TTijtt′ from node i to node j. The following relevant notions are listed for convenience of formulation, which can be clearly seen in Tables 2 and 3.Table 2
Notations used in formulation.
Notations Definition T A discrete time horizon under consideration,T={t0,t0+δ,…,t0+Mδ} t The timestamp in the discretized time horizon,t∈T. N Set of nodes A Set of direction links ( i , j , t , t ′ ) A time-dependent arc on link(i,j) with departure time t and arrival time t′ T T i j t t ′ m i n The time-dependent travel time of link(i,j,t,t′) without adjusting T T i j t t ′ The adjusted time-dependent travel time of link(i,j,t,t′) t i The departure time from nodei g i t The state of signal phase nodei at time t, which is the 0-1 variable C i The signal cycle at signal phase nodei a i The start time of red light in the first signal cycle of signal phase nodei b i The end time of red light in the first signal cycle of signal phase nodei v i j t t ′ The average travel velocity of link(i,j,t,t′) l i j The length of link(i,j)Table 3
Decision variables used in formulation.
Notations Definition x i j t t ′ =1, if the link(i,j,t,t′) is selected=0, otherwiseWe now use the illustrative network to demonstrate primary modeling features of constructed networks, as shown in Figure5. There are two feasible routes from node 1 to node 5 with node sequence 1-2′-4′-5 (route 1) and 1-2′′-3-4′′-5 (route 2), which are connected by bold arrows marked with the travel time. If the signals are not considered, the travel time of the two routes is equal to 7-time intervals. However, the travel time will increase a part of waiting time when the vehicle stops at the signal intersection because of the red light. As shown in Figure 5, the EV must wait at the signal phase node 2′′ at time t2 if it drives along the route 2 with the unadjusted travel time, similarly in route 1 (see the dotted line in Figure 5). It will spend 8-time intervals on route 2 and 9-time intervals on route 1, which will produce unnecessary waiting time and energy consumption. Therefore, we adjust the travel velocity to reduce the speed properly and waiting time on the road to achieve nonstop driving. As a result, the space-time trajectories of two routes are represented by solid line, and the travel time of route 2 (8-time intervals) is shorter than that of route 1 (9-time intervals).Figure 5
The simplified illustrative example of space-time trajectory.Besides, if the state of signal phase is represented as a state dimension, it can be represented as the state-space-time network, as shown in Figure6. Figure 6 can be seen as a projection of Figure 5 on the time-space dimension.Figure 6
The simplified illustrative example of state-space-time trajectory.By the above description, it is proved that taking the signals into account in the route planning conforms to the reality and can also reduce energy consumption. Therefore, this paper presents an energy-efficient dynamic route planning method for EVs.


## 3. Model Formulation

In the process of formulating the model, three assumptions used throughout the paper are explained as follows.Assumption 1.
EV can receive the traffic information including all links' distance, traffic flow, the location, and the change regulation of the traffic signal.Assumption 2.
During the travel, the electricity of the EV is sufficient.Assumption 3.
The velocity is supposed to be a constant on each link without considering specific acceleration and deceleration processes. Thus, the travel velocity is a step function.This section will provide an approach to optimize energy-efficient dynamic route planning problem. Since the signal phrase is the focus of this study, we should start with the description of the state of signal phase node. Next, the travel time can be adjusted according to the state of signal phase node.


### 3.1. The State of Signal Phase Node

For simplicity understanding, we definegit as the state of signal phase node i at time t, which is a binary variable, git=1 represents green light of signal phase node i at time t, and git=0 represents red light of signal phase node i at time t, as shown in (10)git=0,t∈n·Ci+ai,n·Ci+bi1,otherwisewhere Ci represents the signal cycle at signal phase node i; ai and bi separately represent the start and end time of red light in the first signal cycle of signal phase node i; namely, ai,bi is the first red time interval at signal phase node i; n represents the number of signal cycle of signal phase node i at time t.If it is not a signal phase node, the parameters (including the signal cycle, the start and end time of red light in the first signal cycle) are all set as zero andgit is always equal to 1, which means the state of the node is always in green phrase.


### 3.2. The Adjustment of Actual Travel Time

If the EV arrives at the signal intersection in the red phrase, its travel time will be adjusted so as to realize the nonstop driving. Therefore, according to the state of signal, it can be divided into two cases to adjust the actual travel time.Case 1.
If the state of signal phase nodej at time t′ satisfies (11), it illustrates that the signal is a green light when the EV arrives at the signal phase node j, and the EV can go through this intersection without waiting. The actual travel time cannot be adjusted, as shown in (12):(11)gjt′=1,t′=ti+TTijtt′min(12)TTijtt′=TTijtt′minwhere TTijtt′min is the time-dependent travel time from node i to node j at departure time t.Case 2.
If the state of signal phase nodej at time t′ satisfies (13), it illustrates that the signal is a red light when the EV arrives at the signal phase node j, and the EV needs to wait at the intersection until the end of the red light. Thus, the actual travel time should be adjusted.(13)gjt′=0,t′=ti+TTijtt′min
Figure7 shows the adjustment of actual travel time. The red phrase duration at node j is aj+n·Cj,bj+n·Cj. We can see that the EV departures from node i at time ti and arrives in red phrase at node j in the red phrase. To avoid the waiting time at the intersection, the actual travel time should be adjusted.Figure 7
The adjustment of actual travel time.Thus, the actual travel time of link(i,j) at time t can be calculated by (14) and (15).(14)n=ti+TTijtt′minCi(15)TTijtt′=n·Ci+bj-tiTo sum up, the actual travel time of the EV passing through the link(i,j) at time t can be expressed by (16)TTijtt′=TTijtt′min,gjt′=1n·Ci+bj-ti,gjt′=0Therefore, the adjusted travel time can realize nonstop driving, as shown in(17)n·Ci+bj-ti≤TTijtt′≤aj+n+1·Ci-tiThe energy consumption is related to travel time and velocity, and it is difficult to calculate vehicle energy consumption by changeable velocity. Therefore, the average travel velocity of link is adopted in this paper in the process of calculating energy consumption in Section3.3. Further, the average travel velocity of link (i,j) at time t can be calculated by (18)vijtt′=lijTTijtt′where lij is the length of link (i,j).


### 3.3. Mathematical Model

After adjusting the travel time, the energy-saving route planning model can be formulated. The two factors of travel time and energy consumption are considered in this paper, both of which are related to velocity, since the higher velocity corresponds to shorter link travel time and more potential energy consumption. Therefore, a relationship between a space-time link and the corresponding energy consumption will be formulated. Based on the problem description and consideration, the route planning process can be essentially represented as a space-time route choice process in the corresponding space-time network. Then, a binary variable is sufficient to denote the link selection indicator. The model can be formulated as a linear multiobjective 0-1 integer programming model.To minimize the energy consumption and actual travel time, two objective functions are shown in (18) and (19), that is, minimizing energy consumption and actual travel time. Both two objective functions have a linear form with respect to decision variables xijtt′.(19)minEx=∑i,j,t,t′∈AEijtt′·xijtt′(20)minTx=∑i,j,t,t′∈ATTijtt′·xijtt′For the system constraints of the formulated model, travel time adjustment constraints, the flow balance constraints, and binary variable constraints should be satisfied. For clear description, the parameters in Table1 are introduced into the objective function of energy consumption in the model. Hence, the multiobjective 0-1 integer programming model can be formulated as(21)minE=∑i,j,t,t′∈A0.0385·vijtt′3+0.5·vijtt′2+85.25·vijtt′+575·TTijtt′·xijtt′(22)minT=∑i,j,t,t′∈ATTijtt′·xijtt′s.t.Travel time adjustment constraints(23)n·Ci+bj-ti≤TTijtt′≤aj+n+1·Ci-tiFlow balance constraint(24)∑i,j,t,t′∈Axijtt′-∑j,i,t′,t∈Axji′t′t=1,i=O,t=ti-1,i=D,t=tj0,otherwiseBinary variable constraint(25)xijtt′∈0,1∀i,j,t,t′∈AIn general, the multiobjective problem should be transformed to a single objective one. This paper presents two methods to deal with this multiobjective problem. On the one hand, the objective of minimizing actual travel time treated as a side constraint and a constrained shortest path model is formulated. This constrained shortest path (CSP) problem is to find a path from a start node to an end node that minimizes the total energy consumption, subject to not exceeding a maximum travel time. Then, the objectives are unified so as to transform the multiobjective problem into a single objective problem as below.(26)minE=∑i,j,t,t′∈A0.0385·vijtt′3+0.5·vijtt′2+85.25·vijtt′+575·TTijtt′·xijtt′s.t.(27)∑i,j,t,t′∈ATTijtt′·xijtt′<T^(28)n·Ci+bj-ti≤TTijtt′≤aj+n+1·Ci-ti(29)∑i,j,t,t′∈Axijtt′-∑j,i,t′,t∈Axji′t′t=1,i=O,t=ti-1,i=D,t=tj0,otherwise(30)xijtt′∈0,1∀i,j,t,t′∈AConstraint (27) expresses that the actual travel time cannot be more than the threshold T^. Constraint (28) ensures that the adjusted travel time enables the electric vehicle to avoid braking. Constraint (29) ensures the flow balance on each vertex. Constraint (30) is the binary constraint for decision variables, xijtt′=1 if the EV choose link (i,j) at time t; xijtt′=0, otherwise.The solution of constrained shortest path problem can be solved by improved label-setting algorithm or label-correcting algorithm. The most remarkable feature of this algorithm is that it can find the shortest path quickly for a reasonable scale network. However, because of the “dimension explosion” of dynamic programming, when the large number of labels needed to be stored, it may not be well extended to solve the problem in the large-scale networks.The basic idea of improved label-setting algorithm is to visit the origin node to the end node by labeling. When a label sequence runs through the network from one node to another, a feasible pathP including visited nodes, cumulative objective functionE(P), and cumulative time consumptiont(P) is established. That is, each label sequence at the destination contains all information about the feasible paths setP from the origin node to the end node. Without violating the cumulative travel time threshold constraints, the algorithm will enumerate all possible paths from the origin node to the end node to ensure that the optimal path P∗ is found.On the other hand, we adopt the fuzzy set theory to deal with this multiobjective optimization problem, in which the degree of membership function is established for each objective function to represent the satisfaction of the objective function. By using fuzzy theory, membership functions based on energy consumption and travel time can be obtained respectively.The optimal objective value of the total energy consumptionE- is assumed to be given in advance, and (31) is formulated to calculate the membership degree, μE(x), between the actual energy consumption and the objective energy consumption.(31)μEx=1,Ex≤E-Emax-ExEmax-E-,Ex≥E-Accordingly,T- is set as the optimal objective of a given total travel time, and the membership degree between the actual travel time and the target travel time is calculated, as shown in (32)μTx=1,Tx≤T-Tmax-TxTmax-T-,Tx≥T-Because the membership function and the fuzzy set of each objective are different, the intersection operation of fuzzy sets is adopted to balance the two objective functions according to Definition4 [32].Definition 4 (see [32]).
If there are fuzzy setsA and B in the universal set U, then the intersection operation of the fuzzy sets A and B can be defined as follows:(33)μA∩Bx=minμAx,μBx,∀x∈Uwhere μA(x) and μB(x) separately represent the membership functions of the fuzzy sets A and B.In this paper, we will take small operations on the membership functions; that is, the minimum value of energy consumptionE(x) and travel time T(x) is used to represent the comprehensive satisfaction. Then, the objective function of maximum satisfaction is used for modeling. Further, we set up the following optimization problem:(34)max⁡min⁡μEx,μTxsubject to constraints (23) and (25).To solve this model in fuzzy set theory, we need to calculate the total energy consumption and total travel time. To reflect the satisfaction of energy consumption and travel time, the membership function is introduced. That is to say, for the objective of total energy consumption, the nearer the energy consumption is to the optimal target valueE-, the closer the membership (or satisfaction) μE is to 1. It is the same as the objective of total travel time. In order to establish the membership function, the maximum and minimum total energy consumption (or total travel time) based on system constraints are calculated.For example, we assume the range of total energy consumption is[1000,2000], then E-=1000, Emax=2000, and the membership function of total energy consumption is obtained, as shown in (35)μEx=1,Ex≤10002000-Ex2000-1000,Ex≥1000As the same in the membership function of total travel time, we assume the range of total travel time is[900,1800], then T-=900, Tmax=1800, and the membership function of total travel time is shown in (36)μTx=1,Tx≤9001800-Tx1800-900,Tx≥900Obviously, it is important to estimate the maximum and minimum of the objectives for this kind of method to construct the membership function. Based on the two membership functions, the objective function of comprehensive satisfaction will be obtained. Further, this model can also be solved by the label-correcting algorithm.Based on above discussion, two methods of transforming multiobjective model into a single objective one are feasible, but the value of objective function is different. In Section4, we design the experiments on the constrained shortest path model.


## 3.1. The State of Signal Phase Node

For simplicity understanding, we definegit as the state of signal phase node i at time t, which is a binary variable, git=1 represents green light of signal phase node i at time t, and git=0 represents red light of signal phase node i at time t, as shown in (10)git=0,t∈n·Ci+ai,n·Ci+bi1,otherwisewhere Ci represents the signal cycle at signal phase node i; ai and bi separately represent the start and end time of red light in the first signal cycle of signal phase node i; namely, ai,bi is the first red time interval at signal phase node i; n represents the number of signal cycle of signal phase node i at time t.If it is not a signal phase node, the parameters (including the signal cycle, the start and end time of red light in the first signal cycle) are all set as zero andgit is always equal to 1, which means the state of the node is always in green phrase.


## 3.2. The Adjustment of Actual Travel Time

If the EV arrives at the signal intersection in the red phrase, its travel time will be adjusted so as to realize the nonstop driving. Therefore, according to the state of signal, it can be divided into two cases to adjust the actual travel time.Case 1.
If the state of signal phase nodej at time t′ satisfies (11), it illustrates that the signal is a green light when the EV arrives at the signal phase node j, and the EV can go through this intersection without waiting. The actual travel time cannot be adjusted, as shown in (12):(11)gjt′=1,t′=ti+TTijtt′min(12)TTijtt′=TTijtt′minwhere TTijtt′min is the time-dependent travel time from node i to node j at departure time t.Case 2.
If the state of signal phase nodej at time t′ satisfies (13), it illustrates that the signal is a red light when the EV arrives at the signal phase node j, and the EV needs to wait at the intersection until the end of the red light. Thus, the actual travel time should be adjusted.(13)gjt′=0,t′=ti+TTijtt′min
Figure7 shows the adjustment of actual travel time. The red phrase duration at node j is aj+n·Cj,bj+n·Cj. We can see that the EV departures from node i at time ti and arrives in red phrase at node j in the red phrase. To avoid the waiting time at the intersection, the actual travel time should be adjusted.Figure 7
The adjustment of actual travel time.Thus, the actual travel time of link(i,j) at time t can be calculated by (14) and (15).(14)n=ti+TTijtt′minCi(15)TTijtt′=n·Ci+bj-tiTo sum up, the actual travel time of the EV passing through the link(i,j) at time t can be expressed by (16)TTijtt′=TTijtt′min,gjt′=1n·Ci+bj-ti,gjt′=0Therefore, the adjusted travel time can realize nonstop driving, as shown in(17)n·Ci+bj-ti≤TTijtt′≤aj+n+1·Ci-tiThe energy consumption is related to travel time and velocity, and it is difficult to calculate vehicle energy consumption by changeable velocity. Therefore, the average travel velocity of link is adopted in this paper in the process of calculating energy consumption in Section3.3. Further, the average travel velocity of link (i,j) at time t can be calculated by (18)vijtt′=lijTTijtt′where lij is the length of link (i,j).


## 3.3. Mathematical Model

After adjusting the travel time, the energy-saving route planning model can be formulated. The two factors of travel time and energy consumption are considered in this paper, both of which are related to velocity, since the higher velocity corresponds to shorter link travel time and more potential energy consumption. Therefore, a relationship between a space-time link and the corresponding energy consumption will be formulated. Based on the problem description and consideration, the route planning process can be essentially represented as a space-time route choice process in the corresponding space-time network. Then, a binary variable is sufficient to denote the link selection indicator. The model can be formulated as a linear multiobjective 0-1 integer programming model.To minimize the energy consumption and actual travel time, two objective functions are shown in (18) and (19), that is, minimizing energy consumption and actual travel time. Both two objective functions have a linear form with respect to decision variables xijtt′.(19)minEx=∑i,j,t,t′∈AEijtt′·xijtt′(20)minTx=∑i,j,t,t′∈ATTijtt′·xijtt′For the system constraints of the formulated model, travel time adjustment constraints, the flow balance constraints, and binary variable constraints should be satisfied. For clear description, the parameters in Table1 are introduced into the objective function of energy consumption in the model. Hence, the multiobjective 0-1 integer programming model can be formulated as(21)minE=∑i,j,t,t′∈A0.0385·vijtt′3+0.5·vijtt′2+85.25·vijtt′+575·TTijtt′·xijtt′(22)minT=∑i,j,t,t′∈ATTijtt′·xijtt′s.t.Travel time adjustment constraints(23)n·Ci+bj-ti≤TTijtt′≤aj+n+1·Ci-tiFlow balance constraint(24)∑i,j,t,t′∈Axijtt′-∑j,i,t′,t∈Axji′t′t=1,i=O,t=ti-1,i=D,t=tj0,otherwiseBinary variable constraint(25)xijtt′∈0,1∀i,j,t,t′∈AIn general, the multiobjective problem should be transformed to a single objective one. This paper presents two methods to deal with this multiobjective problem. On the one hand, the objective of minimizing actual travel time treated as a side constraint and a constrained shortest path model is formulated. This constrained shortest path (CSP) problem is to find a path from a start node to an end node that minimizes the total energy consumption, subject to not exceeding a maximum travel time. Then, the objectives are unified so as to transform the multiobjective problem into a single objective problem as below.(26)minE=∑i,j,t,t′∈A0.0385·vijtt′3+0.5·vijtt′2+85.25·vijtt′+575·TTijtt′·xijtt′s.t.(27)∑i,j,t,t′∈ATTijtt′·xijtt′<T^(28)n·Ci+bj-ti≤TTijtt′≤aj+n+1·Ci-ti(29)∑i,j,t,t′∈Axijtt′-∑j,i,t′,t∈Axji′t′t=1,i=O,t=ti-1,i=D,t=tj0,otherwise(30)xijtt′∈0,1∀i,j,t,t′∈AConstraint (27) expresses that the actual travel time cannot be more than the threshold T^. Constraint (28) ensures that the adjusted travel time enables the electric vehicle to avoid braking. Constraint (29) ensures the flow balance on each vertex. Constraint (30) is the binary constraint for decision variables, xijtt′=1 if the EV choose link (i,j) at time t; xijtt′=0, otherwise.The solution of constrained shortest path problem can be solved by improved label-setting algorithm or label-correcting algorithm. The most remarkable feature of this algorithm is that it can find the shortest path quickly for a reasonable scale network. However, because of the “dimension explosion” of dynamic programming, when the large number of labels needed to be stored, it may not be well extended to solve the problem in the large-scale networks.The basic idea of improved label-setting algorithm is to visit the origin node to the end node by labeling. When a label sequence runs through the network from one node to another, a feasible pathP including visited nodes, cumulative objective functionE(P), and cumulative time consumptiont(P) is established. That is, each label sequence at the destination contains all information about the feasible paths setP from the origin node to the end node. Without violating the cumulative travel time threshold constraints, the algorithm will enumerate all possible paths from the origin node to the end node to ensure that the optimal path P∗ is found.On the other hand, we adopt the fuzzy set theory to deal with this multiobjective optimization problem, in which the degree of membership function is established for each objective function to represent the satisfaction of the objective function. By using fuzzy theory, membership functions based on energy consumption and travel time can be obtained respectively.The optimal objective value of the total energy consumptionE- is assumed to be given in advance, and (31) is formulated to calculate the membership degree, μE(x), between the actual energy consumption and the objective energy consumption.(31)μEx=1,Ex≤E-Emax-ExEmax-E-,Ex≥E-Accordingly,T- is set as the optimal objective of a given total travel time, and the membership degree between the actual travel time and the target travel time is calculated, as shown in (32)μTx=1,Tx≤T-Tmax-TxTmax-T-,Tx≥T-Because the membership function and the fuzzy set of each objective are different, the intersection operation of fuzzy sets is adopted to balance the two objective functions according to Definition4 [32].Definition 4 (see [32]).
If there are fuzzy setsA and B in the universal set U, then the intersection operation of the fuzzy sets A and B can be defined as follows:(33)μA∩Bx=minμAx,μBx,∀x∈Uwhere μA(x) and μB(x) separately represent the membership functions of the fuzzy sets A and B.In this paper, we will take small operations on the membership functions; that is, the minimum value of energy consumptionE(x) and travel time T(x) is used to represent the comprehensive satisfaction. Then, the objective function of maximum satisfaction is used for modeling. Further, we set up the following optimization problem:(34)max⁡min⁡μEx,μTxsubject to constraints (23) and (25).To solve this model in fuzzy set theory, we need to calculate the total energy consumption and total travel time. To reflect the satisfaction of energy consumption and travel time, the membership function is introduced. That is to say, for the objective of total energy consumption, the nearer the energy consumption is to the optimal target valueE-, the closer the membership (or satisfaction) μE is to 1. It is the same as the objective of total travel time. In order to establish the membership function, the maximum and minimum total energy consumption (or total travel time) based on system constraints are calculated.For example, we assume the range of total energy consumption is[1000,2000], then E-=1000, Emax=2000, and the membership function of total energy consumption is obtained, as shown in (35)μEx=1,Ex≤10002000-Ex2000-1000,Ex≥1000As the same in the membership function of total travel time, we assume the range of total travel time is[900,1800], then T-=900, Tmax=1800, and the membership function of total travel time is shown in (36)μTx=1,Tx≤9001800-Tx1800-900,Tx≥900Obviously, it is important to estimate the maximum and minimum of the objectives for this kind of method to construct the membership function. Based on the two membership functions, the objective function of comprehensive satisfaction will be obtained. Further, this model can also be solved by the label-correcting algorithm.Based on above discussion, two methods of transforming multiobjective model into a single objective one are feasible, but the value of objective function is different. In Section4, we design the experiments on the constrained shortest path model.


## 4. Examples and Results

Based on the proposed model, the simulation of dynamic traffic network is constructed in Figure8. The shadow nodes indicate the signalized intersections. The signalized intersections can be split into several signal nodes according the in-degree and out-degree. Different link combinations are formed by connecting the signal phase nodes with the physical nodes (take nodes 2, 13, and 30 as an example), as shown in Figure 9. The 10∗10 grid network in Figure 8 (with 100 nodes and 180 links) turns to be a new network with 212 nodes (including 160 signal phase nodes) and 324 links (in Figure 10). We implement several numerical experiments to show the effectiveness and efficiency of our proposed model, which were conducted on PC environment running Windows 10 with an Intel Core i7 2.6GHz processor and 8GB of main memory. The algorithm is implemented in C++ and has been compiled using Visual Studio 2015.Figure 8
The simulation of real-time traffic network.Figure 9
The spilt signal phase nodes (take nodes 2, 13, and 30 as an example).Figure 10
The simulation of real-time traffic network with spilt signal phase nodes.In the experiment, we take the time horizon from 8:00 to 9:00 into account. It is assumed that this horizon is discretized into 600 intervals and each time interval is 6s. To simplify the problem, four kinds of signal timing with random phase difference are simulated in the network. The four information scenarios of signal phase node including signal cycle, green time, and red time are displayed in Table 4.Table 4
The four scenarios of signal timing.
Scenario signal cycle green time red time 1 60 30 30 2 60 40 20 3 90 50 40 4 90 60 30Suppose that the EV departures from node 1 to node 100 are at different departure time (8:00, 8:10, 8:20 and 8:30). The travel time, energy consumption, and computational time of the planned routes under four scenarios are shown in Table5. The trajectories of the planned routes are displayed in Figure 11.Table 5
The results under four scenarios from node 1 to node 100.
Scenario 8:00 8:10 8:20 8:30 TT EC CT TT EC CT TT EC CT TT EC CT 1 18.5 0.776 3.37 18.4 0.776 2.81 21.4 0.783 3.35 23.2 0.789 3.01 2 20.1 0.786 3.01 18.5 0.778 2.96 20.3 0.782 3.02 22.1 0.784 3.34 3 27 0.803 2.93 26.1 0.800 3.26 26.6 0.802 3.47 27 0.803 2.87 4 18.3 0.786 3.33 19.1 0.782 3.19 23.9 0.795 2.82 25.7 0.801 2.91 Note: TT: travel time (min), EC: energy consumption (kwh), CT: computational time (s).Figure 11
The shortest routes under four scenarios from node 1 to node 100 at different departure times.Based on the foregoing experimental data in Table5, the travel time and energy consumption are different at different departure time, as well as in different scenarios, which indicates that the value of the objective function is related to the departure time and signal timing. Specifically, the results of travel time and energy consumption in Scenarios 1 and 2 have shorter travel times, and less energy consumptions no matter when to departure. However, the result in Scenario 3 has the largest travel time with more than 26min and the highest energy consumption among the four scenarios. It is more obvious in Figure 11 that the trajectories of the shortest routes in Scenario 3 fluctuate greatly and the time span is large. However, other trajectories are relatively sharp and the fluctuation is also gentle.According to the above results, it can be explained that compared to Scenario 4 (with the same signal cycle, 90s), Scenario 3 has smaller green time ratio (the green time ratio in Scenario 4: 60/90 = 0.67; the green time ratio in Scenario 3: 50/90 = 0.56); it may increase the travel time and the energy consumption correspondingly. Compared to Scenario 1 and Scenario 2, the signal timing in Scenario 3 has a longer signal cycle; however, the advantage of green time ratio is not obvious. Therefore, under the condition of short signal cycle and large green signal ratio, the travel time and energy consumption of the planning route can achieve a better result.As clearly seen from Figure11, the planned routes change continually with different scenarios and departure times because of the dynamic network. The specific driving nodes are shown in Tables 6–9.Table 6
The shortest routes from node 1 to node 100 at different departure time (in Scenario 1).
Departure time Via node Travel time (min) Energy consumption (kwh) 8:00 1→11→12→13→23→33→34→35→36→37→38→48→58→59→69→70→80→90→100 18.5 0.776  8:10 1→2→12→22→32→33→34→44→54→64→65→66→76→77→78→79→89→90→100 18.4 0.776  8:20 1→2→12→13→14→15→16→26→27→28→38→39→49→59→69→79→80→90→100 21.4 0.783  8:30 1→2→12→13→14→15→16→17→27→28→38→48→58→59→69→79→89→99→100 23.2 0.789Table 7
The shortest routes from node 1 to node 100 at different departure time (in Scenario 2).
Departure time Via node Travel time (min) Energy consumption (kwh) 8:00 1→11→12→22→23→24→25→35→45→55→56→66→76→77→78→79→80→90→100 20.1 0.786  8:10 1→11→21→22→32→33→34→35→36→37→47→48→49→59→69→79→89→99→100 18.5 0.778  8:20 1→11→12→22→23→33→34→44→45→46→56→57→67→68→69→79→89→90→100 20.3 0.782  8:30 1→2→12→13→14→24→25→26→27→28→38→48→58→59→69→70→80→90→100 22.1 0.784Table 8
The shortest routes from node 1 to node 100 at different departure time (in Scenario 3).
Departure time Via node Travel time (min) Energy consumption (kwh) 8:00 1→2→12→13→14→24→25→26→36→37→38→48→58→ 59→69→70→80→90→100 27 0.803  8:10 1→11→21→22→23→24→25→26→27→28→38→48→58→59→69→79→80→90→100 26.1 0.800  8:20 1→11→12→13→23→24→25→26→27→28→38→39→49→59→69→70→80→90→100 26.6 0.802  8:30 1→2→12→22→32→42→52→53→63→64→65→75→76→ 77→78→79→89→99→100 27 0.803Table 9
The shortest routes from node 1 to node 100 at different departure time (in Scenario 4).
Departure time Via node Travel time (min) Energy consumption (kwh) 8:00 1→11→21→31→32→33→43→44→54→55→56→66→67→77→78→79→80→90→100 18.3 0.786  8:10 1→2→12→13→14→24→34→44→54→55→56→57→67→77→78→88→89→99→100 19.1 0.782  8:20 1→2→12→13→14→24→34→35→36→37→47→48→49→59→69→79→89→90→100 23.9 0.795  8:30 1→2→12→13→23→24→25→26→36→37→47→48→49→59→69→79→80→90→100 25.7 0.801To compare the energy consumption between stop driving (Case1) and nonstop driving (Case 2), we take the route in Scenario 1 (departure time is 8:00) as an example (1→11→12→13→23→33→34→35→36→37→38→48→58→59→69→70→80→90→100). As shown in Table 10, the numbers on the arrows mean the link travel time (unit: min, exclusion the waiting time).Table 10
The energy consumption in stop driving (Case1) and nonstop driving (Case 2).
Case Via node (with travel time) Travel time (min) Energy consumption (kwh) 1 1 → 1.1 11 → 0.6 12 → 0.5 13 → 1.1 23 → 1.1 33 → 1.1 34 →0.835→0.636→0.737→0.938→0.848→0.958 →0.959→0.969→0.570→0.880→0.990→1.1100 18.5(include 3.2 min waiting time) 1.049  2 1 → 1.1 11 → 1 12 → 1 13 → 1.1 23 → 1.1 33 → 1.1 34 →135→136→137→138→148→158 →159→169→170→180→190→1.1100 18.5 0.776The results show that the nonstop driving mode adjusts the travel time of most sections during traveling, but theoretically the travel times in two cases are the same. However, Case1 includes 3.2 minutes of waiting time; it will increase the driver's waiting anxiety. On the other hand, the energy consumption in Case 2 is 26% less than that in Case 1. To avoid further elaboration, the results of signal timing Scenario 1 (departure time is 8:00) in two driving modes are compared here. The energy consumption can be reduced by 20% to 30% at other different departure time and signal timing. The time adjustment of the planning routes is no longer listed one by one. The energy consumption and energy saving efficiency are shown in Table 11. In summary, the approach we proposed can save the energy and eliminate the waiting time and find the planning route with high efficiency and energy saving.Table 11
The comparison of energy consumption in two cases under different signal timing and departure time.
Departure time Energy consumption in Case1 (kwh) Energy consumption in Case2 (kwh) Efficient Scenario 1 8:00 1.049 0.776 26% 8:10 1.093 0.776 29% 8:20 1.103 0.783 29% 8:30 1.012 0.789 22% Scenario 2 8:00 1.077 0.786 27% 8:10 1.111 0.778 30% 8:20 1.071 0.782 27% 8:30 0.980 0.784 20% Scenario 3 8:00 1.029 0.803 22% 8:10 1.053 0.800 24% 8:20 1.003 0.802 20% 8:30 1.043 0.803 23% Scenario 4 8:00 1.123 0.786 30% 8:10 1.043 0.782 25% 8:20 1.032 0.795 23% 8:30 1.054 0.801 24%


## 5. Conclusions

This paper provides an energy-efficient dynamic route planning approach for EVs. The approach aims to optimize both travel time and energy consumption by avoiding unnecessary stopping brake. To implement the dynamic traffic environment, the state-time-space network is introduced to clearly describe the changeable travel time and intersection signal state in the time axis discretization. Then, a multiobjective 0-1 integer model is formulated, and two methods are adopted to transform the multiobjective 0-1 integer model to the single objective one. The improved label-correcting algorithm is designed to solve the proposed model. The results show that the proposed approach can save the energy and eliminate the waiting time in finding the optimal planning route.Future research can be further worked out from the following aspects:(1) To facilitate the study, we assume that the electricity of the EV is sufficient. However, electric vehicles need to be recharged during travel. The battery capacity of EV and the charging station location may impact the planning route, which will be a field for further research.(2) In this paper, we only simulate the single vehicle with single OD traveling in the dynamic traffic network. However, due to the interaction of multiple vehicles, the actual traffic situation in a realistic road network is more complex. The multivehicle routing problem considering intersection signals will be a challenge in the future research.(3) From the perspective of optimization of traffic flow assignment, the energy-efficient route optimization approach will be another interesting challenge for our future research agenda.



---

*Source: 2607402-2019-08-26.xml*