# Optimal Lane Allocation Strategy in Toll Stations for Mixed Human-Driven and Autonomous Vehicles
## Appendix B The Relaxed Solution of the TSLAP
### Solving Relaxed Bilevel Programming Problems Using Iterative Methods  
When solving a bilevel programming problem, iterative methods are generally an effective approach for tackling such complex issues. Bilevel programming involves two levels of optimization problems, where the upper-level problem (leader) typically influences the decision-making of the lower-level problem (follower). Since the lower-level problem usually depends on the decision variables of the upper-level problem, the core challenge in solving a bilevel programming problem lies in how to effectively interact between these two levels. The following are the steps to solve the two-layer programming problem based on the iterative method:  
**Step 1: Initialization**  
Set the initial upper-level decision variable (e.g., \(n_{di}^{c\ (0)}\)), and solve the lower-level problem to find the optimal solution (e.g., \(\lambda_{di}{}^{(0)}\)) based on these initial decision variables. **Step 2 to 4: Iterative Process**  
Step 2: In the \(m\)-th iteration, solve the lower-level problem using the current upper-level decision variable \(n_{di}^{c\ (m)}\), and obtain the solution \(\lambda_{di}{}^{(m)}\). Step 3: Based on the solution \(\lambda_{di}{}^{(m)}\) of the lower-level problem, use the result to update the upper-level decision variable \(n_{di}^{c\ (m+1)}\). Step 4: Check for convergence. If the convergence criteria are met (e.g., the change in the solution is sufficiently small), stop the iteration; otherwise, return to Step 2 and continue the iteration. We may initialize the upper-level problem with the solution \(n_{di}^{c\ (0)}\) given by Equation (A5). Since \(\lambda_{di}\) serves as both a parameter in the upper-level model and a decision variable in the lower-level model, Equation (A5) cannot be directly applied to the lower level to avoid altering the original lower-level optimization problem. Assume that all vehicles choose the ETC lane, i.e., \(\theta_{d1}=1\), \(\theta_{d2}=0\). In this case, Equation (A5) represents the following set of initial feasible solutions:  
\[n_{di}^{c\ (0)}=\frac{\frac{\lambda_{di}{}^{*}}{\mu_{di}}n_{\text{sum}}}{\sum_{d \in\mathbf{D}}\sum_{i\in\mathbf{I}}\frac{\lambda_{di}{}^{*}}{\mu_{di}}}\] (A10)  
subject to  
\[ \begin{cases}\lambda_{d1}{}^{*}=(p_{1}+p_{3})\lambda_{d},\\ \lambda_{d2}{}^{*}=p_{2}\lambda_{d}.\end{cases} \] (A11)  
Substituting the initial solution \(n_{di}^{c\ (0)}\) into the lower-level objective function (Equation (18)), we do not immediately solve it. Instead, we first prove Proposition A2, thereby avoiding the need for a case analysis of its monotonicity. **Proposition A2**. : _With the initial lane allocation \(n_{di}^{c\ (0)}\), the average travel time on ETC lanes is always less than on MTC lanes, as expressed by the following:_  
\[\frac{1}{Ws_{d1}{}^{(0)}}-\frac{1}{Ws_{d2}{}^{(0)}}>0.\] (A12)  
Proof. : By introducing Equation (A10), we obtain  
\[\frac{1}{Ws_{d1}{}^{(0)}}-\frac{1}{Ws_{d2}{}^{(0)}}=\mu_{d1}-\mu_{d2}-\frac{1 }{n_{\text{sum}}}\sum_{d\in\mathbf{D}}\sum_{i\in\mathbf{I}}\frac{\lambda_{di} {}^{*}}{\mu_{di}}^{\left(\frac{\mu_{d1}\lambda_{d1}}{\lambda_{d1}{}^{*}}- \frac{\mu_{d2}\lambda_{d2}}{\lambda_{d2}{}^{*}}\right),\] (A13)  
where the asterisk (*) denotes a parameter, rather than a decision variable in the lower-level problem. Therefore, proving Equation (A12) is equivalent to proving  
\[\mu_{d1}-\mu_{d2}>\frac{1}{n_{\text{sum}}}\sum_{d\in\mathbf{D}}\sum_{i\in \mathbf{I}}\frac{\lambda_{di}{}^{*}}{\mu_{di}}^{\left(\frac{\mu_{d1}\lambda_{ d1}}{\lambda_{d1}{}^{*}}-\frac{\mu_{d2}\lambda_{d2}}{\lambda_{d2}{}^{*}} \right).\] (A14)  
Considering Equation (16), it follows that \(\frac{\mu_{d1}\lambda_{d1}}{\lambda_{d1}}-\frac{\mu_{d2}\lambda_{d2}}{\lambda _{d2}{}^{*}}\) increases as \(\lambda_{d1}\) increases.