# Selecting Remote Driving Locations for Latency Sensitive Reliable Tele-Operation
## 3 Selecting Driving Locations for Multiple Paths
### Selecting a Fixed Number of Driving Locations for Smallest Distance
Thus, general optimization algorithms such as simulated annealing and genetic algorithm may work for this problem. In this paper, we use simulated annealing as another baseline algorithm to evaluate the performance of the previous two heuristic algorithms. In reality, it might not be feasible to use simulated annealing due to large time complexity. We use simulated annealing to check whether the proposed heuristic algorithms perform near optimal. Since simulated annealing is a well known algorithm, we just briefly mention some necessary information specific to our problem. For simulated annealing, we first find an initial subset of \(k\) driving locations, \(H\), and measure its distance to the base stations, \(B\) of\(H\) becomes the current solution. Then, we choose a neighbor solution, \(H^{\prime}\), which is a solution slightly different from \(H\). In our implementation, we just randomly choose a driving location in \(H\) and replace it by another randomly selected driving location from \(\mathcal{F}\). Then, we compute the distance from \(H^{\prime}\) to \(B\). Based on the distances from \(H\) and \(H^{\prime}\), we compute the transition probability to the neighbor solution. Based on that transition probability, we may move to the neighbor solution or stay at the current solution. We repeat this process for a predefined number of iterations. The detail is shown in Algorithm 4. ```
1:Input: \((P,\mathcal{F},k)\)
2:Output: \(D\)
3:\(P\): List of src-dst paths
4:\(\mathcal{F}\): set of candidate driving locations
5:\(k\): given number of drivers
6:\(D\): Solution Set
7:\(lb\leftarrow\delta\) // the smallest distance, lower bound
8:\(ub\leftarrow\) the largest distance in the area // upper bound
9:while\(lb<ub\)do
10:\(L\leftarrow\frac{lb+ub}{2}\)
11:\(H\leftarrow\)\(ERDSMP(P,\mathcal{F},L)\)
12:if\(|H|>k\) or \(H\) is empty then
13:\(lb\gets L+\delta\)
14:elseif\(|H|=k\)then
15:\(ub\gets L-\delta\)
16:\(D\gets H\)
17:else
18:\(ub\gets L\)
19:return\(D\)
```  
**Algorithm 3** BS. ```
1:Input : \((P,\mathcal{F},k,r)\)
2:Output :\(D\)
3:\(P\): List of src-dst paths
4:\(\mathcal{F}\): set of candidate driving locations
5:\(k\): given number of drivers
6:\(r\) : number of iterations
7:\(D\) : Solution Set
8:// initialization
9:\(B\leftarrow\)



## 4 Evaluation

In this section, we evaluate the performance of remote driving location selection algorithms proposed in the previous section. For the evaluation, we assume a transportation environment of 3000 base stations, i.e., \(|\mathcal{B}|=3000\) and 500 candidate remote driving locations, i.e., \(|\mathcal{F}|=500\), in the area of 1000 \(\times\) 1000, where base stations and remote driver are uniformly randomly distributed over the entire area. One thing to note is that we do not specify the unit of the area and the latency constraints \(L\) because the main purpose of this paper is to propose algorithms for various situations. Thus, depending on situations, the unit could be meters or kilometers and so on. The number of origin-destination pairs is 1000, i.e., \(|P|=1000\). One subtle thing is the unit of the latency constraint \(L\). We need to provide a time unit for the latency constraint. However, since the latency is proportional to the distance, we specify the latency constraint \(L\) in terms of distance. For example, latency constraint 300 means 300 distance unit. Actually, the origin and destinations are simply base stations that are uniformly randomly selected from \(\mathcal{B}\). Then, we need to find the sequence of base stations between the origin and the destination. Since we do not have any road map on this synthetic data set, we mimic the road map by using Delaunay triangulation [36]. To be specific, we run Delaunay triangulation with the positions of the base stations. This generates a planar graph with base stations as nodes. The edges constructed from the Delaunay triangulation are considered as road segments. Then, we find the shortest path between the origin and the destination using the Dijkstra shortest path finding algorithm.