# The Path Optimization Algorithm of Car Navigation System considering Node Attributes under Time-Invariant Network

Authors: Dan-dan Zhu; Jun-qing Sun
Journal: Mobile Information Systems
 (2021)

---

## Abstract

Vehicle path planning plays a key role in the car navigation system. In actual urban traffic, the time spent at intersections accounts for a large proportion of the total time and cannot be ignored. Therefore, studying the shortest path planning problem considering node attributes has important practical significance. In this article, we study the vehicle path planning problem in time-invariant networks, with the minimum travel time from the starting node to the destination node as the optimization goal (including node time cost). Based on the characteristics of the problem, we construct the mathematical model. We propose a Reverse Order Labeling Algorithm (ROLA) based on the traditional Dijkstra algorithm to solve the problem; the correctness of the proposed algorithm is proved theoretically, and we analyse and give the time complexity of the ROLA and design a calculation example to verify the effectiveness of the algorithm. Finally, through extensive simulation experiments, we compare the performance of the proposed ROLA with several other existing algorithms. The experimental results show that the proposed algorithm has good stability and high efficiency.


---

## Body

## 1. Introduction

With rapid economic and social development and accelerated urbanization, exhaust pollution, urban congestion, and an increasing number of traffic accidents have become serious urban problems, especially in big cities. Therefore, in order to increase road traffic efficiency, it is necessary to conduct research on the intelligent transportation system (ITS). ITS refers to a comprehensive transportation system formed by integrating modern information technology, sensor technology communication technology, and other high-tech on the basis of a more complete traditional transportation management systems [1]. Its biggest feature is the integration of intelligent systems with the traditional transportation industry, the use of modern communication technology, and intelligent analysis methods such as big data, cloud computing, and artificial intelligence to realize the real-time perception of existing traffic conditions, synchronize optimization, and adjustments. The current situation of urban road congestion is improved, the efficiency of urban road use is maximized, and people’s travel safety is ensured [2, 3].The United States began to focus on the research of Intelligent Transportation Systems in the 1960s [4]. In the following decades of development, the United States created the electronic route guidance system and carried out road system research. In 1991, the Intelligent Transportation Systems Association of America formally proposed the concept of Intelligent Transportation Systems (ITS). Subsequently, on the basis of the vehicle-road integration project, an in-depth study of the vehicle-road collaborative control was carried out [5]. The development of ITS in Japan began in the 1970s, during which a dynamic route guidance system experiment was carried out. Japan established the Japan Road Traffic Vehicle Intelligent Promotion Association in 1994 to promote ITS. In recent years, Japan has mainly carried out research on vehicle-road coordination, strengthened the application of wireless communication technology in the field of ITS, and carried out research on collaborative safety control technology for traffic objects [6]. Europe began to study road traffic communication technology in the 1970s. In the mid-to-late 1980s, Europe carried out research on the vehicle safety road structure plan and the efficient and safe transportation system plan. The European Road Traffic Communication Technology Application Promotion Organization was established in 1991 to promote cooperation between the European Union and related companies to jointly promote the development of ITS in Europe [7].Dynamic route guidance system (DRGS), as an indispensable part of the ITS, is one of the more direct and effective means to improve urban traffic conditions [8]. The system uses the global positioning system (GPS), computers, electronic traffic maps, advanced communication technologies to obtain a large number of timely, and accurate traffic network data [9]. Then, the optimal driving path is given between the two fixed nodes in the access network is submitted to the user and displayed by the on-board equipment. The characteristic of this system is based on real-time traffic data, fully taking into account the three elements of traffic, people, vehicles, and roads [10]. While maximizing the “benefits” of drivers, it finally realizes the reasonable distribution of traffic flow in the urban traffic road network. The key to DRGS is the optimal path selection problem, and it is also one of the hot topics currently studied [11].In the research of path planning model and optimization strategy, the model is mainly constructed with the path geometric mileage or travel time as the target value. Many methods have been proposed and applied in this field. According to the different principles of solving the shortest path, the algorithm is divided into the traditional graph theory, shortest path algorithm and intelligent optimization algorithm [12]. The former includes Dijkstra [13, 14], A∗ algorithm [15], Floyd algorithm [16], and hierarchical heuristic search algorithm; the intelligent optimization algorithms include simulated annealing algorithm (SA), particle swarm optimization algorithm (PSO), neural network algorithm (NNA), ant colony optimization (ACO), genetic algorithm (GA), and machine learning algorithm. In the next part, we will briefly review the existing path optimization algorithms.


## 2. Related Works

The shortest path problem (SP) is the core content of graph theory and network optimization research. Many real-world problems can be converted into SP problems [4]. The effective combination of classic graph theory and continuously developed computer data structures and algorithms has resulted in the emergence of new optimal path algorithms [17]. The most commonly used traditional shortest path algorithms are Dijkstra algorithm and A∗ algorithm. In 1959, E. W. Dijkstra first proposed an algorithm for solving the shortest path between two points in the weighted graph, namely, the Dijkstra algorithm, which can also be used to solve the shortest distance from a specified vertex to the remaining vertices in the graph path. The complexity of the algorithm can be expressed as On2 [18]. In order to solve the problem of automated guided vehicle (AGV) access path planning in the smart garage and overcome the shortcomings of the traditional Dijkstra algorithm such as high time complexity, large search range, and low search efficiency, Liu et al. proposed an improved Dijkstra algorithm [19]. Hart et al. proposed the A∗ algorithm in 1968, and the literature [20] also gave the main idea of the A∗ algorithm. This algorithm is widely used in artificial intelligence to complete the search on the map and is widely used in the game scene to find the shortest path between two points. The core idea of the algorithm is to evaluate the quality of each branch in the search process through the function value and then to select the best branch to search. Song and Wang combined particle swarm algorithm and A∗ algorithm to solve the robot path planning problem [21].Intelligent algorithms to solve path planning problems have also been extensively studied by scholars. Liu et al. studied the path optimization problem of intelligent driving vehicles and combined the prior reinforcement learning technology with the A∗ algorithm to search for the shortest path [4]. Meng et al. studied the serial color traveling salesman path planning problem (SCTSP) and proposed a population-based incremental learning algorithm with a 2-opt local search [22]. Xu et al. studied the path optimization problem of the general colored traveling salesman problem (GCTSP) and proposed a Delaunay-triangulation-based variable neighborhood search algorithm to solve the problem [23]. Ge et al. studied the ant colony algorithm and its application in path planning. Aiming at the problem of common ant colony optimization that is easy to fall into a dead end, they proposed an improved ant colony algorithm with the return; according to the characteristics of the urban road network, design A∗ dynamic limited area search strategy; finally, combined with the A∗ algorithm, a hierarchical ant colony algorithm based on dynamic area planning is proposed to realize the complementary advantages of the two algorithms [24]. In order to achieve an efficient solution to the vehicle path optimization problem with capacity constraints, Shang et al. proposed an improved simulated annealing algorithm with tempering operation. The characteristics of path optimization under multiple constraints are analyzed, and a simulated annealing framework with simple structure and relatively independent functional modules is constructed, which can facilitate the coupling and nesting of related constraints and their algorithms. On this basis, the acceptance rule of the better solution in the iterative process is changed, and the tempering operation is introduced to achieve a balance between global search and local search; a mandatory random neighborhood transformation strategy is designed to improve quality of new solutions under multiple constraints [25]. Mohammed et al. solved vehicle routing planning problems by using the improved genetic algorithm for optimal solutions [26]. Zhi proposed an improved genetic algorithm and particle swarm algorithm to solve the optimization problem of vehicle path planning with constraints [27]. Kao et al. proposed a hybrid algorithm based on ACO and PSO for capacitated vehicle routing problems [28]. Ma et al. proposed an improved PSO for simultaneous pickup and delivery vehicle routing problems with time windows under a fuzzy random environment [29]. Zhang et al. proposed an evolutionary scatter search PSO algorithm (ESS-PSO) to solve the vehicle routing problem with time windows (VRPTW) with the objective of minimizing the total travel distance [30]. Wang and Lu proposed a competition-based memetic algorithm (MAC) to solve the capable green vehicle routing problem (CGVRP) [31].In the route planning of the existing driving navigation system, generally, only the travel distance and time spent on the road section of the vehicle are considered, and the intersection is regarded as a node. The waiting time of the vehicle at the intersection and the time cost of passing the intersection are generally considered either it is ignored or it is attributed to the corresponding weight of the road segment connecting the intersection. However, in urban traffic, because the road section physical distance between two intersections is relatively short, the time for vehicles to pass the road is short. And because of the influence of traffic lights and traffic regulations on the speed of vehicles passing through the intersection, the time spent by the vehicle at the intersection is not negligible relative to the time spent on the road segment. When vehicles go straight, turn left, right, orU-turn through the intersection, the waiting and passing time consumption is also different. So it is impossible to attribute the time spent waiting at the intersection to the weight of the road arc. Therefore, in the route planning of urban traffic, not only the travel time of the driving vehicle on the road but also the time consumed by the vehicle waiting and passing through the intersection must be considered [32].In this paper, we study the minimum-time path planning problem taking into account the node attribute (weight or time cost) in a deterministic FIFO network. We describe the problem in Section3, establish a mathematical model in Section 4, and present our optimization algorithm in Section 5. Extensive simulation comparison experiments are carried out on the proposed algorithm with the other four common algorithms in Section 6. Our conclusions are summarized in Section 7.


## 3. Problem Description

### 3.1. Problem Definition

The focus of this study is the path-planning problem in a time-invariant deterministic network, taking into account the intersection attribute (time cost). In such a network, we assumed that the travel time along an arc and the waiting time at a node that have different subsequent arcs do not vary with time. We use an abstract road network diagram to illustrate the time consumption of vehicles in the actual road network. As shown in Figure1, the node represents the intersection, the edge represents the road segment, A is the starting point, and G is the destination. The numbers on the edges represent the travel time of the vehicles on the road represented by this edge. The numbers on the nodes, respectively, represent the waiting time for the vehicle to choose the next different edge at the intersection. If only considering the edge and not the time consumption at the node, the shortest travel time path from point A to point GG is A⟶B⟶E⟶G; the time cost is 1 + 2 + 1 = 4. When the waiting time of the node (intersection) is taken into consideration, in fact, the time cost for the vehicle to walk on the path A⟶B⟶E⟶G is 1 + 3 + 2 + 3 + 1 = 101 + 3 + 2 + 3 + 1 = 10; but when the vehicle travels on the path A⟶C⟶F⟶G, the time cost is 2 + 1 + 1 + 1 + 2 = 72 + 1 + 1 + 1 + 2 = 7; so in fact, the shortest travel time path when considering the waiting time at the intersection is A⟶C⟶F⟶G, which is more in line with the preference of the driver.Figure 1
Network graph considering node cost.


### 3.2. Problem Hypothesis

The directed graph studied in this paper is a time-invariant deterministic “first-in, first-out” (FIFO) network. Before proceeding further, we make the following assumptions:(1)
A vehicle travels on a road network in a certain area of a city at a certain time period. During this time period, the time required for a vehicle to drive on any section of the road network does not depend on the time of departure.(2)
The time required for vehicles to pass through the intersection by turning left, right, straight, orU-turn at any intersection during this period is different, but it does not depend on the time of arrival at the intersection.(3)
The time required for a vehicle to travel on any road section during this period is a fixed constant.(4)
The waiting time and the time required for a vehicle to pass through the intersection in any way (turn left, turn right, go straight, orU-turn) at any intersection is also a fixed constant.


## 3.1. Problem Definition

The focus of this study is the path-planning problem in a time-invariant deterministic network, taking into account the intersection attribute (time cost). In such a network, we assumed that the travel time along an arc and the waiting time at a node that have different subsequent arcs do not vary with time. We use an abstract road network diagram to illustrate the time consumption of vehicles in the actual road network. As shown in Figure1, the node represents the intersection, the edge represents the road segment, A is the starting point, and G is the destination. The numbers on the edges represent the travel time of the vehicles on the road represented by this edge. The numbers on the nodes, respectively, represent the waiting time for the vehicle to choose the next different edge at the intersection. If only considering the edge and not the time consumption at the node, the shortest travel time path from point A to point GG is A⟶B⟶E⟶G; the time cost is 1 + 2 + 1 = 4. When the waiting time of the node (intersection) is taken into consideration, in fact, the time cost for the vehicle to walk on the path A⟶B⟶E⟶G is 1 + 3 + 2 + 3 + 1 = 101 + 3 + 2 + 3 + 1 = 10; but when the vehicle travels on the path A⟶C⟶F⟶G, the time cost is 2 + 1 + 1 + 1 + 2 = 72 + 1 + 1 + 1 + 2 = 7; so in fact, the shortest travel time path when considering the waiting time at the intersection is A⟶C⟶F⟶G, which is more in line with the preference of the driver.Figure 1
Network graph considering node cost.


## 3.2. Problem Hypothesis

The directed graph studied in this paper is a time-invariant deterministic “first-in, first-out” (FIFO) network. Before proceeding further, we make the following assumptions:(1)
A vehicle travels on a road network in a certain area of a city at a certain time period. During this time period, the time required for a vehicle to drive on any section of the road network does not depend on the time of departure.(2)
The time required for vehicles to pass through the intersection by turning left, right, straight, orU-turn at any intersection during this period is different, but it does not depend on the time of arrival at the intersection.(3)
The time required for a vehicle to travel on any road section during this period is a fixed constant.(4)
The waiting time and the time required for a vehicle to pass through the intersection in any way (turn left, turn right, go straight, orU-turn) at any intersection is also a fixed constant.


## 4. Formulation and Analysis of the Mathematical Model

### 4.1. Formulation of the Mathematical Model

According to the above assumptions, let the weighted directed graphG=V,E,Θ,Ψ composed of four-tuples be the road network graph. The notations and their meanings used in this article are shown in Table 1.Table 1NotationMeaningi,jThe arc that connecting nodei and node j.ϕi,jThe attribute value of the arc segmenti,j, i.e., the time required for the vehicle to traverse the arc segment i,j. For each arc segment i,j, ϕi,j is a uniquely determined value.θi,j,kThe attribute value of nodej (weight or time cost) represents the time taken for the vehicle to wait at node j (intersection) when the vehicle travels from the road section i,j to the road section (j, k). θi,j,k is also uniquely determined for each node j.VThe set of nodes (representing a set of intersections in an actual road network).EThe set of directed arcs that connect nodes (representing road sections in a road network).N+iThe successor nodes set of nodei∈V, N+i=j|i,j∈E.N−iThe predecessor nodes set of nodei, N−i=j|i,j∈E.ΨThe set of each arc attribute values.Ψ=ϕi,j|i,j∈V,i,j∈E.ΘThe set of each node attribute values in the network.Θ=θi,j,k|j∈V,i∈N−j,andk∈N+jλS,DThe minimum travel time starting from the starting nodeS to the destination node D.λi,j,kThe minimum travel time starting from the first nodei of the road section i,j and passing through this section, then through intersection j, and the section (j, k) to the destination node D.μi,jThe minimum travel time from the first nodei i of the road section i,j passing through this section and through intersection j to the destination node D.Given a destination nodeD in the network, the path from any other node S to D can be defined as {i0,i1,i2,…,in−1,in}, where i0=S and in=D. To find the shortest path, we minimize the sum of the attribute values from S to D (the sum of the times spent on each road section and the times spent waiting at and passing through intersections). This is what we refer to as the shortest-path problem for a time-invariant deterministic network taking into account node attributes (weight or time cost). To facilitate the solution of this problem, the following assumptions are necessary.(1)
When the vehicle travels along the route {i0,i1,i2,…,in−1,in}, if it starts from or arrives at node ik, means that the vehicle at the starting point of the arc (i.e., road section) ik,ik+1 at this time.(2)
When the vehicle reaches the endpointD, we assume that it passes the road section in−1,in through the intersection in=D reaches the starting point of the road section in,in+1, where in+1=D, in,in+1=D,D is a virtual road section, and θin−1,D,D=0.According to the above description, the mathematical model of the shortest-path problem for a time-invariant deterministic network taking into account node time consumption can be defined as(1)λS,D=mini0,i1,i2,⋅⋅⋅,in−1,in∑j=1nϕij−1,ij+θij−1,ij,ij+1.


### 4.2. Analysis of the Mathematical Model

Through the analysis of the problem, it is easy to get the following two theorems.Theorem 1.
Assume that the path (i0,i1,i2,i3,…,in−1,in) is the optimal solution of the shortest-path problem taking into account node attributes in a time-invariant deterministic network that connects a starting point i0=S and an endpoint in=D. Then, an arbitrary subpath (ij+1,ij+2,…,ij+k−1,ij+k) of the optimal path i0,i1,i2,i3,…,in−1,in is also the optimal solution from the starting point ij+1 to the endpoint ij+k (i.e., the starting point of the road section ij+k,ij+k+1). That is, the optimal solution of the shortest-path problem for a time-invariant deterministic network taking into account node attributes has an optimal substructure [33].Proof.
The theorem can be proved by a cut-and-paste method. Assume that the subpathij+1,ij+2,ij+3,…,ij+r−1,ij+r is not the optimal solution of the shortest-path problem for a time-invariant deterministic network taking into account node attributes, starting at ij+1(at the beginning of road section ij+1,ij+2) and ending at ij+r (at the beginning of the road section ij+r,ij+r+1). Then, there must exist another subpath ij+1,ij+2,ij+3′,…,ij+s−1′,ij+s′ where ij+s′ represents the starting point of the road section ij+s′,ij+s+1, such that(2)αij+1,ij+2,ij+3′,ij+4′,…,ij+s′<αij+1,ij+2,ij+3,…,ij+r.
Here,(3)αij+1,ij+2,ij+3′,ij+4′,…,ij+s′=∑q=1s−1ϕij+q′,ij+q+1′+θij+q′,ij+q+1′,ij+q+2′,where node ij+1′ represents the starting point of the arc segment ij+1,ij+2, node ij+2′ represents the starting point of the arc segment ij+2,ij+3′, node ij+s′ represents the starting point of the arc segment ij+s′,ij+r+1, and node ij+s+1′ indicates the starting point of the arc segment ij+r+1,ij+r+2; and(4)αij+1,ij+2,ij+3,…,ij+r=∑q=1r−1ϕij+q,ij+q+1+θij+q,ij+q+1,ij+q+2,where node ij+1 represents the starting point of the arc segment ij+1,ij+2 and node point ij+r the starting point of the arc segment ij+r,ij+r+1. Therefore, we have(5)αi0,i0,i0,…,ij+αij+1,ij+2,ij+3′,ij+4′,…,ij+s′+αij+r+1,ij+r+2,…,in<αi0,i0,i0,…,ij+αij+1,ij+2,ij+3,ij+4,…,ij+r+αij+r+1,ij+r+2,…,in.
This contradicts the assumption that the pathi0,i1,i2,i3,…,in−1,in is the optimal solution of the shortest-path problem from the starting node i0=S to the destination node in=D for the time-invariant deterministic network taking into account node attributes. Therefore, the assumption is not true, and Theorem 1 is proved.Theorem 2.
The shortest-path problem for a time-invariant deterministic network taking into account node attributes has the form of repeating subproblems that can be solved by a recursive algorithm.


## 4.1. Formulation of the Mathematical Model

According to the above assumptions, let the weighted directed graphG=V,E,Θ,Ψ composed of four-tuples be the road network graph. The notations and their meanings used in this article are shown in Table 1.Table 1NotationMeaningi,jThe arc that connecting nodei and node j.ϕi,jThe attribute value of the arc segmenti,j, i.e., the time required for the vehicle to traverse the arc segment i,j. For each arc segment i,j, ϕi,j is a uniquely determined value.θi,j,kThe attribute value of nodej (weight or time cost) represents the time taken for the vehicle to wait at node j (intersection) when the vehicle travels from the road section i,j to the road section (j, k). θi,j,k is also uniquely determined for each node j.VThe set of nodes (representing a set of intersections in an actual road network).EThe set of directed arcs that connect nodes (representing road sections in a road network).N+iThe successor nodes set of nodei∈V, N+i=j|i,j∈E.N−iThe predecessor nodes set of nodei, N−i=j|i,j∈E.ΨThe set of each arc attribute values.Ψ=ϕi,j|i,j∈V,i,j∈E.ΘThe set of each node attribute values in the network.Θ=θi,j,k|j∈V,i∈N−j,andk∈N+jλS,DThe minimum travel time starting from the starting nodeS to the destination node D.λi,j,kThe minimum travel time starting from the first nodei of the road section i,j and passing through this section, then through intersection j, and the section (j, k) to the destination node D.μi,jThe minimum travel time from the first nodei i of the road section i,j passing through this section and through intersection j to the destination node D.Given a destination nodeD in the network, the path from any other node S to D can be defined as {i0,i1,i2,…,in−1,in}, where i0=S and in=D. To find the shortest path, we minimize the sum of the attribute values from S to D (the sum of the times spent on each road section and the times spent waiting at and passing through intersections). This is what we refer to as the shortest-path problem for a time-invariant deterministic network taking into account node attributes (weight or time cost). To facilitate the solution of this problem, the following assumptions are necessary.(1)
When the vehicle travels along the route {i0,i1,i2,…,in−1,in}, if it starts from or arrives at node ik, means that the vehicle at the starting point of the arc (i.e., road section) ik,ik+1 at this time.(2)
When the vehicle reaches the endpointD, we assume that it passes the road section in−1,in through the intersection in=D reaches the starting point of the road section in,in+1, where in+1=D, in,in+1=D,D is a virtual road section, and θin−1,D,D=0.According to the above description, the mathematical model of the shortest-path problem for a time-invariant deterministic network taking into account node time consumption can be defined as(1)λS,D=mini0,i1,i2,⋅⋅⋅,in−1,in∑j=1nϕij−1,ij+θij−1,ij,ij+1.


## 4.2. Analysis of the Mathematical Model

Through the analysis of the problem, it is easy to get the following two theorems.Theorem 1.
Assume that the path (i0,i1,i2,i3,…,in−1,in) is the optimal solution of the shortest-path problem taking into account node attributes in a time-invariant deterministic network that connects a starting point i0=S and an endpoint in=D. Then, an arbitrary subpath (ij+1,ij+2,…,ij+k−1,ij+k) of the optimal path i0,i1,i2,i3,…,in−1,in is also the optimal solution from the starting point ij+1 to the endpoint ij+k (i.e., the starting point of the road section ij+k,ij+k+1). That is, the optimal solution of the shortest-path problem for a time-invariant deterministic network taking into account node attributes has an optimal substructure [33].Proof.
The theorem can be proved by a cut-and-paste method. Assume that the subpathij+1,ij+2,ij+3,…,ij+r−1,ij+r is not the optimal solution of the shortest-path problem for a time-invariant deterministic network taking into account node attributes, starting at ij+1(at the beginning of road section ij+1,ij+2) and ending at ij+r (at the beginning of the road section ij+r,ij+r+1). Then, there must exist another subpath ij+1,ij+2,ij+3′,…,ij+s−1′,ij+s′ where ij+s′ represents the starting point of the road section ij+s′,ij+s+1, such that(2)αij+1,ij+2,ij+3′,ij+4′,…,ij+s′<αij+1,ij+2,ij+3,…,ij+r.
Here,(3)αij+1,ij+2,ij+3′,ij+4′,…,ij+s′=∑q=1s−1ϕij+q′,ij+q+1′+θij+q′,ij+q+1′,ij+q+2′,where node ij+1′ represents the starting point of the arc segment ij+1,ij+2, node ij+2′ represents the starting point of the arc segment ij+2,ij+3′, node ij+s′ represents the starting point of the arc segment ij+s′,ij+r+1, and node ij+s+1′ indicates the starting point of the arc segment ij+r+1,ij+r+2; and(4)αij+1,ij+2,ij+3,…,ij+r=∑q=1r−1ϕij+q,ij+q+1+θij+q,ij+q+1,ij+q+2,where node ij+1 represents the starting point of the arc segment ij+1,ij+2 and node point ij+r the starting point of the arc segment ij+r,ij+r+1. Therefore, we have(5)αi0,i0,i0,…,ij+αij+1,ij+2,ij+3′,ij+4′,…,ij+s′+αij+r+1,ij+r+2,…,in<αi0,i0,i0,…,ij+αij+1,ij+2,ij+3,ij+4,…,ij+r+αij+r+1,ij+r+2,…,in.
This contradicts the assumption that the pathi0,i1,i2,i3,…,in−1,in is the optimal solution of the shortest-path problem from the starting node i0=S to the destination node in=D for the time-invariant deterministic network taking into account node attributes. Therefore, the assumption is not true, and Theorem 1 is proved.Theorem 2.
The shortest-path problem for a time-invariant deterministic network taking into account node attributes has the form of repeating subproblems that can be solved by a recursive algorithm.


## 5. Algorithm Design

On the basis of the above analysis, we adopted the dynamic programming method to design an optimal algorithm for solving the shortest-path problem taking into account node attributes.


### 5.1. Reverse Order Labeling Algorithm for Solving Time-Invariant Network Problems

#### 5.1.1. Basic Formula

Letλi,j,k denote the minimum travel time starting from the first node i of the road section (i, j) and passing through this section, then through intersection j and the section (j, k) to the endpoint D. Then, the following recursion formula holds(6)λi,j,k=minl∈N+kϕi,j+θi,j,k+λj,k,l,where(7)λi,D,D=ϕi,D,∀i∈N−D.From the results in the preceding subsection, it follows that(8)λi,D=minj∈N+i,k∈N+jλi,j,k.Letμi,j denote the minimum travel time from the first node i of the road section (i, j) passing through this section (i, j) and through intersection j to the destination D. Then,(9)μi,j=mink∈N+jλi,j,k,μi,j can also be calculated from the recursion formula as follows:(10)μi,j=minl∈N+jϕi,j+θi,j,l+μj,l,where(11)ϕi,j∈Ψ,θi,j,l∈Θ,j∈N+i,l∈N+j,(12)μi,D=ϕi,D,∀i∈N−D.We recordj,πμi,j as the road section following the section (i, j) on the minimum-travel-time path via (i, j) to the destination D, where(13)πμi,j=argminl∈N+jϕi,j+θi,j,l+μj,l.We denote the minimum travel time from the starting point SS to the destinationD by φS,D, and we record πφi as the successor node of node i for this path. From the above analysis, it follows that(14)φS,D=argminj∈N+SμS,j,(15)πφi=argminj∈N+iμi,j.


#### 5.1.2. Overview of the Algorithm

To solve the problem in this article, a new improved Dijkstra algorithm was proposed, named Reverse Order Labeling Algorithm (ROLA). It gradually explores the minimum-travel-time paths through one (or several) arcs (i, j) starting from a certain node i (or some nodes) to the destination D. During the execution of the algorithm, a value μi,j is calculated for the minimum travel time through a given arc (i, j) to the endpoint D, and the arc (i, j) is labeled with a B (black arc). Then, the minimum travel time through all the arcs (k, i) ending at node i to the destination D is calculated. In this process, if any arc that starts at node i has a label B (i.e., the minimum travel time from the arc to the endpoint is known); then, the minimum travel time from the arc (k, i) to the destination D is calculated directly from the recursion formula (5). If an arc starting at node i does not have a label B, then node i is taken as the tree root and arc segments without label B are taken as the search objects. According to the breadth-first search principle, all the arc segments without label B that start from or are connected with node i are searched for, and a breadth-first search tree is constructed. Any arc segment in the tree is labeled with R (red arc segment); then, the minimum travel time through any arc in the tree to the destination D is calculated and the arcs with label R in the tree are relabeled with B. Finally, the minimum travel time to the destination D via the arc (k, i) is calculated. As can be seen from this description, each step of the method modifies the labels of one or more arc segments, with some arc segments without label B acquiring such a label so that the number of arc segments with label B in the network G increases by at least one. Thus, after at most |V| iterations, the minimum-travel-time path through any arc segment starting with each node to the destination can be found. The minimum-travel-time path from the start point S to the destination D is also obtained. In each iteration of the algorithm, the set of arc segments of the directed network graph taking into account node attributes is divided into three subsets: a set of arcs with label B (EB), a set of arcs with label R (ER), and the set EP=E−EB∪ER (i.e., the complement of EB∪ER, a collection of purple arcs). Since it is performed in reverse order, a feature of the reverse order labeling algorithm is that when calculating the shortest path from the current arc segment to the endpoint, it can make full use of the obtained shortest-path data from the subsequent arc segment to the endpoint, which not only exploits all available resources but also saves calculation time. The execution of the algorithm is illustrated below with a specific example.We intercept a section of the network to illustrate two situations that occur during the calculation of the reverse order labeling method, as shown in Figures2 and 3, where the black solid arc (i, j) indicates that the minimum travel time μi,j from the arc (i, j) to the endpoint has been found, i.e., the arc (i, j) has label B. Assuming that the current scanning node is node 2, it is necessary to compute the minimum travel time μi,j from the arc (1, 2) (the purple dashed line) to the endpoint. In Figure 2, since the arc segments 2,j∀j∈N+2 are already arcs with label B, they can be calculated directly using the recursion formula (5). In Figure 3, when calculating the minimum travel time μ1,2 of the arc (1, 2) to the endpoint, because the arcs (2, 3) and (2, 4) starting with node 2 are not labeled B, we need to establish a breadth-first search tree taking node 2 as the root node. Then, all the arcs without label B (the purple dashed lines) that start from or are connected with node 2 are placed on the search tree and labeled R label (red dash dotted lines), as shown in Figure 4. The minimum travel times μ2,3, μ2,4, and μ3,4 of the arc segments (2, 3), (2, 4), and (3, 4) to the endpoint in the tree are calculated, and finally the minimum travel time μ1,2 from the arc (1, 2) to the endpoint is calculated.Figure 2
First case.Figure 3
Second case.Figure 4
Breadth-first search tree.


#### 5.1.3. Specific Steps of the Algorithm

Given a directed graphG=V,E,Θ,Ψ, node set V, edge set E, node attribute value set Θ, edge attribute value set Ψ, and endpoint D as follows:Step 0. BEGIN. Let EB=ø, ER=ø, VR=v|v∈D; for any i∈V, let Nn+i=N+i, Nn−i=N−i, n = 1.Step 1. Check whether EB=E holds. If it does, then go to Step 5; otherwise, go to Step 2.Step 2. Take one v∈VR, and check whether Nn+v=ø holds. (1) If it does, then go to Step 3. (2) If it does not hold, i.e., there exists at least one j∈N+v, make v,j∉EB (this means that the arc (v, j) does not have label B); then follow the steps below:Step 2.1. Taking the node vv as the tree root on the directed graph G=V,E,Θ,Ψ, take the arc segment without label B as the search object, construct a breadth-first search tree according to the breadth-first search principle, and select all arc segments (i, l) such that l∈Nn+i and (i, l) is not in the breadth-first search tree (i.e., (i, l) has neither label B nor label R); insert (i, l) into the breadth-first search tree and into the stack ER(i.e., label the arc segment (i, l) with R), and delete l from l∈Nn+i, until the search process is no longer able to find an arc segment that has neither a label B nor a label R.Step 2.2. Take the arcs (i, l) from the stack ER one by one, put each node from the node set Nn−l−VR into the queue VR (the node is labeled R), and for each arc (i, l); then calculateμi,l=minj∈N+lϕi,l+θi,l,j+μl,jand recordπμi,l=argminj∈N+lϕi,l+θi,l,j+μl,jγi,l=l,πμi,lInsert the arc segment (i, l) into EB and search for node i from Nn−l and delete it. Repeat these operations until the stack ER is empty, then go to Step 3.Step 3. Check whether Nn−v=ø holds. (1) If it does, then delete v from VR and go to Step 4. (2) Otherwise, for arbitrary i∈Nn−v, if i∉VR, insert i into VR, insert (i, v) into EB, delete v from Nn+i, delete i from Nn−v, delete v from VR; then calculateμi,v=minj∈N+vϕi,v+θi,v,j+μv,jand recordπμi,v=argminj∈N+vϕi,v+θi,v,j+μv,jγi,v=v,πμi,v.Go to Step 4.Step 4. Let n = n + 1, and go to Step 1.Step5. CalculateφS,D=argminj∈N+iμS,jfrom which the minimum travel time from the start pointS to the endpoint D is obtained.Step 6. Construct the optimal path from the start node S to the destination D by πμi,v,πφS=argminj∈N+iμS,j and γi,v END.The steps for constructing the breadth-first search tree algorithm in the algorithm subroutines in Steps 2.1 and 2.2 are as follows:Step 0. BEGIN. Let EY=v,v.Step 1. Check whether EY=ø holds. (1) If it does, then go to Step 3; (2) Otherwise, take an arc segment i,j∈EY If Nn+j is not empty, take out k∈Nn+j sequentially, insert arc segments (j, k) into the stack ER in turn, and record Fj,k=i,j, until Nn+j is empty. Go to Step 2.Step 2. Remove (i, j) from EY, and go to Step 1.Step 3. Output the collection stack ER END.Whether or not the setEY is empty controls whether or not the loop ends. Fj,k=i,j indicates that the subarc of the arc (i, j) on the breadth-first search tree is (j, k).


#### 5.1.4. Modular Flow Chart of ROLA

To give a clearer explanation of the execution process of the algorithm, this section presents the pseudocode of the ROLA in modules corresponding to the specific steps of the algorithm.The execution of the ROLA involves the construction of the breadth-first search tree, the data structure of the queue, and the stack. The breadth-first search algorithm is one of the basic graph search algorithms. Both the Dijkstra single-source shortest path algorithm and the Prim minimum spanning tree algorithm use a similar idea to breadth-first search and belong to the class of blind search methods, which systematically expand and examine all the nodes of a graph to obtain their results. Stacks and queues are two linear data structures that are widely used in programming: a stack operates according to the rule “last-in, first-out” (insert (L, n + 1, x) and delete (L, n)), whereas a queue operates according to the rule “first-in, first-out” (insert (L, n + 1, x) and delete (L, 1)). The algorithm performs enqueue and dequeue operations on the nodes during its execution. Because the enqueue operation starts from the endpoint, nodes close to the endpoint are placed in the queue first, and based on the “first-in, first-out” rule, nodes near the end will be dequeued first and processed first, which matches the reverse order basis of the reverse order labeling method. When constructing the breadth-first search tree, beginning with the root v, the non-B-labeled arc segments that are searched for are pushed into the stack until the search switches to the B-labeled arc segments. After this search has been completed, the pop-up stack operation is performed on the arc according to the “last-in, first-out” rule, which ensures that the minimum travel times from the arcs nearest the endpoint are calculated first, from near-to-far, and only then, the minimum travel times from arcs far from the endpoint are calculated, which is again in accordance with the reverse order labeling method.The ROLA composed of four modules as follows: the breadth-first search tree construction process (Module 1), the arc pushing and popping stack process (Module 2), the node enqueue and dequeue process (Module 3), and the optimal path output (Module 4). In order to understand the relationship between each module more clearly and intuitively, we use pseudo to describe. The pseudo of module 1 to module 4 is shown in the Algorithms1–4.Algorithm 1:Breadth-first search tree (Module 1).
(1)
BFS(G, v)% Given,G=V,E,Θ,Ψ node v as the root of the tree, to construct a breadth-first search tree using the arcs without the B label.(2)
for eachi,l∉EB∪ERdo(3)
Color ← i,l←red(4)
endAlgorithm 2:Arc stack operation (Module 2).
(1)
Push (stackER,i,l);% Select each arc (i, l) that satisfies the condition l∈Nn+i and is not on the breadth-first search tree, insert it into the breadth-first search tree, and insert such arcs (i, l) into the stack ER in turn (the arc ER is marked as R)(2)
do(3)
EB=ER∪i,l;(4)
Nn+i=Nn+i−l;% Remove nodel from the set of successor nodes of node i(5)
Untili,l∉EB&&i,l∉ER;% Breadth-first search tree construction completed(6)
Pop(stack, ER);(7)
WhileER=ø% when the optimal path from all arcs on the tree to the destination has not been obtained, proceed as follows(8)
do(9)
Color ← i,l←Black;(10)
ER=ER−i,l;(11)
μi,l=minj∈N+lϕi,l+θi,l,j+μl,j(12)
πμi,l=argminj∈N+lϕi,l+θi,l,j+μl,j(13)
γi,l=l,πμi,l% Calculate the minimum time from each arc segment on the breadth-first search tree to the destination in the stacking order and record the path.(14)
then(15)
Nn−l=Nn−l−i% Delete nodei from the predecessor node of node l(16)
EndAlgorithm 3:Node queue operation (Module 3).
(1)
DeQueue(VR)% Select each arc (i, l) that satisfies the condition l∈Nn+i and is not on the breadth-first search tree, insert it into the breadth-first search tree, and insert such arcs (i, l) into the stack ER in turn (the arc ER is marked as R)(2)
forv∈VR&&Nn+v=ø do % take a node v from the queue VR(3)
ifNn−v=øthen(4)
VR=VR−v;% Determine whether nodev is isolated, if it is, delete node v from the queue VR.(5)
else(6)
for eachi∈Nn−v;% Perform the following operations for each predecessor nodei of the node v.(7)
ifi∉VR do(8)
EnQueueVR,i;(9)
VR=VR∪i; % insert node i into the queue VR(10)
EB=EB∪i,v;% insert (i, v) into the set EB and mark it as a black arc.(11)
μi,v=minj∈N+vϕi,v+θi,v,j+μv,j(12)
πμi,v=argminj∈N+vϕi,v+θi,v,j+μv,j(13)
γi,v=v,πμi,v% Calculate the optimal path from all arc segments (i, v) with v as the end node to the destination.(14)
then(15)
Nn+i=Nn+i−v; % RemovevfromNn+i.(16)
Nn−v=Nn−v−i; % Remove i from.(17)
VR=VR−v;% Removevfrom the queueVR(18)
UpdateEB(19)
EndAlgorithm 4:Optimal path result output (Module 4).
(1)
Output (·)(2)
φS,D=minj∈N+SμS,j;% obtain the minimum time from start nodeS to destination D.(3)
πφS=argminj∈N+iμS,j;% obtain the subsequent nodes of the node S on the optimal path.(4)
πμi,v=argminj∈N+vϕi,v+θi,v,j+μv,j;% obtain the subsequent arc (v, j) of arc (i, v) on the optimal path from arc (i, v) to destination D.(5)
γi,v=v,πμi,v;% record the subsequent arc of arc (i, v) on the optimal path as v,πμi,v(6)
S,πφS⟶γS,πφS⟶γγS,πφS,…,D,D;% obtain the best path from startS to destination D.(7)
endIt can be seen from Algorithm5 that each module has an interface connected with one or more of the other modules. So the modules are not isolated but closely related. After initialization, Module 1 or Module 4 is selected for execution by checking whether the condition EB=E holds. Module 1 is directly connected to Module 2, indicating that Module 2 is executed after Module 1 has been completed. Similarly, Module 2 is directly connected to Module 3. After Module 3 has been executed, by checking whether or not EB=E holds, the algorithm decides to go to the next iteration or to exit the program after executing Module 4.Algorithm 5:Relationship between modules.
Initialization:G=V,E,Θ,Ψ, n=1,ER=ø, VR=v|v=D, EB=ø, for ∀i∈V,Nn+i=N+i, Nn−i=N−iResult:A SequenceΠ:=S,i,i,j,…,D,DMain procedure(1)
ifEB≠E(2)
for∀v∈VR(3)
ifNn+v=ø% ifNn+v=ø directly performs node vv queue operation (i.e. Module 3)(4)
execute Module 3;(5)
ifEB≠E(6)execute Module 1;(7)
else(8)
execute Module 4;(9)
else(10)
execute Module 1;% perform the breadth-first search tree construction operation withv as the root node(11)
execute Module 2;% perform push and pop operations on the arcs on the breadth-first search tree constructed(12)
execute Module 3% when all the arcs in the stackER are popped out of the stack, perform the queue operation of node v(13)
ifEB≠E(14)
execute Module 1;% ifEB≠E, enter the next loop of the algorithm, first perform the operation of building breadth-first search tree(15)
else(16)
execute Module 4;% ifEB=E, the algorithm loop termination condition is met, execute the algorithm’s route output operation(17)
else execute Module 4;(18)
end.


#### 5.1.5. Correctness of the Algorithm and Proof of Time Complexity

(1) Correctness of the AlgorithmProposition 1.
Before then-th loop execution of the algorithm, if node i already exists in the queue VR, it cannot be inserted into VR again during the n-th loop execution; i.e., during the execution of the algorithm, it is impossible for the same node to appear more than once in the queue VR.PROOF.
This proposition follows clearly from the way in which the algorithm is executed.Proposition 2.
If a nodei∈VR is deleted from VR in the n-th loop execution of the algorithm, then Nn+i=ø must hold after the n-th loop execution; so, for arbitrary m > n, node i cannot be inserted into VR again during the m-th loop execution.Proof.
For any nodei∈VR, if node i is deleted from the queue VR during the n-th loop execution of the algorithm, then after the Step 2 and Step 3 operations in the n-th loop execution, Nn+i=ø a must hold. For any m > n, before the m-th loop execution, Nn+i=ø also holds; and during the m-th loop execution, before a certain node j can be inserted into the queue VR, Nn+j=ø a must hold. Therefore, during the m-th loop execution of the algorithm, node i cannot be inserted into the queue VR, and the proposition is proved.Proposition 3.
After the end of a certain loop execution of the algorithm, ifEB≠E holds, then VR≠ø must hold.Proof.
After the end of a certain loop execution of the algorithm, ifEB≠E holds, then there must exist a certain arc segment (i, j) without label B, and k∈N+j, j,k∈EB, and it is obvious that Nn+i=ø and N+j=ø hold. It is then known from Proposition 2 that node i is either in the queue VR or is not in the queue and has never entered it. If it is assumed that node i is not in the queue VR and has never entered it, then, because the arc segment (j, k) has a label B, node i must have been inserted into VR during the procedure of inserting the arc (j, k) into the set EB, which is contradictory; hence the assumption is not true. Therefore, if EB≠E holds, VR≠ø must hold, and Proposition 3 is proved.
From Propositions1–3, it is easy to derive the following theorem.Theorem 3.
During the execution of the algorithm, any nodei∈V enters and exits the queue VR at most one time, so there can be no more than |V| loops from Step 1 to Step 4 of the algorithm.Proposition 4.
The ROLA has the following loop invariance: before the start of then-th loop, if all the arcs in the set EB have label B, then all the arcs in EB still have label B before the start of the (n + 1)-th loop. The proof of this is omitted here.
From Theorem4 and Propositions 3, and 4, the following theorem can be obtained.Theorem 4.
During the |V||V| loops (at most) from Step 1 to Step 4 of the ROLA, the condition EB=E holds; i.e., for any arc segment i,j∈E, the minimum travel time μi,j though the arc segment (i, j) to the endpoint D can be obtained.Proposition 5.
For any arc segmenti,j∈E, during the |V| loops (at most) from Step 1 to Step 4 of the ROLA, the arc segment (i, j) is put no more than once into the breadth-first search tree that is constructed so that it goes into and out of the stack ER at most once.Proof.
If an arc (i, j) appears in the breadth-first search tree in Step 2 of a certain loop, then, after the end of that loop, the arc (i, j) must have label B (because it has already been inserted into the set EB). During each subsequent loop execution, any arc segment (i, j) inserted into the breadth-first search tree does not have label B before it is inserted, so the arc segment (i, j) cannot be inserted into the breadth-first search tree again during any of the subsequent loop executions. Thus Proposition 5 is proved.
(2) Time Complexity of the Algorithm
It can be seen from the description of the algorithm that the difficulty in analyzing its time complexity lies in the loops from Step 1 to Step 4, of which there |V| at most. The time complexity cost in the execution of the algorithm consists mainly of the following three components:(1)
The time cost of all nodes that are put into or are removed from the queueVR(2)
The time cost of constructing a breadth-first search tree and inserting and removing arcs from the stackER(3)
The time cost of calculating the minimum travel timeμi,j via all arcs (i, j) to the endpoint D
Let(16)N=maxiN+i,N−i.Theorem 5.
From the beginning to the end of the algorithm, during the construction of the breadth-first search tree, including the operations on all nodes that are put into or taken out of the queueVR and on all arcs that are put into or taken out of the stack ER, the total complexity cost in computation time is OV+N⋅E.Proof.
The proof of the theorem is divided into three steps.
In the first step, we first prove that, during the process from the beginning to the end of the algorithm, the computation time complexity cost of all arcs that are put into or taken out of the stackER (i.e., into or out of the breadth-first search tree) is ON⋅E. As can be seen from Proposition 5, any arc segment i,j∈E is put into and taken out of the breadth-first search tree at most once, i.e., into and out of the stack ER at most once. According to the operation of the algorithm, for each i,j that is put into and taken out of the stack ER, the time cost of entering ER is O1, so for all the arcs i,j that are put into and taken out of ER, the total cost of entering ER is OE. For each arc i,j that is put into and taken out of the stack ER, there is an operation of removing i,j from the stack ER and inserting it into the stack EB, and the time complexity of this part of the operation is O1. There is also the operation of searching for node i in the set Nn−j and deleting it from this set, the time complexity cost of which is ON; hence the time complexity of removing the arc i,j from the stack ER is ON. Therefore, for all the arcs i,j that are put into and taken out of the stack ER, the total time cost when they are moved out of ER is ON⋅E. In summary, the total time cost of all the arcs i,j that are put into and taken out of the stack ER is ON⋅|E|.
In the second step, we prove that, for all the nodesi that are put into and taken out of the queue VR , the time cost when they are removed from VR is OV. From Theorem 3, for an arbitrary node i∈V, in the execution of the algorithm from beginning to end, node i enters and exits the queue VR at most once. According to the operation of the algorithm, for each node i that is put into and taken out of VR, the time cost when it is taken out of VR is O1. Therefore, for all nodes i that are put into and taken out of the queue VR , the total time cost when they are removed from VR is OV.
In the third step, we prove that, for each nodei that is put into and taken out of the queue VR, the time cost when it is inserted into VR is OE. For any node ii that is put into and taken out of the queue VR, two situations can occur: in one, node i is the predecessor node of a node v that is about to be moved out of VR (i.e., i∈Nn−v); in the other, node i is the predecessor node of the endpoint l of the arc (j, l) in the breadth-first search tree that has been constructed. In the former situation, when node i is inserted into the queue VR, all the nodes in the set Nn−v that are not included in the queue VR are inserted into VR, which is equivalent to beginning from node v, searching for all the arcs i,v that satisfy the conditions i∈Nn−v and i∉VR, and then inserting node i into the set VR. Therefore, from the beginning to the end of the algorithm, the time cost of all the nodes that are inserted into the queue VR, because they are predecessor nodes of a certain node that was removed from VR, is OE. In the second situation, when the node i is inserted into the queue VR, all the nodes that are in the set Nn−l and do not belong to VR are inserted into VR. This is equivalent to starting from node l, scanning and searching for all the arcs i,l that satisfy the conditions i∈Nn−l and i∉VR, and inserting node ii into the set VR; then Nn−l=Ø holds. Therefore, in this loop or later loops, when we search for an arc k,l that has the same endpoint as the arc segment j,l from the stack ER, because Nn−l=ø, the arc segment i,l that was previously scanned and searched for no longer needs to be searched for. By Proposition 5, any arc segment j,l∈E is inserted into and removed from the breadth-first search tree at most once in the V iterations at most of the algorithm. Therefore, for any node l∈V, each arc i,l that satisfies the condition i∈Nn−l needs at most one scan to search for node i and inserted it into VR. Hence the time complexity of all those nodes that are inserted into VR because they are predecessors of the endpoint of the arc j,l in the breadth-first search tree is OE.
In summary, from the beginning to the end of the algorithm, during the construction of the breadth-first search tree, including the operations on all nodes that are put into and taken out of the queueVR and all arcs that are put into and taken out of the stack ER, the total computation time complexity cost is OV+N⋅E. Thus Theorem 5 is proved.Theorem 6.
Using ROLA, the complexity cost of calculating the minimum time for all arcs inE to reach the destination D is ON⋅E, and(17)μi,j=minl∈N+jϕi,j+θi,j,l+μj,l,where(18)ϕi,j∈Ψ,θi,j,l∈Θ,j∈N+i,l∈N+j,(19)μi,D=φi,D,∀i∈N−D.Proof.
For arbitraryi,j∈E in the process of calculating μi,j according to the above recursion formula, it is necessary to calculate N+j times the following expression and then to perform N+j−1 comparison operations.(20)ϕi,j+θi,j,l+μj,l.
In each calculation using this expression, there are two addition operations, so the time complexity cost of calculatingμi,j for one arc segment i,j is ON. Therefore, the complexity cost of calculating the minimum time through all arcs in E to the endpoint D is ON⋅E, where N=maxiN+i,N−i. Thus Theorem 6 is proved. The following theorem is apparent from Theorems 5 and 6.Theorem 7.
The time complexity of the ROLA in a time-invariant network isOV+N⋅E.
It can be seen that the time complexity of the ROLA is a polynomial in the number of nodes (V), the number of edges (E), the maximum number of predecessors, and the number of subsequent nodes (N) in the network. The time complexity of the algorithm is low.


### 5.2. Calculation Example

A simple directed graph is used to illustrate the execution process of the algorithm. As shown in Figure5, the directed graph G is composed of 11 nodes and 18 edges. The arrows indicate the direction of travel on each road section. Node 11 is a given starting point and node 1111 is the given destination. The travel time values ϕi,j on the arcs i,j are shown in Table 2, and the waiting time values θi,j,k of the arc i,j selected different arcs j,k at the nodes j are shown in Table 3.Figure 5
Directed graph representing a time-invariant network.Table 2
Edge attribute value.
ϕ1,2ϕ1,3ϕ1,4ϕ2,5ϕ2,6ϕ3,2243222ϕ3,7ϕ4,7ϕ4,8ϕ5,9ϕ6,9ϕ6,10345232ϕ7,10ϕ8,10ϕ8,11ϕ9,11ϕ10,9ϕ10,11455645Table 3
Node attribute value.
θ1,2,5θ1,2,6θ1,3,2θ1,3,7θ1,4,7θ1,4,8131232θ2,5,9θ2,6,9θ2,6,10θ3,2,5θ3,2,6θ3,7,10133214θ4,7,10θ4,8,10θ4,8,11θ5,9,11θ6,9,11θ6,10,9223223θ6,10,11θ7,10,9θ7,10,11θ8,10,9θ8,10,11θ10,9,11443321Our goal is to calculate the minimum travel time path from each arc segment to the destination and the minimum travel time path from the starting node 11 to the destination 1111 in the network. When the intersection attribute (weight or time cost) is not considered, the minimum time path from the starting node 11 to the endpoint 1111 is1⟶2⟶6⟶10⟶11 obtained by the Dijkstra algorithm, and the travel time is 11.The Reverse Order Labeling Algorithm given in this paper is used to solve the minimum time path from node 11 to node 11 in Figure5 considering the waiting time of the node. The specific calculation process is omitted here. After 9 iterations of calculation, the data in Table 4 are obtained when the algorithm terminates. Including the minimum time path of each arc in the directed graph to the end and the travel time value. Let(21)φ1,11=minj∈N+1μ1,j=μ1,2=16.Table 4
Algorithm execution result.
μ10,11=5,γ10,11=11,11μ10,9=11,γ10,9=9,11μ9,11=6,γ9,11=11,11μ8,11=5,γ8,11=11,11μ8,10=12,γ8,10=10,11μ7,10=12,γ7,10=10,11μ6,10=10,γ6,10=10,11μ6,9=11,γ6,9=9,11μ5,9=10,γ5,9=9,11μ4,8=12,γ4,8=8,11μ4,7=18,γ4,7=7,10μ3,7=19,γ3,7=7,10μ3,2=17,γ3,2=2,5μ2,6=15,γ2,6=6,10μ2,5=13,γ2,5=5,9μ1,4=17,γ1,4=4,8μ1,3=22,γ1,3=3,7μ1,2=16,γ1,2=2,5According toγi,j, the minimum expected time path from the starting point 11 to the destination 11 is 1⟶2⟶5⟶9⟶11, and the minimum travel time is 16.


## 5.1. Reverse Order Labeling Algorithm for Solving Time-Invariant Network Problems

### 5.1.1. Basic Formula

Letλi,j,k denote the minimum travel time starting from the first node i of the road section (i, j) and passing through this section, then through intersection j and the section (j, k) to the endpoint D. Then, the following recursion formula holds(6)λi,j,k=minl∈N+kϕi,j+θi,j,k+λj,k,l,where(7)λi,D,D=ϕi,D,∀i∈N−D.From the results in the preceding subsection, it follows that(8)λi,D=minj∈N+i,k∈N+jλi,j,k.Letμi,j denote the minimum travel time from the first node i of the road section (i, j) passing through this section (i, j) and through intersection j to the destination D. Then,(9)μi,j=mink∈N+jλi,j,k,μi,j can also be calculated from the recursion formula as follows:(10)μi,j=minl∈N+jϕi,j+θi,j,l+μj,l,where(11)ϕi,j∈Ψ,θi,j,l∈Θ,j∈N+i,l∈N+j,(12)μi,D=ϕi,D,∀i∈N−D.We recordj,πμi,j as the road section following the section (i, j) on the minimum-travel-time path via (i, j) to the destination D, where(13)πμi,j=argminl∈N+jϕi,j+θi,j,l+μj,l.We denote the minimum travel time from the starting point SS to the destinationD by φS,D, and we record πφi as the successor node of node i for this path. From the above analysis, it follows that(14)φS,D=argminj∈N+SμS,j,(15)πφi=argminj∈N+iμi,j.


### 5.1.2. Overview of the Algorithm

To solve the problem in this article, a new improved Dijkstra algorithm was proposed, named Reverse Order Labeling Algorithm (ROLA). It gradually explores the minimum-travel-time paths through one (or several) arcs (i, j) starting from a certain node i (or some nodes) to the destination D. During the execution of the algorithm, a value μi,j is calculated for the minimum travel time through a given arc (i, j) to the endpoint D, and the arc (i, j) is labeled with a B (black arc). Then, the minimum travel time through all the arcs (k, i) ending at node i to the destination D is calculated. In this process, if any arc that starts at node i has a label B (i.e., the minimum travel time from the arc to the endpoint is known); then, the minimum travel time from the arc (k, i) to the destination D is calculated directly from the recursion formula (5). If an arc starting at node i does not have a label B, then node i is taken as the tree root and arc segments without label B are taken as the search objects. According to the breadth-first search principle, all the arc segments without label B that start from or are connected with node i are searched for, and a breadth-first search tree is constructed. Any arc segment in the tree is labeled with R (red arc segment); then, the minimum travel time through any arc in the tree to the destination D is calculated and the arcs with label R in the tree are relabeled with B. Finally, the minimum travel time to the destination D via the arc (k, i) is calculated. As can be seen from this description, each step of the method modifies the labels of one or more arc segments, with some arc segments without label B acquiring such a label so that the number of arc segments with label B in the network G increases by at least one. Thus, after at most |V| iterations, the minimum-travel-time path through any arc segment starting with each node to the destination can be found. The minimum-travel-time path from the start point S to the destination D is also obtained. In each iteration of the algorithm, the set of arc segments of the directed network graph taking into account node attributes is divided into three subsets: a set of arcs with label B (EB), a set of arcs with label R (ER), and the set EP=E−EB∪ER (i.e., the complement of EB∪ER, a collection of purple arcs). Since it is performed in reverse order, a feature of the reverse order labeling algorithm is that when calculating the shortest path from the current arc segment to the endpoint, it can make full use of the obtained shortest-path data from the subsequent arc segment to the endpoint, which not only exploits all available resources but also saves calculation time. The execution of the algorithm is illustrated below with a specific example.We intercept a section of the network to illustrate two situations that occur during the calculation of the reverse order labeling method, as shown in Figures2 and 3, where the black solid arc (i, j) indicates that the minimum travel time μi,j from the arc (i, j) to the endpoint has been found, i.e., the arc (i, j) has label B. Assuming that the current scanning node is node 2, it is necessary to compute the minimum travel time μi,j from the arc (1, 2) (the purple dashed line) to the endpoint. In Figure 2, since the arc segments 2,j∀j∈N+2 are already arcs with label B, they can be calculated directly using the recursion formula (5). In Figure 3, when calculating the minimum travel time μ1,2 of the arc (1, 2) to the endpoint, because the arcs (2, 3) and (2, 4) starting with node 2 are not labeled B, we need to establish a breadth-first search tree taking node 2 as the root node. Then, all the arcs without label B (the purple dashed lines) that start from or are connected with node 2 are placed on the search tree and labeled R label (red dash dotted lines), as shown in Figure 4. The minimum travel times μ2,3, μ2,4, and μ3,4 of the arc segments (2, 3), (2, 4), and (3, 4) to the endpoint in the tree are calculated, and finally the minimum travel time μ1,2 from the arc (1, 2) to the endpoint is calculated.Figure 2
First case.Figure 3
Second case.Figure 4
Breadth-first search tree.


### 5.1.3. Specific Steps of the Algorithm

Given a directed graphG=V,E,Θ,Ψ, node set V, edge set E, node attribute value set Θ, edge attribute value set Ψ, and endpoint D as follows:Step 0. BEGIN. Let EB=ø, ER=ø, VR=v|v∈D; for any i∈V, let Nn+i=N+i, Nn−i=N−i, n = 1.Step 1. Check whether EB=E holds. If it does, then go to Step 5; otherwise, go to Step 2.Step 2. Take one v∈VR, and check whether Nn+v=ø holds. (1) If it does, then go to Step 3. (2) If it does not hold, i.e., there exists at least one j∈N+v, make v,j∉EB (this means that the arc (v, j) does not have label B); then follow the steps below:Step 2.1. Taking the node vv as the tree root on the directed graph G=V,E,Θ,Ψ, take the arc segment without label B as the search object, construct a breadth-first search tree according to the breadth-first search principle, and select all arc segments (i, l) such that l∈Nn+i and (i, l) is not in the breadth-first search tree (i.e., (i, l) has neither label B nor label R); insert (i, l) into the breadth-first search tree and into the stack ER(i.e., label the arc segment (i, l) with R), and delete l from l∈Nn+i, until the search process is no longer able to find an arc segment that has neither a label B nor a label R.Step 2.2. Take the arcs (i, l) from the stack ER one by one, put each node from the node set Nn−l−VR into the queue VR (the node is labeled R), and for each arc (i, l); then calculateμi,l=minj∈N+lϕi,l+θi,l,j+μl,jand recordπμi,l=argminj∈N+lϕi,l+θi,l,j+μl,jγi,l=l,πμi,lInsert the arc segment (i, l) into EB and search for node i from Nn−l and delete it. Repeat these operations until the stack ER is empty, then go to Step 3.Step 3. Check whether Nn−v=ø holds. (1) If it does, then delete v from VR and go to Step 4. (2) Otherwise, for arbitrary i∈Nn−v, if i∉VR, insert i into VR, insert (i, v) into EB, delete v from Nn+i, delete i from Nn−v, delete v from VR; then calculateμi,v=minj∈N+vϕi,v+θi,v,j+μv,jand recordπμi,v=argminj∈N+vϕi,v+θi,v,j+μv,jγi,v=v,πμi,v.Go to Step 4.Step 4. Let n = n + 1, and go to Step 1.Step5. CalculateφS,D=argminj∈N+iμS,jfrom which the minimum travel time from the start pointS to the endpoint D is obtained.Step 6. Construct the optimal path from the start node S to the destination D by πμi,v,πφS=argminj∈N+iμS,j and γi,v END.The steps for constructing the breadth-first search tree algorithm in the algorithm subroutines in Steps 2.1 and 2.2 are as follows:Step 0. BEGIN. Let EY=v,v.Step 1. Check whether EY=ø holds. (1) If it does, then go to Step 3; (2) Otherwise, take an arc segment i,j∈EY If Nn+j is not empty, take out k∈Nn+j sequentially, insert arc segments (j, k) into the stack ER in turn, and record Fj,k=i,j, until Nn+j is empty. Go to Step 2.Step 2. Remove (i, j) from EY, and go to Step 1.Step 3. Output the collection stack ER END.Whether or not the setEY is empty controls whether or not the loop ends. Fj,k=i,j indicates that the subarc of the arc (i, j) on the breadth-first search tree is (j, k).


### 5.1.4. Modular Flow Chart of ROLA

To give a clearer explanation of the execution process of the algorithm, this section presents the pseudocode of the ROLA in modules corresponding to the specific steps of the algorithm.The execution of the ROLA involves the construction of the breadth-first search tree, the data structure of the queue, and the stack. The breadth-first search algorithm is one of the basic graph search algorithms. Both the Dijkstra single-source shortest path algorithm and the Prim minimum spanning tree algorithm use a similar idea to breadth-first search and belong to the class of blind search methods, which systematically expand and examine all the nodes of a graph to obtain their results. Stacks and queues are two linear data structures that are widely used in programming: a stack operates according to the rule “last-in, first-out” (insert (L, n + 1, x) and delete (L, n)), whereas a queue operates according to the rule “first-in, first-out” (insert (L, n + 1, x) and delete (L, 1)). The algorithm performs enqueue and dequeue operations on the nodes during its execution. Because the enqueue operation starts from the endpoint, nodes close to the endpoint are placed in the queue first, and based on the “first-in, first-out” rule, nodes near the end will be dequeued first and processed first, which matches the reverse order basis of the reverse order labeling method. When constructing the breadth-first search tree, beginning with the root v, the non-B-labeled arc segments that are searched for are pushed into the stack until the search switches to the B-labeled arc segments. After this search has been completed, the pop-up stack operation is performed on the arc according to the “last-in, first-out” rule, which ensures that the minimum travel times from the arcs nearest the endpoint are calculated first, from near-to-far, and only then, the minimum travel times from arcs far from the endpoint are calculated, which is again in accordance with the reverse order labeling method.The ROLA composed of four modules as follows: the breadth-first search tree construction process (Module 1), the arc pushing and popping stack process (Module 2), the node enqueue and dequeue process (Module 3), and the optimal path output (Module 4). In order to understand the relationship between each module more clearly and intuitively, we use pseudo to describe. The pseudo of module 1 to module 4 is shown in the Algorithms1–4.Algorithm 1:Breadth-first search tree (Module 1).
(1)
BFS(G, v)% Given,G=V,E,Θ,Ψ node v as the root of the tree, to construct a breadth-first search tree using the arcs without the B label.(2)
for eachi,l∉EB∪ERdo(3)
Color ← i,l←red(4)
endAlgorithm 2:Arc stack operation (Module 2).
(1)
Push (stackER,i,l);% Select each arc (i, l) that satisfies the condition l∈Nn+i and is not on the breadth-first search tree, insert it into the breadth-first search tree, and insert such arcs (i, l) into the stack ER in turn (the arc ER is marked as R)(2)
do(3)
EB=ER∪i,l;(4)
Nn+i=Nn+i−l;% Remove nodel from the set of successor nodes of node i(5)
Untili,l∉EB&&i,l∉ER;% Breadth-first search tree construction completed(6)
Pop(stack, ER);(7)
WhileER=ø% when the optimal path from all arcs on the tree to the destination has not been obtained, proceed as follows(8)
do(9)
Color ← i,l←Black;(10)
ER=ER−i,l;(11)
μi,l=minj∈N+lϕi,l+θi,l,j+μl,j(12)
πμi,l=argminj∈N+lϕi,l+θi,l,j+μl,j(13)
γi,l=l,πμi,l% Calculate the minimum time from each arc segment on the breadth-first search tree to the destination in the stacking order and record the path.(14)
then(15)
Nn−l=Nn−l−i% Delete nodei from the predecessor node of node l(16)
EndAlgorithm 3:Node queue operation (Module 3).
(1)
DeQueue(VR)% Select each arc (i, l) that satisfies the condition l∈Nn+i and is not on the breadth-first search tree, insert it into the breadth-first search tree, and insert such arcs (i, l) into the stack ER in turn (the arc ER is marked as R)(2)
forv∈VR&&Nn+v=ø do % take a node v from the queue VR(3)
ifNn−v=øthen(4)
VR=VR−v;% Determine whether nodev is isolated, if it is, delete node v from the queue VR.(5)
else(6)
for eachi∈Nn−v;% Perform the following operations for each predecessor nodei of the node v.(7)
ifi∉VR do(8)
EnQueueVR,i;(9)
VR=VR∪i; % insert node i into the queue VR(10)
EB=EB∪i,v;% insert (i, v) into the set EB and mark it as a black arc.(11)
μi,v=minj∈N+vϕi,v+θi,v,j+μv,j(12)
πμi,v=argminj∈N+vϕi,v+θi,v,j+μv,j(13)
γi,v=v,πμi,v% Calculate the optimal path from all arc segments (i, v) with v as the end node to the destination.(14)
then(15)
Nn+i=Nn+i−v; % RemovevfromNn+i.(16)
Nn−v=Nn−v−i; % Remove i from.(17)
VR=VR−v;% Removevfrom the queueVR(18)
UpdateEB(19)
EndAlgorithm 4:Optimal path result output (Module 4).
(1)
Output (·)(2)
φS,D=minj∈N+SμS,j;% obtain the minimum time from start nodeS to destination D.(3)
πφS=argminj∈N+iμS,j;% obtain the subsequent nodes of the node S on the optimal path.(4)
πμi,v=argminj∈N+vϕi,v+θi,v,j+μv,j;% obtain the subsequent arc (v, j) of arc (i, v) on the optimal path from arc (i, v) to destination D.(5)
γi,v=v,πμi,v;% record the subsequent arc of arc (i, v) on the optimal path as v,πμi,v(6)
S,πφS⟶γS,πφS⟶γγS,πφS,…,D,D;% obtain the best path from startS to destination D.(7)
endIt can be seen from Algorithm5 that each module has an interface connected with one or more of the other modules. So the modules are not isolated but closely related. After initialization, Module 1 or Module 4 is selected for execution by checking whether the condition EB=E holds. Module 1 is directly connected to Module 2, indicating that Module 2 is executed after Module 1 has been completed. Similarly, Module 2 is directly connected to Module 3. After Module 3 has been executed, by checking whether or not EB=E holds, the algorithm decides to go to the next iteration or to exit the program after executing Module 4.Algorithm 5:Relationship between modules.
Initialization:G=V,E,Θ,Ψ, n=1,ER=ø, VR=v|v=D, EB=ø, for ∀i∈V,Nn+i=N+i, Nn−i=N−iResult:A SequenceΠ:=S,i,i,j,…,D,DMain procedure(1)
ifEB≠E(2)
for∀v∈VR(3)
ifNn+v=ø% ifNn+v=ø directly performs node vv queue operation (i.e. Module 3)(4)
execute Module 3;(5)
ifEB≠E(6)execute Module 1;(7)
else(8)
execute Module 4;(9)
else(10)
execute Module 1;% perform the breadth-first search tree construction operation withv as the root node(11)
execute Module 2;% perform push and pop operations on the arcs on the breadth-first search tree constructed(12)
execute Module 3% when all the arcs in the stackER are popped out of the stack, perform the queue operation of node v(13)
ifEB≠E(14)
execute Module 1;% ifEB≠E, enter the next loop of the algorithm, first perform the operation of building breadth-first search tree(15)
else(16)
execute Module 4;% ifEB=E, the algorithm loop termination condition is met, execute the algorithm’s route output operation(17)
else execute Module 4;(18)
end.


### 5.1.5. Correctness of the Algorithm and Proof of Time Complexity

(1) Correctness of the AlgorithmProposition 1.
Before then-th loop execution of the algorithm, if node i already exists in the queue VR, it cannot be inserted into VR again during the n-th loop execution; i.e., during the execution of the algorithm, it is impossible for the same node to appear more than once in the queue VR.PROOF.
This proposition follows clearly from the way in which the algorithm is executed.Proposition 2.
If a nodei∈VR is deleted from VR in the n-th loop execution of the algorithm, then Nn+i=ø must hold after the n-th loop execution; so, for arbitrary m > n, node i cannot be inserted into VR again during the m-th loop execution.Proof.
For any nodei∈VR, if node i is deleted from the queue VR during the n-th loop execution of the algorithm, then after the Step 2 and Step 3 operations in the n-th loop execution, Nn+i=ø a must hold. For any m > n, before the m-th loop execution, Nn+i=ø also holds; and during the m-th loop execution, before a certain node j can be inserted into the queue VR, Nn+j=ø a must hold. Therefore, during the m-th loop execution of the algorithm, node i cannot be inserted into the queue VR, and the proposition is proved.Proposition 3.
After the end of a certain loop execution of the algorithm, ifEB≠E holds, then VR≠ø must hold.Proof.
After the end of a certain loop execution of the algorithm, ifEB≠E holds, then there must exist a certain arc segment (i, j) without label B, and k∈N+j, j,k∈EB, and it is obvious that Nn+i=ø and N+j=ø hold. It is then known from Proposition 2 that node i is either in the queue VR or is not in the queue and has never entered it. If it is assumed that node i is not in the queue VR and has never entered it, then, because the arc segment (j, k) has a label B, node i must have been inserted into VR during the procedure of inserting the arc (j, k) into the set EB, which is contradictory; hence the assumption is not true. Therefore, if EB≠E holds, VR≠ø must hold, and Proposition 3 is proved.
From Propositions1–3, it is easy to derive the following theorem.Theorem 3.
During the execution of the algorithm, any nodei∈V enters and exits the queue VR at most one time, so there can be no more than |V| loops from Step 1 to Step 4 of the algorithm.Proposition 4.
The ROLA has the following loop invariance: before the start of then-th loop, if all the arcs in the set EB have label B, then all the arcs in EB still have label B before the start of the (n + 1)-th loop. The proof of this is omitted here.
From Theorem4 and Propositions 3, and 4, the following theorem can be obtained.Theorem 4.
During the |V||V| loops (at most) from Step 1 to Step 4 of the ROLA, the condition EB=E holds; i.e., for any arc segment i,j∈E, the minimum travel time μi,j though the arc segment (i, j) to the endpoint D can be obtained.Proposition 5.
For any arc segmenti,j∈E, during the |V| loops (at most) from Step 1 to Step 4 of the ROLA, the arc segment (i, j) is put no more than once into the breadth-first search tree that is constructed so that it goes into and out of the stack ER at most once.Proof.
If an arc (i, j) appears in the breadth-first search tree in Step 2 of a certain loop, then, after the end of that loop, the arc (i, j) must have label B (because it has already been inserted into the set EB). During each subsequent loop execution, any arc segment (i, j) inserted into the breadth-first search tree does not have label B before it is inserted, so the arc segment (i, j) cannot be inserted into the breadth-first search tree again during any of the subsequent loop executions. Thus Proposition 5 is proved.
(2) Time Complexity of the Algorithm
It can be seen from the description of the algorithm that the difficulty in analyzing its time complexity lies in the loops from Step 1 to Step 4, of which there |V| at most. The time complexity cost in the execution of the algorithm consists mainly of the following three components:(1)
The time cost of all nodes that are put into or are removed from the queueVR(2)
The time cost of constructing a breadth-first search tree and inserting and removing arcs from the stackER(3)
The time cost of calculating the minimum travel timeμi,j via all arcs (i, j) to the endpoint D
Let(16)N=maxiN+i,N−i.Theorem 5.
From the beginning to the end of the algorithm, during the construction of the breadth-first search tree, including the operations on all nodes that are put into or taken out of the queueVR and on all arcs that are put into or taken out of the stack ER, the total complexity cost in computation time is OV+N⋅E.Proof.
The proof of the theorem is divided into three steps.
In the first step, we first prove that, during the process from the beginning to the end of the algorithm, the computation time complexity cost of all arcs that are put into or taken out of the stackER (i.e., into or out of the breadth-first search tree) is ON⋅E. As can be seen from Proposition 5, any arc segment i,j∈E is put into and taken out of the breadth-first search tree at most once, i.e., into and out of the stack ER at most once. According to the operation of the algorithm, for each i,j that is put into and taken out of the stack ER, the time cost of entering ER is O1, so for all the arcs i,j that are put into and taken out of ER, the total cost of entering ER is OE. For each arc i,j that is put into and taken out of the stack ER, there is an operation of removing i,j from the stack ER and inserting it into the stack EB, and the time complexity of this part of the operation is O1. There is also the operation of searching for node i in the set Nn−j and deleting it from this set, the time complexity cost of which is ON; hence the time complexity of removing the arc i,j from the stack ER is ON. Therefore, for all the arcs i,j that are put into and taken out of the stack ER, the total time cost when they are moved out of ER is ON⋅E. In summary, the total time cost of all the arcs i,j that are put into and taken out of the stack ER is ON⋅|E|.
In the second step, we prove that, for all the nodesi that are put into and taken out of the queue VR , the time cost when they are removed from VR is OV. From Theorem 3, for an arbitrary node i∈V, in the execution of the algorithm from beginning to end, node i enters and exits the queue VR at most once. According to the operation of the algorithm, for each node i that is put into and taken out of VR, the time cost when it is taken out of VR is O1. Therefore, for all nodes i that are put into and taken out of the queue VR , the total time cost when they are removed from VR is OV.
In the third step, we prove that, for each nodei that is put into and taken out of the queue VR, the time cost when it is inserted into VR is OE. For any node ii that is put into and taken out of the queue VR, two situations can occur: in one, node i is the predecessor node of a node v that is about to be moved out of VR (i.e., i∈Nn−v); in the other, node i is the predecessor node of the endpoint l of the arc (j, l) in the breadth-first search tree that has been constructed. In the former situation, when node i is inserted into the queue VR, all the nodes in the set Nn−v that are not included in the queue VR are inserted into VR, which is equivalent to beginning from node v, searching for all the arcs i,v that satisfy the conditions i∈Nn−v and i∉VR, and then inserting node i into the set VR. Therefore, from the beginning to the end of the algorithm, the time cost of all the nodes that are inserted into the queue VR, because they are predecessor nodes of a certain node that was removed from VR, is OE. In the second situation, when the node i is inserted into the queue VR, all the nodes that are in the set Nn−l and do not belong to VR are inserted into VR. This is equivalent to starting from node l, scanning and searching for all the arcs i,l that satisfy the conditions i∈Nn−l and i∉VR, and inserting node ii into the set VR; then Nn−l=Ø holds. Therefore, in this loop or later loops, when we search for an arc k,l that has the same endpoint as the arc segment j,l from the stack ER, because Nn−l=ø, the arc segment i,l that was previously scanned and searched for no longer needs to be searched for. By Proposition 5, any arc segment j,l∈E is inserted into and removed from the breadth-first search tree at most once in the V iterations at most of the algorithm. Therefore, for any node l∈V, each arc i,l that satisfies the condition i∈Nn−l needs at most one scan to search for node i and inserted it into VR. Hence the time complexity of all those nodes that are inserted into VR because they are predecessors of the endpoint of the arc j,l in the breadth-first search tree is OE.
In summary, from the beginning to the end of the algorithm, during the construction of the breadth-first search tree, including the operations on all nodes that are put into and taken out of the queueVR and all arcs that are put into and taken out of the stack ER, the total computation time complexity cost is OV+N⋅E. Thus Theorem 5 is proved.Theorem 6.
Using ROLA, the complexity cost of calculating the minimum time for all arcs inE to reach the destination D is ON⋅E, and(17)μi,j=minl∈N+jϕi,j+θi,j,l+μj,l,where(18)ϕi,j∈Ψ,θi,j,l∈Θ,j∈N+i,l∈N+j,(19)μi,D=φi,D,∀i∈N−D.Proof.
For arbitraryi,j∈E in the process of calculating μi,j according to the above recursion formula, it is necessary to calculate N+j times the following expression and then to perform N+j−1 comparison operations.(20)ϕi,j+θi,j,l+μj,l.
In each calculation using this expression, there are two addition operations, so the time complexity cost of calculatingμi,j for one arc segment i,j is ON. Therefore, the complexity cost of calculating the minimum time through all arcs in E to the endpoint D is ON⋅E, where N=maxiN+i,N−i. Thus Theorem 6 is proved. The following theorem is apparent from Theorems 5 and 6.Theorem 7.
The time complexity of the ROLA in a time-invariant network isOV+N⋅E.
It can be seen that the time complexity of the ROLA is a polynomial in the number of nodes (V), the number of edges (E), the maximum number of predecessors, and the number of subsequent nodes (N) in the network. The time complexity of the algorithm is low.


## 5.1.1. Basic Formula

Letλi,j,k denote the minimum travel time starting from the first node i of the road section (i, j) and passing through this section, then through intersection j and the section (j, k) to the endpoint D. Then, the following recursion formula holds(6)λi,j,k=minl∈N+kϕi,j+θi,j,k+λj,k,l,where(7)λi,D,D=ϕi,D,∀i∈N−D.From the results in the preceding subsection, it follows that(8)λi,D=minj∈N+i,k∈N+jλi,j,k.Letμi,j denote the minimum travel time from the first node i of the road section (i, j) passing through this section (i, j) and through intersection j to the destination D. Then,(9)μi,j=mink∈N+jλi,j,k,μi,j can also be calculated from the recursion formula as follows:(10)μi,j=minl∈N+jϕi,j+θi,j,l+μj,l,where(11)ϕi,j∈Ψ,θi,j,l∈Θ,j∈N+i,l∈N+j,(12)μi,D=ϕi,D,∀i∈N−D.We recordj,πμi,j as the road section following the section (i, j) on the minimum-travel-time path via (i, j) to the destination D, where(13)πμi,j=argminl∈N+jϕi,j+θi,j,l+μj,l.We denote the minimum travel time from the starting point SS to the destinationD by φS,D, and we record πφi as the successor node of node i for this path. From the above analysis, it follows that(14)φS,D=argminj∈N+SμS,j,(15)πφi=argminj∈N+iμi,j.


## 5.1.2. Overview of the Algorithm

To solve the problem in this article, a new improved Dijkstra algorithm was proposed, named Reverse Order Labeling Algorithm (ROLA). It gradually explores the minimum-travel-time paths through one (or several) arcs (i, j) starting from a certain node i (or some nodes) to the destination D. During the execution of the algorithm, a value μi,j is calculated for the minimum travel time through a given arc (i, j) to the endpoint D, and the arc (i, j) is labeled with a B (black arc). Then, the minimum travel time through all the arcs (k, i) ending at node i to the destination D is calculated. In this process, if any arc that starts at node i has a label B (i.e., the minimum travel time from the arc to the endpoint is known); then, the minimum travel time from the arc (k, i) to the destination D is calculated directly from the recursion formula (5). If an arc starting at node i does not have a label B, then node i is taken as the tree root and arc segments without label B are taken as the search objects. According to the breadth-first search principle, all the arc segments without label B that start from or are connected with node i are searched for, and a breadth-first search tree is constructed. Any arc segment in the tree is labeled with R (red arc segment); then, the minimum travel time through any arc in the tree to the destination D is calculated and the arcs with label R in the tree are relabeled with B. Finally, the minimum travel time to the destination D via the arc (k, i) is calculated. As can be seen from this description, each step of the method modifies the labels of one or more arc segments, with some arc segments without label B acquiring such a label so that the number of arc segments with label B in the network G increases by at least one. Thus, after at most |V| iterations, the minimum-travel-time path through any arc segment starting with each node to the destination can be found. The minimum-travel-time path from the start point S to the destination D is also obtained. In each iteration of the algorithm, the set of arc segments of the directed network graph taking into account node attributes is divided into three subsets: a set of arcs with label B (EB), a set of arcs with label R (ER), and the set EP=E−EB∪ER (i.e., the complement of EB∪ER, a collection of purple arcs). Since it is performed in reverse order, a feature of the reverse order labeling algorithm is that when calculating the shortest path from the current arc segment to the endpoint, it can make full use of the obtained shortest-path data from the subsequent arc segment to the endpoint, which not only exploits all available resources but also saves calculation time. The execution of the algorithm is illustrated below with a specific example.We intercept a section of the network to illustrate two situations that occur during the calculation of the reverse order labeling method, as shown in Figures2 and 3, where the black solid arc (i, j) indicates that the minimum travel time μi,j from the arc (i, j) to the endpoint has been found, i.e., the arc (i, j) has label B. Assuming that the current scanning node is node 2, it is necessary to compute the minimum travel time μi,j from the arc (1, 2) (the purple dashed line) to the endpoint. In Figure 2, since the arc segments 2,j∀j∈N+2 are already arcs with label B, they can be calculated directly using the recursion formula (5). In Figure 3, when calculating the minimum travel time μ1,2 of the arc (1, 2) to the endpoint, because the arcs (2, 3) and (2, 4) starting with node 2 are not labeled B, we need to establish a breadth-first search tree taking node 2 as the root node. Then, all the arcs without label B (the purple dashed lines) that start from or are connected with node 2 are placed on the search tree and labeled R label (red dash dotted lines), as shown in Figure 4. The minimum travel times μ2,3, μ2,4, and μ3,4 of the arc segments (2, 3), (2, 4), and (3, 4) to the endpoint in the tree are calculated, and finally the minimum travel time μ1,2 from the arc (1, 2) to the endpoint is calculated.Figure 2
First case.Figure 3
Second case.Figure 4
Breadth-first search tree.


## 5.1.3. Specific Steps of the Algorithm

Given a directed graphG=V,E,Θ,Ψ, node set V, edge set E, node attribute value set Θ, edge attribute value set Ψ, and endpoint D as follows:Step 0. BEGIN. Let EB=ø, ER=ø, VR=v|v∈D; for any i∈V, let Nn+i=N+i, Nn−i=N−i, n = 1.Step 1. Check whether EB=E holds. If it does, then go to Step 5; otherwise, go to Step 2.Step 2. Take one v∈VR, and check whether Nn+v=ø holds. (1) If it does, then go to Step 3. (2) If it does not hold, i.e., there exists at least one j∈N+v, make v,j∉EB (this means that the arc (v, j) does not have label B); then follow the steps below:Step 2.1. Taking the node vv as the tree root on the directed graph G=V,E,Θ,Ψ, take the arc segment without label B as the search object, construct a breadth-first search tree according to the breadth-first search principle, and select all arc segments (i, l) such that l∈Nn+i and (i, l) is not in the breadth-first search tree (i.e., (i, l) has neither label B nor label R); insert (i, l) into the breadth-first search tree and into the stack ER(i.e., label the arc segment (i, l) with R), and delete l from l∈Nn+i, until the search process is no longer able to find an arc segment that has neither a label B nor a label R.Step 2.2. Take the arcs (i, l) from the stack ER one by one, put each node from the node set Nn−l−VR into the queue VR (the node is labeled R), and for each arc (i, l); then calculateμi,l=minj∈N+lϕi,l+θi,l,j+μl,jand recordπμi,l=argminj∈N+lϕi,l+θi,l,j+μl,jγi,l=l,πμi,lInsert the arc segment (i, l) into EB and search for node i from Nn−l and delete it. Repeat these operations until the stack ER is empty, then go to Step 3.Step 3. Check whether Nn−v=ø holds. (1) If it does, then delete v from VR and go to Step 4. (2) Otherwise, for arbitrary i∈Nn−v, if i∉VR, insert i into VR, insert (i, v) into EB, delete v from Nn+i, delete i from Nn−v, delete v from VR; then calculateμi,v=minj∈N+vϕi,v+θi,v,j+μv,jand recordπμi,v=argminj∈N+vϕi,v+θi,v,j+μv,jγi,v=v,πμi,v.Go to Step 4.Step 4. Let n = n + 1, and go to Step 1.Step5. CalculateφS,D=argminj∈N+iμS,jfrom which the minimum travel time from the start pointS to the endpoint D is obtained.Step 6. Construct the optimal path from the start node S to the destination D by πμi,v,πφS=argminj∈N+iμS,j and γi,v END.The steps for constructing the breadth-first search tree algorithm in the algorithm subroutines in Steps 2.1 and 2.2 are as follows:Step 0. BEGIN. Let EY=v,v.Step 1. Check whether EY=ø holds. (1) If it does, then go to Step 3; (2) Otherwise, take an arc segment i,j∈EY If Nn+j is not empty, take out k∈Nn+j sequentially, insert arc segments (j, k) into the stack ER in turn, and record Fj,k=i,j, until Nn+j is empty. Go to Step 2.Step 2. Remove (i, j) from EY, and go to Step 1.Step 3. Output the collection stack ER END.Whether or not the setEY is empty controls whether or not the loop ends. Fj,k=i,j indicates that the subarc of the arc (i, j) on the breadth-first search tree is (j, k).


## 5.1.4. Modular Flow Chart of ROLA

To give a clearer explanation of the execution process of the algorithm, this section presents the pseudocode of the ROLA in modules corresponding to the specific steps of the algorithm.The execution of the ROLA involves the construction of the breadth-first search tree, the data structure of the queue, and the stack. The breadth-first search algorithm is one of the basic graph search algorithms. Both the Dijkstra single-source shortest path algorithm and the Prim minimum spanning tree algorithm use a similar idea to breadth-first search and belong to the class of blind search methods, which systematically expand and examine all the nodes of a graph to obtain their results. Stacks and queues are two linear data structures that are widely used in programming: a stack operates according to the rule “last-in, first-out” (insert (L, n + 1, x) and delete (L, n)), whereas a queue operates according to the rule “first-in, first-out” (insert (L, n + 1, x) and delete (L, 1)). The algorithm performs enqueue and dequeue operations on the nodes during its execution. Because the enqueue operation starts from the endpoint, nodes close to the endpoint are placed in the queue first, and based on the “first-in, first-out” rule, nodes near the end will be dequeued first and processed first, which matches the reverse order basis of the reverse order labeling method. When constructing the breadth-first search tree, beginning with the root v, the non-B-labeled arc segments that are searched for are pushed into the stack until the search switches to the B-labeled arc segments. After this search has been completed, the pop-up stack operation is performed on the arc according to the “last-in, first-out” rule, which ensures that the minimum travel times from the arcs nearest the endpoint are calculated first, from near-to-far, and only then, the minimum travel times from arcs far from the endpoint are calculated, which is again in accordance with the reverse order labeling method.The ROLA composed of four modules as follows: the breadth-first search tree construction process (Module 1), the arc pushing and popping stack process (Module 2), the node enqueue and dequeue process (Module 3), and the optimal path output (Module 4). In order to understand the relationship between each module more clearly and intuitively, we use pseudo to describe. The pseudo of module 1 to module 4 is shown in the Algorithms1–4.Algorithm 1:Breadth-first search tree (Module 1).
(1)
BFS(G, v)% Given,G=V,E,Θ,Ψ node v as the root of the tree, to construct a breadth-first search tree using the arcs without the B label.(2)
for eachi,l∉EB∪ERdo(3)
Color ← i,l←red(4)
endAlgorithm 2:Arc stack operation (Module 2).
(1)
Push (stackER,i,l);% Select each arc (i, l) that satisfies the condition l∈Nn+i and is not on the breadth-first search tree, insert it into the breadth-first search tree, and insert such arcs (i, l) into the stack ER in turn (the arc ER is marked as R)(2)
do(3)
EB=ER∪i,l;(4)
Nn+i=Nn+i−l;% Remove nodel from the set of successor nodes of node i(5)
Untili,l∉EB&&i,l∉ER;% Breadth-first search tree construction completed(6)
Pop(stack, ER);(7)
WhileER=ø% when the optimal path from all arcs on the tree to the destination has not been obtained, proceed as follows(8)
do(9)
Color ← i,l←Black;(10)
ER=ER−i,l;(11)
μi,l=minj∈N+lϕi,l+θi,l,j+μl,j(12)
πμi,l=argminj∈N+lϕi,l+θi,l,j+μl,j(13)
γi,l=l,πμi,l% Calculate the minimum time from each arc segment on the breadth-first search tree to the destination in the stacking order and record the path.(14)
then(15)
Nn−l=Nn−l−i% Delete nodei from the predecessor node of node l(16)
EndAlgorithm 3:Node queue operation (Module 3).
(1)
DeQueue(VR)% Select each arc (i, l) that satisfies the condition l∈Nn+i and is not on the breadth-first search tree, insert it into the breadth-first search tree, and insert such arcs (i, l) into the stack ER in turn (the arc ER is marked as R)(2)
forv∈VR&&Nn+v=ø do % take a node v from the queue VR(3)
ifNn−v=øthen(4)
VR=VR−v;% Determine whether nodev is isolated, if it is, delete node v from the queue VR.(5)
else(6)
for eachi∈Nn−v;% Perform the following operations for each predecessor nodei of the node v.(7)
ifi∉VR do(8)
EnQueueVR,i;(9)
VR=VR∪i; % insert node i into the queue VR(10)
EB=EB∪i,v;% insert (i, v) into the set EB and mark it as a black arc.(11)
μi,v=minj∈N+vϕi,v+θi,v,j+μv,j(12)
πμi,v=argminj∈N+vϕi,v+θi,v,j+μv,j(13)
γi,v=v,πμi,v% Calculate the optimal path from all arc segments (i, v) with v as the end node to the destination.(14)
then(15)
Nn+i=Nn+i−v; % RemovevfromNn+i.(16)
Nn−v=Nn−v−i; % Remove i from.(17)
VR=VR−v;% Removevfrom the queueVR(18)
UpdateEB(19)
EndAlgorithm 4:Optimal path result output (Module 4).
(1)
Output (·)(2)
φS,D=minj∈N+SμS,j;% obtain the minimum time from start nodeS to destination D.(3)
πφS=argminj∈N+iμS,j;% obtain the subsequent nodes of the node S on the optimal path.(4)
πμi,v=argminj∈N+vϕi,v+θi,v,j+μv,j;% obtain the subsequent arc (v, j) of arc (i, v) on the optimal path from arc (i, v) to destination D.(5)
γi,v=v,πμi,v;% record the subsequent arc of arc (i, v) on the optimal path as v,πμi,v(6)
S,πφS⟶γS,πφS⟶γγS,πφS,…,D,D;% obtain the best path from startS to destination D.(7)
endIt can be seen from Algorithm5 that each module has an interface connected with one or more of the other modules. So the modules are not isolated but closely related. After initialization, Module 1 or Module 4 is selected for execution by checking whether the condition EB=E holds. Module 1 is directly connected to Module 2, indicating that Module 2 is executed after Module 1 has been completed. Similarly, Module 2 is directly connected to Module 3. After Module 3 has been executed, by checking whether or not EB=E holds, the algorithm decides to go to the next iteration or to exit the program after executing Module 4.Algorithm 5:Relationship between modules.
Initialization:G=V,E,Θ,Ψ, n=1,ER=ø, VR=v|v=D, EB=ø, for ∀i∈V,Nn+i=N+i, Nn−i=N−iResult:A SequenceΠ:=S,i,i,j,…,D,DMain procedure(1)
ifEB≠E(2)
for∀v∈VR(3)
ifNn+v=ø% ifNn+v=ø directly performs node vv queue operation (i.e. Module 3)(4)
execute Module 3;(5)
ifEB≠E(6)execute Module 1;(7)
else(8)
execute Module 4;(9)
else(10)
execute Module 1;% perform the breadth-first search tree construction operation withv as the root node(11)
execute Module 2;% perform push and pop operations on the arcs on the breadth-first search tree constructed(12)
execute Module 3% when all the arcs in the stackER are popped out of the stack, perform the queue operation of node v(13)
ifEB≠E(14)
execute Module 1;% ifEB≠E, enter the next loop of the algorithm, first perform the operation of building breadth-first search tree(15)
else(16)
execute Module 4;% ifEB=E, the algorithm loop termination condition is met, execute the algorithm’s route output operation(17)
else execute Module 4;(18)
end.


## 5.1.5. Correctness of the Algorithm and Proof of Time Complexity

(1) Correctness of the AlgorithmProposition 1.
Before then-th loop execution of the algorithm, if node i already exists in the queue VR, it cannot be inserted into VR again during the n-th loop execution; i.e., during the execution of the algorithm, it is impossible for the same node to appear more than once in the queue VR.PROOF.
This proposition follows clearly from the way in which the algorithm is executed.Proposition 2.
If a nodei∈VR is deleted from VR in the n-th loop execution of the algorithm, then Nn+i=ø must hold after the n-th loop execution; so, for arbitrary m > n, node i cannot be inserted into VR again during the m-th loop execution.Proof.
For any nodei∈VR, if node i is deleted from the queue VR during the n-th loop execution of the algorithm, then after the Step 2 and Step 3 operations in the n-th loop execution, Nn+i=ø a must hold. For any m > n, before the m-th loop execution, Nn+i=ø also holds; and during the m-th loop execution, before a certain node j can be inserted into the queue VR, Nn+j=ø a must hold. Therefore, during the m-th loop execution of the algorithm, node i cannot be inserted into the queue VR, and the proposition is proved.Proposition 3.
After the end of a certain loop execution of the algorithm, ifEB≠E holds, then VR≠ø must hold.Proof.
After the end of a certain loop execution of the algorithm, ifEB≠E holds, then there must exist a certain arc segment (i, j) without label B, and k∈N+j, j,k∈EB, and it is obvious that Nn+i=ø and N+j=ø hold. It is then known from Proposition 2 that node i is either in the queue VR or is not in the queue and has never entered it. If it is assumed that node i is not in the queue VR and has never entered it, then, because the arc segment (j, k) has a label B, node i must have been inserted into VR during the procedure of inserting the arc (j, k) into the set EB, which is contradictory; hence the assumption is not true. Therefore, if EB≠E holds, VR≠ø must hold, and Proposition 3 is proved.
From Propositions1–3, it is easy to derive the following theorem.Theorem 3.
During the execution of the algorithm, any nodei∈V enters and exits the queue VR at most one time, so there can be no more than |V| loops from Step 1 to Step 4 of the algorithm.Proposition 4.
The ROLA has the following loop invariance: before the start of then-th loop, if all the arcs in the set EB have label B, then all the arcs in EB still have label B before the start of the (n + 1)-th loop. The proof of this is omitted here.
From Theorem4 and Propositions 3, and 4, the following theorem can be obtained.Theorem 4.
During the |V||V| loops (at most) from Step 1 to Step 4 of the ROLA, the condition EB=E holds; i.e., for any arc segment i,j∈E, the minimum travel time μi,j though the arc segment (i, j) to the endpoint D can be obtained.Proposition 5.
For any arc segmenti,j∈E, during the |V| loops (at most) from Step 1 to Step 4 of the ROLA, the arc segment (i, j) is put no more than once into the breadth-first search tree that is constructed so that it goes into and out of the stack ER at most once.Proof.
If an arc (i, j) appears in the breadth-first search tree in Step 2 of a certain loop, then, after the end of that loop, the arc (i, j) must have label B (because it has already been inserted into the set EB). During each subsequent loop execution, any arc segment (i, j) inserted into the breadth-first search tree does not have label B before it is inserted, so the arc segment (i, j) cannot be inserted into the breadth-first search tree again during any of the subsequent loop executions. Thus Proposition 5 is proved.
(2) Time Complexity of the Algorithm
It can be seen from the description of the algorithm that the difficulty in analyzing its time complexity lies in the loops from Step 1 to Step 4, of which there |V| at most. The time complexity cost in the execution of the algorithm consists mainly of the following three components:(1)
The time cost of all nodes that are put into or are removed from the queueVR(2)
The time cost of constructing a breadth-first search tree and inserting and removing arcs from the stackER(3)
The time cost of calculating the minimum travel timeμi,j via all arcs (i, j) to the endpoint D
Let(16)N=maxiN+i,N−i.Theorem 5.
From the beginning to the end of the algorithm, during the construction of the breadth-first search tree, including the operations on all nodes that are put into or taken out of the queueVR and on all arcs that are put into or taken out of the stack ER, the total complexity cost in computation time is OV+N⋅E.Proof.
The proof of the theorem is divided into three steps.
In the first step, we first prove that, during the process from the beginning to the end of the algorithm, the computation time complexity cost of all arcs that are put into or taken out of the stackER (i.e., into or out of the breadth-first search tree) is ON⋅E. As can be seen from Proposition 5, any arc segment i,j∈E is put into and taken out of the breadth-first search tree at most once, i.e., into and out of the stack ER at most once. According to the operation of the algorithm, for each i,j that is put into and taken out of the stack ER, the time cost of entering ER is O1, so for all the arcs i,j that are put into and taken out of ER, the total cost of entering ER is OE. For each arc i,j that is put into and taken out of the stack ER, there is an operation of removing i,j from the stack ER and inserting it into the stack EB, and the time complexity of this part of the operation is O1. There is also the operation of searching for node i in the set Nn−j and deleting it from this set, the time complexity cost of which is ON; hence the time complexity of removing the arc i,j from the stack ER is ON. Therefore, for all the arcs i,j that are put into and taken out of the stack ER, the total time cost when they are moved out of ER is ON⋅E. In summary, the total time cost of all the arcs i,j that are put into and taken out of the stack ER is ON⋅|E|.
In the second step, we prove that, for all the nodesi that are put into and taken out of the queue VR , the time cost when they are removed from VR is OV. From Theorem 3, for an arbitrary node i∈V, in the execution of the algorithm from beginning to end, node i enters and exits the queue VR at most once. According to the operation of the algorithm, for each node i that is put into and taken out of VR, the time cost when it is taken out of VR is O1. Therefore, for all nodes i that are put into and taken out of the queue VR , the total time cost when they are removed from VR is OV.
In the third step, we prove that, for each nodei that is put into and taken out of the queue VR, the time cost when it is inserted into VR is OE. For any node ii that is put into and taken out of the queue VR, two situations can occur: in one, node i is the predecessor node of a node v that is about to be moved out of VR (i.e., i∈Nn−v); in the other, node i is the predecessor node of the endpoint l of the arc (j, l) in the breadth-first search tree that has been constructed. In the former situation, when node i is inserted into the queue VR, all the nodes in the set Nn−v that are not included in the queue VR are inserted into VR, which is equivalent to beginning from node v, searching for all the arcs i,v that satisfy the conditions i∈Nn−v and i∉VR, and then inserting node i into the set VR. Therefore, from the beginning to the end of the algorithm, the time cost of all the nodes that are inserted into the queue VR, because they are predecessor nodes of a certain node that was removed from VR, is OE. In the second situation, when the node i is inserted into the queue VR, all the nodes that are in the set Nn−l and do not belong to VR are inserted into VR. This is equivalent to starting from node l, scanning and searching for all the arcs i,l that satisfy the conditions i∈Nn−l and i∉VR, and inserting node ii into the set VR; then Nn−l=Ø holds. Therefore, in this loop or later loops, when we search for an arc k,l that has the same endpoint as the arc segment j,l from the stack ER, because Nn−l=ø, the arc segment i,l that was previously scanned and searched for no longer needs to be searched for. By Proposition 5, any arc segment j,l∈E is inserted into and removed from the breadth-first search tree at most once in the V iterations at most of the algorithm. Therefore, for any node l∈V, each arc i,l that satisfies the condition i∈Nn−l needs at most one scan to search for node i and inserted it into VR. Hence the time complexity of all those nodes that are inserted into VR because they are predecessors of the endpoint of the arc j,l in the breadth-first search tree is OE.
In summary, from the beginning to the end of the algorithm, during the construction of the breadth-first search tree, including the operations on all nodes that are put into and taken out of the queueVR and all arcs that are put into and taken out of the stack ER, the total computation time complexity cost is OV+N⋅E. Thus Theorem 5 is proved.Theorem 6.
Using ROLA, the complexity cost of calculating the minimum time for all arcs inE to reach the destination D is ON⋅E, and(17)μi,j=minl∈N+jϕi,j+θi,j,l+μj,l,where(18)ϕi,j∈Ψ,θi,j,l∈Θ,j∈N+i,l∈N+j,(19)μi,D=φi,D,∀i∈N−D.Proof.
For arbitraryi,j∈E in the process of calculating μi,j according to the above recursion formula, it is necessary to calculate N+j times the following expression and then to perform N+j−1 comparison operations.(20)ϕi,j+θi,j,l+μj,l.
In each calculation using this expression, there are two addition operations, so the time complexity cost of calculatingμi,j for one arc segment i,j is ON. Therefore, the complexity cost of calculating the minimum time through all arcs in E to the endpoint D is ON⋅E, where N=maxiN+i,N−i. Thus Theorem 6 is proved. The following theorem is apparent from Theorems 5 and 6.Theorem 7.
The time complexity of the ROLA in a time-invariant network isOV+N⋅E.
It can be seen that the time complexity of the ROLA is a polynomial in the number of nodes (V), the number of edges (E), the maximum number of predecessors, and the number of subsequent nodes (N) in the network. The time complexity of the algorithm is low.


## 5.2. Calculation Example

A simple directed graph is used to illustrate the execution process of the algorithm. As shown in Figure5, the directed graph G is composed of 11 nodes and 18 edges. The arrows indicate the direction of travel on each road section. Node 11 is a given starting point and node 1111 is the given destination. The travel time values ϕi,j on the arcs i,j are shown in Table 2, and the waiting time values θi,j,k of the arc i,j selected different arcs j,k at the nodes j are shown in Table 3.Figure 5
Directed graph representing a time-invariant network.Table 2
Edge attribute value.
ϕ1,2ϕ1,3ϕ1,4ϕ2,5ϕ2,6ϕ3,2243222ϕ3,7ϕ4,7ϕ4,8ϕ5,9ϕ6,9ϕ6,10345232ϕ7,10ϕ8,10ϕ8,11ϕ9,11ϕ10,9ϕ10,11455645Table 3
Node attribute value.
θ1,2,5θ1,2,6θ1,3,2θ1,3,7θ1,4,7θ1,4,8131232θ2,5,9θ2,6,9θ2,6,10θ3,2,5θ3,2,6θ3,7,10133214θ4,7,10θ4,8,10θ4,8,11θ5,9,11θ6,9,11θ6,10,9223223θ6,10,11θ7,10,9θ7,10,11θ8,10,9θ8,10,11θ10,9,11443321Our goal is to calculate the minimum travel time path from each arc segment to the destination and the minimum travel time path from the starting node 11 to the destination 1111 in the network. When the intersection attribute (weight or time cost) is not considered, the minimum time path from the starting node 11 to the endpoint 1111 is1⟶2⟶6⟶10⟶11 obtained by the Dijkstra algorithm, and the travel time is 11.The Reverse Order Labeling Algorithm given in this paper is used to solve the minimum time path from node 11 to node 11 in Figure5 considering the waiting time of the node. The specific calculation process is omitted here. After 9 iterations of calculation, the data in Table 4 are obtained when the algorithm terminates. Including the minimum time path of each arc in the directed graph to the end and the travel time value. Let(21)φ1,11=minj∈N+1μ1,j=μ1,2=16.Table 4
Algorithm execution result.
μ10,11=5,γ10,11=11,11μ10,9=11,γ10,9=9,11μ9,11=6,γ9,11=11,11μ8,11=5,γ8,11=11,11μ8,10=12,γ8,10=10,11μ7,10=12,γ7,10=10,11μ6,10=10,γ6,10=10,11μ6,9=11,γ6,9=9,11μ5,9=10,γ5,9=9,11μ4,8=12,γ4,8=8,11μ4,7=18,γ4,7=7,10μ3,7=19,γ3,7=7,10μ3,2=17,γ3,2=2,5μ2,6=15,γ2,6=6,10μ2,5=13,γ2,5=5,9μ1,4=17,γ1,4=4,8μ1,3=22,γ1,3=3,7μ1,2=16,γ1,2=2,5According toγi,j, the minimum expected time path from the starting point 11 to the destination 11 is 1⟶2⟶5⟶9⟶11, and the minimum travel time is 16.


## 6. Simulation Comparison Experiment

### 6.1. Actual Urban Network Simulation of ROLA

This section presents an example of the use of the ROLA to solve a path planning problem in an actual urban transportation network. We implement the algorithm in MATLAB on an Intel Core i3-550 processor at 3.20 GHz with 4 GB memory on a Windows 10 32-bit operating system. The data of the passing time for each road section and the waiting times for different turns at the intersections in the selected area are randomly generated by the simulation software.


#### 6.1.1. Map Selection and Graphics

To provide a realistic example of the shortest-path optimization problem in an actual road network taking account of the waiting times at intersections, the road traffic map of Tianjin was selected as the research object, shown by the red lines in Figure6.Figure 6
Target road network.The roads and their intersections in the selected area are represented by the 39 edges and 25 nodes in the map, as shown in Figure7, where the arrows indicate the directions of travel on the road sections. The travel time ϕi,j on each edge and the time spent θi,j,k on each node are all uniformly distributed with U [1, 10]. The goal of the optimization is to obtain the minimum-time path from N1 to N25 in the directed graph.Figure 7
Graphical representation of the selected road network.The diagram of the simulated road network as drawn in MATLAB according to the relationship between nodes and edges is shown in Figure8.Figure 8
Road network simulation diagram.


#### 6.1.2. Simulation Program Design

The experimental program consists of four sections: two data input sections, the algorithm section (the most important part), and a framework for data processing, data transmission, and display of the results. A simple menu interface is displayed in the main window of MATLAB. To facilitate the functions of calling input and calculation using the menu, the functions of each section are written as independent.m files, which are listed together with their functions in Table5. An error handling function is integrated. For example, when the start and endpoints of the shortest path are input, the program will judge whether the start point and the endpoint are the same. If they are equal, an error message will be output. The connections between them are illustrated in Figure 9.Table 5
List of M files and their functions.
menu.mDisplays the menu and calls other functions. It is the entrance to the program.ROLA.mPerforms the ROLA operation on the data input and returns the result. It is the core of the program.input_arc.mCalls the arc travel time data to generate the adjacency matrix and return it.input_node.mCalls the node travel time data to generate the adjacency matrix and return it.Figure 9
Call relationship of each section of the program.


#### 6.1.3. ROLA Simulation Result

The data needed in the algorithm is represented by the adjacency matrix. Because MATLAB language itself is used for matrix calculation and has inherent advantages for matrix calculation. Usearc_datai,j represent the travel time of any arc i,j, and node_datai,j,k represent the waiting time of arc i,j tuning arc j,k. Since we are studying a directed graph, in general: arc_datai,j≠arc_dataj,i and node_datai,j,k≠node_datak,j,i, if there is no path from i to j, then arc_datai,j=∞ and node_datai,j,k=∞. For a network with n nodes, arc_datai,j is a n∗n two-dimensional matrix, and node_datai,j,k is a n∗n∗n three-dimensional matrix.The simulation procedure is as follows: start MATLAB (version 7.11.0 R2010b), put all.m files into the MATLAB search path, enter the “menu” in the MATLAB interface, and output the main menu. Enter “1” to input the adjacency matrix of the arc. The program prompts success and outputs the menu again. Enter “2” to input the node adjacency matrix. The program then prompts success and outputs the menu again. Enter “3” to view the data and output the array ofarc_data and node_data. Enter “4” to find the path, obtain the minimum-time path from the given arc to the destination and the minimum-time path from the starting node to the destination, and arbitrarily select two target arcs for verification.Because there are 39 edges in the network, the fourth step is performed 39 times to find the minimum-time paths and values for all the arcs to the endpoint. It is easy to find the subsequent arcs on the optimal path from each arc to the endpoint. The minimum-time path from the starting node N1 to the destination node N25 is N1⟶N2⟶N7⟶N12⟶N13⟶N14⟶N15⟶N20⟶N23⟶N25. The travel time is 67.8, and the CPU running time of the simulation is 0.0238s. The optimal simulation route is shown in Figure 10 by the thick gray arrows and the corresponding optimal route on the map is shown in Figure 11.Figure 10
Optimal route simulation.Figure 11
Optimal route on the map.By calling the traditional Dijkstra algorithm in the MATLAB simulation environment, we easily obtain the minimum-time path from the starting point N1 (do not consider node attribute) to the destination N25 (do not consider node attribute) is N1⟶N2⟶N7⟶N12⟶N13⟶N14⟶N15⟶N20⟶N23⟶N25, with travel time 45.6.It can be seen from the simulation results for the above two cases that the same optimal paths (under the coincidence) are obtained but with different values, which depending on whether or not node attributes are taken into account.


### 6.2. Comparative Simulation Experiment

#### 6.2.1. Test Environment and Parameter Settings

In this section, in order to measure the performance of the algorithm ROLA proposed in this paper and the more widely used algorithms [34], we have conducted extensive simulation experiments, and the implemented algorithms include PSO, ACO, GA, NNA, and OPABRL [4]. Table 6 gives the parameter settings of each algorithm.Table 6
Parameters setting.
AlgorithmParametersValueACOAnt number m80Heuristic factor a1Pheromone volatilityρ0.3GAPopulation sizeM100Cross probabilityP10.6Mutation probabilityp20.01NNANetwork layers3Number of input nodes6Number of output nodes1Number of hidden layer nodes12PSOParticle swarm size80Learning factorc11.5Learning factorc22.0Inertia weight parameterω0.9OPABRLLearning factorα0.7Discount factorθ1Greedy strategyε0.5The simulation process will be carried out on the MATLAB platform (same as above). Under the condition of selecting the same starting node and destination node, we compare the differences among the path obtained by different algorithms. The main measurement indicators include (1) algorithm convergence speed; (2) algorithm running time.We select 10 groups of networks with different numbers of nodes and edges. The grouping is shown in Table7. The number of network nodes, respectively, are 50,100,…,500, and the number of corresponding arc segments, respectively, are 100,250,…,1450. Regarding the composition of each group of the network, similar to Figure 7, each node is connected to at least one other node and at most six other nodes. Starting from the first node, each node is numbered from near to far, and the first node is the starting node and the last node is the destination. Same as before, for the network with n nodes,arc_datai,j is an n∗n two-dimensional matrix, and node_datai,j,k is a n∗n∗n three-dimensional matrix. The value of travel time ϕi,j for each arc is uniformly distributed with U[1, 5], the value of time spent θi,j,k for each node are uniformly distributed with U(1, 5). In the experiment, we need to call each algorithm to find the minimum time path from the starting node to the destination in each group of the network, each algorithm runs ten times for each group of networks, and the average value is taken as the statistics. The total number of runs of all algorithms is 500.Table 7
Grouping of networks selected.
NODE_COUNTARC_COUNTGROUP150100GROUP2100250GROUP3150400GROUP4200550GROUP5250700GROUP6300850GROUP73501000GROUP84001150GROUP94501300GROUP105001450


#### 6.2.2. Simulation Experiment Results and Analysis

The average iterations, path length change, running time of the proposed ROLA, and the other five comparison algorithms running ten times in each network size are shown in Table8.Table 8
Statistics of experimental results.
Statistical indicatorsMethodNODE 50NODE 100NODE 150NODE 200NODE 250NODE 300NODE 350NODE 400NODE 450NODE 500IterationsROLA3487104155202267349452495522PSO4393136203301399452469475479ACO51102165255342415455487492513GA60105134234331408464501512527NNA57110173265358422456478501526OPABRL3992125187258312341363371390Path lengthROLA9730351467581610231225142117322003PSO10630852269282410351243143617322014ACO11231052767982810441218142117472005GA11731053271283310291228143117292011NNA11431453370481910231237144017442025OPABRL10530651468381610311234142617532047Running time (ms)ROLA8621813697089141251162518441893PSO141904421004121315671617163916521666ACO211686071298159117601792182818341829GA301535241158153918221910192619341927NNA1542735731067133015481667174617621769OPABRL119238188799111621159121312311242The convergence rate of these algorithms is shown in Figures12–17 (here, we give the experimental results of the network with 100 nodes) where the x-axis represents the number of iterations and y-axis represents the shortest path length (travel time) change in the algorithm process. From the experiment result, we observed that, although there are fluctuations at the beginning, all the implemented algorithms can reach convergence after multiple iterations. The number of iterations for the proposed ROLA to reach convergence is significantly less than that of GA, NNA, and ACO, we also found there is some instability after the ant colony algorithm converges. Even though the ROLA fluctuates greatly at the beginning, under the same experimental environment, the algorithm can converge to the shortest path result earlier and has a better stability.Figure 12
Convergence rate of ROLA (NODE_COUNT = 100).Figure 13
Convergence rate of PSO (NODE_COUNT = 100).Figure 14
Convergence rate of ACO (NODE_COUNT = 100).Figure 15
Convergence rate of GA (NODE_COUNT = 100).Figure 16
Convergence rate of NNA (NODE_COUNT = 100).Figure 17
Convergence rate of OPABRL (NODE_COUNT = 100).Regarding the computational effort required by the different algorithms, Figure18 shows the average computational times (in milliseconds) for all considered algorithms for each instance size. In view of the results, the following points can be highlighted: (1) with the increase of network nodes, the running time of the other five algorithms increasing faster and faster, when the network nodes reach a certain number, the running time changes very little. However, the growth rate of running time changes for the ROLA changes very little, when the network nodes reach a certain number, and it also tends to be stable. (2) When network nodes are less than 350, the ROLA outperforms all the other algorithms. (3) When network nodes more than 350, the OPABRL outperforms all the other algorithms. Therefore, the running time performance of the proposed ROLA significantly outperforms other algorithms in the small to medium scale network.Figure 18
Running time of different algorithms.Through all experiments, it can be concluded that the ROLA in this paper is easy to implement and shows good practicability and high efficiency under certain conditions.


## 6.1. Actual Urban Network Simulation of ROLA

This section presents an example of the use of the ROLA to solve a path planning problem in an actual urban transportation network. We implement the algorithm in MATLAB on an Intel Core i3-550 processor at 3.20 GHz with 4 GB memory on a Windows 10 32-bit operating system. The data of the passing time for each road section and the waiting times for different turns at the intersections in the selected area are randomly generated by the simulation software.


### 6.1.1. Map Selection and Graphics

To provide a realistic example of the shortest-path optimization problem in an actual road network taking account of the waiting times at intersections, the road traffic map of Tianjin was selected as the research object, shown by the red lines in Figure6.Figure 6
Target road network.The roads and their intersections in the selected area are represented by the 39 edges and 25 nodes in the map, as shown in Figure7, where the arrows indicate the directions of travel on the road sections. The travel time ϕi,j on each edge and the time spent θi,j,k on each node are all uniformly distributed with U [1, 10]. The goal of the optimization is to obtain the minimum-time path from N1 to N25 in the directed graph.Figure 7
Graphical representation of the selected road network.The diagram of the simulated road network as drawn in MATLAB according to the relationship between nodes and edges is shown in Figure8.Figure 8
Road network simulation diagram.


### 6.1.2. Simulation Program Design

The experimental program consists of four sections: two data input sections, the algorithm section (the most important part), and a framework for data processing, data transmission, and display of the results. A simple menu interface is displayed in the main window of MATLAB. To facilitate the functions of calling input and calculation using the menu, the functions of each section are written as independent.m files, which are listed together with their functions in Table5. An error handling function is integrated. For example, when the start and endpoints of the shortest path are input, the program will judge whether the start point and the endpoint are the same. If they are equal, an error message will be output. The connections between them are illustrated in Figure 9.Table 5
List of M files and their functions.
menu.mDisplays the menu and calls other functions. It is the entrance to the program.ROLA.mPerforms the ROLA operation on the data input and returns the result. It is the core of the program.input_arc.mCalls the arc travel time data to generate the adjacency matrix and return it.input_node.mCalls the node travel time data to generate the adjacency matrix and return it.Figure 9
Call relationship of each section of the program.


### 6.1.3. ROLA Simulation Result

The data needed in the algorithm is represented by the adjacency matrix. Because MATLAB language itself is used for matrix calculation and has inherent advantages for matrix calculation. Usearc_datai,j represent the travel time of any arc i,j, and node_datai,j,k represent the waiting time of arc i,j tuning arc j,k. Since we are studying a directed graph, in general: arc_datai,j≠arc_dataj,i and node_datai,j,k≠node_datak,j,i, if there is no path from i to j, then arc_datai,j=∞ and node_datai,j,k=∞. For a network with n nodes, arc_datai,j is a n∗n two-dimensional matrix, and node_datai,j,k is a n∗n∗n three-dimensional matrix.The simulation procedure is as follows: start MATLAB (version 7.11.0 R2010b), put all.m files into the MATLAB search path, enter the “menu” in the MATLAB interface, and output the main menu. Enter “1” to input the adjacency matrix of the arc. The program prompts success and outputs the menu again. Enter “2” to input the node adjacency matrix. The program then prompts success and outputs the menu again. Enter “3” to view the data and output the array ofarc_data and node_data. Enter “4” to find the path, obtain the minimum-time path from the given arc to the destination and the minimum-time path from the starting node to the destination, and arbitrarily select two target arcs for verification.Because there are 39 edges in the network, the fourth step is performed 39 times to find the minimum-time paths and values for all the arcs to the endpoint. It is easy to find the subsequent arcs on the optimal path from each arc to the endpoint. The minimum-time path from the starting node N1 to the destination node N25 is N1⟶N2⟶N7⟶N12⟶N13⟶N14⟶N15⟶N20⟶N23⟶N25. The travel time is 67.8, and the CPU running time of the simulation is 0.0238s. The optimal simulation route is shown in Figure 10 by the thick gray arrows and the corresponding optimal route on the map is shown in Figure 11.Figure 10
Optimal route simulation.Figure 11
Optimal route on the map.By calling the traditional Dijkstra algorithm in the MATLAB simulation environment, we easily obtain the minimum-time path from the starting point N1 (do not consider node attribute) to the destination N25 (do not consider node attribute) is N1⟶N2⟶N7⟶N12⟶N13⟶N14⟶N15⟶N20⟶N23⟶N25, with travel time 45.6.It can be seen from the simulation results for the above two cases that the same optimal paths (under the coincidence) are obtained but with different values, which depending on whether or not node attributes are taken into account.


## 6.1.1. Map Selection and Graphics

To provide a realistic example of the shortest-path optimization problem in an actual road network taking account of the waiting times at intersections, the road traffic map of Tianjin was selected as the research object, shown by the red lines in Figure6.Figure 6
Target road network.The roads and their intersections in the selected area are represented by the 39 edges and 25 nodes in the map, as shown in Figure7, where the arrows indicate the directions of travel on the road sections. The travel time ϕi,j on each edge and the time spent θi,j,k on each node are all uniformly distributed with U [1, 10]. The goal of the optimization is to obtain the minimum-time path from N1 to N25 in the directed graph.Figure 7
Graphical representation of the selected road network.The diagram of the simulated road network as drawn in MATLAB according to the relationship between nodes and edges is shown in Figure8.Figure 8
Road network simulation diagram.


## 6.1.2. Simulation Program Design

The experimental program consists of four sections: two data input sections, the algorithm section (the most important part), and a framework for data processing, data transmission, and display of the results. A simple menu interface is displayed in the main window of MATLAB. To facilitate the functions of calling input and calculation using the menu, the functions of each section are written as independent.m files, which are listed together with their functions in Table5. An error handling function is integrated. For example, when the start and endpoints of the shortest path are input, the program will judge whether the start point and the endpoint are the same. If they are equal, an error message will be output. The connections between them are illustrated in Figure 9.Table 5
List of M files and their functions.
menu.mDisplays the menu and calls other functions. It is the entrance to the program.ROLA.mPerforms the ROLA operation on the data input and returns the result. It is the core of the program.input_arc.mCalls the arc travel time data to generate the adjacency matrix and return it.input_node.mCalls the node travel time data to generate the adjacency matrix and return it.Figure 9
Call relationship of each section of the program.


## 6.1.3. ROLA Simulation Result

The data needed in the algorithm is represented by the adjacency matrix. Because MATLAB language itself is used for matrix calculation and has inherent advantages for matrix calculation. Usearc_datai,j represent the travel time of any arc i,j, and node_datai,j,k represent the waiting time of arc i,j tuning arc j,k. Since we are studying a directed graph, in general: arc_datai,j≠arc_dataj,i and node_datai,j,k≠node_datak,j,i, if there is no path from i to j, then arc_datai,j=∞ and node_datai,j,k=∞. For a network with n nodes, arc_datai,j is a n∗n two-dimensional matrix, and node_datai,j,k is a n∗n∗n three-dimensional matrix.The simulation procedure is as follows: start MATLAB (version 7.11.0 R2010b), put all.m files into the MATLAB search path, enter the “menu” in the MATLAB interface, and output the main menu. Enter “1” to input the adjacency matrix of the arc. The program prompts success and outputs the menu again. Enter “2” to input the node adjacency matrix. The program then prompts success and outputs the menu again. Enter “3” to view the data and output the array ofarc_data and node_data. Enter “4” to find the path, obtain the minimum-time path from the given arc to the destination and the minimum-time path from the starting node to the destination, and arbitrarily select two target arcs for verification.Because there are 39 edges in the network, the fourth step is performed 39 times to find the minimum-time paths and values for all the arcs to the endpoint. It is easy to find the subsequent arcs on the optimal path from each arc to the endpoint. The minimum-time path from the starting node N1 to the destination node N25 is N1⟶N2⟶N7⟶N12⟶N13⟶N14⟶N15⟶N20⟶N23⟶N25. The travel time is 67.8, and the CPU running time of the simulation is 0.0238s. The optimal simulation route is shown in Figure 10 by the thick gray arrows and the corresponding optimal route on the map is shown in Figure 11.Figure 10
Optimal route simulation.Figure 11
Optimal route on the map.By calling the traditional Dijkstra algorithm in the MATLAB simulation environment, we easily obtain the minimum-time path from the starting point N1 (do not consider node attribute) to the destination N25 (do not consider node attribute) is N1⟶N2⟶N7⟶N12⟶N13⟶N14⟶N15⟶N20⟶N23⟶N25, with travel time 45.6.It can be seen from the simulation results for the above two cases that the same optimal paths (under the coincidence) are obtained but with different values, which depending on whether or not node attributes are taken into account.


## 6.2. Comparative Simulation Experiment

### 6.2.1. Test Environment and Parameter Settings

In this section, in order to measure the performance of the algorithm ROLA proposed in this paper and the more widely used algorithms [34], we have conducted extensive simulation experiments, and the implemented algorithms include PSO, ACO, GA, NNA, and OPABRL [4]. Table 6 gives the parameter settings of each algorithm.Table 6
Parameters setting.
AlgorithmParametersValueACOAnt number m80Heuristic factor a1Pheromone volatilityρ0.3GAPopulation sizeM100Cross probabilityP10.6Mutation probabilityp20.01NNANetwork layers3Number of input nodes6Number of output nodes1Number of hidden layer nodes12PSOParticle swarm size80Learning factorc11.5Learning factorc22.0Inertia weight parameterω0.9OPABRLLearning factorα0.7Discount factorθ1Greedy strategyε0.5The simulation process will be carried out on the MATLAB platform (same as above). Under the condition of selecting the same starting node and destination node, we compare the differences among the path obtained by different algorithms. The main measurement indicators include (1) algorithm convergence speed; (2) algorithm running time.We select 10 groups of networks with different numbers of nodes and edges. The grouping is shown in Table7. The number of network nodes, respectively, are 50,100,…,500, and the number of corresponding arc segments, respectively, are 100,250,…,1450. Regarding the composition of each group of the network, similar to Figure 7, each node is connected to at least one other node and at most six other nodes. Starting from the first node, each node is numbered from near to far, and the first node is the starting node and the last node is the destination. Same as before, for the network with n nodes,arc_datai,j is an n∗n two-dimensional matrix, and node_datai,j,k is a n∗n∗n three-dimensional matrix. The value of travel time ϕi,j for each arc is uniformly distributed with U[1, 5], the value of time spent θi,j,k for each node are uniformly distributed with U(1, 5). In the experiment, we need to call each algorithm to find the minimum time path from the starting node to the destination in each group of the network, each algorithm runs ten times for each group of networks, and the average value is taken as the statistics. The total number of runs of all algorithms is 500.Table 7
Grouping of networks selected.
NODE_COUNTARC_COUNTGROUP150100GROUP2100250GROUP3150400GROUP4200550GROUP5250700GROUP6300850GROUP73501000GROUP84001150GROUP94501300GROUP105001450


### 6.2.2. Simulation Experiment Results and Analysis

The average iterations, path length change, running time of the proposed ROLA, and the other five comparison algorithms running ten times in each network size are shown in Table8.Table 8
Statistics of experimental results.
Statistical indicatorsMethodNODE 50NODE 100NODE 150NODE 200NODE 250NODE 300NODE 350NODE 400NODE 450NODE 500IterationsROLA3487104155202267349452495522PSO4393136203301399452469475479ACO51102165255342415455487492513GA60105134234331408464501512527NNA57110173265358422456478501526OPABRL3992125187258312341363371390Path lengthROLA9730351467581610231225142117322003PSO10630852269282410351243143617322014ACO11231052767982810441218142117472005GA11731053271283310291228143117292011NNA11431453370481910231237144017442025OPABRL10530651468381610311234142617532047Running time (ms)ROLA8621813697089141251162518441893PSO141904421004121315671617163916521666ACO211686071298159117601792182818341829GA301535241158153918221910192619341927NNA1542735731067133015481667174617621769OPABRL119238188799111621159121312311242The convergence rate of these algorithms is shown in Figures12–17 (here, we give the experimental results of the network with 100 nodes) where the x-axis represents the number of iterations and y-axis represents the shortest path length (travel time) change in the algorithm process. From the experiment result, we observed that, although there are fluctuations at the beginning, all the implemented algorithms can reach convergence after multiple iterations. The number of iterations for the proposed ROLA to reach convergence is significantly less than that of GA, NNA, and ACO, we also found there is some instability after the ant colony algorithm converges. Even though the ROLA fluctuates greatly at the beginning, under the same experimental environment, the algorithm can converge to the shortest path result earlier and has a better stability.Figure 12
Convergence rate of ROLA (NODE_COUNT = 100).Figure 13
Convergence rate of PSO (NODE_COUNT = 100).Figure 14
Convergence rate of ACO (NODE_COUNT = 100).Figure 15
Convergence rate of GA (NODE_COUNT = 100).Figure 16
Convergence rate of NNA (NODE_COUNT = 100).Figure 17
Convergence rate of OPABRL (NODE_COUNT = 100).Regarding the computational effort required by the different algorithms, Figure18 shows the average computational times (in milliseconds) for all considered algorithms for each instance size. In view of the results, the following points can be highlighted: (1) with the increase of network nodes, the running time of the other five algorithms increasing faster and faster, when the network nodes reach a certain number, the running time changes very little. However, the growth rate of running time changes for the ROLA changes very little, when the network nodes reach a certain number, and it also tends to be stable. (2) When network nodes are less than 350, the ROLA outperforms all the other algorithms. (3) When network nodes more than 350, the OPABRL outperforms all the other algorithms. Therefore, the running time performance of the proposed ROLA significantly outperforms other algorithms in the small to medium scale network.Figure 18
Running time of different algorithms.Through all experiments, it can be concluded that the ROLA in this paper is easy to implement and shows good practicability and high efficiency under certain conditions.


## 6.2.1. Test Environment and Parameter Settings

In this section, in order to measure the performance of the algorithm ROLA proposed in this paper and the more widely used algorithms [34], we have conducted extensive simulation experiments, and the implemented algorithms include PSO, ACO, GA, NNA, and OPABRL [4]. Table 6 gives the parameter settings of each algorithm.Table 6
Parameters setting.
AlgorithmParametersValueACOAnt number m80Heuristic factor a1Pheromone volatilityρ0.3GAPopulation sizeM100Cross probabilityP10.6Mutation probabilityp20.01NNANetwork layers3Number of input nodes6Number of output nodes1Number of hidden layer nodes12PSOParticle swarm size80Learning factorc11.5Learning factorc22.0Inertia weight parameterω0.9OPABRLLearning factorα0.7Discount factorθ1Greedy strategyε0.5The simulation process will be carried out on the MATLAB platform (same as above). Under the condition of selecting the same starting node and destination node, we compare the differences among the path obtained by different algorithms. The main measurement indicators include (1) algorithm convergence speed; (2) algorithm running time.We select 10 groups of networks with different numbers of nodes and edges. The grouping is shown in Table7. The number of network nodes, respectively, are 50,100,…,500, and the number of corresponding arc segments, respectively, are 100,250,…,1450. Regarding the composition of each group of the network, similar to Figure 7, each node is connected to at least one other node and at most six other nodes. Starting from the first node, each node is numbered from near to far, and the first node is the starting node and the last node is the destination. Same as before, for the network with n nodes,arc_datai,j is an n∗n two-dimensional matrix, and node_datai,j,k is a n∗n∗n three-dimensional matrix. The value of travel time ϕi,j for each arc is uniformly distributed with U[1, 5], the value of time spent θi,j,k for each node are uniformly distributed with U(1, 5). In the experiment, we need to call each algorithm to find the minimum time path from the starting node to the destination in each group of the network, each algorithm runs ten times for each group of networks, and the average value is taken as the statistics. The total number of runs of all algorithms is 500.Table 7
Grouping of networks selected.
NODE_COUNTARC_COUNTGROUP150100GROUP2100250GROUP3150400GROUP4200550GROUP5250700GROUP6300850GROUP73501000GROUP84001150GROUP94501300GROUP105001450


## 6.2.2. Simulation Experiment Results and Analysis

The average iterations, path length change, running time of the proposed ROLA, and the other five comparison algorithms running ten times in each network size are shown in Table8.Table 8
Statistics of experimental results.
Statistical indicatorsMethodNODE 50NODE 100NODE 150NODE 200NODE 250NODE 300NODE 350NODE 400NODE 450NODE 500IterationsROLA3487104155202267349452495522PSO4393136203301399452469475479ACO51102165255342415455487492513GA60105134234331408464501512527NNA57110173265358422456478501526OPABRL3992125187258312341363371390Path lengthROLA9730351467581610231225142117322003PSO10630852269282410351243143617322014ACO11231052767982810441218142117472005GA11731053271283310291228143117292011NNA11431453370481910231237144017442025OPABRL10530651468381610311234142617532047Running time (ms)ROLA8621813697089141251162518441893PSO141904421004121315671617163916521666ACO211686071298159117601792182818341829GA301535241158153918221910192619341927NNA1542735731067133015481667174617621769OPABRL119238188799111621159121312311242The convergence rate of these algorithms is shown in Figures12–17 (here, we give the experimental results of the network with 100 nodes) where the x-axis represents the number of iterations and y-axis represents the shortest path length (travel time) change in the algorithm process. From the experiment result, we observed that, although there are fluctuations at the beginning, all the implemented algorithms can reach convergence after multiple iterations. The number of iterations for the proposed ROLA to reach convergence is significantly less than that of GA, NNA, and ACO, we also found there is some instability after the ant colony algorithm converges. Even though the ROLA fluctuates greatly at the beginning, under the same experimental environment, the algorithm can converge to the shortest path result earlier and has a better stability.Figure 12
Convergence rate of ROLA (NODE_COUNT = 100).Figure 13
Convergence rate of PSO (NODE_COUNT = 100).Figure 14
Convergence rate of ACO (NODE_COUNT = 100).Figure 15
Convergence rate of GA (NODE_COUNT = 100).Figure 16
Convergence rate of NNA (NODE_COUNT = 100).Figure 17
Convergence rate of OPABRL (NODE_COUNT = 100).Regarding the computational effort required by the different algorithms, Figure18 shows the average computational times (in milliseconds) for all considered algorithms for each instance size. In view of the results, the following points can be highlighted: (1) with the increase of network nodes, the running time of the other five algorithms increasing faster and faster, when the network nodes reach a certain number, the running time changes very little. However, the growth rate of running time changes for the ROLA changes very little, when the network nodes reach a certain number, and it also tends to be stable. (2) When network nodes are less than 350, the ROLA outperforms all the other algorithms. (3) When network nodes more than 350, the OPABRL outperforms all the other algorithms. Therefore, the running time performance of the proposed ROLA significantly outperforms other algorithms in the small to medium scale network.Figure 18
Running time of different algorithms.Through all experiments, it can be concluded that the ROLA in this paper is easy to implement and shows good practicability and high efficiency under certain conditions.


## 7. Conclusion

In view of the importance of intersections in the actual road network, this paper studies the minimum time path optimization problem in time-invariant networks considering node attributes (weight or time cost). Based on the Dijkstra algorithm, we propose a Reverse Order Labeling Algorithm (ROLA) to solve the problem. We theoretically proved the correctness of the ROLA , analyzed, and gave its time complexity. Through large-scale simulation experiments, the convergence efficiency and calculation speed of the ROLA and the PSO, GA, ACO, NNA, and OPABRL algorithms are compared. The experimental results show that the algorithm proposed (ROLA) in this paper has certain advantages in the running time and search efficiency under certain conditions.In the future, on the basis of the research in this article, we will try to extend the research results of this article to more realistic stochastic time-varying networks and conduct research on the path planning of stochastic time-varying networks considering node attributes.



---

*Source: 2963092-2021-01-04.xml*