nach oben

Complex & Intelligent Systems

Open Access 05.03.2024 | Original Article

SRNN-RSA: a new method to solving time-dependent shortest path problems based on structural recurrent neural network and ripple spreading algorithm

verfasst von: Shilin Yu, Yuantao Song

Erschienen in: Complex & Intelligent Systems

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Patentsuche

Aus

Abstract

Influenced by external factors, the speed of vehicles in the traffic network is changing all the time, which makes the traditional static shortest route unable to meet the real logistics distribution needs. Considering that the existing research on time-dependent shortest path problems (TDSPP) do not include the topological information of the traffic network, it is unable to reflect the spatial and temporal dynamic characteristics of the traffic network during the vehicle travelling process and is unable to update to the changes of the vehicle speed in real time, and poor scalability. Therefore, we used the structural RNN (SRNN) model containing topological information of the road network is used to predict time-varying speeds in the traffic road network. We proposed an SRNN-RSA framework for solving the TDSPP problem, which achieves a synergistic evolution between the real-time vehicle speed change process and the RSA solving process, and the scalability of the proposed SRNN-RSA is demonstrated and validated using different real data. Compared with other algorithms, the results show that SRNN-RSA has the lowest error with the actual situation, which can balance the solution accuracy and calculation speed and is more consistent with the real traffic road network, with better stability and expandability.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Introduction

The shortest path problem (SPP) is a vital issue in the logistics field. Previous studies usually assumed vehicle speed as a static known constant, without considering changes during the path. However, in actual logistics activities, factors such as vehicle flow, traffic accidents, and weather conditions constantly affect the speed, resulting in variations in the driving time for each section of the road network. Consequently, the traditional static shortest path approach fails to meet the requirements of real logistics distribution. Thus, there is an urgent need to address the time-dependent shortest path problem (TDSPP).

With the advancement of artificial intelligence and the availability of traffic big data, it has now become possible to predict the continuously changing trends of vehicle speeds using historical road network data. This presents a new approach and data support for studying the TDSPP.

The rest of this paper is organized as follows. It starts with discussing the related work and establishing the shortest path problem with time-dependent speed in a traffic network in “Introduction” and Related work. We present the proposed architecture of the SRNN for traffic speed prediction and the SRNN-RSA algorithmic framework for solving TDSPP in “Time-dependent shortest path problem” and “Structural recurrent neural network”. The proposed approach and results of the performance evaluation with a real dataset are given in "Ripple spreading algorithm". Finally, "Experimental validation" discusses the results.

In this section, we give a detailed overview of the relevant literature about previous works on time-dependent shortest path problems (TDSPP), structural recurrent neural network (SRNN) and the ripple spreading algorithm (RSA). This will help readers figure out the background and differentiate our work from the existing works.

TDSPP

TDSPP is one of the general problems in the real world. In the time-dependent shortest path problem, different departing times of a node lead to different arrival times of its successive node. Under the condition of time-varying speed, vehicle speed is related to time, and vehicles have different driving speeds in different time periods and different driving areas. In the past decades, this classical problem has been the subject of extensive research resulting in a large number of algorithms. Pioneering work by references has proposed a variety of algorithms for solving TDSPP (Table 1).

Table 1

Overview of TDSPP solving algorithms

Type	Algorithm	Literature
Approximation algorithm	Dijkstra	[1‐9]
	K-fastest paths algorithm	[10]
	A* algorithm	[11‐13]
	Dynamic discretization discovery algorithms	[14]
	Algorithms based on Bender decomposition	[15]
	Improved AND/OR Tree Search Algorithm (AO ∗)	[16]
	Pseudo-FPTAS	[17]
	ε-approximation algorithms	[18‐20]
	Output-sensitive algorithm	[21, 22]
	Dynamic-moment-matching-based A* algorithm	[23]
	Time-increment based dynamic programming method	[24, 25]
	Mobile crowdsourcing model	[26]
Heuristic algorithm	Simulated annealing algorithm (SA)	[27]
	Tabu search algorithm (TS)	[28]
	Ant colony algorithm (ACO)	[29]
	Single-source single-destination algorithm	[30]
	Nonconvex mixed-integer nonlinear programs	[31]
Artificial intelligence method	Fuzzy time-dependent network (FTDN)	[32] [33]
	Time-delay neural network (TDNN)	[34]
	Practical feedback neural network (PFNN)	[35]
	Q-learning	[36, 38]
	Time impulse neural network (TINN)	[37]
	Sarsa, Q-learning and double Q-learning method	[38]

SRNN

The SRNN has been proposed in [39] with the application in human motion forecasting, human activity anticipation, and driver maneuver anticipation where the connected components in a system of interest are represented as nodes in a graph. The SRNN is based on the spatio-temporal graphs which are usually used to model spatial and temporal reasoning [40]. The spatial and temporal interactions between nodes are parametrized with a factor graph [41]. As the principles described in [39] implies, the SRNN is applicable to any system that can be expressed as spatio-temporal graphs. An attention model has recently been applied to the SRNN [42] to find subsets of human crowds within which humans interact with each other, instead of using a fixed graph to represent the connection among the humans. This approach deals with only one kind of node, humans, to predict human trajectories, which resembles the problem of short-term traffic prediction.

RSA

The ripple spreading algorithm (RSA) proposed by Hu [43‐63], simulating the generation of a ripple relay race. The optimal path can be obtained only by running once. The computational process of RSA consists of an addition operation that updates the ripple radius according to the ripple speed and a comparison operation that compares the ripple radius with the link length.

Hence, it is feasible to simulate vehicle speed changes by manipulating the variation in ripple speed, leading to a simultaneous development of the real-time speed change and algorithmic solution processes. This approach resolves the time-dependent shortest path problem in evolving road networks. Previous literature has presented three common cases for ripple velocity, including fixed constants, minimum edge weights, and dynamic change functions (Table 2).

Table 2

Overview of ripple speed setting situations

Situations	Content
Fixed constants	K shortest paths [43, 48]
	K optimal solutions of project time management problem [44]
	Optimal path [45, 50, 52, 54]
	Node division problem [46]
	Linear cellular automaton model [47]
	Many-to-many path optimization problem [49]
	Vehicle pollutant emissions [51]
	Binary representation ripple expansion genetic algorithm [53]
	Spatial and temporal characteristics of infectious diseases [55]
	Multi-intelligence emergency evacuation simulation system [56]
Minimum edge weights	Multi-objective path optimization problems [57, 58]
	Multi-start-multi-endpoint SPTP [59]
	Path optimization problem [60]
	Fuzzy multi-objective path optimization problem [61]
	Potential for path length to be affected by interference [62]
Dynamic change function	Path optimization problem in dynamic disaster environment [63]

After reviewing the existing literature, the relevant research work still has the following problems and deficiencies.

Currently, most studies use speed-time dependency functions to represent the changing trend of vehicle speed, without considering the differences in traffic network topology such as road grades, traffic capacity, and congestion levels at different time periods. As a result, they fail to reflect the spatial and temporal dynamic characteristics of traffic networks during vehicle travel.

In existing studies, in most cases, the time-varying speeds are provided first, then algorithms are used to calculate the routes. This approach cannot adapt to the changing vehicle speeds in real time. Additionally, different traffic networks require different speed-time dependency functions, and existing algorithms lack scalability when applied to different types of traffic networks.

Inspired by previous research, we apply the SRNN to predict the short-term traffic speed, considering road segments as nodes that are semantically the same but use a road network topology to construct the spatiotemporal graph. Meanwhile, we take the predicted vehicle speed of each specific period as the ripple speed, applying the RSA to solve TDSPP. Moreover, we verify the scalability of the SRNN-RSA by using training and evaluation datasets that have different network topologies. The main contributions of this work are as follows:

A structural RNN (SRNN) approach for traffic speed prediction that incorporates the topological information of the road network is used, where all nodes and edges are associated with the RNNs after joint trained, which can represent well both the spatial and temporal dynamics of the traffic;

The SRNN-RSA framework for solving the TDSPP is proposed, that is, the time-varying speed predicted by the SRNN is used to represent the ripple speed, which achieves the synergistic evolution of the real-time vehicle speed change process and the RSA solution process;

More importantly, we show the SRNN-RSA framework is scalable, which is evaluated with the real dataset from Santander and Guangzhou; The SRNN model trained with a road network is capable of predicting traffic states in other road networks that have different network topologies (the number of road segments and how they are connected with one another).

Time-dependent shortest path problem

Time-dependent road network

Let G = (V, E) be a directed graph that represents a road network, where V is a set of N nodes and E = {(i, j)∣i,j ∊ V}is a set of M edges. i and j are neighboring nodes. A is the directed adjacency matrix of edge, that is, A (i, j) = 1 denotes that there is an edge connecting nodes i and j, otherwise it is 0. Each edge (i, j) ∊ E has an arrival function (AF) f: R → R_≥0 that for the given departure time t_i at node i gets the arrival time t_j at node j. Alternatively, we can define a travel time function (TTF) g(t_ij) that returns the time needed to cross the edge. A relationship between the TTF and the corresponding AF is defined as g(t_ij) = t_j − t_i = f(t_i) − t_i.

It is assumed that every f fulfills the first-in-first-out (FIFO) property at all edges: ∀ (i, j) ∊ E and ∀ t_i1 < t_i2, having t_j1 ≤ t_j2 ⟺ f (t_i1) ≤ f (t_i2) and the departure time must be smaller than the arrival time (the travel time t_da must be positive). AFs are implemented as piecewise linear functions.

Problem description

More precisely, TDSPP can be defined as minimizing the travel time over the set P_s,d of all paths in G from the source node s to the destination node d:

$$ f_{d} = \min \left\{ {f_{p} \left( t \right)\left| {p \in P_{s,d} } \right.} \right\}, $$

(1)

where f_d is the function of the earliest arrival time (minimal AF) from node s to node d and f_p is AF of the path p ∊ P_s,d. This paper deals with single source and single-destination shortest-path problem. The input data are the graph G, AF f_uv for every edge (u, v) ∊ E, the source node s and destination node d. The output is the set F of the earliest AFs from s to d: F = {f_sd∣d ∊ V}.

Structural recurrent neural network

Speed prediction problem

In this subsection, we predict traffic speeds based on historical traffic speed data and road network graph in preparation for RSA to update the ripple speed during each time cycle. Let x^t_u represent the traffic speed on road segment u at time step t. Given a sequence of traffic speed data {x^t_u} for road segments u = 1, 2 … N − 1, N at time steps t = t_c − (l − 1), t_c − (l − 2),…, t_c − [l − (l − 1)],t_c. we predict the future traffic speed x^t+1_u on each road segment where t_c denotes the current time step and l denotes the length of the historical data sequence under consideration.

Spatio-temporal graph representation

We use a spatio-temporal graph representation G_ST = (V_ST, E_S, E_T). Let G_ST denotes the spatio-temporal graph. V_ST, E_S and E_T denote the set of road segment nodes, the set of spatial edges, and the set of temporal edges, respectively.

Figure 1 represents an example spatio-temporal graph and Fig. 2 represents the spatio-temporal graph that is unrolled over time through the temporal edges in E_T, where nodes u,v,w ∊ V_ST represent road segments and the nodes are linked by edges in E_S and temporal edges in E_T. Edges are labelled with corresponding feature vectors. E_S represents the dynamics of traffic interaction between two adjacent road segments and E_T represents the dynamics of the temporal evolution of the traffic speed in road segments.

The feature of node u at time step t is x^t_u, denoting the traffic speed on the road segment. The feature vector of spatial edge (u,v) ∊ E_S at time step t is x^t_(u,v) = [x^t_u, x^t_v], which is obtained by concatenating the features of nodes u and v as a row vector. Two spatial edges linking two nodes u and v in opposite direction have different feature vectors, that is, x^t_(u,v) ≠ x^t_(v,u) = [x^t_v, x^t_u]. The feature vector of temporal edge (u,u) ∊ E_T at time step t is x^t_(u,u) = [x^t−1_u, x^t_u], which is obtained by concatenating the features of node u at the previous time step and the current time step.

SRNN model architecture

In SRNN architecture, sets V_ST, E_S and E_T are associated with RNNs. The architecture is the simplest case where the nodes, spatial edges and temporal edges are sharing the same factors, respectively.

This means the dynamics of the spatio-temporal interactions are semantically the same for all road segments, which keeps the overall parametrization compact and makes the architecture scalable and independent of the road network topology.

Figure 3 visualizes the overall architecture. For each node u, a sequence of node features {x^t_u}^tc_{t=tc−(l−1)}, is fed into the architecture. Every time each node feature enters, the SRNN is supposed to predict the node label y^t_u, which corresponds to the traffic speed at the next time step, x^t+1_u. The node feature x^t_u is concatenated with the outputs of the edgeRNNs to be fed into the nodeRNN.

In this study, we used long short-term memory networks (LSTMs) for the RNNs. The hidden state dimension of nodeRNN is 128, and that of edgeRNNs is 256. We employed embedding layers in the network that convert the input into 128-dimensional vector using a rectified linear unit (ReLU) activation function to achieve nonlinearity.

After using the forward path algorithm, the prediction error, {x^t+1_u} − {y^t_u}, is jointly backpropagated through the nodeRNN, the spatial edgeRNN, and the temporal edgeRNN involved in the forward path, employing mean squared error (MSE) as a loss function. Note that the trainable parameters of this SRNN whose size is in dependent on the size of the spatio-temporal graph. It only depends on the sizes of the RNNs.

We provide a detailed explanation of how the SRNN algorithm works in a forward path. The inputs to the RNNs are converted into fixed-length vectors by an embedding function, denoted as φ(·). The embedding function applies a linear transformation to the input with a rectified linear unit (ReLU) activation and dropout. For each node u, the following RNNs are executed to predict the node label y^t_u (Table 3 and Algorithm 1).

Table 3

Notations in the SRNN and their meanings

Notations	Meaning
C(u)	Edges connected to node u
a^t_S	Fixed-length vector
W^E_S	The weight associated with the embedding function of spatial edge
W^L_S	The weight associated with the LSTM cell of spatial edge
W^E_T	The weight associated with the embedding function of the temporal edge
W^L_T	The weight associated with the LSTM cell of the temporal edge
λ_ES	The size of the spatial edgeRNN
λ_ET	The size of the temporal edgeRNN
h^t−1_S	The hidden state of spatial edge, dimension of \|E_S\|× λ_ES
h^t−1_T	The hidden state of temporal edge, dimension of \|E_T\|× λ_ET
h^t_C(u)	The hidden state of the edge
h^t_Su	The hidden state of the average spatial influence to node u
h^t_Tu	The hidden state of the temporal-spatial influence to node u
H^t_u	The influence of the spatio-temporal edges associated with node u
W^E	The weight associated with the embedding function for node features
W^E_H	The weight associated with the embedding function for the concatenated hidden state
W^L	The weight associated with the LSTM cell
W^O	The weight of the linear layer

We employ summation to realize a fixed architecture regardless of the graph topology. This is one of the key efforts to control the number of parameters by representing the variable context with a fixed-length vector.

After using the forward path algorithm, the prediction error, {x^t+1_u} − {y^t_u}, is jointly backpropagated through the nodeRNN, the spatial edgeRNN, and the temporal edgeRNN involved in the forward path, employing mean squared error (MSE) as a loss function. Note that the trainable parameters of this SRNN are {W^E_S, W^L_S, W^E_T, W^L_T, W^E, W^E_H, W^L, W^O} whose size is in dependent on the size of the spatio-temporal graph. It only depends on the sizes of the RNNs.

Ripple spreading algorithm

Ripple spreading principle

Like other optimization algorithms, the basic idea of RSA [43‐63] is inspired by nature and tries to mimic the phenomenon of a stone falling into water and creating ripples that propagate in all directions. The core of the algorithm is based on a divisible, parallel computing Ripple Relay Race to search for optimal paths, which has excellent optimality and robustness when solving static or dynamic network problems. Nodes have three states: inactive (blue node), activated (red node), and dead (black node). States can only be changed in one direction and each node can only be activated once.

The schematic diagram of the RSA is shown in Fig. 4, using the example of finding the shortest path between node 1 and node 4. At the moment t = 1, source node 1 is in the activated state and generates ripples that spread to its neighboring nodes 2 and 3; At the moment t = 2, when the ripples generated by source node 1 reach node 2, which is in the inactive state, it converts node 2 from the inactive state to the activated state and creates new ripples. At the same time, the ripples from node 1 continue to spread to node 3; At the moment t = 3, the new ripples generated by node 2 continue to spread along the link until they reach their neighboring nodes. Meanwhile, node 1 activates node 3 and creates new ripples to spread. After node 1 activates all neighboring nodes, it will be in a dead state and no longer spread ripples; At the moment t = 4, while the ripple relay race is running continuously, more ripples gradually compete with each other until one ripple reaches and activates the destination node 4, and the remaining ripples immediately stop spreading. The shortest path from a source node to the destination node is determined by backtracking. Since path 1–3–4 has the smallest total length, 1–3–4 is the shortest path in the four-node network.

RSA operational steps

Given the actual situation of solving shortest paths in time-dependent road network, it is assumed that road network is G = (V, E). Each node is activated at most once during the entire ripple-spreading process. The relevant variables and definitions are listed (Table 4).

Table 4

Notations in the RSA and their meanings

Notations	Meaning
G	Time-dependent traffic road network
V	Node set
N	Total number of nodes
E	Edge set
M	Total number of edges
i,j	Neighboring nodes, (i,j) ∊ E
t	Time
s	Source node
d	Destination node
r_i	Ripple generated by node i
v(i,j,t)	Spreading speed of ripple r_i from node i to node j at time step t
R(i,j,t)	The cumulative ripple radius of ripple r_i from node i to node j at time step t
C(i,j)	The link value between node i and node j
N(i)	The set of all neighboring nodes of node i
E(j)	The node that activates node j; E(j) = i means node j is activated by ripple r_i of node i
S(i)	1 or 2 or 3, node i is in inactive or activated or dead state
t_re	Remaining time after a ripple reaches and activates a new node in a certain time unit
Ω_i	The cumulative objective value from source node s to node i
p*	The optimal path from source node s to destination node d

The formulae for the parameters associated with the RSA algorithm for solving the complete Pareto front for TDSPP are as follows below.

Ripple spreading speed

Assuming that the ripple spreading speed between node i and node j at time step t is denoted as v(i,j,t), and after updating the iteration time t′, the ripple-spreading speed between node i and neighboring node j at moment t + t′ are denoted as v(i,j,t + t′), so the speed matrix at moment t is obtained based on the SRNN predicted speed in different unit times.

Update the ripple spreading radius

The ripple-spreading radius is updated once in the iteration time t^´ and the spreading radius at moment t + t′ is equal to the product of the spreading radius at moment t plus the ripple spreading speed and the iteration time t′. The ripple-spreading radius for spreading from node i to node j at moment t + t′ is calculated as follows:

$$ R(i,j,t + t^{\prime}) = R\left( {i,j,t} \right) + v\left( {i,j,t + t^{\prime}} \right) \times t^{\prime}. $$

(2)

Radius of ripple spreading in the remaining time

In a certain iteration time t′, there exists a ripple that activates a node and the activated node generates new ripples to continue to spread in the remaining time. When node i activates the neighboring node j within the iteration time t′ and there is still a remaining time, the ripple spreading radius for node j to generate new ripples to spread to the neighboring node k within the remaining time t_re is calculated as follows:

$$ t_{re} = \frac{{R(i,j,t + t^{\prime}) - C(i,j)}}{{v(i,j,t + t^{\prime})}}, $$

(3)

$$ R(j,k,t + t^{\prime}) = R(j,k,t) + v(j,k,t + t^{\prime}) \times t_{re} . $$

(4)

The flow chart of the RSA is shown in Fig. 5.

Step 1 indicates generating the road network; Step 2 indicates initializing the parameters and setting an initial ripple at the source node; Step 3 indicates updating the time and predicting the speed of the road segment through the SRNN model; Step 4 indicates updating the ripple spreading radius; Step 5 determines whether a node in the road network is activated or not; Step 6 indicates updating the node status; Step 7 determines whether the destination node is activated or not; Step 8 indicates computing the ripple spreading radius for the remaining time; Step 9 indicates that a node is in a dead state when all neighboring nodes of the node are activated or are all in a dead state; Step 10 indicates obtaining the optimal path and the minimum time by backtracking.

SRNN-RSA framework

Based on the above principles of SRNN prediction speed and RSA solving for path, we combined the two parts to construct the SRNN-RSA framework, which can be used to solve TDSPP (Fig. 6).

Algorithm 2 is the pseudo-code of the SRNN-RSA framework for solving TDSPP. Input a specific traffic network, update the time once in each time interval and use SRNN to predict the real-time speed of each road segment at that moment, then use RSA to solve for the optimal path given the source and destination.

Experimental validation

Experimental data

To validate the effectiveness and scalability of the SRNN-RSA framework, this section conducts experiments using two differen-sized traffic networks and traffic speed datasets. All experiments were conducted uniformly using Python programming language, and the environment of all algorithms was a personal computer with an Intel(R) Core (TM) i5-8250U CPU @ 1.60 GHz (Table 5).

Table 5

Examples of different-scales traffic networks

Dataset	Road segment	Observation interval/min	Time step
Santander, Spain	16	15	10
Guangzhou, China	214	10	10

The first traffic speed dataset consists of 16 road segments in the central Santander city of Spain. Traffic speed measurements had been taken every 15 min. The overall dataset contains 33,504 speed readings per road segment [64, 65].

The second traffic speed dataset consists of 214 anonymous road segments (mainly consist of urban expressways and arterials) from Aug. 1, 2016 to Sep. 30, 2016 in Guangzhou, China. Traffic speed measurements had been taken every 10 min. Each road segment is observed for 61 days and there are 144 10-min time windows every day [66].

SRNN parameters

SRNN employs the mean squared error (MSE) as a loss function and Adam optimizer to minimize the sum of the MSE [67]. The traffic speed data, measured in [km/h], are scaled into the range [0, 1] before being fed into the networks.

The SRNN shows its best performance with the following hyperparameters. The major hyperparameters of the SRNN are summarized (Table 6). The SRNN is built based on the Pytorch implementation. The computational complexity of the SRNN is O(W). Note that the number of trainable parameters W is independent of the size of the road network.

Table 6

Hyperparameters of SRNN

Hyperparameters	Value
NodeRNN size, λ	64
Spatial edgeRNN size, λ_ES	64
Temporal edgeRNN size, λ_ET	64
Embedding size	32
Learning rate	0.0005
Decay rate	0.99
Dropout rate	0.5

Result analysis of Santander

We use data from the first 9 months (75%, 25, 128 speed readings per road segment) as a training set and the remaining data from the last 3 months (25%, 8376 speed readings per road segment) as an evaluation set. Given the datasets, the neural networks are supposed to give 15-min prediction of traffic speed based on 150-min data, which corresponds to a short-term prediction for the next time step based on data of previous 10-time steps (l = 10).

In the experiment, Santander consists of 16 road segments and 8 nodes. Next to each road segment is a unique ID number for the segment. Their graph representation illustrated clarifies the spatial connections between the road segments (Fig. 7) and the distribution of nodes in the road network (Fig. 8). The traffic data from the adjacent road segments are correlated, which is referred to as their spatial relationship to be learned by the SRNN.

To further validate the accuracy and stability of the SRNN model in predicting traffic speeds on each road segment, three additional different types of traffic speeds (historical average values, fitting Gaussian distribution functions and fitting Sigmoid function) were selected and analyzed compared with the actual speeds (Table 7).

Table 7

Types of traffic speed on different road segment in Santander

Road segment	Traffic speed type
Road segment	Prediction	Historical average	Fitting Gaussian functions	Fitting sigmoid functions
237	SRNN	22.53	$\mu = 22.53,\sigma = 7.48$	$v(t) = \frac{22.53}{{1 + e^{ - 1.15 \times (t + 2.78)} }}$
238		22.47	$\mu = 22.47,\sigma = 7.54$	$v(t) = \frac{22.47}{{1 + e^{ - 1.59 \times (t + 35.79)} }}$
239		15.19	$\mu = 15.19,\sigma = 10.83$	$v(t) = \frac{15.19}{{1 + e^{ - 1.18 \times (t + 20.25)} }}$
245		27.30	$\mu = 27.30,\sigma = 11.84$	$v(t) = \frac{27.30}{{1 + e^{ - 0.08 \times (t + 3.51)} }}$
241		24.16	$\mu = 24.16,\sigma = 5.13$	$v(t) = \frac{24.16}{{1 + e^{ - 0.06 \times (t + 34.66)} }}$
247		23.05	$\mu = 23.05,\sigma = 16.37$	$v(t) = \frac{23.05}{{1 + e^{ - 0.09 \times (t + 2.62)} }}$
250		27.39	$\mu = 27.39,\sigma = 11.13$	$v(t) = \frac{27.39}{{1 + e^{ - 0.03 \times (t + 32.91)} }}$
248		42.96	$\mu = 42.96,\sigma = 19.78$	$v(t) = \frac{42.96}{{1 + e^{ - 2.36 \times (t + 19.03)} }}$
246		28.81	$\mu = 28.81,\sigma = 15.03$	$v(t) = \frac{28.81}{{1 + e^{ - 0.02 \times (t + 35.52)} }}$
249		_15.31	$\mu = 15.31,\sigma = 7.73$	$v(t) = \frac{15.31}{{1 + e^{{ - 4.74 \times (t{ + }1.72)}} }}$
251		_21.34	$\mu = 21.34,\sigma = 15.19$	$v(t) = \frac{21.34}{{1 + e^{ - 116.89 \times (t + 753.49)} }}$
252		_22.50	$\mu = 22.50,\sigma = 7.46$	$v(t) = \frac{22.50}{{1 + e^{ - 643.91 \times (t + 8.91)} }}$
253		22.48	$\mu = 22.48,\sigma = 7.23$	$v(t) = \frac{22.48}{{1 + e^{ - 1.83 \times (t + 15.05)} }}$
254		22.62	$\mu = 22.62,\sigma = 7.23$	$v(t) = \frac{22.62}{{1 + e^{ - 2.32 \times (t + 0.19)} }}$
255		22.54	$\mu = 22.54,\sigma = 7.27$	$v(t) = \frac{22.54}{{1 + e^{ - 18.40 \times (t + 1804.37)} }}$
256		22.51	$\mu = 22.51,\sigma = 7.25$	$v(t) = \frac{22.51}{{1 + e^{ - 11.77 \times (t + 5.85)} }}$

Based on RSA optimality, it is necessary to further explore the effect of different speed types on the path result of TDSPP, so as to make it more accurately reflect the real traffic network.

According to Table 7, we set up RSA [43‐63] based on real speeds (Real-RSA), RSA based on predicted SRNN speeds (SRNN-RSA), RSA based on historical averages (AVG-RSA), and RSA based on fitting Gaussian distribution speeds to historical information (Gaussian-RSA), and RSA based on fitting Sigmoid functions speeds to historical information (Sigmoid-RSA). Taking Fig. 7 as an example, node 7 and node 3, node 5 and node 2 are selected as the source node and destination node, respectively. TDSPP is solved using RSA with different traffic speeds (Table 8).

Table 8

Comparison of TDSPP path results for different traffic speed types in Santander

Source	Destination	Algorithm	Path	Length/km	Time/h	Time percentage error
7	3	Real-RSA	[3‐7]	16.38	0.784
		SRNN-RSA			0.685	− 12.63%
		AVG-RSA			0.618	− 21.17%
		Gaussian-RSA			1.033	31.76%
		Sigmoid-RSA			0.674	− 14.03%
5	2	Real-RSA	[1, 2, 5]	8.165	0.351
		SRNN-RSA	[1, 2, 5]	8.165	0.364	3.704%
		AVG-RSA	[2, 4, 5]	8.187	0.237	− 32.48%
		Gaussian-RSA	[2, 4, 5]	8.187	0.266	− 24.22%
		Sigmoid-RSA	[1, 2, 5]	8.165	0.368	4.843%

Based on the data in Table 8, the following conclusions can be drawn:

When a source is node 7 and destination node is node 3, the optimal paths and distances of RSAs with different speeds are the same. However, SRNN-RSA has the lowest timing percentage errors and is closest to Real-RSA, which always outperforms the other situations.

When a source is node 5 and destination is node 2, the optimal paths and distances of SRNN-RSA and Sigmoid-RSA are the same as Real-RSA. The path selection of AVG-RSA and Gaussian-RSA to reach node 2 through node 4 results in length of 0.022 more than Real-RSA. In addition, SRNN-RSA has the lowest timing percentage error, which is superior in terms of path quality and errors.

Considering the path results and timing percentage errors together, SRNN-RSA performs well in both examples and is closer to Real-RSA. This suggests that SRNN-RSA may have higher accuracy and efficiency in the path planning task of solving TDSPP, which is more consistent with the actual transportation situation.

To verify the superiority of the SRNN-RSA framework in solving TDSPP, the SRNN-RSA is compared with Dijkstra's algorithm [1‐9], Branch and Bound (BB) [68], Genetic Algorithm (GA) [69], Simulated Annealing Algorithms (SA) [27], Ant Colony Algorithm (ACO) [29], and Q-learning [36, 38]. The above seven algorithms are applied to solve the optimal path respectively and each group of experiments is carried out 30 times (Table 9).

Table 9

Comparison of TDSPP path results for different algorithms in Santander

	Path	Length/km	Time/h	Accuracy rate	Running time/s
SRNN-RSA	[3‐7]	16.38	0.685	100%	0.26158
Dijkstra			1.113		1.56172
Branch and bound			0.654		1.37214
GA			0.955		1.08768
SA			1.402		1.14655
ACO			1.337		1.72275
Q-learning			1.409		0.91956

When analyzing the data in Table 9, in a small transport network of Santander, the following conclusions can be drawn:

In terms of optimal paths and path lengths, SRNN-RSA's search results are consistent with other algorithms;

In terms of vehicle travel time, the result of SRNN-RSA (0.685) is closer to that of Real-RSA (0.784), which is better than other algorithms and is most consistent with the TDSPP result under the actual traffic network;

In terms of the accuracy rate, SRNN-RSA always maintains a success rate of 100%.

In terms of the running time of the algorithms, SRNN-RSA is significantly lower than the other six algorithms. Exact algorithms such as Dijkstra and Branch and Bound require more time to ensure accuracy, and GA, SA, ACO and Q-Learning are probability-based stochastic algorithms that fall into the local optimum to varying degrees and require more running time to ensure accuracy ensure optimal solution.

SRNN-RSA can balance the solution accuracy and calculation speed.

Result analysis of Guangzhou

We use data from the first 75% readings per road segment as a training set and the remaining data as an evaluation set. Given the datasets, the neural networks are supposed to give 10-min prediction of traffic speed based on 100-min data, which corresponds to a short-term prediction for the next time step based on data of previous 10-time steps (l = 10).

In a similar way as in the small Santander network, we select different speed types of RSAs such as Real-RSA, SRNN-RSA, AVG-RSA, Gaussian-RSA and Sigmoid-RSA in the Guangzhou network to further explore the impact of different RSAs on the TDSPP path results in large-scale networks. Node 59 and node 117, node 9 and node 204 are selected as source and destination nodes, respectively. TDSPP with different traffic speeds is solved using RSA (Table 10).

Table 10

Comparison of TDSPP path results for different traffic speed types in Guangzhou

Source	Destination	Algorithm	Path	Length/km	Time/h	Time percentage error
59	117	Real-RSA	[59, 178, 172, 8, 117]	37.01	1.414
		SRNN-RSA	[59, 178, 172, 8, 117]	37.01	1.382	− 2.26%
		AVG-RSA	[59, 151, 22, 125, 117]	43.23	1.058	− 25.18%
		Gaussian-RSA	[59, 119, 47, 33, 117]	47.01	1.362	− 3.68%
		Sigmoid-RSA	[59, 153, 170, 16, 117]	41.63	1.487	5.16%
9	204	Real-RSA	[9, 31, 12, 89, 204]	65.42	2.012
		SRNN-RSA	[9, 174, 81, 77, 204]	67.24	2.265	12.57%
		AVG-RSA	[9, 147, 54, 37, 204]	75.89	1.757	− 12.67%
		Gaussian-RSA	[9, 142, 205, 151, 204]	88.09	2.292	13.92%
		Sigmoid-RSA	[9, 113, 66, 175, 204]	85.33	2.668	32.60%

Based on the data in Table 10, the following conclusions can be drawn:

When a source is node 59 and the destination is node 117, the optimal path and distance of SRNN-RSA are the same as Real-RSA. In addition, SRNN-RSA has the lowest percentage timing error (− 2.26%), which is better than other cases in terms of path quality and error.

When a source is node 9 and the destination is node 204, the large-scale node network leads to errors in all cases with Real-RSA. However, SRNN-RSA has the lowest percentage timing error (12.57%). Considering the path results and the percentage timing error, SRNN-RSA has a clear advantage even in large cases, which corresponds to the actual traffic situation.

In the large-scale nodes network, SRNN-RSA is also used to compare with the other six algorithms. The results of the algorithms are shown in Table 11.

Table 11

Comparison of TDSPP path results for different algorithms in Guangzhou

	Path	Length/km	Time/h	Accuracy rate	Running time/s
SRNN-RSA	[59, 178, 172, 8, 117]	37.01	1.382	100%	1.84582
Dijkstra			1.694	86%	12.44784
BB			2.122	83%	15.59052
GA	[59, 24, 15, 156, 117]	66.51	2.380	0	5.62203
SA	[59, 76, 30, 131, 117]	54.59	2.021	0	3.83403
ACO	[59, 178, 172, 8, 117]	37.05	1.998	66.67%	3.39089
Q-learning	[59, 32, 193, 50, 117]	50.24	2.099	0	6.35897

By analyzing the data in Table 11, the following conclusions can be drawn in a large-scale traffic network:

In terms of optimal paths and path lengths, the search results of RSA are consistent with the exact algorithms such as Dijkstra and BB.

In terms of vehicle travelling time, the results of SRNN-RSA are closer to those of Real-RSA (1.414), which is better than other algorithms, and is the most consistent with the results of TDSPP under the actual traffic network.

In terms of success rate, SRNN-RSA always maintains 100% success rate, Dijkstra uses speeds obeying a Gaussian distribution, whose randomness makes the success rate of Dijkstra's path results less than 100%, and BB's branching optimization process makes the path results have the possibility of bias, and algorithms such as GA, SA, ACO and Q-learning are based on probabilistic optimization and have a lower success rate in large-scale networks.

In terms of the running time of the algorithms, the running time of SRNN-RSA is significantly lower than that of the other six algorithms, which can take into account the solution accuracy and calculation speed.

In summary, compared with other algorithms, RSA comprehensively traverses the search solution space, and the search mechanism better balances the algorithm's breadth-mining and depth-mining capabilities, which prevents the algorithm from entering the blind and disorderly search state, thus reducing the algorithm's computation time, guaranteeing the accuracy of the solution, and ultimately obtaining better search results.

Ablation study

To verify the validity of the SRNN model in the SRNN-RSA framework proposed in this paper, the standard RSA is constructed as the Baseline benchmark in this section. SRNN-RSA denotes that the SRNN model is used to predict the speeds of each road segment, which will be used as the input to solve the TDSPP with RSA to obtain the path results; RSA indicates that the TSDPP is solved by setting the relevant speed parameters only according to the basic principles of the standard RSA algorithm (Table 12).

Table 12

Experiments on the validity of the SRNN prediction module

Dataset	Source	Destination	Algorithm	Path	Length/km	Time/h
Santander	7	3	SRNN-RSA	[3–7]	16.38	0.685
	7	3	RSA	[3–7]	16.38	4.036
	5	2	SRNN-RSA	[1, 2, 5]	8.165	0.364
	5	2	RSA	[1, 2, 5]	8.165	2.012
Guangzhou	59	117	SRNN-RSA	[59, 178, 172, 8, 117]	37.01	1.414
	59	117	RSA	[59, 210, 141, 155, 117]	45.76	8.252
	9	204	SRNN-RSA	[9, 174, 81, 77, 204]	67.24	2.265
	9	204	RSA	[9, 117, 166, 156, 104]	79.05	14.277

The experimental findings demonstrate that the TSDPP solution performs better when the SRNN prediction module is added, outperforming the baseline when standard RSA is used alone.

In the small-scale example of Santander, the addition of the SRNN prediction module improves the travelling time but has no influence on the path results or path lengths. Standard RSA will not take into account the real traffic speeds because it bases its determination of the speeds on the example's network structure. This leads to a high bias and poor timing accuracy. With the help of the SRNN module, standard RSA can now account for the traffic network's temporal and geographical dynamics, improving timing accuracy and making it more in line with actual traffic patterns.

In the large-scale example of Guangzhou, the addition of the SRNN prediction module positively improves standard RSA, increasing the accuracy of path length by 19.12% and 14.94%, and the accuracy of travel time by 82.86% and 84.14%. It also shows that the benefit of the SRNN prediction module becomes more noticeable with increasing instance size.

The above ablation experiments prove that the SRNN prediction module proposed in this paper is effective. After adding the SRNN prediction module, the performance of RSA is greatly improved and the path results of solving TDSPP are more in line with the actual situation.

Conclusion

In this paper, we used an SRNN architecture that learns the spatial and temporal relationship between the traffic data represented as a spatio-temporal graph, which contains topological information of the road network to predict time-varying speeds in traffic road networks. Based on this, we proposed an SRNN-RSA framework for solving the TDSPP problem, which achieves a synergistic evolution between the real-time process of vehicle speed changes and the RSA-solving process.

In the future, the proposed SRNN-RSA framework can be integrated into traffic management systems or route planning systems to provide accurate predictions of future traffic states in an efficient and scalable manner.

Declarations

Conflict of interest

The authors have no conflict of interest regarding this paper.

Not applicable.

Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Sperb RC (2010) Solving time-dependent shortest path problems in a database context. University of Twente

Hu L, Peng B, Jiang Y et al (2011) Model and algorithm for continuous time-varying shortest path problem. In: ICTE 2011, pp 271–276

Kim J, Han WS, Oh J et al (2014) Processing time-dependent shortest path queries without pre-computed speed information on road networks. Inf Sci 255:135–154MathSciNetCrossRef

Sung K, Bell MGH, Seong M et al (2000) Shortest paths in a network with time-dependent flow speeds. Eur J Oper Res 121(1):32–39MathSciNetCrossRef

Dell’Amico M, Iori M, Pretolani D (2008) Shortest paths in piecewise continuous time-dependent networks. Oper Res Lett 36(6):688–691MathSciNetCrossRef

Yıldırım UM, Çatay B (2020) An enhanced network-consistent travel speed generation scheme on time-dependent shortest path and routing problems. IEEE Trans Intell Transp Syst 23(2):873–884CrossRef

Kolovský F, Ježek J, Kolingerová I (2019) The ε-approximation of the time-dependent shortest path problem solution for all departure times. ISPRS Int J Geo Inf 8(12):538CrossRef

Rozas H, Muñoz-Carpintero D, Saéz D et al (2021) Solving in real-time the dynamic and stochastic shortest path problem for electric vehicles by a prognostic decision making strategy. Expert Syst Appl 184:115489CrossRef

Wen L, Çatay B, Eglese R (2014) Finding a minimum cost path between a pair of nodes in a time-varying road network with a congestion charge. Eur J Oper Res 236(3):915–923MathSciNetCrossRef

10.

Zhang Z, Li M (2023) Finding paths with least expected time in stochastic time-varying networks considering uncertainty of prediction information. IEEE Trans Intell Transport Syst

11.

Zhao L, Ohshima T, Nagamochi H (2008) A* algorithm for the time-dependent shortest path problem. In: WAAC08: the 11th Japan–Korea joint workshop on algorithms and computation, p 10

12.

Ohshima T, Eumthurapojn P, Zhao L et al (2011) An A* algorithm framework for the point-to-point time-dependent shortest path problem. In: Computational geometry, graphs and applications: 9th international conference, CGGA 2010, Dalian, China, November 3–6, 2010, revised selected papers. Springer, Berlin, pp 154–163

13.

Ruß M, Gust G, Neumann D (2021) The constrained reliable shortest path problem in stochastic time-dependent networks. Oper Res 69(3):709–726MathSciNetCrossRef

14.

He EY, Boland N, Nemhauser G et al (2022) Dynamic discretization discovery algorithms for time-dependent shortest path problems. INFORMS J Comput 34(2):1086–1114MathSciNetCrossRef

15.

Conde E, Leal M, Puerto J (2018) A minmax regret version of the time-dependent shortest path problem. Eur J Oper Res 270(3):968–981MathSciNetCrossRef

16.

Xie Z, He YR, Jiang Y et al (2021) Improved and/or tree search algorithm in analysis of stochastic and time-dependent shortest path problem. Sci Prog 2021:1–19

17.

Omer J, Poss M (2019) Time-dependent shortest paths with discounted waits. Networks 74(3):287–301MathSciNetCrossRef

18.

Omran M, Sack JR (2014) Improved approximation for time-dependent shortest paths. In: International computing and combinatorics conference. Springer International Publishing, Cham, pp 453–464

19.

Foschini L, Hershberger J, Suri S (2011) On the complexity of time-dependent shortest paths. In: Proceedings of the 22nd annual ACM-SIAM symposium on discrete algorithms, pp 327–341

20.

Foschini L, Hershberger J, Suri S (2012) On the complexity of time-dependent shortest paths. Algorithmica 1–23

21.

Dehne F, Omran MT, Sack J-R (2009) Shortest paths in time-dependent FIFO networks using edge load forecasts. In: Proceedings of the 2nd international workshop on computational transportation science, pp 1–6

22.

Dehne F, Omran MT, Sack J-R (2012) Shortest paths in time-dependent FIFO networks. Algorithmica 62(1–2):416–435MathSciNetCrossRef

23.

Chen P, Tong R, Yu B et al (2020) Reliable shortest path finding in stochastic time-dependent road network with spatial-temporal link correlations: a case study from Beijing. Expert Syst Appl 147:113192CrossRef

24.

Poon MH, Wong SC, Tong CO (2004) A dynamic schedule-based model for congested transit networks. Transport Res Part B Methodol 38(4):343–368CrossRef

25.

Qian J, Eglese R (2014) Finding least fuel emission paths in a network with time-varying speeds. Networks 63(1):96–106MathSciNetCrossRef

26.

Halim Z, Khan A, Sulaiman M et al (2022) On finding optimum commuting path in a road network: a computational approach for smart city traveling. Trans Emerg Telecommun Technol 33(2):e3786CrossRef

27.

Jaballah R, Veenstra M, Coelho LC et al (2021) The time-dependent shortest path and vehicle routing problem. Inf Syst Oper Res 59(4):592–622MathSciNet

28.

Gmira M, Gendreau M, Lodi A et al (2021) Tabu search for the time-dependent vehicle routing problem with time windows on a road network. Eur J Oper Res 288(1):129–140MathSciNetCrossRef

29.

Fa-mei HE, Yi-na XU, Xu-ren W et al (2019) An improved ant colony algorithm for solving time-dependent road network path planning problem. In: 2019 6th international conference on information science and control engineering (ICISCE). IEEE, 2019, pp 126–130

30.

Idri A, Oukarfi M, Boulmakoul A et al (2017) A new time-dependent shortest path algorithm for multimodal transportation network. Procedia Comput Sci 109:692–697CrossRef

31.

Nannicini G (2010) Point-to-point shortest paths on dynamic time-dependent road networks. 4OR 8:327–330

32.

Huang W, Wang J (2016) The shortest path problem on a time-dependent network with mixed uncertainty of randomness and fuzziness. IEEE Trans Intell Transp Syst 17(11):3194–3204CrossRef

33.

Huang W, Ding L (2012) The shortest path problem on a fuzzy time-dependent network. IEEE Trans Commun 60(11):3376–3385CrossRef

34.

Huang W, Yan C, Wang J et al (2017) A time-delay neural network for solving time-dependent shortest path problem. Neural Netw 90:21–28CrossRefPubMed

35.

Hong HE, Daming ZHU, Shaohan MA (2004) A new algorithm for the shortest paths computation by neural networks on time-dependent networks. J Fudan (Nat Sci Ed) 43(5):714–716

36.

Cao Z, Guo H, Song W et al (2020) Using reinforcement learning to minimize the probability of delay occurrence in transportation. IEEE Trans Veh Technol 69(3):2424–2436CrossRef

37.

Huang W, Wang Y, Zhu L (2022) A time impulse neural network framework for solving the minimum path pair problems of the time-varying network. IEEE Trans Knowl Data Eng

38.

Zhang K, Li M, Shan Y (2021) Reinforcement learning for shortest path problem on stochastic time-dependent road network. In: CICTP 2021. 2021, pp 410–417

39.

Jain A, Zamir A R, Savarese S et al (2016) Structural-rnn: Deep learning on spatio-temporal graphs. In: Proceedings of the ieee conference on computer vision and pattern recognition. 2016, pp 5308–5317

40.

Brendel W, Todorovic S (2011) Learning spatiotemporal graphs of human activities. In: 2011 international conference on computer vision. IEEE, 2011, pp 778–785

41.

Kschischang FR, Frey BJ, Loeliger HA (2001) Factor graphs and the sum-product algorithm. IEEE Trans Inf Theory 47(2):498–519MathSciNetCrossRef

42.

Vemula A, Muelling K, Oh J (2018) Social attention: Modeling attention in human crowds. In: 2018 IEEE international conference on robotics and automation (ICRA). IEEE, 2018, pp 4601–4607

43.

Guo Rongmei Hu, Xiaobing. (2020) An effective method to find the k shortest paths in a generalized time-window network. Acta Electron Sin 48(7):1387

44.

Cheng-yue LIU, Jia-ru LI, Xiao-bing HU (2020) A new method to calculate the k best solutions to the project time management problem. Syst Eng 38(06):118–128

45.

Zhang MK, Hu XB, Wang JA (2019) Research on evacuation route from high-rise building under real effect of fire spread. China Saf Sci J 29(03)

46.

Liu H, Liu Q, Zhang L, Ding N (2018) A fast selection method of division node in large power grid. Power Syst Prot Control 46(09):116–121

47.

Zhang Y, Zhang G, Li H, Hu X (2022) Research on evacuation model of cellular automata based on ripple spreading algorithm. J Saf Environ 1–12

48.

Chen XL,Yang J, Luo C et al (2015) A high-speed searching method for power flow transferring paths in large power grid. Power Syst Technol 39(4):1045–1052

49.

Xiaobing Hu, Xuemei Z, Hang Z, Yiming Ma (2022) A method for improved air luggage check-in service based on optimized urban mobile stations. J Transport Inf Saf 40(03):136145

50.

Xu W, Li J (2020) A fissile ripple spreading algorithm to solve timedependent vehicle routing problem via coevolutionary path optimization. J Adv Transport 2020

51.

Zhang M, Hu X, Wang J (2019) A method to assess and reduce pollutant emissions of logistic transportation under adverse weather. Sustainability 11(21):5961CrossRef

52.

Zhang MK, Hu XB, Liao JQ (2016) A new path optimization method in dynamic adverse weathers. In: 2016 12th international conference on natural computation, fuzzy systems and knowledge discovery (ICNCFSKD). IEEE, pp 370–375

53.

Hu XB, Leeson MS, Hines EL et al (2010) A review on ripple-spreading genetic algorithms for combinatorial optimization problems. In: 9th IEEE international conference on cognitive informatics (ICCI’10). IEEE, 2010, pp 441–448

54.

Zhou H, Hu XB (2020) A ripple spreading algorithm for free-flight route optimization in dynamical airspace. In: 2020 IEEE symposium series on computational intelligence (SSCI). IEEE, 2020, pp 281–288

55.

Liao JQ, Hu XB, Wang M et al (2012) A ripple-spreading network model for the study of infectious disease transmission. In: 2012 5th international conference IEEE, 2012, p 10041010

56.

Yingfei Z, Gongpeng Z, Ruixin W et al (2020) A simulation method of personnel evacuation management based on mulit-agent models. In: 2020 IEEE symposium series on computational intelligence (SSCI). IEEE, 2020, pp 1634–1639

57.

Yu S, Song Y (2023) Ripple spreading algorithm: a new method for solving multi-objective shortest path problems with mixed time windows. Complex Intell Syst. https://doi.org/10.1007/s40747-023-01260-8CrossRef

58.

Ma Y, Hu X, Zhou H (2022) Efficient ripple-spreading algorithm for shortest path tour problem. Appl Res Comput 1–7

59.

Hu XB, Wang M, Leeson MS et al (2016) Deterministic agent-based path optimization by mimicking the spreading of ripples. Evol Comput 24(2):319–346CrossRefPubMed

60.

Ma YM, Hu XB, Zhou H (2022) A deterministic and nature-inspired algorithm for the fuzzy multi-objective path optimization problem. Complex Intell Syst 1–13

61.

Hu XB, Zhang MK, Liao JQ (2016) A ripple-spreading algorithm for network performance assessment. In: 2016 IEEE symposium series on computational intelligence (SSCI). IEEE, 2016, pp 1–8

62.

Hu XB, Wang M, Sun Q et al (2013) A ripple-spreading algorithm for route optimization. In: 2013 IEEE symposium on foundations of computational intelligence (FOCI). IEEE, p 5259

63.

Hu XB, Meng XZ (2022) Many-to-many path planning method for material distribution under dynamic disaster environment. Comput Eng Appl 58(08):297–306

64.

SETA EU Project (2016) A ubiquitous data and service ecosystem for better metropolitan mobility, Horizon 2020 Programme. http://setamobility.weebly.com/

65.

Kim Y, Wang P, Zhu Y et al (2018) A capsule network for traffic speed prediction in complex road networks. In: 2018 sensor data fusion: trends, solutions, applications (SDF). IEEE, pp 1–6

66.

OpenITS Org (2021) OpenData V12.0-large-scale traffic speed data set. https://www.openits.cn/openData2/792.jhtml. Accessed 3 Dec 2023

67.

Kingma DP, Ba J (2014) Adam: a method for stochastic optimization. arXiv:1412.6980

68.

Lawler EL, Wood DE (1966) Branch-and-bound methods: a survey. Oper Res 14(4):699–719MathSciNetCrossRef

69.

Katoch S, Chauhan SS, Kumar V (2021) A review on genetic algorithm: past, present, and future. Multim Tools Appl 80:8091–8126CrossRef

Titel: SRNN-RSA: a new method to solving time-dependent shortest path problems based on structural recurrent neural network and ripple spreading algorithm
verfasst von: Shilin Yu
Yuantao Song
Publikationsdatum: 05.03.2024
Verlag: Springer International Publishing
Erschienen in: Complex & Intelligent Systems
Print ISSN: 2199-4536
Elektronische ISSN: 2198-6053
DOI: https://doi.org/10.1007/s40747-024-01351-0

Springer Professional

Abstract

Publisher's Note

Introduction

Related work

TDSPP

SRNN

RSA

Time-dependent shortest path problem

Time-dependent road network

Problem description

Structural recurrent neural network

Speed prediction problem

Spatio-temporal graph representation

SRNN model architecture

Ripple spreading algorithm

Ripple spreading principle

RSA operational steps

SRNN-RSA framework

Experimental validation

Experimental data

SRNN parameters

Result analysis of Santander

Result analysis of Guangzhou

Ablation study

Conclusion

Declarations

Conflict of interest

Ethics approval and consent to participate

Publisher's Note