## 3 Resequencing and Platooning Algorithm for Solving CSP
### Resequencing Algorithm based on State Transition Network  
To enhance the performance of the RA, we have introduced state transition networks [16]. For the research object composed of four organizing segments, a state vector \(\textbf{st}=[st_{1},\ st_{2},\ st_{3},\ st_{4},\ k_{st}]\) has been defined to represent the current state \(ST\). Each element \(st_{k}\in[0,n_{k}]\) in **st** denotes the number of CAVs sorted on organizing segment \(k\), while \(k_{st}\) identifies the segment where the sorted CAV is located when transitioning from the previous state \(ST^{\prime}\) to the current state \(ST\). Taking the state vector \(\textbf{st}^{\prime}=[st^{\prime}{}_{1},\ st^{\prime}{}_{2},\ st^{\prime}{}_{3 },\ st^{\prime}{}_{4},\ 4]\) representing the state \(ST^{\prime}\) as an example, suppose that, in this state, a CAV on organizing segment 3 has been sorted. Then, the correspondence between the state vector **st** of the new state \(ST\) and \(\textbf{st}^{\prime}\) is \(st_{1}=st^{\prime}{}_{1}\), \(st_{2}=st^{\prime}{}_{2}\), \(st_{3}=st^{\prime}{}_{3}+1\), \(st_{4}=st^{\prime}{}_{4}\), \(k_{st}=3\). This state transition process incurs a transition cost \(C(ST^{\prime},\ ST)\), which equals the collision avoidance cost between the CAV currently being sorted and the last sorted CAV, identified as \(\sum_{i=1}^{3}n_{i}+st^{\prime}{}_{4}\) and \(\sum_{i=1}^{2}n_{i}+st^{\prime}{}_{3}+1\). To enhance the intuitive understanding of the state transition network, we categorize the states \(ST\) into different stages \(h=\sum_{k\in M}st_{k}\) based on the total number of sorted CAVs. Since the value of \(\sum_{k\in M}st_{k}\) increases by 1 with each transition, it ensures that the transition can only occur from stage \(h\) to stage \(h+1\), thereby guaranteeing a finite path length in the state transition network. Finally, we define the initial state \(ST_{start}\) as \(\textbf{st_{start}}=[0,\ 0,\ 0,\ 0,\ 0]\), which is connected to the states in stage 1 through corresponding transitions. Similarly, we introduce the final state \(ST_{end}\) as \(\textbf{st_{end}}=[n_{1},\ n_{2},\ n_{3},\ n_{4},\ 0]\), connecting the states in stage \(n\). Figure 6 illustrates an example of a state transition network in the intersection area with two organizing segments, each containing two CAVs. The path from the initial state \(ST_{start}\) to the final state \(ST_{end}\) in the state transition network represents a feasible sorting arrangement for CAVs. This arrangement involves a systematic sorting process of CAVs on 4 organizing segments, facilitated through a series of state transitions. Throughout the state transition process, each transition is associated with a specific transition cost. Consequently, the global optimal solution of the CSP corresponds to the path from \(ST_{start}\) to \(ST_{end}\) that results in the minimum total transition cost. In Algorithm 1, \(cost(end)\) represents the minimum transition cost in the state transition network, and \(route(end)\) denotes the shortest path containing \(n\) states, where \(n\) represents the total number of CAVs on four organizing segments. The sorting vector \(\textbf{sq_{i}}\) comprises two elements: \(sq_{i}\) records the identification of the CAV entering MZ in the \(i\)-th sorted order, and \(os_{i}\) is used to denote the identification of the segment in which the CAV is located. The obtained set \(SQ=\{\textbf{sq_{i}},\ldots,\textbf{sq_{n}}\}\) represents a crossing sequence of CAVs, achieving the minimization of the total collision avoidance cost, thereby constituting the  
Figure 6: State transition network of CSP. global optimal solution of the CSP. Additionally, \(SQ\) also contains information about the organizing segments where each CAV is situated, which is crucial for subsequent platoon forming algorithms. ```
1. Input: The count of CAVs on each organizing segment \(k\), denoted as \(n_{k}\), the collision avoidance cost \(C_{ij}\) between any two CAVs \(i\) and \(j\), and the organizing segment counter \(m\) initialized to zero. 2.