{'fraction_non_alphanumeric': 0.043232277696382285, 'fraction_numerical': 0.012509861377211766, 'mean_word_length': 4.201172332942556, 'pattern_counts': {'":': 0, '<': 33, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 13, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Optimizing Coordinated Vehicle Platooning: An Analytical Approach Based on Stochastic Dynamic Programming

Platooning connected and autonomous vehicles (CAVs) can improve traffic and fuel efficiency. However, scalable platooning operations require junction-level coordination, which has not been well studied. In this paper, we study the coordination of vehicle platooning at highway junctions. We consider a setting where CAVs randomly arrive at a highway junction according to a general renewal process. When a CAV approaches the junction, a system operator determines whether the CAV will merge into the platoon ahead according to the positions and speeds of the CAV and the platoon. We formulate a Markov decision process to minimize the discounted cumulative travel cost, i.e. fuel consumption plus travel delay, over an infinite time horizon. We show that the optimal policy is threshold-based: the CAV will merge with the platoon if and only if the difference between the CAV's and the platoon's predicted times of arrival at the junction is less than a constant threshold. We also propose two ready-to-implement algorithms to derive the optimal policy. Comparison with the classical value iteration algorithm implies that our approach explicitly incorporating the characteristics of the optimal policy is significantly more efficient in terms of computation. Importantly, we show that the optimal policy under Poisson arrivals can be obtained by solving a system of integral equations. We also validate our results in simulation with Real-time Strategy (RTS) using real traffic data. The simulation results indicate that the proposed method yields better performance compared with the conventional method.


Introduction
In the recent decade, the technology of connected and autonomous vehicles (CAVs) has been developing fast due to continuous progress in deploying communication and computation capabilities on vehicles and on infrastructure [1,2]. Platooning is a novel highway operation enabled by the CAV technology, where vehicles travel in groups with very short inter-vehicle spacing [3]. The major advantages of platooning include throughput improvement, fuel savings, and reduced pollutant emissions [4,5]. Such advantages lead to considerable incentives for the transportation industry to adopt this operation. The architecture of a comprehensive platoon management system consists of three layers: the network layer, the link (junction) layer, and the vehicle layer [6]. The network layer deals with trip scheduling, goods assignment and route planning. The link layer coordinates the formulation, splitting, and reordering of platoons. The vehicle layer regulates the longitudinal and lateral motion of the vehicle in a platoon. However, although much progress has been made for microscopic regulation of vehicle strings [7][8][9][10], very limited methods and results are available for link-and network-layer coordination for platooning.
In this paper, we consider a novel Markov decision process (MDP) formulation to study the coordinated platooning problem at independent highway junctions and propose an easy-toimplement but provably optimal strategy to coordinate CAVs. Figure 1 illustrates the scenario that we consider. The local coordinator is located at the junction, and there are two flows of CAVs entering the junction. The coordinator has access to kinematic information (speeds and locations) of CAVs within the coordinating zone of radius D 1 on each highway branch. The decision of whether a CAV merges into a platoon is made when the CAV arrives at the detector and enters the coordinating zone. If the coordinator decides to merge a CAV into a platoon, the CAV will be instructed to traverse the coordinating zone with a specified speed such that it can catch up with the nearest platoon ahead at the junction. There is a cruising zone beyond the junction where CAV platoons that have formed in the coordinating zone will be maintained. To design efficient coordination algorithms, we focus on the trade-off between the travel cost (time and fuel) over the coordinating zone due to acceleration/deceleration for platooning and the reduced fuel consumption over the cruising zone due to platooning. Most previous work on coordinated platooning is based on optimization (typically mixed integer programming) formulations with heuristic solution algorithms; see [4] for a rather complete overview. In particular, Larson et al. [11] considered a distributed formulation where platooning decisions are made at each junction; this distributed framework is practical and thus adopted in our modeling approach. Larsson et al. [12] proposed an integer programming for platooning-oriented routing and compared the performance of multiple heuristics. Boysen et al. [13] studied the coordinated platooning problem on a single route, which is similar to the setting considered in this paper, with various objective functions. Luo et al. [14] used an integer programming to design coordination algorithms with multiple speeds. Johansson et al. [15] considered a game-theoretic formulation to study the share of economical benefits due to platooning. Sun and Yin [16] quantifies the share of benefits due to platooning and studied the allocation of benefits. In addition, there exists a line of work on higher-level trip planning for platooning [17][18][19], which focuses on strategical routing and schedule. There also exists a line of work on lower-level coordination between CAVs for platooning [20][21][22][23], which focuses more on the kinematics (and sometimes even dynamics) of individual vehicles rather than the overall traffic. However, the above approaches require exact knowledge of each CAV's trip plan (or constraints), which is not always available. Furthermore, although heuristic algorithms are usually efficient and practical, it is also beneficial to derive structural and insightful results on optimal platooning strategies. This paper is, to the best of our knowledge, the first effort that explicitly characterize the structure of optimal coordinated platooning strategies in an MDP environment.
In our formulation, CAVs enter the coordinating zone upstream to a highway junction as a general renewal process, i.e. with independent and identically distributed inter-arrival times. Note that if the inter-arrival times are exponentially distributed, then we have a Poisson process. The control action is the spatial-average speed in the coordinating zone recommended to each CAV, which determines whether a CAV will merge with the CAV(s) ahead to form a platoon. The objective is to minimize the travel cost, which is the sum of fuel consumption and travel delay. This objective function captures the trade-off between the fuel benefits due to platooning and the cost for forming platoons. The merging can be achieved by deceleration of leading vehicle or acceleration of following vehicle. Our formulation does not explicitly consider routing [11] and travel time window constraints [13,24]; the uncertainty/variation of each CAV's trip before entering the coordinating zone is captured by the stochastic arrival process. A similar model was considered in our previous work [25], which studied a rather intuitive off-line, open-loop coordination strategy in a static setting. In this paper, we consider a MDP with feedback coordination strategies and use the open-loop strategy in [25] as a baseline for evaluation.
The main result that we derive for the MDP is an explicit characterization of the structure of an optimal policy (Theorem 1). Such characterization is essential for computing the actual optimal policy, since standard dynamic programming (DP) algorithms do not directly apply to our formulation with a continuous and unbounded state space. By analyzing the Bellman optimality equation for the MDP, we show that an optimal policy is threshold-based : the following vehicle is supposed to merge with the leading vehicle if the predicted time interval between the arrivals of these two vehicles at the junction is less than a given threshold. This threshold essentially captures the comparison between the benefit (fuel savings over the cruising zone) and the cost (travel delay and/or additional fuel consumption over the coordinating zone) of platooning. If the predicted time interval is larger than the threshold, the following vehicle is supposed to travel with an optimal speed that is typically lower than the nominal speed, in anticipation of the arrival of the next vehicle as an opportunity for platooning. The proof of this result uses an analytical approach based on stochastic dynamic programming. We first consider an N -stage, finite time horizon problem and show that the optimal policy for that problem is threshold-based. Then, we extend the argument to the infinite time horizon. Our result is rather general in that (i) the arrival process is a general renewal process and (ii) the cost function is general (with assumptions on concavity).
We also develop ready-to-implement algorithms for computing the optimal policy in practical settings. For general arrival processes, we compare two solution algorithms, viz. bounded value iteration (BVI) and recursive approximation (RA). BVI is derived from value iteration (VI), a classical approach in dynamic programming [26]. Since the state space of our MDP is continuous and unbounded, the BVI first trims and discretizes the state space and then proceeds analogously to classical VI. Since BVI exhaustively iterates the value as well as the optimal action for each discretized state, it is computationally costly. The RA algorithm that we consider is intended to address this challenge by incorporating the threshold-based structure that we identified. Instead of computing the optimal actions for all states, the RA algorithm assumes the threshold-based structure a priori and only computes the parameters thereof; this significantly accelerates the computation. Furthermore, for Poisson arrival processes, we show that the parameters of the optimal policy can be obtained by solving a system of integral equations (Theorem 2), which is much faster than iteration-based algorithms such as BVI and RA. The computational efficiency of these algorithms are compared in a numerical example with various arrival processes. In particular, for Poisson processes, the convergence times for the BVI, RA, and integral equationbased methods are 9.6 hours, 54 minutes, and less than 1 second.
We also validate our results in a realistic simulation environment. The simulation model is calibrated with real traffic data for a junction of US Interstate 210 (I210) obtained from the Freeway Performance Measurement System (PeMS [27]). We consider a hypothetical scenario where various percentages of all traffic are CAVs that can be platooned. Simulation results show that, under our Real-time Strategy (RTS) of coordination, the average monetary savings (time plus fuel) at one junction is $3736.8 per day. In addition, we analyze the sensitivity of the optimal savings with respect to key model parameters, including the sizes of the cruising zone, and the discount factor for the MDP. Finally, we present the interpretation of the RTS.
The rest of this paper is organized as follows. In Section 2, we introduce the stochastic model and formulate the Markov decision process for coordinated platooning. In Section 3, we characterize the structure of the optimal policy to the MDP. In Section 4, we formulate and solve an optimization problem for coordinated platooning. In Section 5, we present the numerical results using real traffic data. In Section 6, we summarize the conclusions and propose several directions for future work.

Modeling and Formulation
In this section, we introduce our model for the process of coordinated platooning and formulate a Markov decision process (MDP) to minimize the system-wide travel cost based on this model. Consider the scenario in Figure 1, where flows on two branches merge at the junction. Two detectors located equivalent distance D 1 from the junction on each branch would transmit the arrival time of each vehicle to the coordinator, which would determine whether the vehicle will merge with the previous platoon. When the coordinator sends the merging signal, the vehicle would accommodate its speed to meet the previous platoon at the junction, after which the vehicle will cruise together with the previous platoon, and experience fuel savings due to decreased air resistance. The vehicle will cruise with an optimal speed if the coordinator sends the non-merging signal. We assume that all vehicles share the identical path during the cruising zone D 2 to give insights into the one-junction coordination. The rest of this section is devoted to the details of our modeling and formulation.

Modeling
In this subsection, we define the arrival process of CAVs and the control actions that the platooning coordinator can take. We also introduce the travel cost model for the platooning process, based on which we formulate the decision problem in the next subsection.

Platooning coordination
The coordination strategy is determined based on the arrival times on both branches. The following vehicle would merge with the previous platoon either on the same branch or on the other one. To simplify the modeling, two flows are assumed to appear on the same route, and one detector is used to record the arrival times of each vehicle. In Figure 2, the (k − 1)th vehicle, k = 1, 2, . . . , enters the coordinating zone at time T k−1 . The following vehicle k is recorded by either detector, and the arrival time is T k . The inter-arrival time X k = T k − T k−1 is assumed to follow an independent and identically distributed (i.i.d.) process, and the probability density function (PDF) is f (x). The platooning strategy is realized by adapting the vehicle speed during the coordinating zone D 1 . In real implementation, the intra-platoon headway h 0 is much smaller than coordinating distance D 1 and cruising distance D 2 , then h 0 ≈ 0 is assumed to simplify the analysis.

State: predicted headway
Without loss of generality, we assume that vehicles cruise with an average speed v, hence the average transverse time on D 1 is t 0 = D 1 v . The kth vehicle would arrive at the junction at (T k + t 0 ) without changing the speed. In practice, vehicle k can accelerate or decelerate to transverse the coordinating zone. We neglect the speed variation and assume that the vehicle would keep constant speed during the coordinating zone. In Figure 2, the actual arrival time would be earlier than (T k + t 0 ) when vehicle k choose to accelerate, in which time reduction U k > 0. Also U k < 0 occurs in the deceleration case. The maximum time reduction for vehicle k arises when vehicle k meets vehicle (k − 1) at the junction. Then they would form a platoon, and vehicle k would experience the reduced fuel consumption. We use S k = max{U k } to denote the maximum time reduction for vehicle k. S k can be negative when the actual arrival time of vehicle (k−1) is larger than (T k +t 0 ), in which vehicle k and vehicle (k−1) would both drive with lower speeds. Note that the speed adaptation only occurs during the coordinating zone, and the spatial-average speed is assigned once passing the detector. After the junction, all vehicles would return to the average speed v. The coordinating zone is only used to coordinate platooning between consecutive vehicles by changing time reduction U k taking value from −∞, S k , i.e., the speed during the coordinating zone, v k = Obviously, S k should be less than t 0 if the two vehicles would merge at the junction.
A related work [25] designed the threshold-based policy based on the inter-arrival time X k , which would result in frequent acceleration and thus high speed when forming long platoons. In addition, deceleration was not considered for the vehicle maneuver. In this paper, we incorporate the deceleration option, and use the time reduction S k as the decision variable, which incorporates the information of the previous vehicle, and hence S k is sensitive to platoon size. Specifically, the previous vehicle may leave the coordinating zone while the following vehicle arrives at the detection. In Figure 2, the actual arrival time at the junction for vehicle k is (T k + t 0 − S k ) if it would merge with vehicle (k − 1). When vehicle (k + 1) enters the coordinating zone at T k+1 > T k + t 0 − S k , vehicle (k + 1) cannot meet with vehicle k at the junction. To generalize the decision variable for all vehicles, the concept of time reduction S k is extended to the predicted headway S k , which denotes the hypothetical time used to catch up with the first vehicle in the previous platoon. Consider the scenario where all vehicles drive towards the junction before the detector in Figure 3. The predicted headway of vehicle k still meets the equation S k = S k . However, vehicle (k + 1) requires (S k + T k+1 − T k ) to catch up with vehicle k (also vehicle (k − 1) due to h 0 ≈ 0) even though vehicle (k + 1) would not merge with the previous platoon. Hence the predicted headway of vehicle (k + 1) is S k+1 = S k + T k+1 − T k .

Problem definition
We consider travel cost that consists of fuel consumption and travel time. When the vehicle is assigned to catch up with previous vehicle, the increased (decreased) speed would incur more (less) fuel consumption. The increased (decreased) speed during the coordinating zone would reduce (increase) the travel time. In addition, the vehicle would have less fuel consumption in D 2 . We then formulate the optimization problem to minimize the travel cost. In section 2.1.2, the predicted headway S k is proposed to be the decision variable for vehicle k. The action we used is the time reduction U k , which affects the spatial-average speed, lies in (−∞, S k ] since the following vehicle could not surpass the leading vehicle. When S k ≥ t 0 , the accessible time reduction U k ∈ (−∞, t 0 ). The benefits of platooning consist of reduced travel time and improved fuel economy. Typically, we use the relative benefits instead of absolute values [11]. The total cost for kth vehicle can be defined as: where w 1 represents the value of time, and w 2 denotes the fuel price. ∆F 1 is the increased fuel during D 1 , and ∆F 2 is the fuel reduction resulting from reduced air resistance in D 2 , which only arises when kth vehicle merges with (k + 1)th vehicle.
Following the definition in [11], ∆F 1 results from the air drag depending on the vehicle speed v and the distance of D 1 , ∆F 1 = αD 1 where α represents the coefficient of increased fuel based on speed and distance. Typically, ∆F 2 occurs when the following vehicle merges with the previous platoon, i.e., U k = S k , and is denoted as: ∆F 2 = ηφD 2 , where η represents the fuel saving fraction compared with driving alone, and φ denotes the fuel efficiency [11]. When the following vehicle would not merge with the previous platoon, i.e., U k < S k , ∆F 2 = 0. The total platooning cost for vehicle k is: (1) To minimize the total travel cost for all vehicles, we need to find the optimal strategy of platooning based on the predicted headway. The optimization problem can be formulated as: drive towards the junction. The inter-arrival time X k is independent and identically distributed, and the probability density function is f (x). The predicted headway for vehicle k is S k , k = 1, 2, . . . , N . We need to find the optimal policy π * = {µ * 1 (s 1 ), µ * 2 (s 2 ), . . .}, to minimize the expected total travel cost for all vehicles.

MDP for coordinated platooning
Specifically, the number of platooning combinations under N vehicles is 2 N , i.e., each vehicle can choose to merge with the previous vehicle or not ( Figure 3). In addition, the time reduction U k is continuous, which makes it difficult to find the π * in Problem 1. Since the inter-arrival time X k follows an independent and identically distributed (i.i.d.) process with the probability density function (PDF) f (x), we then use the stochastic dynamic programming (SDP) [26], which captures the recursive interaction among consecutive vehicles, to find the optimal solution. We formulate the problem as a discrete-time problem with N control steps. The state at each step is the predicted headway S k . The action A k is the time reduction U k . The reward where a k ∈ (−∞, t 0 ) when s k ≥ t 0 , and a k ∈ (−∞, s k ] when s k < t 0 . The reward function is discontinuous at a k = s k when s k < t 0 due to the fuel savings in D 2 . Definition 1. We use G(s) to denote the reward when a = s with s < t 0 , and use H(a) to denote the reward when a < s, Since w 1 , w 2 , and α are all positive, G(s) is a concave function with the maximum value Similarly, H(s) is concave and has the maximum value when s = c N . In addition, lim Assumption 1. To generalize the total cost which balances fuel consumption and travel time, the generic total cost G(s) follows: The next state S k+1 is the predicted headway for vehicle (k + 1). The deterministic relationship between vehicle k and vehicle (k + 1) is, . . , N , to denote the maximum expected total rewards, i.e., optimal state-value function, from step k to step N , and then for all k and s ∈ S, where 0 < γ < 1 is the discount factor, which denotes the extent of valuing long-term rewards. We use the discounted reward γ j R(s j+k , a j+k ) at each step since we start with vehicle k and end with vehicle N . Let Q * k (s, a) be the optimal action-value function, Then for all k, s ∈ S and a ∈ A, The objective is to maximize the discounted total rewards R, where R is associated with a policy π = {µ 1 , µ 2 , . . .}

Optimal Policy under General Arrival Processes
In this section, we study the structure of the optimal policy to the DP problem formulated in the previous section with general arrival processes for CAVs. Specifically, we show that the optimal strategy is threshold-based as follows: Theorem 1. An optimal policy to the coordinated platooning Problem 1 is a threshold-based policy such that where θ is the threshold, and c is the constant time reduction.
One can interpret the optimal policy as follows. When the kth vehicle enters the coordinating zone, if the predicted headway s k is less than or equal to a threshold θ, then vehicle k will be instructed to catch up with vehicle (k − 1) and thus platoon. Otherwise, vehicle k will slightly slow down with the constant time reduction c in anticipation of platooning with vehicle (k + 1).
We prove Theorem 1 by analyzing the value function associated with the MDP. We firstly study the finite-horizon, N -stage problem and characterize the structure of the optimal policy for s ≥ c N . Then we take the limit of N and obtain the result. Furthermore, the general thresholdbased policy is presented. Throughout the derivation of this result, we assume a general arrival process and the generic cost function in Assumption 1.

Optimal returns of N -stage problem
Proposition 1. The optimal policy for vehicle k, k = 1, 2, . . . , N is a threshold-based policy for s ≥ c N such that where θ k is the threshold for vehicle k, and c k is the optimal constant time reduction for vehicle k.
We prove Proposition 1 by starting from the initial optimal returns for vehicle N , and then derive the optimal policies for all vehicles using the induction of value functions with known transition probabilities.
Definition 3. For all s k , a k takes value from (−∞, s k ]. We use a 1 k < s k to denote the action of non-merging, and use a 2 k = s k to represent the action of platooning with the previous vehicle.

Initial optimal returns
Lemma 1. The optimal policy for vehicle N is a threshold-based policy such that where θ N is the threshold, θ N ∈ (c N , t 0 ), and c N is the optimal constant time reduction.
Proof. Since there is no vehicle after N th vehicle, V * N (s) = max a N R(s N , a N ), for all s N . We use (Z N + G(0)) to denote the maximum value (Figure 4), and Z N is the maximum value of H(s) when s < t 0 due to H(s) = G(s) − G(0). lim The optimal action is a 2 N = s N , i.e., merging with the previous vehicle.
(ii) When s N ∈ (c N , θ N ], for all a 1 N < s N and a 2 N = s N , and then Q * N (s N , a 1 N ) < Z N ≤ G(s N ) = Q * N (s N , a 2 N ). The optimal action is a 2 N = s N .
(iii) When s N ∈ (θ N , t 0 ), for all a 1 N < s N and a 2 N = s N , and then the optimal action is a 1 N = c N , i.e., cruising with the non-merging time reduction c N .
(iv) When s N ∈ [t 0 , +∞), and then the optimal action is also a N = c N .
Above all, the optimal policy for vehicle N is a threshold-based policy as shown in Lemma 1. Furthermore, the value function V * N (s) is: Remark 1. Vehicle N should merge with the previous vehicle if the predicted headway is below the threshold θ N , otherwise it should cruise with the optimal constant time reduction c N . In practice, we usually value fuel consumption over travel time, i.e., w 2 w 1 , then Vehicle N would cruise with lower speed with time reduction c N .

Induction of value function
Lemma 2. If vehicle k, k = 2, . . . , N , follows an optimal threshold-based policy for s ≥ c N such that where θ k is the threshold for vehicle k, θ k ∈ (c N , θ N ], and c k is the optimal constant time reduction for vehicle k, c k ∈ θ N , c N . In addition, V * k (s) is monotonically decreasing for s ≥ c N , V * k (s) = Z k for s ≥ θ k , and V * k (c k ) = Z k + G(0). Then vehicle (k − 1) also follows an optimal threshold-based policy for s ≥ c N , where θ k−1 is the threshold for vehicle (k − 1), θ k−1 ∈ (c N , θ N ), and c k−1 is the optimal constant time reduction for vehicle (k − 1), Proof. We consider vehicle k and vehicle (k − 1), When s k−1 < t 0 , for all a 1 k−1 < s k−1 and a 2 k−1 = s k−1 , and We then derive the lower bound of J k−1 (c N ), hence Since dG ds < 0, and V * k (s) is monotonically decreasing for s ≥ c N , J k−1 (s) in Equation (5) is monotonically decreasing in [c N , t 0 ) for all f (x) (Figure 5(b)), we suppose Then we analyze the upper bound and lower bound of Z k−1 .

Then we compare
and then From Equation (7) and Equation (8), We then analyze the action-value functions under different s: and then Q * k−1 (s k−1 , a 1 k−1 ) ≤ Q * k−1 (s k−1 , a 2 k−1 ). The optimal action is a 2 k−1 = s k−1 , i.e., merging with the previous vehicle.
and then the optimal action is a k−1 = c k−1 .
Above all, the optimal policy for vehicle (k − 1) is a threshold-based policy for s ≥ c N as shown in Lemma 2. Furthermore, the value function V * k−1 (s) is: Note that we cannot know V * k−1 (s) for s < c N due to the unknown f (x). We will clarify this in Section 3.3.
Since vehicle N follows the optimal policy shown in Lemma 1, and V * N (s) meets the conditions in Lemma 2, vehicle k, k = 1, 2, . . . , N − 1 also follows an optimal threshold-based policy for s ≥ c N as shown in Proposition 1, and V * k (s) has the characteristics in Lemma 2.

Extension to infinite horizon
Proposition 2. When N → ∞, the optimal policy for vehicle k, k = 1, 2, . . ., converges to the threshold-based policy for s ≥ c N such that where θ is the threshold, θ ∈ [c N , θ N ], and c is the optimal time reduction, c ∈ θ N , c N .
When N → ∞, V * k (s) would converge to V * (s), Z k would converge to Z, and V * (s) is monotonically decreasing for s ≥ c N . In addition, and V * (c) = Z + G(0).
The Bellman optimality equation for V * (s) is, where s is the next state of s.
Since the probability density function is f (x), where V * (s) is continuous at s = θ.

The general threshold-based policy
Proposition 3. The optimal stationary policy for s < c N is, where the vehicle would merge with the previous vehicle.
We first present the lower bound of the value function difference, and then compare the action-value functions to derive the policy for s < c N .

Action value comparison
Definition 4. For s ∈ S, the action a ∈ (−∞, s]. a * 1 < s is the action of non-merging, and a * 2 = s is the action of merging. Note that when s ≥ t 0 , a ∈ (−∞, t 0 ). Lemma 4. For s < c N , where a * 1 < s, and a * 2 = s. The optimal action for s < c N is to merge with the previous vehicle. Proof. For s < c N , Then for the action a * 1 < a * 2 = s, We take the difference, Since s + x > a * 1 + x, the lower bound of the state-value function difference (Lemma 3) is , ∀x > 0, and then for all f (x), 2 ) > Q * (s, a * 1 ), ∀s < c N . Then the optimal policy for s < c N is to merge with the previous vehicle as shown in Proposition 3.
In summary, from Proposition 2 and Proposition 3, the optimal stationary policy is, where θ is the threshold, θ ∈ [c N , θ N ], and c is the optimal time reduction, c ∈ θ N , c N . The optimal value function is,

Solution Algorithm
In this section, we propose algorithms to compute the optimal coordinated platooning policies. For general arrival processes, we design two dynamic programming (DP) algorithms based on previous analysis: bounded value iteration and recursive approximation, to determine the optimal θ and c in Equation (3). The bounded value iteration is a generic DP algorithm with the threshold-structure (Section 4.1), while the recursive approximation (Section 4.2) explicitly incorporates the characteristics of the optimal policy obtained in the previous section. We compare the computational efficiency of these two algorithms in various scenarios (Section 4.4). For Poisson arrival processes (which is the most commonly used model for vehicle arrivals), we further show that θ and c can be obtained by solving a system of integral equations (Section 4.3), which is significantly faster than DP-based algorithms.

Bounded value iteration
Value iteration is a generic approach in dynamic programming [28]. According to our analysis in Section 3.3, the value function V * (s) stays constant when s > θ N . We only need to update the value function for s ≤ θ N to reduce algorithm complexity. The bounded value iteration is shown in Algorithm 1.

Algorithm 1 Bounded value iteration.
Input end for 12: end while 13: Output the optimal deterministic policy π * such that 14: π * (s) = argmax a R(s, a) + γ +∞ 0 The action is the time reduction a, which lies in (−∞, s]. Although the state s and action a are both continuous, the problem is transformed into the tabular framework due to the discontinuous reward R(s, a) at a = s shown in Equation (2). In Algorithm 1, we firstly discretize the states in a given range [m, n], m < c N < θ N < n. Then we let V * (s)| s>θ N = V * (s)| s=θ N to simplify the value iteration process. The optimal policy would converge when the estimation gap is smaller than the small positive number ε, which determines the estimation accuracy.

Recursive approximation
The complexity of value iteration in Algorithm 1 is determined by the small positive number ε. The iteration steps would increase significantly if we choose a small ε. To improve the efficiency, we design the algorithm (Algorithm 2) that approximates the optimal solution based on the characteristics of V * (s).
In Equation (13), V * (s) is continuous at s = θ, hence, For each discrete θ i ∈ [m, n], we can derive the Z i based on Equation (14). Since the optimal solution is a threshold-based policy, V * i (s) = Z i for s ≥ θ i . Then we can derive V * i (s) for s < θ i recursively from θ i to m using the following equation, For each θ i , we can derive the specific function V * i (s). In Section 3.2, V * i (s) has the maximum value M i = Z i + G(0) when s = c i . The optimal θ and c should be the values that make M i approximate (Z i + G(0)) best. The methodology of Algorithm 2 is in accordance with the essence of dynamic programming since we derive V * i (s) recursively from θ i to m, which would avoid the value iteration.
for each s in the reversed list from n to m do 5: if s ≥ θ i then 6: M i ← max s V * i (s); 12: c i ← argmax s V * i (s); 13: end for 14: Optimal c, θ = argmin c i ,θ i |M i − (G(0) + Z i )|

Optimal strategy under Poisson arrivals
Theorem 2. The optimal policy to the coordinated platooning Problem 1 under Poisson arrivals with f (x) = λe −λx is a threshold-based policy such that where θ and c satisfy the following equations: in which λ is the arrival rate, G (s) is the derivative of G(s).
Proof. For all s < θ, in which the integral interval (s, +∞) can be divided into (s, θ) and (θ, +∞). In Equation (9), which meets the format of Ordinary Differential Equation (ODE), the solution of the ODE [29] with V * (c) = Z + G(0) in Equation (10) is Since V * (θ) = Z, V * (s) has the maximum value when s = c, and V * (s) is derivable for s < θ, We can find the optimal threshold θ and constant time reduction c by solving Equation 14, 18, and 19.

Algorithm efficiency comparison
In this subsection, we compare the efficiency of the proposed algorithms: Bounded value iteration (BVI), Recursive approximation (RA), and the refinement under Poisson arrivals (PR). The time complexity comparison is shown in Table 1. Since I is large due to the small ε, the RA algorithm is more efficient than BVI under general arrival processes. The time of solving a system of integral equations is constant.  The time of finding the optimal solution is shown in Table 2. When the headway follows an exponential distribution, the solution time of bounded value iteration is 9.6 hours, while the solution time of recursive approximation is less than 1 hour. When the discrete random and constant headway distributions are chosen, recursive approximation still yields better performance than bounded value iteration. In addition, the time in exponential distribution is more significant due to the calculation of the integral. Specifically, solving the system of equations is the most efficient approach under Poisson arrivals. The results indicate that adding more prior knowledge can improve algorithm efficiency.

Numerical Results
In this section, we use real data to evaluate our proposed policy presented in the previous sections. The Real-time Strategy (RTS) is developed to coordinate platooning under different flows. The case study setting is provided in Section 5.1. The validation is conducted in three steps. In Section 5.2, we compare the threshold-based policy with a straightforward policy and quantify the improvement. In Section 5.3, we study the sensitivity of the average cost with respect to key operational parameters. In Section 5.4, we present the interpretation of the RTS.

Setting
We study the implementation of heavy-duty vehicle platooning at the interchange of I-210 and 134 located in the Los Angles metropolitan area. The real data are acquired through the Freeway Performance Measurement System (PeMS), which provides historical traffic data based on Caltrans loop detectors [27]. The 24-hour data on January 22, 2019 are used to evaluate the policy (Table 3). Poisson arrivals are assumed to generate vehicle departures during each hour, and the flow within each hour keeps constant. Detectors are located D 1 = 1 km from the junction on freeway I-210 and 134. The platooning decision is made based on the predicted headway introduced in Section 2.1.2. When the following vehicle is determined to merge with the leading vehicle, the following vehicle would adjust its speed to meet the leading vehicle at the junction. We consider a safety reaction time 2.3 s for the following vehicle to avoid collision [30], i.e., the following vehicle would arrive 2.3 s later than the expected arrival time given by our policy. Note that there is no safety reaction time under non-merging case. The maximum speed on the freeway in our setting is 40 m/s. Since the vehicle flow fluctuates during the day, we consider the M -step discounted previous headways as an estimator for the arrival rate: where β ∈ (0, 1) is the discounted factor of inter-arrival time, and larger β denotes longer headway calculation period. X k−m is the mth previous headway. When M is large enough,λ k can be an estimator for the real arrival rate λ.
The estimated arrival rateλ k is updated once the vehicle is detected on either branch. Under Poisson arrivals, the optimal threshold and C could be obtained by solving a system of integral equations in Theorem 2. In our case study, Real-time Strategy (RTS) is realized by solving Equation (16) based on dynamic prediction of the arrival rate, i.e., each vehicle would have the specific threshold and C value, which would yield better performance with respect to the flow fluctuation. The solution of Equation (16) is calculated using the Python package scipy.optimize, which relies on the initial value. To avoid the divergence in real implementation, the calculated threshold and C value of vehicle k are the initial values of vehicle (k + 1).
The evaluation metric is the absolute total cost including fuel consumption and travel time. Fuel consumption is calculated by the sum of fuel cost at every step. The fuel rate f (L/s) is derived using the data in Simulation of Urban MObility (SUMO) [31]: f = 3.51×10 −7 v 3 +4.07× 10 −4 v, in which we neglect the effect of acceleration. The fuel consumption in the coordinating zone is: which v k is the modified speed of vehicle k, and then α = 3.51 × 10 −7 L · s 2 /m 3 . Fuel consumption and travel time both include cost in the coordinating zone D 1 and cruising zone D 2 . Nominal parameters shown in Table 4 are used in the case study.

Performance comparison
In this subsection, we compare three platooning policies under different flows: 1. Baseline: all vehicles keep the original speed during the coordinating zone, and the following vehicle would merge with the leading vehicle if they arrive at the junction within the safety reaction time 2.3 s.
2. Policy A: we use the proposed policy in [25]. The following vehicle would merge with the previous vehicle if their inter-arrival time is below an optimal threshold, otherwise it would keep the original speed v. Note that only acceleration is enabled in this policy.
3. Policy B: our proposed policy is implemented according to Theorem 1.
Note that Policy A and Policy B are both RTS due to the dynamic prediction of arrival rate.
Since we study the platooning of heavy-duty vehicles, the arrival rate is much smaller than the real traffic flow. We assume that a percentage of real flow on I-210 and 134 is the heavy-duty vehicle, and all vehicles in the simulation can be connected. Figure 7(a) shows total cost under different average flows, i.e., different percentages of Average Daily Traffic (ADT) in Table 3. The evaluation metric is the average cost per vehicle, AC = T C Nt , where T C is the total cost, and N t is the total number of vehicles. The results show that our proposed policy yield the minimum average total cost compared with other policies. The improvement is more significant under higher average flows.  In Figure 7(a), Policy B yields $0.9 average cost reduction from the baseline when the average flow is 173 veh/hour, i.e., we can save $3736.8 at one junction after one-day coordination. Policy A can reduce $0.6 average cost, and the total cost reduction is only $2491.2. Hence, policy B is more effective in reducing the absolute total cost. Figure 7 The two figures show that Policy B has the best performance by reducing the fuel consumption. The average travel time in Policy B is even larger than the baseline. Policy A reduces both fuel consumption and travel time, however, the total cost is more than Policy B.

Sensitivity analysis
In this subsection, we study the sensitivity of the average cost with key parameters: discount factor γ and cursing distance D 2 . We have conducted the sensitivity analysis of γ when D 2 = 30 km and D 2 = 70 km. The average vehicle flow is 45 veh/hour. The results in Figure 8(a) indicate that the average total cost would decrease as we increase γ, which denotes the extent of considering long-term rewards, when the cruising distance is 30 km. However, when we increase the cruising the distance to 70 km (Figure 8(b)), the curve would firstly decrease and then increase with γ. When we increase the cruising distance, the policy enables more deceleration to form longer platoons under large γ due to fuel savings in D 2 . When the following vehicle receives the non-merging signal, lower speed would increase the travel time, and thus increase the total cost. Analysis of the vehicle deceleration with respect to D 2 is shown in Section 5.4.  Then we investigate the effect of the cruising distance D 2 . The evaluation metric is the average cost per kilometer, AC = T C Nt * (D 1 +D 2 ) . Figure 9(a) shows the average cost AC with D 2 under γ = 0.6. Average cost would decrease as we increase the cruising distance due to the fuel reduction in D 2 . However, the results in Figure 9(b) show that the average cost per kilometer curve firstly decreases, and then does not change too much after 60 km. The initial decrease of AC results from the benefits of fuel savings in D 2 . The marginal improvement of extending the cruising distance is negligible after 60 km with a large γ. Figure 8 and Figure 9 indicate that large discount factor and long cruising distance together can increase the average total cost.

Interpretation of Real-time Strategy
In this subsection, we present the insights of the Real-time Strategy (RTS). Figure 10 shows the dynamic threshold and C value with respect to the estimated flowλ k . The analysis period is from 9:10 A.M. to 9:57 A.M., and the number of vehicle arrival is 50. When we increase D 2 from 30 km to 70 km, the threshold would not change too much, while the C values in Figure 10(d) are much smaller than those in Figure 10(b). When D 2 = 70 km, the leading vehicle would have smaller speed due to more deceleration, which would reduce the platoon average speed.  In Figure 10(a) and Figure 10(c), the threshold changes toward the opposite direction of the flow, which indicates that lower flow can increase the threshold and thus enable more platooning. The C values in Figure 10(b) change toward the opposite direction of the flow, however, the C values in Figure 10(d) change toward the same direction. The gap between threshold and C, i.e., threshold minus the C, would increase as we have longer D 2 .
We then select 5 vehicles during the analysis period to show their longitudinal maneuvers by the space-time diagram (Figure 11) in the coordinating zone D 1 . In Figure 11(a), these 5 vehicles form 2 platoons with higher speeds under D 2 = 30 km. In contrast, vehicles form 1 platoon with lower speeds in Figure 11(b) under D 2 = 70 km, which indicates that higher cruising distance can facilitate the platooning process and reduce the average speed in D 1 , thus increase the total cost resulting from more travel time. The average cost of extending D 2 would firstly decrease and then increase slightly in Figure 9(b).

Concluding Remarks
In this paper, we consider the coordinated platooning problem using a Markov decision process formulation. The formulation is general in the sense that the arrival process can be a rather general class of renewal processes and that the cost function is generic. By studying the Bellman optimality condition for the MDP, we show that the optimal coordination strategy is threshold based. Using this structural result, we develop a recursive approximation algorithm to compute the optimal strategy, which is significantly faster than the generic value iteration algorithm.  Furthermore, we show that for Poisson arrival processes, the optimal strategy can be directly computed by solving a system of integral equations. We also validate our results in simulation with Real-time Strategy using real traffic data.
This work can be extended in several directions. First, the analysis for a single junction is the basis for the analysis of centralized or distributed coordination at networks of junctions (see e.g. [32] for a preliminary simulation-based analysis). Second, the interaction between CAV platoons and the background traffic still needs to be appropriately modeled and addressed. Third, social-economical mechanisms that incent CAVs to cooperate still needs to be designed and validated, since the benefit of platooning is not evenly distributed over all vehicles.