A new algorithm for finding the K shortest paths in a time-schedule network with constraints on arcs

Abstract

Time-schedule network with constraints on arcs (TSNCA) means network with a list of pre-defined departure times for each arc. Compared to past research on finding the K shortest paths in TSNCA, the algorithm in this paper is suitable for networks having parallel arcs with the same direction between two nodes. A node label algorithm for finding the K shortest paths between two nodes is proposed. Temporal-arcs are put into the labels of nodes and arranged by ascending order. The number of temporal-arcs is limited to K in every label of node to improve the effectiveness of the algorithm. The complexity of this algorithm is $O(|A|\log r+K2|A|+K2|N|\log (K\left|N\right|))$ , where $r$ is the maximum number of departure times from a node, $\left|A\right|$ is the number of arcs in network, and $\left|N\right|$ is the number of nodes in network. Experiments are carried out on major part of real urban mass transit network in Beijing, China. The result proves that the algorithm is effective and practical.

Introduction

Since 1950s, many researchers have paid much attention to K shortest paths. ¹ The classical methods were proposed by Hoffman and Pavley, ² Yen, ³ Eugene, ⁴ and Katoh et al. ⁵ Based on the classical methods, more efficient algorithms^6–8 were introduced. And more constraints^9–11 were considered when finding K shortest paths as well. Time windows^12–15 and time schedule^16–18 are two important constraints which were extensively studied in recent years.

Time window is a time period with the earliest and latest time, when a node is available for visiting.^12,13 For example, time window of a traffic signal decides when the intersection can be passed through. Time schedule is a special type of time window, which assumes that a node^16,17 or an arc ¹⁸ has a list of departure times and the departure from that node can only happen at one of the departure times. The time-schedule constraint is common in the real world. For example, a node in a time-schedule network may be a transportation station, and an arc may be a section of a line. Finding the K shortest paths in a time-schedule network can help passengers or shippers to get the K shortest ways by bus, trains, or planes.

Time-schedule constraints can be divided into two different types: constraints on nodes and constraints on arcs. For time schedule on nodes, different lines out from the same node share the same schedule. For time schedule on arcs, different lines out from the same node can have different schedules. Comparing to time schedule on nodes, time schedule on arcs is more applicable.

Jin et al. ¹⁸ proposed an algorithm for finding K shortest paths in time-schedule network with constraints on arcs (TSNCA) in 2013. In that algorithm, there is no more than one arc with same direction between two nodes (parallel arcs). In fact, it is common that there are parallel arcs in networks. For example, different bus line passing the same two stations can have different schedules. Similar case exists in railway network and aviation network. In this paper, we studied the algorithm for finding K shortest paths in TSNCA with parallel arcs.

The rest of this paper is organized as follows. The definitions and concepts are introduced in next section. Then, the processes of extending temporal-arcs and generating paths are proposed. The main steps, example and complexity analysis of the algorithm are then presented. The experiments of the algorithm are tested in the fifth section. Finally, the conclusion is drawn.

Definitions and concepts

Time-schedule network

With reference to Jin et al., ¹⁸ an example of TSNCA in this paper is shown in Figure 1. In this example, $\{s,B,C,d\}$ is the set of nodes and $\{\mathrm{sB}1,\mathrm{sB}2,\mathrm{sC}1,\mathrm{BC}1,\mathrm{Bd}1,\mathrm{Cd}1\}$ is the set of arcs. Denote N as the set of nodes and A as the set of arcs. Each arc in A has a non-negative travel time and a list of pre-specified departure times. For two nodes u and v ( $u\in N,v\in N$ ), $\mathrm{uv}\rightharpoonup i$ is the i-th arc from u to v, where u is called start node and v is called end node. $C(\mathrm{uv}i)$ means the cost of arc $\mathrm{uv}i$ . Arcs in set A are sorted in ascending order of $C(\mathrm{uv}i)$ , which means $C(\mathrm{uv}i)\le C(\mathrm{uv}i+1)$ . Denote $\mathrm{dt}(\mathrm{uv}i)j$ as the j-th departure time on arc $\mathrm{uv}i$ and $\mathrm{dt}(\mathrm{uv}i)j<\mathrm{dt}(\mathrm{uv}i)j+1$ . The constraint on arc is described as [ $C(\mathrm{uv}i)$ , $\mathrm{dt}(\mathrm{uv}i)1$ ,…, $\mathrm{dt}(\mathrm{uv}i)j$ ,…, $\mathrm{dt}(\mathrm{uv}i)r$ ], such as $\mathrm{sB}1=[3;(1,4,8,12)]$ and $\mathrm{sB}2=[4;(2,5,9,12)]$ in Figure 1.

Figure 1.

Example of time-schedule network with constraint on arcs.

Similar to Jin et al., ¹⁸ s is the source node and d is the destination node. The K shortest paths between s and denote d as the first K paths from s to d in non-descending order of their arrival times.

Several concepts

Temporal-arc

For the network example in Figure 1, if we arrive at node s at time 2 and we want to go along $\mathrm{sB}1$ , whose constraint is [3;(1,4,8,12)], we will need to wait at least two time units and depart at 4 and then arrive at node B at time 7. Or we can wait six time units at s and depart at time 8 and then arrive at node B at 11 along arc $\mathrm{sB}1$ .

Denote a temporal-arc as the arc with arrival time. As shown in Figure 2, $\mathrm{sB}1$ (7) and $\mathrm{sB}1$ (11) are temporal-arcs of $\mathrm{sB}1$ . To differentiate a temporal-arc from the ordinary arc, denote static-arc as the ordinary arc, such as $\mathrm{sB}1$ .

Figure 2.

Example of temporal-arcs.

Moreover, $\mathrm{sB}1$ (7) is named as the nearest temporal-arc of $\mathrm{sB}1$ for we cannot arrive at B before 7 along $\mathrm{sB}1$ if we arrive at node s at time 2. With constraint of arrival time at s, for a specific static arc, the temporal-arcs with the first K arrival time are called K nearest temporal-arcs.

Set of scan eligible temporal-arc

Denote EA as the set of scan eligible temporal-arcs. EA is similar to the scan eligible node set ¹⁹ and branches set II in Dijkstra algorithm ²⁰ for finding shortest path. Similar to Dijkstra algorithm, the elements in EA are in order of increasing cost from original node. Here, the cost is the arrival time of temporal-arc. For example, 7 is the arrival time of temporal-arc $\mathrm{sB}1(7)$ . Denote $\tilde{a}$ as a temporal-arc and $t(\tilde{a})$ is the arrival time of temporal-arc $\tilde{a}$ .

During process of finding, temporal-arcs are put into or taken out of EA. Here, we describe the status of a temporal-arc according to whether it is in $EA$ . Denote $s(\tilde{a})$ as the status of temporal-arc. When $s(\tilde{a})$ equals 1, the temporal-arc is in set EA. When $s(\tilde{a})$ equals 2, the temporal-arc has been taken out of EA.

Label of node

Denote $\mathrm{nl}(v)$ as the label of node v. A list of K first arrival temporal-arcs is stored in $\mathrm{nl}(v)$ . The information of the j-th element in $\mathrm{nl}(v)$ can be described as $\mathrm{nl}(v)j$  = ( $\mathrm{uv}i(t)$ , $s(\mathrm{uv}i(t))$ ). $\mathrm{uv}i(t)$ can be expressed as ${\mathrm{nl}(v)}_j^1$ . $s(\mathrm{uv}i(t))$ represents the status of the temporal-arc $\mathrm{uv}i(t)$ , which can be expressed as ${\mathrm{nl}(v)}_j^2$ . K elements are sorted by arrival times of temporal-arcs in $\mathrm{nl}(v)$ in ascending order.

Theorem 1 is proposed to support that the number of elements in label of node is less than K.

Theorem 1

For every node which can be reached from s, the maximum number of temporal-arcs in label of the node is K in TSNCA. These K temporal-arcs can support to finding K shortest path departing from s.

Proof

As shown in Figure 3, in TSNCA, d′ is a node on the K shortest path from s to d. If there are K temporal-arcs with K first arrival time at d′, we can construct K shortest paths from s to d′. If K shortest paths from s to d pass d′, the K shortest paths from s to d′ are enough for constructing the K shortest paths from s to d. Thus, K first arrival temporal-arcs are enough for finding K shortest paths.

Figure 3.

Temporal-arcs for special node d′.

Assume K = 3, relationship between temporal-arcs and label of node is illustrated as Figure 4.

Figure 4.

Relationship between temporal-arcs and label of node.

There are two static arcs, $\mathrm{sB}1$ and $\mathrm{sB}2$ , from s to B. We can extend nearest temporal-arcs for every static arc till to find three first arrival temporal-arcs which are stored in label of B.

Key processes of finding K shortest path

Process of generating new temporal-arcs and labeling node

Define the extending-arc as the current temporal-arc taken out from $EA$ . From the end node of extending-arc, we can generate some new temporal-arcs. The extending-arc is the father of these new temporal-arcs.

During the process of generating new temporal-arcs, different methods are applied according to whether static arcs have been extended. Here, we define $b(\mathrm{uv}i)$ to describe whether $\mathrm{uv}i$ has been extended. If $b(\mathrm{uv}i)$ is true, $\mathrm{uv}i$ has been extended, we can get the nearest temporal-arc from the label of node v; else we must find the nearest temporal-arc according to the departure times of the $\mathrm{uv}i$ .

The new temporal-arcs are inserted into the label of their end node and set $\text{EA}$ when their arrival time is less than that of the existed temporal-arcs in label of their node. If the number of temporal-arcs in label of a node exceeds K, the last element needs to be removed from the label and the same temporal-arc of the last element needs to be removed from EA.

Assuming K = 3, an example of generating new temporal-arcs and labeling node is shown as Figure 5. In Figure 5(a), the extending-arc is $\mathrm{sB}2(6)$ , the nearest departure time is 7, which is obtained by comparing the arrival time with departure times in (3,7,12,16), and then the nearest temporal-arc is $\mathrm{Bd}1(10)$ . Similarly, $\mathrm{Bd}1(15)$ and $\mathrm{Bd}1(19)$ are obtained corresponding to departure time 12 and 16, respectively. In Figure 5(b), when extending-arc is $\mathrm{sB}1(7)$ , arc $\mathrm{Bd}1$ has been extended, the nearest temporal-arc of $\mathrm{sB}1(7)$ is $\mathrm{Bd}1(10)$ , which can be obtained from label of node d in Figure 5(a). The new temporal-arc $\mathrm{Bd}1(10)$ is inserted into label of node d while temporal-arc $\mathrm{Bd}1(19)$ is deleted from the label of node d. Two $\mathrm{Bd}1(10)$ in label of d have different father.

Figure 5.

Example of generating new temporal-arcs (a) and labeling node (b).

Process of generating paths

The information of K shortest paths is stored in set $p(s-v)$ . $p(s-v)j(1\le j\le K)$ is the j-th shortest path from s to v. The elements in $p(s-v)$ are sorted in ascending of arrival time at node v. The detail of path contains the start node with arrival time, such as $s(t0)$ , and a list of travel information. The travel information contains the time when departing and arriving through the static arcs.

When a temporal-arc $\mathrm{uv}i(t)$ is taken out from $\text{EA}$ , a new path can be generated as follows. where $\mathrm{jth}(\mathrm{uv}i(t))$ means the index of $\mathrm{uv}i(t)$ its in label. $\mathrm{xth}(\mathrm{uv}i(t))$ means the index of the father of $\mathrm{uv}i(t)$ in its label.

The stop condition of finding is that the eligible temporal-arc set EA is null or equation (2) is satisfied.

$$\forall \mathrm{nl}(d)j2=2(1<j\le K)$$

(2)

When finding stopped, $p(s-d)j(1\le j\le K)$ are the K shortest paths we need.

A label setting algorithm

Based on the concepts and processes stated in earlier sections, a label setting algorithm is proposed in this section.

Main steps of algorithm

Some temporary variables are used in the algorithm. Denote $\mathrm{as}(u)$ as the set of static arcs out from node u, $\mathrm{ne}(u)$ as the set of succeed nodes from node u, M as a maximum value, $\mathrm{ea}1$ as the first element in $EA$ . $\mathrm{at}(\mathrm{uv}i)j$ is the arrival time at v after departing from u at $\mathrm{dt}(\mathrm{uv}i)j$ through arc $\mathrm{uv}i$ , and $\mathrm{at}(\mathrm{uv}i)j=\mathrm{dt}(\mathrm{uv}i)j+C(\mathrm{uv}i)$ . Denote $b(u)$ as whether the node u can be extended in next iteration. Denote $b(\mathrm{uv}i)$ as whether the static arc $\mathrm{uv}i$ has been extended. t₀ is the arrival time at node s. $\mathrm{Os}$ is the dummy arc.

The steps of the algorithm for finding the K shortest paths from s to d are as follows:

Step 1: Initialize.

$$\mathrm{EA}\to \{\mathrm{Os}(t0)\},\mathrm{\hspace{1em}\hspace{1em}\hspace{1em}}b(\mathrm{uv}i)\to \mathrm{false}(\forall \mathrm{uv}i\in A),b(u)\to \mathrm{true}(\forall u\in N),\mathrm{\hspace{1em}\hspace{1em}\hspace{1em}}p(s-s)\to s(t0)$$

Step 2: While set EA is not null, get first element from EA as extending temporal-arc $\tilde{a}$ and generate new path according to equation (1). If equation (2) is satisfied, return. If the end node of $\tilde{a}$ can be extended, go to step 3.

while $EA\ne Ø$ {

$\tilde{a}\to$ $\mathrm{ea}1(\mathrm{ea}1=\mathrm{uv}i(t))$ , $EA\to EA$ < $\mathrm{ea}1$ >, $s(\tilde{a})\to 2$ ;

$\mathrm{gp}(s-v)j$ ;// generate new path according to equation (1)

If $\forall \mathrm{nl}(d)j2=2(1<j\le K)$

 return;

if $b(v)\ne \mathrm{false}$

 go to Step 3;

}

return.

Step 3: According to “Process of generating new temporal-arcs and labeling node” subsection, if the static arc has not been extended, find nearest departure time after $t(\tilde{a})$ from departure times of the arc. The nearest departure time $\mathrm{dt}(\mathrm{vw}i)t$ should satisfy $\mathrm{dt}(\mathrm{vw}i{)}_t^{3}t(\tilde{a})\cap \mathrm{dt}(\mathrm{vw}i)t-1<t(\tilde{a})$ . Then, get no more than K nearest arrival times by function $\mathrm{getaxK}$ . If the static arc has been extended, find the nearest arrival temporal-arc of static arc $\mathrm{vw}i$ from label of node w and get no more than K elements arrival time of which is not earlier than $t(\tilde{a})+c(\mathrm{vw}i)$ . Here, the function getax K returns K elements to $\mathrm{ax}(\mathrm{vw}i)$ .

for each arc $\mathrm{vw}i\in \mathrm{as}(v)$ {

 if $b(\mathrm{vw}i)=\mathrm{false}$ {

   $j\to \mathrm{findt}(\mathrm{vw}i,t(\tilde{a}))$ , $b(\mathrm{vw}i)\to \mathrm{true}$ ;

   $\mathrm{ax}(\mathrm{vw}i)\to \mathrm{getaxK}(\mathrm{vw}i,j)$

}

else {

   $j\to \mathrm{findj}(\mathrm{nl}(w),t(\tilde{a})+c(\mathrm{vw}i))$ ;

   $\mathrm{ax}(\mathrm{vw}i)\to \mathrm{getaxK}(\mathrm{nl}(w),j)$

 }

}

Step 4: Denote c as the number of new elements in the label of w, $\mathrm{ax}(\mathrm{vw})$ as the set of all $\mathrm{ax}(\mathrm{vw}i)$ . c is no more than K. $\mathrm{getM}(\mathrm{ax}(\mathrm{vw}))$ means getting the first arrival temporal-arc in $\mathrm{ax}(\mathrm{vw})$ . $\mathrm{update}(\mathrm{nl}(w),\mathrm{axM})$ means inserting $\mathrm{axM}$ into $\mathrm{nl}(w)$ and EA respectively with increasing order of arrival times, and deleting the (k+1)th element in $\mathrm{nl}(w)$ and the same temporal-arc from EA. If $\mathrm{axM}$ is larger than the largest arrival times in $\mathrm{nl}(w)$ , return false to $\mathrm{bx}$ , else return true. If c equals zero, there is no element being inserted into $\mathrm{nl}(w)$ and return false to $b(w)$ . Then go to step 2.

$c\to 0$ ;

while c < K {

  $\mathrm{axM}\to \mathrm{getM}(\mathrm{ax}(\mathrm{vw}))$

  $\mathrm{bx}\to \mathrm{update}(\mathrm{nl}(w),\mathrm{axM})$ ;

 if $\mathrm{bx}=\mathrm{true}$

   $c\to c+1$

 else

  break;

}

 if $c=0$ , $b(w)\to \mathrm{false}$ ;

go to step 2.

Example

Table 1 shows the steps when we apply our algorithm to find the K shortest paths from s to d in the example network. Here, K = 3. The asterisk symbol (*) in the table means the element in the label is same as that in previous iteration. During iteration 4, the arrival time of temporal-arc $\mathrm{sB}2$ (9) is 9, the nearest arrival time at C is 12, and nearest arrival time at d is 15. Both of the arrival times cannot bring updating at node C and d, so B cannot be extended in next iteration and b(B) equals false. Similarly, during iteration 5, the nearest arrival time at d is 16 after time 10 from node C, which cannot bring updating for the label of node d, so C cannot be extended in next iteration and b(C) equals false.

Table 1.

Example of application.

Iteration	Extending-arc	Node label update	Path update
1	$\mathrm{Os}(2)$	$\mathrm{nl}(B)$  = <( $\mathrm{sB}2(6),1$ ),( $\mathrm{sB}1(7)$ ,1),( $\mathrm{sB}2(9)$ ,1)> $\mathrm{nl}(C)$  = <( $\mathrm{sC}1(10)$ ,1),( $\mathrm{sC}1$ (15),1),( $\mathrm{sC}1$ (19),1)>	$p(s-s)1$  = < $s(2)$ >
2	$\mathrm{sB}2$ (6)	$\mathrm{nl}(B)$  = <( $\mathrm{sB}2$ (6),2),*,*> $\mathrm{nl}(C)$  = <*,( $\mathrm{BC}1$ (11),1),( $\mathrm{BC}1$ (13),1)> $\mathrm{nl}(d)$  = <( $\mathrm{Bd}1$ (10),1),( $\mathrm{Bd}1$ (15),1),( $\mathrm{Bd}1$ (19),1)>	$p(s-B)1$  = < $s(2)$ , $\mathrm{sB}2(2,6)$ >
3	$\mathrm{sB}1$ (7)	$\mathrm{nl}(B)$  = < *,( $\mathrm{sB}1$ (7),2),*> $\mathrm{nl}(C)$  = <*,( $\mathrm{BC}1$ (10),1),( $\mathrm{BC}1$ (11),1)> $\mathrm{nl}(d)$  = <*,( $\mathrm{Bd}1$ (10),1),( $\mathrm{Bd}1$ (15),1)>	$p(s-B)2$  = < $s(2)$ , $\mathrm{sB}1(4,7)$ >
4	$\mathrm{sB}2$ (9)	$\mathrm{nl}(B)$  = < *,*,( $\mathrm{sB}2$ (9),2)> b(B) = false	$p(s-B)3$  = < $s(2)$ , $\mathrm{sB}2(5,9)$ >
5	$\mathrm{sC}1(10)$	b(C) = false
6	$\mathrm{Bd}1$ (10)	$\mathrm{nl}(d)$  = <( $\mathrm{Bd}1(10)$ ,2),*,*> b(d) = false	$p(s-d)1$  = < $s(2)$ , $\mathrm{sB}2(2,6)$ , $\mathrm{Bd}1(7,10)$ >
7	$\mathrm{Bd}1$ (10)	$\mathrm{nl}(d)$  = <*,( $\mathrm{Bd}1(10)$ ,2),( $\mathrm{Bd}1(15)$ ,2)>	$p(s-d)2$  = < $s(2)$ , $\mathrm{sB}1(4,7)$ , $\mathrm{Bd}1(7,10)$ > $p(s-d)3$  = < $s(2)$ , $\mathrm{sB}2(5,9)$ , $\mathrm{Bd}1(12,15)$ >

Complexity analysis of algorithm

Denote |N| and |A| as the number of elements in set A and set N, respectively. The maximum number of departure times on an arc is denoted as r. According to “Main Steps of Algorithm” subsection, the complexity of algorithm is analyzed as follows:

In step 1, the nodes, static arcs and other sets are initialized. The complexity of step 1 is $O(|N|+|A|)$ .

In step 2, searching is end or step 3 is called according to the conditions which first element of EA satisfied. The complexity of step 2 equals to the maximum number of elements in EA, which is K|N|.

In step 3, function $\mathrm{findt}$ is called no more than one time for each static arc in whole algorithm. The total times of calling function $\mathrm{findt}$ are no more than |A|. If $\mathrm{findt}$ is not called, the temporal-arc will be got by calling $\mathrm{findt}$ . Because the number of static arcs of all nodes is no more than $\left|A\right|$ , the number of static arcs at the end nodes of temporal-arcs in EA is no more than $K\left|A\right|$ . So the times of calling $\mathrm{findt}$ are $K\left|A\right|-\left|A\right|=(K-1)\left|A\right|$ . In function $\mathrm{findt}$ , the satisfying time is found from the list of departure times. The number of departure times is no more than r, so the complexity of $\mathrm{findt}$ is $O(\log r)$ . In function $\mathrm{findt}$ , the temporal-arc is found from K elements in label of a node. So the complexity of $\mathrm{findt}$ is $O(\log K)$ . After $\mathrm{findt}$ or $\mathrm{findt}$ is called, function $\mathrm{getaxK}$ is called, which can be ignored because much simpler than $\mathrm{findt}$ and $\mathrm{findt}$ . Thus, the complexity brought by step 3 in the whole algorithm is $O(|A|\log r+(K-1)|A|\log K)$ .

In step 4, function $\mathrm{getM}$ and $\mathrm{update}$ is called no more than K times for each temporal-arc in EA. The complexity of $\mathrm{getM}(\mathrm{ax}(\mathrm{vw}))$ is $O(d(\mathrm{vw}))$ , where $d(\mathrm{vw})$ is the number of static arcs of $\mathrm{vw}$ . The complexity brought by $\mathrm{getM}(\mathrm{ax}(\mathrm{vw}))$ in the whole algorithm is $O(K2\left|N\right|d(\mathrm{vw}))$ . Because the number of static arcs of all node is no more than $\left|A\right|$ , $O(K2\left|N\right|d(\mathrm{vw}))$ can be converted to $O(K2\left|A\right|)$ . The function $\mathrm{update}$ inserts element into $\mathrm{nl}(v)$ and EA, the complexity of which is $O(\log K+\log (K\left|N\right|))$ and is equivalent to $O(\log (K\left|N\right|))$ . The complexity brought by $\mathrm{update}$ in the whole algorithm is $O(K2\left|N\right|\log (K|N|))$ . Thus, the complexity brought by step 4 in the whole algorithm is $O(K2\left|A\right|+K2\left|N\right|\log (K|N|))$ .

In conclusion, the whole algorithm is sum of $O(|N|+|A|)$ , $O(|A|l\mathrm{ogr}+(K-1)|A|\log K)$ and $O(K2\left|A\right|+K2\left|N\right|\log (K|N|)$ . It can be simplified to $O(|A|\log r+K2|A|+K2|N|\log (K\left|N\right|))$ .

We compared the algorithm in this paper with two classical algorithms in the past research. The algorithm in this paper is named as algorithm A. The algorithm proposed by Chen and Tang ¹⁷ is named as algorithm B. The algorithm proposed by Jin et al. ¹⁸ is named as algorithm C. The applicative network and complexity of these three algorithms are shown in Table 2.

Table 2.

Comparison of network and complexity.

Algorithm	Type of network	Complexity
Algorithm A	A time-schedule network with constrained on arcs and with parallel arcs	$O(|A|\log r+\text{K}2|A|+\text{K}2|\text{N}|\log (K\left|N\right|))$
Algorithm B	A time-schedule network with constrained on node and without parallel arcs	$\text{O}(r|A|+\text{r}|N|(\log r\left|N\right|)+K\times L)$ L means the number of nodes in the path
Algorithm C	A time-schedule network with constrained on arcs, and without parallel arcs	$\text{O}(|A\left|\text{log}(\right|\text{N}|\text{r})+\text{K}|A|\text{r}2\eta )$ η is the maximum in-degree of a node.

As shown in Table 2, algorithm A can handle more complex network than the other two. When $K<r2\eta \cap K\left|N\right|\log (K|N|)<\left|A\right|r2\eta$ , algorithm A is better than Algorithm C for same network. This inequality can be satisfied easily when K is small and r is large.

Experiments

The algorithm developed in this paper was tested on major part of urban mass transit network in Beijing, China, which are shown as Figure 6. In the test network, there are 275 stations, 16 bidirectional lines, 1 pair parallel arcs, and 130,779 departure times.

Figure 6.

Part of urban mass transit network in Beijing.

Algorithms are programmed by JAVA language. Experiments are tested on a personal computer with an Intel Core i5, 2.50 GHz CPU and 4 GB RAM. The value of K is changed in different experiments, when finding K shortest paths for each station to other stations. The value of K, the time used and the number of paths are shown in Table 3, where $\left|A\right|$  = 521, $\left|N\right|$  = 275 and r = 586.

Table 3.

Result of experiments.

Value of K	Time used (s)	Number of paths
1	24	75,260
2	46	150,520
3	83	225,780
4	118	301,040
5	145	376,300
10	401	752,600
20	1146	1,505,200
30	2142	2,257,800
40	3238	3,010,400
50	4949	3,763,000

Conclusions

This paper proposed a new algorithm for finding the K shortest paths in a TSNCA with parallel arcs. It brought up the concept temporal-arc and proposed a label setting algorithm with the key steps. The complexity of this algorithm is $O(|A|\log r+K2|A|+K|N|\log (K\left|N\right|))$ , which is better than the past research when the K is small and r is large. Moreover, it is suitable when there are parallel arcs in network. Experiments are carried out on real urban mass transit network in Beijing, China. The result proves the algorithm is effective and practical.