# Automatic Vehicles’ Trajectories Optimization on Highway Exclusive Lanes

Authors: Lingjuan Chen; Yangbo Ruan; Yiquan Gou
Journal: Journal of Advanced Transportation
 (2022)

---

## Abstract

The rapid development of V2X communication has made it possible to optimize and control the trajectories of vehicles from the whole traffic flow’s perspective and improve traffic performance. Therefore, this paper discusses the trajectories management problem on highway facilitated with lanes exclusively for autonomous vehicles (AVs). The paper proposes a model that aims to search for optimal trajectories and minimize total travel time for AVs with multiple initial and target states while averting crashes and conforming to vehicles’ kinetic. Dividing the time zone into discrete pieces, the model is analyzed as a large-scale discrete problem influenced by the randomness of the sequence of vehicles. A two-phase algorithm combined with upper evolution strategies and lower dynamic programming is developed to diminish stochastics and reduce computation step by step and solve the trajectories optimization model. Numerical experiments validate that the proposed method is capable of generating optimal trajectories for multiple AVs and approaching to system optimum by simultaneously solving all the spatial and temporal values of the trajectories. The two-phase algorithm can be applied efficiently in practice to obtain a feasible approximate solution for trajectories optimization by presetting appropriate algorithm parameters.


---

## Body

## 1. Introduction

Autonomous vehicles (AVs) are likely to create a revolutionary paradigm shift in the near future for real-time traffic system automation and control. The AVs can improve the transportation system’s performance and reduce congestion, emissions, accidents, and time consumption by delivering system optimum travel strategies to vehicles with V2X communication. Although it may take a long time to realize a popular market occupancy, an intermediate step could be achieved and bring significant improvements that AVs travel on exclusive lanes in a special zone, such as autonomous vehicle lanes [1–4] or autonomous vehicle areas [4–6]. It is envisaged that while AVs enter into the specialized area [5], the vehicle’s control is handed over to a central agent where the cyber component (e.g., data and shared information through vehicle-to-vehicle and vehicle-to-infrastructure communication) can aim to optimally control the physical entities (e.g., CAVs and non-CAVs); see [6]. The agent would guide it through the area (presumably by sending detailed trajectories to the vehicle’s onboard computer).Therefore, AV technologies allow vehicles to conform to uniform and global optimum trajectories aided by the cloud system’s central computation. For traditional human drivers, numerous studies on travel behaviors or trajectories choice have been conducted, including UE or SUE, predeparture route choice or en route revision, static or dynamic flow assignment, and macroscopic or microscopic vehicles’ trajectories with various information [7–12]. The above-mentioned studies are based on the foundation that travelers are selfish to reduce their consumption, and all travelers are unfamiliar with each other. While the drivers benefit much from traffic guidance to reduce congestion with the development of information systems, the travel cost still remains at a high level due to the users being unable to observe others’ reflections on multiple information. The AV technologies could change this mode with the evolution of communication and guide vehicles to respond immediately to preplanned trajectories. The route choice or trajectory solving is transformed into a mathematic optimization problem with several constraints similar to railway or aviation systems and different from the former choice behavior models. In recent years, significant attention has been given to AVs’ trajectories optimization, and a review can be concluded as follows.


### 1.1. Review of AV Developments in Traffic Management

Microsimulation models (cellular automata model and following model) have been used to develop the mixed traffic flow basic diagram and the influence of automatic driving on traffic flow [13]. Due to the difficulty in carrying out real vehicle experiments, the research on the traffic flow theory of connected and automated vehicles (CAV) is mainly focused on the longitudinal control technology of assisted driving, such as adaptive cruise and coadaptive cruise systems [14], as well as the road intersection management of AVs [15]. Studies have also been conducted to smooth highway traffic by controlling individual vehicles [16–18]. Since traffic management focuses on the interactions between the vehicles and resolving the conflicts that result from them, the studies that exclusively deal with trajectory planning for a single vehicle are not considered [19–23]. Liu et al. [24] solved an optimal trajectory problem for one single vehicle and used this trajectory as a template to control multiple vehicles with variable speed limits. Ahn et al. [25] also proposed a rolling-horizon individual CAV control strategy that only considered the road geometries. To find optimal trajectories for multiple AVs and improve the computational efficiency, Lu et al. [26] subsequently developed a specialized algorithm based on the rolling horizon approach (RHA) to obtain the best approximate solution.Despite relatively homogenous constraints and complex algorithms, the studies mentioned above demonstrated great potential in traffic management. Therefore, according to multiple performance indicators (such as distance, time, and energy), an optimal trajectory is generated from the initial state to the final state, which has important research significance in the field of intelligent vehicle motion planning.


### 1.2. Review of Vehicle Trajectory Optimization Models

Vehicle trajectory optimization has been extensively studied in a broader domain. According to the summary presented by Betts [27], the path planning problem is discretized in time by allowing the vehicle to only make decisions at discrete time intervals. It is further discretized in space by only allowing the vehicle to make a limited number of choices at each time step. For multivehicle trajectories, the vehicles move from the initial-boundary states to the final states, which can be solved directly by using linear programming or integer programming solver tools (CPLEX). He et al. [20] introduced vehicle queue constraints into a multiphase optimal control model to construct an approximation formulation that contained fewer decision variables and was easier to solve. Furthermore, Wu et al. [21] applied the model and the algorithm to obtain the trajectories across intersections. In terms of car-following behavior, Chen et al. [1, 5] proposed a time-dependent model to optimally deploy AV lanes on a general network consisting of both CVs and AVs. In the network [28], AVs and HDVs (human-driving vehicles) in the road links were managed to use exclusive lanes (common lane and AV lane). In this case, no interference between the two different types of vehicles existed in the links, so the advantage of AV technology would be fully utilized. Ghiasi et al. [29] obtained the optimal number of AV exclusive lanes under some common vehicle spacing settings. Kakimoto et al. [3] also studied the influence of CAVs on single-lane expressways based on different time intervals. Actually, there will be a long period of the mixed traffic flow by AVs and HDVs temporarily. For lane changing, Zhang [30] decomposed complex maneuvers into two submaneuvers, that is, lane change and lane keeping. Thus, the trajectory planning was simplified mainly based on lane-change maneuvers. Luo et al. [22] proved that vehicles could perform real-time calculations and update the lane-changing track before completing lane changing. Li et al. [15] studied the problem of simultaneous lane changing of multiple vehicles through the cooperation of multiple vehicles. Lu et al. [26] subsequently developed a mathematical model with safety and car-following constraints. This paper also assumes that the vehicle’s lane changing is instantaneous. The assumption would hold if AVs have sufficiently high autonomy and maneuverability; the travel time reduction of en route lane change could be offset.


### 1.3. Review of Vehicle Trajectory Optimization Methods

From the perspective of optimization methods, these problems are all nondeterministic polynomial-time-hard (NP-hard). The traditional methods for trajectory optimization include analytical approaches that can only solve simple problems with special structures and numerical approaches [31]. A vehicle trajectory is essentially an infinite-dimensional object in which the state (e.g., location, speed, acceleration) at each time spot can be varied. In the optimization model established by [32, 33], the traditional genetic algorithm has a small processing scale and is difficult to effectively deal with optimization problems with higher dimensions.It is challenging to obtain one single vehicle’s trajectory, particularly under nonlinear constraints. Therefore, Barnier and Brisset [34] adopted a new optimization method combining the genetic algorithm with the constraint satisfaction solving technology. The main idea was to deal with the subdomains of variables through the genetic algorithm, which is used for combinatorial optimization problems. Zhou et al. [35] devised a heuristic algorithm satisfying the need for formulating high-dimensional objects or complex system constraints, which could efficiently construct a smooth feasible trajectory vector with limited control parameters. Several studies have attempted to improve the algorithms by reducing the computation time. Gong’s [36] numerical experiments showed that the original algorithms in Koshal et al. [37] and their convergence analysis often led to small step lengths and slow convergence. While the two algorithms achieve the same numerical accuracy and convergence, the computation time of the modified algorithm was nearly reduced by half. Several recent studies have improved the results by approximating the trajectories with a simple piecewise quadratic function [35–38]. However, these approaches are heuristics and cannot guarantee the exact optimal solutions.Through Lu’s mixed-integer program (MIP) formulation, the feasible set may be tightened by rewriting some of the constraints or adding more valid constraints [26]. The RHA seems promising but requires further development to address the scheduling and equity constraints. Rios-Torres and Malikopoulos [39] presented an optimization framework and an analytical closed-form solution to find the optimal sequence and trajectory of vehicles. Wang et al. [40] proposed a distributed consensus protocol approach. However, the approach manages CAV based on relevant rules and does not use the optimization method to optimize the vehicle timing and trajectory as a whole.As concluded above, significant progress has been made in resolving the trajectories issues. One approach is establishing multiple models in various circumstances, such as planning tracks at sections, ramps, working zones, and other special areas. The goals are aimed to maximize capacity, reduce time cost, and fuel emissions with diversiform restrain. The other approach is adopting a mathematical algorithm or car-following simulation to decrease the computation time. However, there are several problems:(1)
Models of trajectory optimization for multiple vehicles operating in distinct lanes are typically simplified for two reasons: first, it is challenging to solve the resulting nonlinear optimization problems involving a large number of decision variables (note that we often). Second, it is generally accepted that modeling errors do not significantly contribute to the loss of objective values when long planning time horizons are considered [41]. However, this central issue has not been fully addressed in the literature [42–45], and conventional research suffers from two limitations. First, numerical methods alone (e.g., Liu et al. and Ahn et al.) do not provide sufficient analytical knowledge, intuitive understanding, or fundamental insight into the structure of problems and solutions, which may obstruct the discovery of some potentially useful management insights in real-world applications. Second, the trajectory generated by these methods [20, 21] may not be smooth and comfortable enough for the vehicle to follow in practice. Compared to previous research, to address this gap, this paper focuses on determining the optimal trajectory for each vehicle over the entire setting time horizon with a variety of initial and final states. In this paper, the spontaneous idea is to decompose the problem into a two-phase model. In the first phase, a commonly used strategy, evolutionary strategy (ES) algorithm is designed to define the lane-change slot and the lane occupation for each interval combined with lane-change rules. In the second phase, a mixed integrated linear model constituted by constraint conditions is solved, and the objective function is the fitness of the first phase. The algorithm can solve optimum trajectories satisfying all the constraints in an acceptable running time. The trajectories are relatively smooth while simultaneously conforming to car-following, lane-changing behaviors, and maintaining steady speeds.(2)
A modified algorithm is established to reduce the computation time: most existing studies [30, 46, 47] either oversimplified the trajectories’ constraints, adopted ad hoc heuristics [35, 38] without optimality assurance, or relied on complicated numerical procedures [48–50] that are unsuitable for real-time applications. In this paper, the ES can reduce the large scale of lane-change spots and rapidly search for optimum results by gathering a series of individuals’ advantages. In the second phase, cutting invalid vehicles’ orders reserves sufficient optimum results and speeds up the solving process in the dynamic programming for fitness computation. The evolution strategy is capable of reducing the large scale of lane-change spots and searching for optimum results. Cutting invalid vehicles’ orders at each stage reserves sufficient optimum results.The remainder of this paper is organized as follows. Section2 discusses the hypothesis of automatic traffic flow in an exclusive area and the objectives and constraints of trajectory management. Section 3 introduces and analyzes a trajectory optimization model. Section 4 proposes a two-phase solution algorithm that utilizes upper evolution strategies and lowers dynamic programming to reduce the stochasticity associated with lane-change slot and vehicle order. Section 5 summarizes the results of a numerical experiment and presents the results of a controlled experiment designed to verify the algorithm’s effectiveness. Finally, Section 6 summarizes the findings, implications, and limitations and suggests some future research directions.


## 1.1. Review of AV Developments in Traffic Management

Microsimulation models (cellular automata model and following model) have been used to develop the mixed traffic flow basic diagram and the influence of automatic driving on traffic flow [13]. Due to the difficulty in carrying out real vehicle experiments, the research on the traffic flow theory of connected and automated vehicles (CAV) is mainly focused on the longitudinal control technology of assisted driving, such as adaptive cruise and coadaptive cruise systems [14], as well as the road intersection management of AVs [15]. Studies have also been conducted to smooth highway traffic by controlling individual vehicles [16–18]. Since traffic management focuses on the interactions between the vehicles and resolving the conflicts that result from them, the studies that exclusively deal with trajectory planning for a single vehicle are not considered [19–23]. Liu et al. [24] solved an optimal trajectory problem for one single vehicle and used this trajectory as a template to control multiple vehicles with variable speed limits. Ahn et al. [25] also proposed a rolling-horizon individual CAV control strategy that only considered the road geometries. To find optimal trajectories for multiple AVs and improve the computational efficiency, Lu et al. [26] subsequently developed a specialized algorithm based on the rolling horizon approach (RHA) to obtain the best approximate solution.Despite relatively homogenous constraints and complex algorithms, the studies mentioned above demonstrated great potential in traffic management. Therefore, according to multiple performance indicators (such as distance, time, and energy), an optimal trajectory is generated from the initial state to the final state, which has important research significance in the field of intelligent vehicle motion planning.


## 1.2. Review of Vehicle Trajectory Optimization Models

Vehicle trajectory optimization has been extensively studied in a broader domain. According to the summary presented by Betts [27], the path planning problem is discretized in time by allowing the vehicle to only make decisions at discrete time intervals. It is further discretized in space by only allowing the vehicle to make a limited number of choices at each time step. For multivehicle trajectories, the vehicles move from the initial-boundary states to the final states, which can be solved directly by using linear programming or integer programming solver tools (CPLEX). He et al. [20] introduced vehicle queue constraints into a multiphase optimal control model to construct an approximation formulation that contained fewer decision variables and was easier to solve. Furthermore, Wu et al. [21] applied the model and the algorithm to obtain the trajectories across intersections. In terms of car-following behavior, Chen et al. [1, 5] proposed a time-dependent model to optimally deploy AV lanes on a general network consisting of both CVs and AVs. In the network [28], AVs and HDVs (human-driving vehicles) in the road links were managed to use exclusive lanes (common lane and AV lane). In this case, no interference between the two different types of vehicles existed in the links, so the advantage of AV technology would be fully utilized. Ghiasi et al. [29] obtained the optimal number of AV exclusive lanes under some common vehicle spacing settings. Kakimoto et al. [3] also studied the influence of CAVs on single-lane expressways based on different time intervals. Actually, there will be a long period of the mixed traffic flow by AVs and HDVs temporarily. For lane changing, Zhang [30] decomposed complex maneuvers into two submaneuvers, that is, lane change and lane keeping. Thus, the trajectory planning was simplified mainly based on lane-change maneuvers. Luo et al. [22] proved that vehicles could perform real-time calculations and update the lane-changing track before completing lane changing. Li et al. [15] studied the problem of simultaneous lane changing of multiple vehicles through the cooperation of multiple vehicles. Lu et al. [26] subsequently developed a mathematical model with safety and car-following constraints. This paper also assumes that the vehicle’s lane changing is instantaneous. The assumption would hold if AVs have sufficiently high autonomy and maneuverability; the travel time reduction of en route lane change could be offset.


## 1.3. Review of Vehicle Trajectory Optimization Methods

From the perspective of optimization methods, these problems are all nondeterministic polynomial-time-hard (NP-hard). The traditional methods for trajectory optimization include analytical approaches that can only solve simple problems with special structures and numerical approaches [31]. A vehicle trajectory is essentially an infinite-dimensional object in which the state (e.g., location, speed, acceleration) at each time spot can be varied. In the optimization model established by [32, 33], the traditional genetic algorithm has a small processing scale and is difficult to effectively deal with optimization problems with higher dimensions.It is challenging to obtain one single vehicle’s trajectory, particularly under nonlinear constraints. Therefore, Barnier and Brisset [34] adopted a new optimization method combining the genetic algorithm with the constraint satisfaction solving technology. The main idea was to deal with the subdomains of variables through the genetic algorithm, which is used for combinatorial optimization problems. Zhou et al. [35] devised a heuristic algorithm satisfying the need for formulating high-dimensional objects or complex system constraints, which could efficiently construct a smooth feasible trajectory vector with limited control parameters. Several studies have attempted to improve the algorithms by reducing the computation time. Gong’s [36] numerical experiments showed that the original algorithms in Koshal et al. [37] and their convergence analysis often led to small step lengths and slow convergence. While the two algorithms achieve the same numerical accuracy and convergence, the computation time of the modified algorithm was nearly reduced by half. Several recent studies have improved the results by approximating the trajectories with a simple piecewise quadratic function [35–38]. However, these approaches are heuristics and cannot guarantee the exact optimal solutions.Through Lu’s mixed-integer program (MIP) formulation, the feasible set may be tightened by rewriting some of the constraints or adding more valid constraints [26]. The RHA seems promising but requires further development to address the scheduling and equity constraints. Rios-Torres and Malikopoulos [39] presented an optimization framework and an analytical closed-form solution to find the optimal sequence and trajectory of vehicles. Wang et al. [40] proposed a distributed consensus protocol approach. However, the approach manages CAV based on relevant rules and does not use the optimization method to optimize the vehicle timing and trajectory as a whole.As concluded above, significant progress has been made in resolving the trajectories issues. One approach is establishing multiple models in various circumstances, such as planning tracks at sections, ramps, working zones, and other special areas. The goals are aimed to maximize capacity, reduce time cost, and fuel emissions with diversiform restrain. The other approach is adopting a mathematical algorithm or car-following simulation to decrease the computation time. However, there are several problems:(1)
Models of trajectory optimization for multiple vehicles operating in distinct lanes are typically simplified for two reasons: first, it is challenging to solve the resulting nonlinear optimization problems involving a large number of decision variables (note that we often). Second, it is generally accepted that modeling errors do not significantly contribute to the loss of objective values when long planning time horizons are considered [41]. However, this central issue has not been fully addressed in the literature [42–45], and conventional research suffers from two limitations. First, numerical methods alone (e.g., Liu et al. and Ahn et al.) do not provide sufficient analytical knowledge, intuitive understanding, or fundamental insight into the structure of problems and solutions, which may obstruct the discovery of some potentially useful management insights in real-world applications. Second, the trajectory generated by these methods [20, 21] may not be smooth and comfortable enough for the vehicle to follow in practice. Compared to previous research, to address this gap, this paper focuses on determining the optimal trajectory for each vehicle over the entire setting time horizon with a variety of initial and final states. In this paper, the spontaneous idea is to decompose the problem into a two-phase model. In the first phase, a commonly used strategy, evolutionary strategy (ES) algorithm is designed to define the lane-change slot and the lane occupation for each interval combined with lane-change rules. In the second phase, a mixed integrated linear model constituted by constraint conditions is solved, and the objective function is the fitness of the first phase. The algorithm can solve optimum trajectories satisfying all the constraints in an acceptable running time. The trajectories are relatively smooth while simultaneously conforming to car-following, lane-changing behaviors, and maintaining steady speeds.(2)
A modified algorithm is established to reduce the computation time: most existing studies [30, 46, 47] either oversimplified the trajectories’ constraints, adopted ad hoc heuristics [35, 38] without optimality assurance, or relied on complicated numerical procedures [48–50] that are unsuitable for real-time applications. In this paper, the ES can reduce the large scale of lane-change spots and rapidly search for optimum results by gathering a series of individuals’ advantages. In the second phase, cutting invalid vehicles’ orders reserves sufficient optimum results and speeds up the solving process in the dynamic programming for fitness computation. The evolution strategy is capable of reducing the large scale of lane-change spots and searching for optimum results. Cutting invalid vehicles’ orders at each stage reserves sufficient optimum results.The remainder of this paper is organized as follows. Section2 discusses the hypothesis of automatic traffic flow in an exclusive area and the objectives and constraints of trajectory management. Section 3 introduces and analyzes a trajectory optimization model. Section 4 proposes a two-phase solution algorithm that utilizes upper evolution strategies and lowers dynamic programming to reduce the stochasticity associated with lane-change slot and vehicle order. Section 5 summarizes the results of a numerical experiment and presents the results of a controlled experiment designed to verify the algorithm’s effectiveness. Finally, Section 6 summarizes the findings, implications, and limitations and suggests some future research directions.


## 2. Analysis of Automatic Traffic Management

This section proposes an AV trajectory optimization problem on a single exclusive highway segment. All the vehicles on the segment consisting of three lanes are automatic, which could be comprehensively organized, aiming to uniform objectives. Mixed traffic management with HDVs is the next research topic. Unlike the existing HDV management theories, the AV trajectory problem is a travel behavior optimization program instead of human-driven habits’ approximate simulation. The main purpose is to determine each vehicle’s optimum trajectory along the whole setting time horizon with various initial and final states.


### 2.1. Hypothesis of Automatic Traffic Flow

The research problem and the details of the hypothesis are presented as follows:(1)
Trajectory optimization is strictly a time-continuous problem. However, in reality, the velocity, acceleration, or deceleration are impossible to change continuously due to the constraints of vehicles’ mechanical properties and reaction time. Therefore, in this paper, the time horizon is initially divided into identical segments denoted byk and Δt is each interval’s duration k=1,2,…,K. For the consideration of optimization efficiency and computation consumption, the interval’s duration should be set as a proper value to obtain a satisfying result and reduce the computational complexity as much as possible.(2)
The driven road is set as a highway or freeway and not as an urban network, as depicted in Figure1. Vehicle characteristic parameters include entry time, velocity, acceleration, entry lane, and objective exit lane. If the entry does not conform with the exit lane, the vehicle must change the lane at the optimum interval. Some rules for lane-changing are explained as follows:①
The objective lane of the lane-changing vehicle must be the adjacent lane close to the final exit lane. Specifically, the vehicles are forbidden to travel across two lanes in one interval.②
In this paper, compulsory lane-change induced by nonconformity of entry and exit lanes is the sole concern. However, en route lane change due to lanes’ travel time difference is not considered.This assumption could be reasonable in automatic traffic management. For AVs, the trajectories are controlled and optimized comprehensively, and the travel time reduction of en route lane change could be offset. This explanation is different from the HDVs, whose trajectories are decided by the drivers’ self-strategy, and lane-change for shorter travel cost is obvious for individuals.③
Lane changes of vehicles can be completed during a time interval. In other words, if a vehicle’s lane-change time spot isk, then the vehicle will drive on the objective lane during the whole interval k. It will hold since the lane-change preparation and space adjustment are already accomplished before.(3)
In reality, incoming flow to the highway segment is continuous along the time axis. Therefore, a discrete-time horizon is set in this paper for the optimization section. The spatial-temporal segmentation and rolling promotion are credible and efficient for traffic management complex systems. Therefore, the proposed model and theory can be utilized in a continuous system.Figure 1
Illustration of vehicle trajectories.


### 2.2. Trajectory Management Objectives and Constraints

Under the above assumptions, the proposed solution aims to obtain the vehicle’s velocity, acceleration/deceleration, position for each interval, and travel time on the segment. The optimal objective includes but is not limited to all vehicles’ total time cost, fuel consumption, emission, and driven comfort. These indexes are all vital and closely correlate to the vehicle’s maneuvers. In the proposed model, a minimum travel time is simplistically established for the unique objective of efficiency. Similarly, others could be utilized just by adopting various index calculation methods.Vehicles’ trajectories are subject to many constraints: (1) ensuring no collisions and safe space for each lane during the time horizon, (2) guaranteeing the vehicles travel on the exact lane before exiting from the road segment, and (3) restricting the lane-change maneuvers to the above hypothesis and avoiding crashes on the current and objective lanes simultaneously. The following section will explicitly explain the optimization problem and establish a mathematical model based on the above analysis.


## 2.1. Hypothesis of Automatic Traffic Flow

The research problem and the details of the hypothesis are presented as follows:(1)
Trajectory optimization is strictly a time-continuous problem. However, in reality, the velocity, acceleration, or deceleration are impossible to change continuously due to the constraints of vehicles’ mechanical properties and reaction time. Therefore, in this paper, the time horizon is initially divided into identical segments denoted byk and Δt is each interval’s duration k=1,2,…,K. For the consideration of optimization efficiency and computation consumption, the interval’s duration should be set as a proper value to obtain a satisfying result and reduce the computational complexity as much as possible.(2)
The driven road is set as a highway or freeway and not as an urban network, as depicted in Figure1. Vehicle characteristic parameters include entry time, velocity, acceleration, entry lane, and objective exit lane. If the entry does not conform with the exit lane, the vehicle must change the lane at the optimum interval. Some rules for lane-changing are explained as follows:①
The objective lane of the lane-changing vehicle must be the adjacent lane close to the final exit lane. Specifically, the vehicles are forbidden to travel across two lanes in one interval.②
In this paper, compulsory lane-change induced by nonconformity of entry and exit lanes is the sole concern. However, en route lane change due to lanes’ travel time difference is not considered.This assumption could be reasonable in automatic traffic management. For AVs, the trajectories are controlled and optimized comprehensively, and the travel time reduction of en route lane change could be offset. This explanation is different from the HDVs, whose trajectories are decided by the drivers’ self-strategy, and lane-change for shorter travel cost is obvious for individuals.③
Lane changes of vehicles can be completed during a time interval. In other words, if a vehicle’s lane-change time spot isk, then the vehicle will drive on the objective lane during the whole interval k. It will hold since the lane-change preparation and space adjustment are already accomplished before.(3)
In reality, incoming flow to the highway segment is continuous along the time axis. Therefore, a discrete-time horizon is set in this paper for the optimization section. The spatial-temporal segmentation and rolling promotion are credible and efficient for traffic management complex systems. Therefore, the proposed model and theory can be utilized in a continuous system.Figure 1
Illustration of vehicle trajectories.


## 2.2. Trajectory Management Objectives and Constraints

Under the above assumptions, the proposed solution aims to obtain the vehicle’s velocity, acceleration/deceleration, position for each interval, and travel time on the segment. The optimal objective includes but is not limited to all vehicles’ total time cost, fuel consumption, emission, and driven comfort. These indexes are all vital and closely correlate to the vehicle’s maneuvers. In the proposed model, a minimum travel time is simplistically established for the unique objective of efficiency. Similarly, others could be utilized just by adopting various index calculation methods.Vehicles’ trajectories are subject to many constraints: (1) ensuring no collisions and safe space for each lane during the time horizon, (2) guaranteeing the vehicles travel on the exact lane before exiting from the road segment, and (3) restricting the lane-change maneuvers to the above hypothesis and avoiding crashes on the current and objective lanes simultaneously. The following section will explicitly explain the optimization problem and establish a mathematical model based on the above analysis.


## 3. Trajectory Optimization Model

### 3.1. Model Notations and Variables

The road segment is denoted asRxo,xd; the symbols xo,xd are location stamped as origin and terminus; and road length is L. Notation i1≤i≤C represents vehicle’s number ordered by entering time, where C is the total number of vehicles. The artery consists of three lanes denoted as l=1,2,3. lsi,lei are set as the initial and final lanes for vehicle i, respectively. Other variables are listed in Table 1.Table 1
Description of variables.
VariablesDescriptionxikPosition of vehiclei at interval kaikAcceleration/deceleration of vehiclei at interval kdikDeceleration of vehiclei at interval kvikVelocity of vehiclei at interval klikOccupied lane of vehiclei at interval kNi1, Ni2, …Lane-change intervals of vehicleikiin, kioutEntering and exiting time of vehiclei


### 3.2. Objectives and Constraints

In this paper, vehicles’ total travel cost traversing the road is the unique objective for trajectory optimization.(1)Z=min∑i∈Ckiout−kiin.A binary variableθik is induced to indicate whether the vehicle i still travels on the segment. If xik−xd≥0, θik=0; otherwise, θik=1. θik is subject to the constraints as described below:(2)θik−1×M<xd−xik≤θik×M,(3)ifk<kiin,θik=0,xik+1=0,where M is a large positive real number. If θik=1, equation (2) reads 0<xd−xik≤M and means xd>xik; otherwise, if θik=0, equation (2) reads xd<xik. Thus, formulas (2)∼(3) explain the variable δik exactly, and objective Z could be reconstructed as follows:(4)Z=min∑i∈C∑1≤k≤Kθik×Δt.The vehicles’ movement on the segment is constrained to a series of conditions:


#### 3.2.1. Velocity and Acceleration Constraints

(5)−dimax≤aik≤aimax,1≤i≤C,(6)0≤vik≤vimax,1≤i≤C,(7)vik=vik+aik×Δt,(8)xik=xik−1+vik×Δt+12×aik×Δt2.dimax, aimax and vimax are the limited deceleration, acceleration, and velocity for vehicle i, respectively. Equations (7) and (8) explain the recurrence relation among variables aik, vik, and xik and can hold in a short time duration.


#### 3.2.2. Collision Avoidance Constraints

Two binary auxiliary variables,δijk and θik, are defined to construct the safety constraints. If vehicle i is the former vehicle of j on the identical lane k, δijk=1; otherwise, δijk=0. The position relationship can be imposed as follows:(9)0≤δijk−xik−xjkM<1,where xik−xjk>0 and variable δijk=1; otherwise, δijk=0. Therefore, equation (9) is consistent with the meaning of δijk.Constraint 1.
Safety constraints for vehicles in the same lane. If vehiclei is the former one, i and j are not intended to change lanes:(10)xik+1−xjk+1≥th×vjk+1.such that lik=ljk,k≠Ni1,Ni2,Nj1,Nj2, where th is the reaction time for driving straight. Ni1,Ni2,Nj1,Nj2 are vehicles’ lane-change intervals. If 1≤k≤Ni1, lik=lsi; if Ni1+1≤k≤Ni2, lik=lsi±1. To indicate the vehicle sequence and lane occupation, equation (10) becomes(11)1−δijk−θik−θjk+2×M+xik+1−xjk+1≥th×vjk+1.
It can be proved that equation (11) is equivalent to equation (10). If θik=0 or θjk = 0, equation (11) is not validated. When θik=1, θjk = 1; if δijk = 0, vehicle i is not following vehicle j, and equation (11) is not validated; if δijk = 1, equation (11) is active and consistent with equation (10).Constraint 2.
Safety constraints at a lane-change time interval. When vehiclei intends to the objective lane at slots Ni1,Ni2, a shorter reaction time th′ and safety space th′×xik+1 could be accepted. Meanwhile, collisions on the current and objective lanes must be avoided simultaneously.
For the vehicles in the current lane, equation (11) can be amended as follows:(12)1−δijk−θik−θjk+2×M+xik+1−xjk+1≥th'×vjk+1such that lik=ljk,k=Ni1,Ni2.
For the vehicles on the target lanelik', equation (12) can be repeated such that lik'=lik±1;ljk=lik';k=Ni1,Ni2.


#### 3.2.3. Compulsory Lane-Change Constraints

When vehiclei leaves out the road segment, it is ensured that the current lane is identical to the final objective lane. In other words, lane change is guaranteed to accomplish before the destination. The following constraint should be satisfied:(13)xiNimi<xd,where mi is the total lane-change number and Nimi represents the last lane-change interval.


### 3.3. Model Properties

Claim 1.
The established model is an NP-hard problem. The size of the model can be estimated as follows:(14)∏i=1C'T−NCi′−C′−i+1∗C'−i∗C3+1∗C∗T,where C and C′ represent the total numbers of vehicles and “lane-changing” vehicles, respectively; Ci′ is the i-th lane-change vehicle with ascending order; and NCi′ is the i-th lane-change interval.
The proposed model is equivalent to the traveling salesman problem (TSP). The variable described as “lane-changing time” is the critical element bringing out the uncertainties of vehicles’ order in the same lane. For safety constraints in equations (9)–(12), the adjacent vehicles i,j cannot be determined that deduces the computational complexity of the model.
In equation (14), for any Ci′, summed as C′−i, the feasible lane-change interval can take any integer value between NCi−1'+1 and T−C′−i. The minimum value coincides with Assumption (2), and the maximum value guarantees time possibility for the subsequent vehicles. Thus, just considering lane-changing time, the complexity can be expressed as T−C′−i−NCi−1'+1∗C′−i.
For considering entering into multiple vehicles’ gaps, roughlyC/3 vehicles can be counted on the target lane with C/3+1 gaps. Thus, the total number of vehicle orders can be expressed as follows:(15)∏i=1C'T−NCi′−C′−i+1∗C'−i∗C/3+1.
For a stationary vehicle order, the model employsC∗T variables to define acceleration for every vehicle at each time interval. Therefore, the size of the model is ∏i=1C′T−NCi′−C′−i+1∗C′−i∗C/3+1∗C∗T. It is obvious that the computation complexity increases exponentially with C′ and T and quadratically with C.
From the above analysis, for vehiclei, lane-change intervals Ni1,Ni2,…,NimiNimi are the core variables to generate uncertainty of lane occupation and vehicle order, resulting in large model size. The spontaneous idea is to decompose the problem into a two-phase model to reduce the computational complexity.
In the first phase, a commonly used strategy, ES is designed to define the lane-change interval and lane occupation combined with lane-change rules.
For example, if vehiclei on the initial lane lsi needs to change lane at k=Ni1,Ni2Ni2>Ni1 to enter into the final lane lei, the following can be defined:(16)Ifkiin≤k<Ni1,thenlik=lsi,(17)IfNi1≤k<Ni2,thenlik=li1±1,(18)IfNi2≤kiout,thenlik=lei.
In the second phase, a mixed integrated linear model constituted by equations (1)–(13)is solved, and equation (4) is the fitness of the first phase. With the determination of lane occupation’s time, the mixed integrated linear model’s complexity is reduced drastically. However, the vehicle orders dependent on chosen gap are also discrete random variables that can be further reduced in the solution space and illustrated in Section 4 explicitly.
The proposed strategy focuses on the lane occupation and vehicle sequence and decomposes the complex problem into two phases. On the one hand, the maneuver reduces the size of variables and constraints. On the other hand, the lane-change define solution is a commonly used and maturely developed algorithm that can rapidly obtain a satisfactory scheme.


## 3.1. Model Notations and Variables

The road segment is denoted asRxo,xd; the symbols xo,xd are location stamped as origin and terminus; and road length is L. Notation i1≤i≤C represents vehicle’s number ordered by entering time, where C is the total number of vehicles. The artery consists of three lanes denoted as l=1,2,3. lsi,lei are set as the initial and final lanes for vehicle i, respectively. Other variables are listed in Table 1.Table 1
Description of variables.
VariablesDescriptionxikPosition of vehiclei at interval kaikAcceleration/deceleration of vehiclei at interval kdikDeceleration of vehiclei at interval kvikVelocity of vehiclei at interval klikOccupied lane of vehiclei at interval kNi1, Ni2, …Lane-change intervals of vehicleikiin, kioutEntering and exiting time of vehiclei


## 3.2. Objectives and Constraints

In this paper, vehicles’ total travel cost traversing the road is the unique objective for trajectory optimization.(1)Z=min∑i∈Ckiout−kiin.A binary variableθik is induced to indicate whether the vehicle i still travels on the segment. If xik−xd≥0, θik=0; otherwise, θik=1. θik is subject to the constraints as described below:(2)θik−1×M<xd−xik≤θik×M,(3)ifk<kiin,θik=0,xik+1=0,where M is a large positive real number. If θik=1, equation (2) reads 0<xd−xik≤M and means xd>xik; otherwise, if θik=0, equation (2) reads xd<xik. Thus, formulas (2)∼(3) explain the variable δik exactly, and objective Z could be reconstructed as follows:(4)Z=min∑i∈C∑1≤k≤Kθik×Δt.The vehicles’ movement on the segment is constrained to a series of conditions:


### 3.2.1. Velocity and Acceleration Constraints

(5)−dimax≤aik≤aimax,1≤i≤C,(6)0≤vik≤vimax,1≤i≤C,(7)vik=vik+aik×Δt,(8)xik=xik−1+vik×Δt+12×aik×Δt2.dimax, aimax and vimax are the limited deceleration, acceleration, and velocity for vehicle i, respectively. Equations (7) and (8) explain the recurrence relation among variables aik, vik, and xik and can hold in a short time duration.


### 3.2.2. Collision Avoidance Constraints

Two binary auxiliary variables,δijk and θik, are defined to construct the safety constraints. If vehicle i is the former vehicle of j on the identical lane k, δijk=1; otherwise, δijk=0. The position relationship can be imposed as follows:(9)0≤δijk−xik−xjkM<1,where xik−xjk>0 and variable δijk=1; otherwise, δijk=0. Therefore, equation (9) is consistent with the meaning of δijk.Constraint 1.
Safety constraints for vehicles in the same lane. If vehiclei is the former one, i and j are not intended to change lanes:(10)xik+1−xjk+1≥th×vjk+1.such that lik=ljk,k≠Ni1,Ni2,Nj1,Nj2, where th is the reaction time for driving straight. Ni1,Ni2,Nj1,Nj2 are vehicles’ lane-change intervals. If 1≤k≤Ni1, lik=lsi; if Ni1+1≤k≤Ni2, lik=lsi±1. To indicate the vehicle sequence and lane occupation, equation (10) becomes(11)1−δijk−θik−θjk+2×M+xik+1−xjk+1≥th×vjk+1.
It can be proved that equation (11) is equivalent to equation (10). If θik=0 or θjk = 0, equation (11) is not validated. When θik=1, θjk = 1; if δijk = 0, vehicle i is not following vehicle j, and equation (11) is not validated; if δijk = 1, equation (11) is active and consistent with equation (10).Constraint 2.
Safety constraints at a lane-change time interval. When vehiclei intends to the objective lane at slots Ni1,Ni2, a shorter reaction time th′ and safety space th′×xik+1 could be accepted. Meanwhile, collisions on the current and objective lanes must be avoided simultaneously.
For the vehicles in the current lane, equation (11) can be amended as follows:(12)1−δijk−θik−θjk+2×M+xik+1−xjk+1≥th'×vjk+1such that lik=ljk,k=Ni1,Ni2.
For the vehicles on the target lanelik', equation (12) can be repeated such that lik'=lik±1;ljk=lik';k=Ni1,Ni2.


### 3.2.3. Compulsory Lane-Change Constraints

When vehiclei leaves out the road segment, it is ensured that the current lane is identical to the final objective lane. In other words, lane change is guaranteed to accomplish before the destination. The following constraint should be satisfied:(13)xiNimi<xd,where mi is the total lane-change number and Nimi represents the last lane-change interval.


## 3.2.1. Velocity and Acceleration Constraints

(5)−dimax≤aik≤aimax,1≤i≤C,(6)0≤vik≤vimax,1≤i≤C,(7)vik=vik+aik×Δt,(8)xik=xik−1+vik×Δt+12×aik×Δt2.dimax, aimax and vimax are the limited deceleration, acceleration, and velocity for vehicle i, respectively. Equations (7) and (8) explain the recurrence relation among variables aik, vik, and xik and can hold in a short time duration.


## 3.2.2. Collision Avoidance Constraints

Two binary auxiliary variables,δijk and θik, are defined to construct the safety constraints. If vehicle i is the former vehicle of j on the identical lane k, δijk=1; otherwise, δijk=0. The position relationship can be imposed as follows:(9)0≤δijk−xik−xjkM<1,where xik−xjk>0 and variable δijk=1; otherwise, δijk=0. Therefore, equation (9) is consistent with the meaning of δijk.Constraint 1.
Safety constraints for vehicles in the same lane. If vehiclei is the former one, i and j are not intended to change lanes:(10)xik+1−xjk+1≥th×vjk+1.such that lik=ljk,k≠Ni1,Ni2,Nj1,Nj2, where th is the reaction time for driving straight. Ni1,Ni2,Nj1,Nj2 are vehicles’ lane-change intervals. If 1≤k≤Ni1, lik=lsi; if Ni1+1≤k≤Ni2, lik=lsi±1. To indicate the vehicle sequence and lane occupation, equation (10) becomes(11)1−δijk−θik−θjk+2×M+xik+1−xjk+1≥th×vjk+1.
It can be proved that equation (11) is equivalent to equation (10). If θik=0 or θjk = 0, equation (11) is not validated. When θik=1, θjk = 1; if δijk = 0, vehicle i is not following vehicle j, and equation (11) is not validated; if δijk = 1, equation (11) is active and consistent with equation (10).Constraint 2.
Safety constraints at a lane-change time interval. When vehiclei intends to the objective lane at slots Ni1,Ni2, a shorter reaction time th′ and safety space th′×xik+1 could be accepted. Meanwhile, collisions on the current and objective lanes must be avoided simultaneously.
For the vehicles in the current lane, equation (11) can be amended as follows:(12)1−δijk−θik−θjk+2×M+xik+1−xjk+1≥th'×vjk+1such that lik=ljk,k=Ni1,Ni2.
For the vehicles on the target lanelik', equation (12) can be repeated such that lik'=lik±1;ljk=lik';k=Ni1,Ni2.


## 3.2.3. Compulsory Lane-Change Constraints

When vehiclei leaves out the road segment, it is ensured that the current lane is identical to the final objective lane. In other words, lane change is guaranteed to accomplish before the destination. The following constraint should be satisfied:(13)xiNimi<xd,where mi is the total lane-change number and Nimi represents the last lane-change interval.


## 3.3. Model Properties

Claim 1.
The established model is an NP-hard problem. The size of the model can be estimated as follows:(14)∏i=1C'T−NCi′−C′−i+1∗C'−i∗C3+1∗C∗T,where C and C′ represent the total numbers of vehicles and “lane-changing” vehicles, respectively; Ci′ is the i-th lane-change vehicle with ascending order; and NCi′ is the i-th lane-change interval.
The proposed model is equivalent to the traveling salesman problem (TSP). The variable described as “lane-changing time” is the critical element bringing out the uncertainties of vehicles’ order in the same lane. For safety constraints in equations (9)–(12), the adjacent vehicles i,j cannot be determined that deduces the computational complexity of the model.
In equation (14), for any Ci′, summed as C′−i, the feasible lane-change interval can take any integer value between NCi−1'+1 and T−C′−i. The minimum value coincides with Assumption (2), and the maximum value guarantees time possibility for the subsequent vehicles. Thus, just considering lane-changing time, the complexity can be expressed as T−C′−i−NCi−1'+1∗C′−i.
For considering entering into multiple vehicles’ gaps, roughlyC/3 vehicles can be counted on the target lane with C/3+1 gaps. Thus, the total number of vehicle orders can be expressed as follows:(15)∏i=1C'T−NCi′−C′−i+1∗C'−i∗C/3+1.
For a stationary vehicle order, the model employsC∗T variables to define acceleration for every vehicle at each time interval. Therefore, the size of the model is ∏i=1C′T−NCi′−C′−i+1∗C′−i∗C/3+1∗C∗T. It is obvious that the computation complexity increases exponentially with C′ and T and quadratically with C.
From the above analysis, for vehiclei, lane-change intervals Ni1,Ni2,…,NimiNimi are the core variables to generate uncertainty of lane occupation and vehicle order, resulting in large model size. The spontaneous idea is to decompose the problem into a two-phase model to reduce the computational complexity.
In the first phase, a commonly used strategy, ES is designed to define the lane-change interval and lane occupation combined with lane-change rules.
For example, if vehiclei on the initial lane lsi needs to change lane at k=Ni1,Ni2Ni2>Ni1 to enter into the final lane lei, the following can be defined:(16)Ifkiin≤k<Ni1,thenlik=lsi,(17)IfNi1≤k<Ni2,thenlik=li1±1,(18)IfNi2≤kiout,thenlik=lei.
In the second phase, a mixed integrated linear model constituted by equations (1)–(13)is solved, and equation (4) is the fitness of the first phase. With the determination of lane occupation’s time, the mixed integrated linear model’s complexity is reduced drastically. However, the vehicle orders dependent on chosen gap are also discrete random variables that can be further reduced in the solution space and illustrated in Section 4 explicitly.
The proposed strategy focuses on the lane occupation and vehicle sequence and decomposes the complex problem into two phases. On the one hand, the maneuver reduces the size of variables and constraints. On the other hand, the lane-change define solution is a commonly used and maturely developed algorithm that can rapidly obtain a satisfactory scheme.


## 4. Two-Phase Algorithm for Trajectory Management

### 4.1. The First Phase

Lane-change interval optimization. Evolution strategies are search procedures aiming to mimic the natural evolution of the large-scale stochastic and reduce the feasible solutions using elimination mechanisms based on objective function and mutation, crossover, and selection operations. This method is used for the upper level to determine the optimal lane-changing interval.


#### 4.1.1. Coding for Individual Representation

It should be noted that the multidimensional coding combined with lane-change time and vehicles’ order is not used. Although the multidimensional coding has the advantage of a simple points search operation, the critical defect is that the points’ feasibility is not guaranteed. In the evolution process, a large number of infeasible solutions cause the loss of solutions’ diversity. Therefore, the ES methods just eliminate one random element, and the vehicle orders’ diversity is remained to solve in the second phase.Implementing the ES for the trajectory optimization model requires the representation of the potential solution, which is a point in the feasible search space. Each solution is a vector consisting of integer variables, denoted asN11,N12,…,N1m1⋯Nn1,Nn2,…,NnmnN1m1Nn1,Nn2Nnmn. In the expression, Nij represents the j-th lane-change slot of vehicle i, and mi is the number of total maneuvers. The lane-change slots coding by integer representations can be defined with a series of requirements as follows:(1)
Coding Approach Coding approach: for each vehicle i, the coding variables Ni1,Ni2,…,NimiNimi satisfy Ni1<Ni2<⋯<Nimi. It is obvious that the posterior lane change is later than the former one. Spontaneously, two coding methods can be utilized to realize variables’ feasibility. Table 2 introduces and compares the two approaches. In this paper, Approach 1 is chosen for variable coding by generating new individuals to eliminate duplicate ones and augment diversity. Approach 2 is prone to cause the latter variable to be out of range due to a large frontier value, and the individual representation is an unfeasible solution. Therefore, Approach 2 is abandoned.(2)
Variables range constraints:Nij<Nij=1,2,…,mi, where Ni is preset to ensure that vehicle i completes changing lanes before driving out.(3)
Initialization: a random value in the boundary range is assigned to each decision variable for every individual of the initial population.(19)Nij0=kiin+rand0,1×Ni−kiin.Table 2
Reranking and construction coding methods.
Approach 1: rerankingApproach 2: constructionCoding processRank coding variablesNi1,Ni2,…,NimiNimi with ascending sort for each i to constitute a new feasible individual.DenoteNij+1=Nij+εij, where εij is a random integer number, and generate a valid individual by coding εij.AdvantageEasily practicable and code value restricted in variable range by simple constraints.Guarantee individuals’ diversity, which is the shortage of approach 1.DisadvantageReduce diversity. For example, codeNi1,Ni2,…,NimiNi1,Ni2Nimi is identical with Nimi,Ni2,…,Ni1Ni1.Difficult to satisfy variables’ value range


#### 4.1.2. Mutation

At generationg, for each parent vector N11g,N12g,…,N1m1g,…,Nn1g,Nn2g,…,NmnngN1m1gNn1g,Nn2g,Nnmng in the population, introduce indexes r1,r2 (r1≠r2) to stamp different locations of vectors. The corresponding mutational vector is translated by three common strategies as follows:First strategy: interconverting values at two random points(20)Nr1g+1=Nr2g,Nr2g+1=Nr1g.Second strategy: permute the variables located in the intervalr1,r2 in reverse order(21)Njg+1=Nr1+r2−jg,r1≤j≤r2.Third strategy: insert variable located at the spotr1 into spot r2(22)Nr2g+1=Nr1g,(23)Njg+1=Nj+1g,r1≤j<r2.Random numbersr1,r2 are required to ensure that the two variables correspond to disparate vehicles. Reranking the new created vector is a subsequent maneuver to obtain a feasible solution.The above three strategies can be repeated at stated times, aiming to search for better individuals in the neighbor region for each parent vector.


#### 4.1.3. Crossover

Introduce indexesr1,r2,r3r1≠r2≠r3. Two random parent vectors N1g,N2g,…,NΣ∀imigN∑∀imig and M1g,M2g,…,MΣ∀imigM∑∀imig at generation g are selected to generate new vectors using the following scheme:(24)Njg+1=Njg,Mjg+1=Mjg,1≤j<r1,orr2≤j<r3,(25)Njg+1=Mjg,Mjg+1=Njg,r1≤j<r2,orr3≤j≤∑∀imi.


#### 4.1.4. Selection

Only if the new-created vector yields a better fitness value, then update the parent individual. Otherwise, retain it.


#### 4.1.5. Stopping Criterion

The search process is to break up when one of the two conditions is satisfied: (1) a maximum consuming time of iterations is reached and (2) improvement of the fitness value is not found for a preset number of generations.Fg+Δg−Fg<τ, where τ is a small positive number.


### 4.2. The Second Phase

Fitness Computation. To diminish the vehicle sequence’s stochastics on the identical lane, compute fitness for each coding individual. Dynamic programming is introduced as follows:(1)
Reorder the variablesN11,N12, …, N1m1,….Nn1,Nn2,…,NnmnNnmn in ascending order and determine vehicles’ sequence on each lane. To explain the entire process and list all the order states, Figure 2 presents a simple example of four vehicles coded as [3 5 11 14], corresponding to vehicles [1 2 3 3] with initial lanes [1 2 3 3] and terminal lanes [2 3 1 3]. It can be observed that the entire process has 48 different states, and the fitness for coding individuals [3 5 11 14] is the optimum one in the various states. Noticeably, the order state remains stable in the time range between two sequential lane-change spots.(2)
The second-part model will be solved as dynamic programming. Divide the entire process into a few stages according to lane-change spots. The status of vehicle order and the status transition for each stage can be confirmed as shown in Figure2. Solving a maximization problem will obtain other statuses, including velocity, acceleration, and position. In equation (1), the objective is to minimize the total travel time. Conversely, the benefit function Zs∈Sd of state s at stage d can be defined as follows:(26)Zs∈Sd=max∑i∈C∑k∈dxik.The above expression aims to maximize vehicles’ total travel distance at each stage. It can be regarded as equal to the original objective, which can be guaranteed by setting proper lane-changing boundaries that vehicles cannot drive out at staged.(3)
At staged, for each state s∈Sd, the terminal states set of stage d (the initial state of stage d+1) can be assured, and stage benefit with variables of each interval is to be computed by solving linear programming with objective (26) and constraints (2)–(13). The binary variables δijk can be removed, and the constraints significantly decrease for the determined vehicle order.(4)
Define effective states to reduce the computation complexity. As illustrated in Figure2 and equation (14), if C′, T, and C are large, the states will dramatically increase. Theoretically, the lane-change vehicle is likely to insert into the space between any two adjacent vehicles at the end of the stage. However, it is time-consuming for several states; for example, in the condition that vehicle i located as xi chooses to insert into the gap xj,xj−1, xi≪xj or xi≫xj−1, maximum velocity deceleration must be enforced to satisfy the lane-changing criteria.Definition of effective states: For statesdi∈Sd, Sd is states set in descending order by states’ fitness at stage d. For kk=maxi|Zs1−Zsdi≤εd or kk is a preset value, sdii≤kk is defined as effective states at stage d, and the other states can be removed from Sd.(5)
For each codingN11,N12, …, N1m1, …Figure 2
Demonstration example of order states on lanes.Nn1,Nn2, …, Nnmn, the time zone T is divided into D=∑i=1nmi segments. At stage d, the linear programming is solved by the simplex algorithm to compute each effective initial state’s objective. Individual’s fitness is the maximum value among all the effective states at the terminal stage. The pseudocode of the two-phase algorithm for trajectory optimization is described in Algorithm 1. And a computational flowchart is presented in Figure 3 to display the algorithm more clearly.Figure 3
Computational flowchart.Algorithm 1: Two-phase algorithm.
(1)
Input: initial velocity, acceleration, entering time, occupied lane, terminal lane, maximum acceleration and deceleration for each vehicle; road’s length;(2)
Output: trajectory including acceleration, velocity, position, and an occupied lane for each interval;(3)
Main loop:(4)
Outer iteration: Evolution strategy(5)
Initialization: set k=1, generating the first population of random individuals;(6)
While the stopping criterion is not satisfied, do:(7)
Fitness computation: for each individual, enter into inner iteration to obtain the individual’s fitness;(8)
Inner iteration: Fitness computation(9)
Divide time zone T into D segments, d=1;(10)
Whiled≤D, for each terminal vehicles’ order, do:(11)
Update position, velocity, acceleration, occupied lane, and vehicles’ sequence using results of stage d−1;(12)
Use MATLAB toolbox “lapdog” to solve linear programming;(13)
Repeat solving linear programming for each state and select effective states to enter into stage d+1;(14)
Then update d=d+1; repeat steps 10 to 13;(15)
Whend=D+1, iteration ends, output: individual’s fitness maxZSn; break inner iteration; enter into outer iteration;(16)
Perform mutation, crossover, and selection strategies on thekth generation of individuals to obtain the k+1th generation; then set k=k+1; repeat Steps 6 to 15;(17)
When the stopping criterion is satisfied, the two-phase algorithm ends, output: the optimum individual corresponding to vehicles’ lane-changing time, acceleration, velocity, and position at each time interval.


## 4.1. The First Phase

Lane-change interval optimization. Evolution strategies are search procedures aiming to mimic the natural evolution of the large-scale stochastic and reduce the feasible solutions using elimination mechanisms based on objective function and mutation, crossover, and selection operations. This method is used for the upper level to determine the optimal lane-changing interval.


### 4.1.1. Coding for Individual Representation

It should be noted that the multidimensional coding combined with lane-change time and vehicles’ order is not used. Although the multidimensional coding has the advantage of a simple points search operation, the critical defect is that the points’ feasibility is not guaranteed. In the evolution process, a large number of infeasible solutions cause the loss of solutions’ diversity. Therefore, the ES methods just eliminate one random element, and the vehicle orders’ diversity is remained to solve in the second phase.Implementing the ES for the trajectory optimization model requires the representation of the potential solution, which is a point in the feasible search space. Each solution is a vector consisting of integer variables, denoted asN11,N12,…,N1m1⋯Nn1,Nn2,…,NnmnN1m1Nn1,Nn2Nnmn. In the expression, Nij represents the j-th lane-change slot of vehicle i, and mi is the number of total maneuvers. The lane-change slots coding by integer representations can be defined with a series of requirements as follows:(1)
Coding Approach Coding approach: for each vehicle i, the coding variables Ni1,Ni2,…,NimiNimi satisfy Ni1<Ni2<⋯<Nimi. It is obvious that the posterior lane change is later than the former one. Spontaneously, two coding methods can be utilized to realize variables’ feasibility. Table 2 introduces and compares the two approaches. In this paper, Approach 1 is chosen for variable coding by generating new individuals to eliminate duplicate ones and augment diversity. Approach 2 is prone to cause the latter variable to be out of range due to a large frontier value, and the individual representation is an unfeasible solution. Therefore, Approach 2 is abandoned.(2)
Variables range constraints:Nij<Nij=1,2,…,mi, where Ni is preset to ensure that vehicle i completes changing lanes before driving out.(3)
Initialization: a random value in the boundary range is assigned to each decision variable for every individual of the initial population.(19)Nij0=kiin+rand0,1×Ni−kiin.Table 2
Reranking and construction coding methods.
Approach 1: rerankingApproach 2: constructionCoding processRank coding variablesNi1,Ni2,…,NimiNimi with ascending sort for each i to constitute a new feasible individual.DenoteNij+1=Nij+εij, where εij is a random integer number, and generate a valid individual by coding εij.AdvantageEasily practicable and code value restricted in variable range by simple constraints.Guarantee individuals’ diversity, which is the shortage of approach 1.DisadvantageReduce diversity. For example, codeNi1,Ni2,…,NimiNi1,Ni2Nimi is identical with Nimi,Ni2,…,Ni1Ni1.Difficult to satisfy variables’ value range


### 4.1.2. Mutation

At generationg, for each parent vector N11g,N12g,…,N1m1g,…,Nn1g,Nn2g,…,NmnngN1m1gNn1g,Nn2g,Nnmng in the population, introduce indexes r1,r2 (r1≠r2) to stamp different locations of vectors. The corresponding mutational vector is translated by three common strategies as follows:First strategy: interconverting values at two random points(20)Nr1g+1=Nr2g,Nr2g+1=Nr1g.Second strategy: permute the variables located in the intervalr1,r2 in reverse order(21)Njg+1=Nr1+r2−jg,r1≤j≤r2.Third strategy: insert variable located at the spotr1 into spot r2(22)Nr2g+1=Nr1g,(23)Njg+1=Nj+1g,r1≤j<r2.Random numbersr1,r2 are required to ensure that the two variables correspond to disparate vehicles. Reranking the new created vector is a subsequent maneuver to obtain a feasible solution.The above three strategies can be repeated at stated times, aiming to search for better individuals in the neighbor region for each parent vector.


### 4.1.3. Crossover

Introduce indexesr1,r2,r3r1≠r2≠r3. Two random parent vectors N1g,N2g,…,NΣ∀imigN∑∀imig and M1g,M2g,…,MΣ∀imigM∑∀imig at generation g are selected to generate new vectors using the following scheme:(24)Njg+1=Njg,Mjg+1=Mjg,1≤j<r1,orr2≤j<r3,(25)Njg+1=Mjg,Mjg+1=Njg,r1≤j<r2,orr3≤j≤∑∀imi.


### 4.1.4. Selection

Only if the new-created vector yields a better fitness value, then update the parent individual. Otherwise, retain it.


### 4.1.5. Stopping Criterion

The search process is to break up when one of the two conditions is satisfied: (1) a maximum consuming time of iterations is reached and (2) improvement of the fitness value is not found for a preset number of generations.Fg+Δg−Fg<τ, where τ is a small positive number.


## 4.1.1. Coding for Individual Representation

It should be noted that the multidimensional coding combined with lane-change time and vehicles’ order is not used. Although the multidimensional coding has the advantage of a simple points search operation, the critical defect is that the points’ feasibility is not guaranteed. In the evolution process, a large number of infeasible solutions cause the loss of solutions’ diversity. Therefore, the ES methods just eliminate one random element, and the vehicle orders’ diversity is remained to solve in the second phase.Implementing the ES for the trajectory optimization model requires the representation of the potential solution, which is a point in the feasible search space. Each solution is a vector consisting of integer variables, denoted asN11,N12,…,N1m1⋯Nn1,Nn2,…,NnmnN1m1Nn1,Nn2Nnmn. In the expression, Nij represents the j-th lane-change slot of vehicle i, and mi is the number of total maneuvers. The lane-change slots coding by integer representations can be defined with a series of requirements as follows:(1)
Coding Approach Coding approach: for each vehicle i, the coding variables Ni1,Ni2,…,NimiNimi satisfy Ni1<Ni2<⋯<Nimi. It is obvious that the posterior lane change is later than the former one. Spontaneously, two coding methods can be utilized to realize variables’ feasibility. Table 2 introduces and compares the two approaches. In this paper, Approach 1 is chosen for variable coding by generating new individuals to eliminate duplicate ones and augment diversity. Approach 2 is prone to cause the latter variable to be out of range due to a large frontier value, and the individual representation is an unfeasible solution. Therefore, Approach 2 is abandoned.(2)
Variables range constraints:Nij<Nij=1,2,…,mi, where Ni is preset to ensure that vehicle i completes changing lanes before driving out.(3)
Initialization: a random value in the boundary range is assigned to each decision variable for every individual of the initial population.(19)Nij0=kiin+rand0,1×Ni−kiin.Table 2
Reranking and construction coding methods.
Approach 1: rerankingApproach 2: constructionCoding processRank coding variablesNi1,Ni2,…,NimiNimi with ascending sort for each i to constitute a new feasible individual.DenoteNij+1=Nij+εij, where εij is a random integer number, and generate a valid individual by coding εij.AdvantageEasily practicable and code value restricted in variable range by simple constraints.Guarantee individuals’ diversity, which is the shortage of approach 1.DisadvantageReduce diversity. For example, codeNi1,Ni2,…,NimiNi1,Ni2Nimi is identical with Nimi,Ni2,…,Ni1Ni1.Difficult to satisfy variables’ value range


## 4.1.2. Mutation

At generationg, for each parent vector N11g,N12g,…,N1m1g,…,Nn1g,Nn2g,…,NmnngN1m1gNn1g,Nn2g,Nnmng in the population, introduce indexes r1,r2 (r1≠r2) to stamp different locations of vectors. The corresponding mutational vector is translated by three common strategies as follows:First strategy: interconverting values at two random points(20)Nr1g+1=Nr2g,Nr2g+1=Nr1g.Second strategy: permute the variables located in the intervalr1,r2 in reverse order(21)Njg+1=Nr1+r2−jg,r1≤j≤r2.Third strategy: insert variable located at the spotr1 into spot r2(22)Nr2g+1=Nr1g,(23)Njg+1=Nj+1g,r1≤j<r2.Random numbersr1,r2 are required to ensure that the two variables correspond to disparate vehicles. Reranking the new created vector is a subsequent maneuver to obtain a feasible solution.The above three strategies can be repeated at stated times, aiming to search for better individuals in the neighbor region for each parent vector.


## 4.1.3. Crossover

Introduce indexesr1,r2,r3r1≠r2≠r3. Two random parent vectors N1g,N2g,…,NΣ∀imigN∑∀imig and M1g,M2g,…,MΣ∀imigM∑∀imig at generation g are selected to generate new vectors using the following scheme:(24)Njg+1=Njg,Mjg+1=Mjg,1≤j<r1,orr2≤j<r3,(25)Njg+1=Mjg,Mjg+1=Njg,r1≤j<r2,orr3≤j≤∑∀imi.


## 4.1.4. Selection

Only if the new-created vector yields a better fitness value, then update the parent individual. Otherwise, retain it.


## 4.1.5. Stopping Criterion

The search process is to break up when one of the two conditions is satisfied: (1) a maximum consuming time of iterations is reached and (2) improvement of the fitness value is not found for a preset number of generations.Fg+Δg−Fg<τ, where τ is a small positive number.


## 4.2. The Second Phase

Fitness Computation. To diminish the vehicle sequence’s stochastics on the identical lane, compute fitness for each coding individual. Dynamic programming is introduced as follows:(1)
Reorder the variablesN11,N12, …, N1m1,….Nn1,Nn2,…,NnmnNnmn in ascending order and determine vehicles’ sequence on each lane. To explain the entire process and list all the order states, Figure 2 presents a simple example of four vehicles coded as [3 5 11 14], corresponding to vehicles [1 2 3 3] with initial lanes [1 2 3 3] and terminal lanes [2 3 1 3]. It can be observed that the entire process has 48 different states, and the fitness for coding individuals [3 5 11 14] is the optimum one in the various states. Noticeably, the order state remains stable in the time range between two sequential lane-change spots.(2)
The second-part model will be solved as dynamic programming. Divide the entire process into a few stages according to lane-change spots. The status of vehicle order and the status transition for each stage can be confirmed as shown in Figure2. Solving a maximization problem will obtain other statuses, including velocity, acceleration, and position. In equation (1), the objective is to minimize the total travel time. Conversely, the benefit function Zs∈Sd of state s at stage d can be defined as follows:(26)Zs∈Sd=max∑i∈C∑k∈dxik.The above expression aims to maximize vehicles’ total travel distance at each stage. It can be regarded as equal to the original objective, which can be guaranteed by setting proper lane-changing boundaries that vehicles cannot drive out at staged.(3)
At staged, for each state s∈Sd, the terminal states set of stage d (the initial state of stage d+1) can be assured, and stage benefit with variables of each interval is to be computed by solving linear programming with objective (26) and constraints (2)–(13). The binary variables δijk can be removed, and the constraints significantly decrease for the determined vehicle order.(4)
Define effective states to reduce the computation complexity. As illustrated in Figure2 and equation (14), if C′, T, and C are large, the states will dramatically increase. Theoretically, the lane-change vehicle is likely to insert into the space between any two adjacent vehicles at the end of the stage. However, it is time-consuming for several states; for example, in the condition that vehicle i located as xi chooses to insert into the gap xj,xj−1, xi≪xj or xi≫xj−1, maximum velocity deceleration must be enforced to satisfy the lane-changing criteria.Definition of effective states: For statesdi∈Sd, Sd is states set in descending order by states’ fitness at stage d. For kk=maxi|Zs1−Zsdi≤εd or kk is a preset value, sdii≤kk is defined as effective states at stage d, and the other states can be removed from Sd.(5)
For each codingN11,N12, …, N1m1, …Figure 2
Demonstration example of order states on lanes.Nn1,Nn2, …, Nnmn, the time zone T is divided into D=∑i=1nmi segments. At stage d, the linear programming is solved by the simplex algorithm to compute each effective initial state’s objective. Individual’s fitness is the maximum value among all the effective states at the terminal stage. The pseudocode of the two-phase algorithm for trajectory optimization is described in Algorithm 1. And a computational flowchart is presented in Figure 3 to display the algorithm more clearly.Figure 3
Computational flowchart.Algorithm 1: Two-phase algorithm.
(1)
Input: initial velocity, acceleration, entering time, occupied lane, terminal lane, maximum acceleration and deceleration for each vehicle; road’s length;(2)
Output: trajectory including acceleration, velocity, position, and an occupied lane for each interval;(3)
Main loop:(4)
Outer iteration: Evolution strategy(5)
Initialization: set k=1, generating the first population of random individuals;(6)
While the stopping criterion is not satisfied, do:(7)
Fitness computation: for each individual, enter into inner iteration to obtain the individual’s fitness;(8)
Inner iteration: Fitness computation(9)
Divide time zone T into D segments, d=1;(10)
Whiled≤D, for each terminal vehicles’ order, do:(11)
Update position, velocity, acceleration, occupied lane, and vehicles’ sequence using results of stage d−1;(12)
Use MATLAB toolbox “lapdog” to solve linear programming;(13)
Repeat solving linear programming for each state and select effective states to enter into stage d+1;(14)
Then update d=d+1; repeat steps 10 to 13;(15)
Whend=D+1, iteration ends, output: individual’s fitness maxZSn; break inner iteration; enter into outer iteration;(16)
Perform mutation, crossover, and selection strategies on thekth generation of individuals to obtain the k+1th generation; then set k=k+1; repeat Steps 6 to 15;(17)
When the stopping criterion is satisfied, the two-phase algorithm ends, output: the optimum individual corresponding to vehicles’ lane-changing time, acceleration, velocity, and position at each time interval.


## 5. Numerical Example and Results

In this section, experiments are conducted to validate the proposed model and algorithm on a road segment consisting of three lanes, similar to Figure1. The main targets are as follows: (1) optimize vehicles’ trajectory on a numerical example and (2) compare with the no optimized case. All experiments were implemented using MATLAB and conducted on a PC workstation running Windows 10 with an Intel Xeon e5 3.5 GHz processor and 64 GB of main memory.


### 5.1. Optimized Vehicles’ Trajectory

A road lengthL=1800m, 10 vehicles with an initial entering time kiin = [0 0 0 2 4 4 4 6 6 6] ss will be optimized. To ensure that all vehicles can drive out, the time horizon is T=80s, and coding boundary in the ES algorithm is preset 60 s (which is estimated by maximum velocity), discretized into 40 and 30 intervals of equal duration, where each interval is 2 seconds due to precision deficiency and warranty of lane-change completeness. A reasonable spatial and temporary division is necessary for continuous traffic flow to realize discretization.The values of other parameters are listed in Table3. In each generation, 10 individuals are produced, and the entire algorithm is executed in the 60 s. To select effective states in the inner dynamic trajectories programming, kk=2. The results are shown in Figures 4–6 .Table 3
Parameters values.
VariablesDescriptionValuele1,le2,…,le10Initial lane vector[1 2 3 1 2 3 1 1 2 3]ls1,ls2,…,ls10Terminal lane vector[1 2 3 1 3 1 2 2 2 3]aimaxThe maximum acceleration3 m/s2vimaxThe maximum velocity30 m/sdimaxThe maximum deceleration3 m/s2th/th′th'Reaction time/short reaction time0.3 s/0.2 sFigure 4
Optimal vehicles trajectories.Figure 5
Vehicles trajectories on lane 1: (a) 2–10 s, (b) 10–18 s, (c) 18–22 s, (d) 22–54 s, and (e) 54–80 s.
(a)(b)(c)(d)(e)Figure 6
Optical objective value for the repeated running of the algorithm.Vehicles trajectories are displayed in Figure4. Lane-change times are 22 s (vehicle 5), 10 s (vehicle 6), 18 s (vehicle 6), and 54 s (vehicle 7). It is observable that all vehicles drive on the target lane before the exit positioned at 1,800 m. The safe distance between the adjacent vehicles along the whole time zone is guaranteed (the vehicle’s gap is larger than the rear vehicle’s velocity multiple reaction time).Figure5 presents vehicles trajectories on lane 1 as a demonstration sample and shows the occupied lanes variation with time interval. All the vehicles are able to exit before interval 33, which indicates that the coding range [0 30] is reasonable. The trajectory lines are smooth, and just several inflection points exist at lane-changing intervals. This phenomenon validates the results availability ensuring the vehicles are driven steadier. To analyze the influence of ES randomness, the algorithm was rerun 28 times repetitiously, setting the programming running time as 1 min. Figure 6 shows that the optimum fitness values’ variation range remains within 600 m for 10 vehicles, and the randomness is acceptable in practical application.


### 5.2. Comparison with Unoptimizable Situation

In this section, the proposed trajectory programming is compared with an unoptimizable situation in which drivers follow the preceding car with intelligent driver model (IDM) and change lanes by self-decision as follows:The IDM details can be expressed as follows:(27)aik=aimax1−vikvimaxδ−sk′Dik2,(28)sk′=s0+max0,thvik+vikΔvik2aimaxb,(29)xik+1=xik+vikΔt+0.5aikΔt2,whereDik=xik−xi+1k is the headway gap to the preceding vehicle (m), s0 is the minimum safe gap for congested flow (m) computed by reaction time th, Δvik is the velocity difference (m/s), and b is the comfortable deceleration (m/s2). In this part, b = 3 m/s2; other parameters are identical to the values in Section 5.1. The self-decision lane-change strategy can be described as follows:(1)
If the following constraints are simultaneously satisfied, change to the adjacent lane directly:(30)xik−xjk≥xjk×th',(31)xj−1k−xik≥xik×th′,wherexj−1k and xjk are the positions of the preceding and the subsequent vehicles on the target lane, respectively.(2)
If the gap conditions in equations (30) and (31) are not satisfied, the following two cases can exist:Case 1: Ifxd−xik>L′L′<L, a long distance is acceptable to await safe gap; vehicles choose IDM to follow carsCase 2: Ifxd−xik<L′, a speed adjustment mode will be activated to enlarge the vehicles’ gapIf equation (30) is not satisfied,(32)ajk+1=max−amax,(vmin−vjkΔt.If equation (31) is not satisfied,(33)aik+1=max−amax,vmin−vikΔt.The common parameters and the initial settings are assigned with identical values as in Section5.1, executing the entire process in the same running environment. Vehicles’ trajectories and other meaningful results are shown in Figures 7–9. Consistent with Section 5.1, the vehicle trajectories are presented in Figure 7, and the trajectories on lane 1 are illustrated in Figure 8. It can be seen that lane-change time spots are 58 s (vehicle 5), 56 s (vehicle 6), 62 s (vehicle 6), and 8 s (vehicle 7), different from the results in Section 5.1. Similar conclusions can be found that a safe gap is provided throughout the process, and all vehicles exist out of the target lanes.Figure 7
Optimal vehicle trajectories.Figure 8
Comparison of vehicle trajectories on lane 1: (a) 2–8 s, (b) 8–56 s, (c) 56–58 s, (d) 58–62 s, and (e) 62–100 s.
(a)(b)(c)(d)(e)Figure 9
The vehicles’ speeds.Compared with Figure4, more inflection points and longer periods of speed adjustment appear in the trajectory lines in Figure 8. The speeds of human-driven vehicles are depicted in Figure 9. As illustrated in Figure 9, speeds fluctuate significantly throughout the time zone, particularly around lane-change intervals. In contrast, the speeds are significantly smoother in the AV trajectories depicted in Figure 5. This indicates that the proposed algorithm may improve driving stability, thereby lowering fuel consumption and gas emissions.The reason is that when the HDVs intend to change lanes, they slow their speed to satisfy the safe gap in the shortest time, simultaneously inducing a significant speed oscillation range. But, for AVs, speed adjustment is dispersed in the whole time zone through global optimization.Figure10 shows that each vehicle spends more travel time on the whole journey in the contrastive example. The total time cost is saved by 20%, and the average speed is increased by 18%. The road length is longer, and the trajectory algorithm will obtain more significant optimum results for the entire process.Figure 10
Total travel time of the vehicles.


## 5.1. Optimized Vehicles’ Trajectory

A road lengthL=1800m, 10 vehicles with an initial entering time kiin = [0 0 0 2 4 4 4 6 6 6] ss will be optimized. To ensure that all vehicles can drive out, the time horizon is T=80s, and coding boundary in the ES algorithm is preset 60 s (which is estimated by maximum velocity), discretized into 40 and 30 intervals of equal duration, where each interval is 2 seconds due to precision deficiency and warranty of lane-change completeness. A reasonable spatial and temporary division is necessary for continuous traffic flow to realize discretization.The values of other parameters are listed in Table3. In each generation, 10 individuals are produced, and the entire algorithm is executed in the 60 s. To select effective states in the inner dynamic trajectories programming, kk=2. The results are shown in Figures 4–6 .Table 3
Parameters values.
VariablesDescriptionValuele1,le2,…,le10Initial lane vector[1 2 3 1 2 3 1 1 2 3]ls1,ls2,…,ls10Terminal lane vector[1 2 3 1 3 1 2 2 2 3]aimaxThe maximum acceleration3 m/s2vimaxThe maximum velocity30 m/sdimaxThe maximum deceleration3 m/s2th/th′th'Reaction time/short reaction time0.3 s/0.2 sFigure 4
Optimal vehicles trajectories.Figure 5
Vehicles trajectories on lane 1: (a) 2–10 s, (b) 10–18 s, (c) 18–22 s, (d) 22–54 s, and (e) 54–80 s.
(a)(b)(c)(d)(e)Figure 6
Optical objective value for the repeated running of the algorithm.Vehicles trajectories are displayed in Figure4. Lane-change times are 22 s (vehicle 5), 10 s (vehicle 6), 18 s (vehicle 6), and 54 s (vehicle 7). It is observable that all vehicles drive on the target lane before the exit positioned at 1,800 m. The safe distance between the adjacent vehicles along the whole time zone is guaranteed (the vehicle’s gap is larger than the rear vehicle’s velocity multiple reaction time).Figure5 presents vehicles trajectories on lane 1 as a demonstration sample and shows the occupied lanes variation with time interval. All the vehicles are able to exit before interval 33, which indicates that the coding range [0 30] is reasonable. The trajectory lines are smooth, and just several inflection points exist at lane-changing intervals. This phenomenon validates the results availability ensuring the vehicles are driven steadier. To analyze the influence of ES randomness, the algorithm was rerun 28 times repetitiously, setting the programming running time as 1 min. Figure 6 shows that the optimum fitness values’ variation range remains within 600 m for 10 vehicles, and the randomness is acceptable in practical application.


## 5.2. Comparison with Unoptimizable Situation

In this section, the proposed trajectory programming is compared with an unoptimizable situation in which drivers follow the preceding car with intelligent driver model (IDM) and change lanes by self-decision as follows:The IDM details can be expressed as follows:(27)aik=aimax1−vikvimaxδ−sk′Dik2,(28)sk′=s0+max0,thvik+vikΔvik2aimaxb,(29)xik+1=xik+vikΔt+0.5aikΔt2,whereDik=xik−xi+1k is the headway gap to the preceding vehicle (m), s0 is the minimum safe gap for congested flow (m) computed by reaction time th, Δvik is the velocity difference (m/s), and b is the comfortable deceleration (m/s2). In this part, b = 3 m/s2; other parameters are identical to the values in Section 5.1. The self-decision lane-change strategy can be described as follows:(1)
If the following constraints are simultaneously satisfied, change to the adjacent lane directly:(30)xik−xjk≥xjk×th',(31)xj−1k−xik≥xik×th′,wherexj−1k and xjk are the positions of the preceding and the subsequent vehicles on the target lane, respectively.(2)
If the gap conditions in equations (30) and (31) are not satisfied, the following two cases can exist:Case 1: Ifxd−xik>L′L′<L, a long distance is acceptable to await safe gap; vehicles choose IDM to follow carsCase 2: Ifxd−xik<L′, a speed adjustment mode will be activated to enlarge the vehicles’ gapIf equation (30) is not satisfied,(32)ajk+1=max−amax,(vmin−vjkΔt.If equation (31) is not satisfied,(33)aik+1=max−amax,vmin−vikΔt.The common parameters and the initial settings are assigned with identical values as in Section5.1, executing the entire process in the same running environment. Vehicles’ trajectories and other meaningful results are shown in Figures 7–9. Consistent with Section 5.1, the vehicle trajectories are presented in Figure 7, and the trajectories on lane 1 are illustrated in Figure 8. It can be seen that lane-change time spots are 58 s (vehicle 5), 56 s (vehicle 6), 62 s (vehicle 6), and 8 s (vehicle 7), different from the results in Section 5.1. Similar conclusions can be found that a safe gap is provided throughout the process, and all vehicles exist out of the target lanes.Figure 7
Optimal vehicle trajectories.Figure 8
Comparison of vehicle trajectories on lane 1: (a) 2–8 s, (b) 8–56 s, (c) 56–58 s, (d) 58–62 s, and (e) 62–100 s.
(a)(b)(c)(d)(e)Figure 9
The vehicles’ speeds.Compared with Figure4, more inflection points and longer periods of speed adjustment appear in the trajectory lines in Figure 8. The speeds of human-driven vehicles are depicted in Figure 9. As illustrated in Figure 9, speeds fluctuate significantly throughout the time zone, particularly around lane-change intervals. In contrast, the speeds are significantly smoother in the AV trajectories depicted in Figure 5. This indicates that the proposed algorithm may improve driving stability, thereby lowering fuel consumption and gas emissions.The reason is that when the HDVs intend to change lanes, they slow their speed to satisfy the safe gap in the shortest time, simultaneously inducing a significant speed oscillation range. But, for AVs, speed adjustment is dispersed in the whole time zone through global optimization.Figure10 shows that each vehicle spends more travel time on the whole journey in the contrastive example. The total time cost is saved by 20%, and the average speed is increased by 18%. The road length is longer, and the trajectory algorithm will obtain more significant optimum results for the entire process.Figure 10
Total travel time of the vehicles.


## 6. Discussion and Conclusions

This study studies the trajectory optimization problem for autonomous vehicles on particular roads with communication facilities. The objective of the proposed model is to search for optimal trajectories for autonomous vehicles. Meanwhile, the trajectories are restrained by some incorporating constraints, including safe gaps for collision avoidance, vehicle kinematic requirements, and occupied lane variations. Due to the diversity of lane-change spots and the order of the vehicles in each lane, a two-phase algorithm is proposed to diminish the uncertainties and improve the computation efficiency. A numerical example and a comparative experiment indicate the following meaningful findings:(1)
The proposed two-phase algorithm is able to solve optimum trajectories satisfying all the constraints in an acceptable running time. The trajectories are relatively smooth while simultaneously conforming to car-following, lane-changing behaviors, and maintaining steady speeds.(2)
Solving the trajectory problem has high computation complexity, and the required running time is relative to the total vehicles, time scope, and section’s length. The evolution strategy can reduce the large scale of lane-change spots and search for optimum results. Cutting invalid vehicles’ orders at each stage reserves sufficient optimum results and speeds up the solving process in the dynamic programming for fitness computation.(3)
The proposed two-phase algorithm demonstrates favorable computational performance, while some optimal solutions are lost. Due to the large scale and high stochastic in reality, it is reasonable and practical to locate a satisfactory solution in a limited time range.(4)
The comparative experimental results show that vehicles’ lane-change spots positions are close to the road exit unless the target lane has low-density flow and provides a suitable vehicle gap. It can be explained that the drivers are opposed to speed adjustment and tend to wait for an opportunity for an adequate gap until driving near the exit. Also, the solution efficiency has been significantly improved by decreasing the total travel time in the proposed algorithm. It is observable that the AVS’ trajectories approach system optimum by global optimization. Otherwise, the comparative experimental results are users’ manual decisions through communication and just realize user optimum at a discrete-time interval.As a result of the preceding discussions and conclusions, it can be concluded that the proposed model and algorithm can be used to manage traffic in an AV-only zone. A cost-effective and smooth trajectory scheme will be computed and transmitted to vehicles via a central system in a timely manner. It is anticipated that it will be used in congested areas. There are, however, some limitations. Notably, if the vehicles are not evenly distributed relative to one another in each lane at the entrance, the algorithm will be combined with a pretrip lane selection maneuver to achieve satisfactory results. Moreover, the ES algorithm yields an approximation result. Parameters and stopping criteria should be dynamically adjusted.



---

*Source: 3582355-2022-06-29.xml*