-In this paper, we consider the stochastic on-time 2. The -reliable path models [4], [7], [8] minimize the time arrival problem in a transportation network with the following interval which is necessary to arrive at the terminal vertex optimization criteria: maximizing the probability of arriving at (destination) on-time for a given probability . faordmesutliantaiotinonalwloiwthsincoansipdreerdinefginnedot toimnley bthuedgmete.aTnhtirsavperlobtilemme 3. The most reliable shortest path models [3], [9] maximize of the road links but also the travel time variance. Existing the probability of arriving at the destination within a given approaches to solving this problem show good results in terms time budget (stochastic on-time arrival - SOTA problem). of the quality of the found route but have high computational In this paper, we consider the reliable path finding problem cnoamvipglaetxi oitnya.l Taphpislicfaatcitondsoiensrenaolttimalleo.wIn uthsiinsgpatpheerm,weininpversatcitgiacatel with the following formulation: to determine the optimal the parallelization strategy of the stochastic on-time arrival navigation strategy that maximizes the probability of arriving routing algorithm using the CUDA GPU. Experimental studies at the destination within a predefined time interval (time conducted on the large-scale transportation network of the budget). Samara city, Russia show that the proposed approach can reduce In [3], the authors proposed an algorithm for the exact the computation time by an average of 5 times. solution of the SOTA problem. One of the steps of the
The routing problem remains one of the most actual
problems in transportation systems. Existing navigation systems
and routing web-services usually consider transportation
networks as directed graphs with deterministic edge weights and
do not take into account the stochastic properties of traffic
flows w hen s olving t he r outing p roblem. A t t he s ame timec,omputation complexity of the algorithm or the development
the travel time of road segments depends on many factors of approximation algorithms.
including the day of the week, time of day, weather conditions, In the article [
In this paper, we propose a strategy for parallelizing the reliable path finding algorithm using the CUDA GPU . The work is organized as follows. In the second section, the main notation, problem statement, and description of the algorithm are given. The parallelization strategy is presented in the third section. The fourth section describes the experimental setup and results of experimental studies. Finally, we give the conclusion and possible directions for further research.
II. PROBLEM STATEMENT
The transportation network is considered as a directed graph G = (N; A; P ), where N is the set of nodes, jN j is the number of nodes, A is the set of edges, jAj is the number of edges, P is the probabilistic description of the edge weights (i.e. the road link travel times.
The weight of the edge (i; j) 2 A is considered as a random variable Tij ( ) with a time-dependent probability density function pij (t).
Denote the destination node as d 2 N , time interval within which is necessary to reach the destination node (time budget) denote as T . An optimal routing strategy is defined as a policy that maximizes the probability of arriving at the destination node d 2 N from the origin node o 2 N within the given time budget T .
Let ui(t) be the probability of arriving at the destination node d from the node i in time less than t. Then, the optimal routing strategy can be formulated as follows:
t
Z ui (t) =
max j2N ^(i;j)2A
0 8i 2 N n fdg; t 2 [0; T ]; ud (t) = 1; t 2 [0; T ]; 0: pij ( )uj + (t )d ; 0;
(1)
To solve the problem (1), a discrete algorithm was proposed
in [
In Algorithm 1, we use the following notations: t is the discretization interval, is the minimum realizable link travel time across the entire network.
The selection of the next vertex j in the transportation graph (and, accordingly, the next road link) using the remaining time budget t and the calculated array of arrival probabilities ui(x) is performed as follows: j = arg max ui(t): (2)
i2N
In the next section, we describe an algorithm parallelization strategy using the GPU.
III. METHODOLOGY
To decrease the running time of the reliable shortest path search algorithm, it is proposed to implement it on a graphics accelerator using CUDA.
8i 2 N; i 6= d; x 2 N; 0 x 2 N; 0 x Tt x
T t end Step 1. Update for k = 1; 2; ; L do
k = k udk(x) = 1; x 2 N; 0 x Tt uik(x) = uik 1(x)
8i 2 N; i 6= d; (i; j) 2 A; x 2 N; 0 uik(x) = maxj Pxh=0 pij (h)ujk 1(x 8(ik2 N; i 6= d; (i; j) 2 A; x 2 N; t ) + 1 x kt h) x k t
CUDA (Compute Unified Device Architecture) is a hardware-software parallel computing architecture developed by Nvidia that allows using the GPUs for general-purpose computing.
The host computer transfers data to the device’s memory and calls a special function called the kernel. When calling the kernel function, two parameters are set: the number of blocks and the number of threads in the block. Each thread executes the same set of instructions, but with different data elements. Streams within one block can exchange the results of calculations using the shared memory mechanism.
Fig. 1 presents the computation model.
Kernel 1 Kernel 2
uij (x) = x X pij (h)uj (x h=0 h); that is, uij (x) is the probability of reaching the terminal vertex d from the origin vertex i during the time interval x when moving on the road edge (i; j).
Algorithm 1 is executed sequentially in time (a cycle by the variable k), however, the calculation of the probabilities of arrival uik(x) can be performed in parallel mode. The implementation of this process in CUDA consists of calling the kernel function (Algorithm 2), which calculates the probability of reaching the terminal vertex from each vertex of the graph at a given time step.
Algorithm 2: Parallel algorithm for k = 1; 2; ; L do
process<< Nc, Tc >>(k) end load p(1); memory ;
k calculate uix8(i; x) 2 A ; calculate ukx = maxi uikx ; return function process(k): /* calculate index of the processed vertex x x = threadIdx:x + blockDim:x blockIdx:x; */ ; p(t) and corresponding u from the
In the Algorithm 2, threadIdx is the thread index, blockDim is the block dimension, blockIdx is the processing block index.
Thus, the calculation of the probabilities of reaching the destination node for a given time interval will be performed in parallel for each node of the graph in a separate stream of the graphic accelerator.
IV. EXPERIMENTS
Experimental studies of the base and parallel algorithms were carried out for a large-scale transportation network of Samara, Russia, consisting of 47274 road links (edges) and 18582 nodes.
To compare the running time of the base and parallel implementations of the algorithm for finding a reliable shortest path, 6 pairs of different origin-destination nodes were selected in the graph, after which the navigation problem was solved for each pair of nodes and different days of the week, the start time and the time budget. The origin-destination nodes were selected so that the average travel time was from 15 to 60 minutes. A total of 6300 experiments were conducted.
Characteristics of the PC used: Intel Core i7-9700K 3.60 GHz, 64 GB RAM, graphics accelerator GeForce RTX 2080 Ti. The average running time of the algorithms is presented in the table 1.
The implementation of the algorithm using the CUDA architecture allows reducing the running time by an average of 5 times.
The running time of the algorithm depends on the time budget, which determines the number of iterations. Fig. 2 shows the dependency of the running time of the base and parallel algorithms on the time budget.
With an increase in the time budget, the gain of the parallel algorithm in running time increases.
A detailed analysis of the running time of the parallel algorithm allows us to conclude that most part of the running takes the data exchange between the host computer and the device.
In this paper, we consider the problem of finding a reliable shortest path in a stochastic network that maximizes the probability of arriving at a destination within a predetermined period of time. A parallelization strategy for the algorithm using a graphic accelerator was developed and a parallel algorithm was implemented on the CUDA software-hardware architecture.
Experimental studies conducted on a large-scale transportation network of Samara, Russia have shown that parallel implementation of the algorithm reduces the computation time by an average of 5 times.
Further research may focus on developing an algorithm with fewer data transfers between the host computer and the graphics accelerator.
ACKNOWLEDGMENT
The work was partially supported by RFBR research projects nos. 18-07-00605 A, 18-29-03135-mk.