# Floyd-A∗ Algorithm Solving the Least-Time Itinerary Planning Problem in Urban Scheduled Public Transport Network

Authors: Yu Zhang; Jiafu Tang; Shimeng Lv; Xinggang Luo
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

We consider an ad hoc Floyd-A∗ algorithm to determine the a priori least-time itinerary from an origin to a destination given an initial time in an urban scheduled public transport (USPT) network. The network is bimodal (i.e., USPT lines and walking) and time dependent. The modified USPT network model results in more reasonable itinerary results. An itinerary is connected through a sequence of time-label arcs. The proposed Floyd-A∗ algorithm is composed of two procedures designated as Itinerary Finder and Cost Estimator. The A∗-based Itinerary Finder determines the time-dependent, least-time itinerary in real time, aided by the heuristic information precomputed by the Floyd-based Cost Estimator, where a strategy is formed to preestimate the time-dependent arc travel time as an associated static lower bound. The Floyd-A∗ algorithm is proven to guarantee optimality in theory and, demonstrated through a real-world example in Shenyang City USPT network to be more efficient than previous procedures. The computational experiments also reveal the time-dependent nature of the least-time itinerary. In the premise that lines run punctually, “just boarding” and “just missing” cases are identified.


---

## Body

## 1. Introduction

When a traveler plans to travel from one place (origin) to another (destination) beginning at a given initial time (or imposed by a deadline) in a real-world urban scheduled public transport (USPT) network, it can be difficult to determine the a priori least-time (LT) itinerary. Typically speaking, the itinerary should specify the USPT services (e.g., metro lines, bus lines) that combine the vehicle trips to take, the roads to walk, and the stops at which to transfer in order to arrive at a destination consuming the least time. The aforementioned least-time itinerary planning problem in an urban scheduled public transport network (LTIP-USPT) is a common decision problem for travelers in a city travelling from an origin to a destination to make a date, attend a conference, participate in a party, and, most often, to go to work.Unlike the well-studied shortest path problems in static networks, LTIP-USPT is more difficult to address concerning the following reasons: (i) the topological structures and timetables of the public transport services in a city are prescheduled. (ii) One or more transfers are unavoidable in most cases, resulting in walking time and waiting time as penalties. (iii) In addition to spatial connectivity and distance, travelers must also consider temporal and operational factors. In a word, public-transport travelers, as opposed to private-vehicle travelers, cannot wander in a USPT network freely without any constraints (for more detailed explanation, please see [1]). Moreover, in real-world applications, the solution procedure should be as fast as possible. It is a challenging task because in the time-dependent USPT network, various nodes and lines are interconnected, thus leading to numerous combinations of lines, vehicle trips, walks, and transfers, making a difficult combination optimization problem.The headway-based public transport services were considered in early researches (see [2–4]). Recent years witness a boom in the development of schedule-based public transport. Correspondingly, in the transportation research community, the focuses have shifted from headway-based services to schedule-based ones. The main difference comes from the evaluating of each transfer waiting time. The transfer waiting time is typically assumed to be half of the headway concerning headway-based services. However, for schedule-based services, it could be precisely evaluated depending on the combined timetables. Thus the network travel times (especially transfer waiting times) shift from deterministic to time dependent, resulting in the needs of methodological changes for many transportation problems, for example, itinerary planning (see [5–8]) and traffic assignment (see [9–11]). And these methodologies appear more promising and competing against those for the traditional headway-based services. Note that in reality, the “schedule-based lines” are a generalized concept that might include bus lines and metro lines. In this sense, the bimodal (USPT lines and walking) network considered in this paper could also be interpreted as a multimodal one, which is a typical urban public transport network in real world.There are numerous related works in the existing literatures. Tong and Richardson [12] were among the first to study the scheduled public transport; they developed a branch-and-bound type algorithm for the minimum itinerary. Along this vein, research community extended the itinerary planning problems by introducing different real-world considerations. Horn introduced multimodal transport services, and a Dijkstra-based algorithm was considered for minimizing generalized travel costs [13]. Tan et al. [7] developed a recursive algorithm for finding reasonable paths that satisfy the defined acceptable time criterion and transfer-walk criterion, where travelers’ preferences were required to give. Not only the LT itinerary, but also the k-LT itinerary need to be determined for travelers. Accordingly, Xu et al. [6] and Canca et al. [5] studied the k-shortest path problems in schedule-based transit networks. Androutsopoulos and Zografos considered a dynamic programming based algorithm [14, 15] for the itinerary planning problem in the context where traveler imposes time windows on nodes; multiobjective was also considered. These works have significantly contributed to real-world derived itinerary planning problems for different types of travelers’ requirements. However, their focuses were mainly on the considerations of real-world factors. With regard to the algorithmic efficiency, they only cared about whether a query could be completed within a short time. In query-intensive scenarios, the query should be as fast as possible, which motivated researchers in recent years to examine heuristic methods to speed up computing.Fu et al. reviewed the heuristic shortest path algorithms for transportation applications [16], noting that A*-based algorithms were widely used. The heuristic A* algorithm was first proposed by Hart et al. [17], typically for the shortest path problems in static networks. The performance of A* algorithm depends primarily on the strategy of estimating the travel time of a partial path. A well-designed strategy leads to a considerable savings of computational time while assuring an optimal solution. Chabini and Lan adapted A* for the fastest path in deterministic discrete-time dynamic networks [18]; they proposed three estimating strategies. Subsequently, numerous works appeared in the literatures that primarily applied A*-based algorithms to LT path problems in unscheduled time-dependent road networks (see [19, 20]). Chen et al. proposed an A*-based integrated approach combining offline precomputation and online path retrieval for a road navigation system [21]. This work introduced precomputation (see [22, 23]) technology and significantly improved the efficiency. However, determining the LT itinerary in a scheduled network is more challenging than that of unscheduled network. But relatively little related works were found.In fact, two notable works had studied the itinerary planning problem in scheduled public transport network, especially focusing on the speed-up technologies [24, 25]. They showed that the time-dependent model is superior to the time-expanded model in the sense of itinerary-finding efficiency. A*-based and other strategies are demonstrated to be capable of speeding up computing. Following the previous works, this paper goes beyond in the following aspects: (i) modelling a modified bimodal (i.e., USPT services and walking), time-dependent USPT network. This model is observed to be more applicable in that the results over the modified network model intrinsically have smaller number of transfer times. (ii) An ad hoc Floyd-A* algorithm is developed to solve the LTIP-USPT where transit vehicles are assumed to run punctually. A novel approach to estimating travel time of the partial itinerary is embodied in Floyd-A*. To implement the approach, we generate a slacked network and let the arc travel time be a static tight lower bound of the associated real time-dependent arc travel time. Precomputing technology is also used. The algorithm is proven to be optimal in theory and was demonstrated with a real-world example to be very applicable. The Floyd-A* procedure outperforms the previous procedures. It reduces the averaged computational time by 63.9% compared with a conventional Dijkstra-like procedure. (iii) From the management perspective, an illustrated example reveals the time-dependent nature of the least-time itinerary. In the premise that lines run punctually, the solution aids travelers in avoiding “just missing” cases.The remainder of this paper is organized as follows. Section2 formulates the modified USPT network model and itinerary structure, develops the formula for each time-dependent time-label arc, and subsequently formulates the LTIP-USPT followed by hypotheses. In Section 3, we propose an ad hoc Floyd-A* algorithm composed of two procedures, that is, Floyd-based Cost Estimator and A*-based Itinerary Finder. The Cost Estimator precomputes the estimated travel time of destination-ended partial itineraries as heuristic information. The Itinerary Finder heuristically determines the LT itinerary in real-time. Floyd-A* is mathematically proven to be admissible and efficient. Furthermore, an illustrated example is presented in Section 4 that reveals the time-dependent nature of an LT itinerary and provides guidance for travelers in determining the initial time to begin travel. Meanwhile, through both a numerical example and a real-world case, the Floyd-A* procedure is proven to be more efficient than two other conventional procedures, that is, Dijkstra-like and Plain-A* procedures. Finally, concluding remarks and future works are discussed in Section 5.


## 2. Formulation of the Least-Time Itinerary Planning Problem in Urban Scheduled Public Transport Network (LTIP-USPT)

In modeling the urban scheduled public transport (USPT) network, both USPT lines and walking modes should be considered. An itinerary should encompass spatial, temporal, and operational features. In an USPT network, a passenger who plans to travel from an origin to a destination at a given initial time will select the USPT lines to take, the roads to walk, and the stops at which to transfer in order to arrive at their destination as quickly as possible. We identify this problem hereafter as LTIP-USPT. To solve a LTIP-USPT, a challenge is to model a more applicable USPT network and a reasonable itinerary structure; these are developed in Sections2.1 and 2.2, respectively. In Section 2.3, we formulate the LTIP-USPT as the least-time itinerary planning problem in a deterministic bimodel time-dependent scheduled network.


### 2.1. A Modified Scheduled Network Model

Intuitively, Figure1(a) shows an example of a physical USPT network, and the associated modified network model G
:
=
(
N
,
A
,
L
) is shown in Figure 1(b). The advantage of this model beyond previous scheduled network model can be found in Remark 1. Table 1 gives an associated timetable example.Table 1
A timetable example.
k
n
l
1
l
2
l
3
l
4
l
5
n
1
n
2
n
3
n
4
n
1
n
2
n
4
n
5
n
6
n
7
n
1
n
7
1
6:02
6:14
6:25
6:05
6:18
6:30
6:05
6:15
6:02
6:16
6:00
6:12
2
6:08
6:21
6:31
6:15
6:29
6:40
6:10
6:20
6:10
6:23
6:03
6:15
3
6:13
6:25
6:36
6:25
6:39
6:51
6:15
6:24
6:18
6:32
6:06
6:17
4
6:18
6:29
6:39
6:33
6:46
6:58
6:20
6:30
6:26
6:40
6:09
6:20
5
6:22
6:34
6:44
6:41
6:54
7:07
6:23
6:33
6:30
6:45
6:12
6:24
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮A USPT network example.
(a)
(b)Letl
:
=
(
N
l
,
A
l
,
T
l
)
∈
L denote the scheduled directed USPTlinethat operates on the USPT network. The USPT line typically refers to (but not constrained to) the bus line or metro line that runs on fixed road and runs through a predetermined serious of nodes N
l based on a timetable T
l. There are numerousvehicle trips within a single day. θ
l
,
k
n, element of T
l represents the scheduled time when the kth vehicle trip of l arrives or departs at node n
∈
N
l. Table 1 shows a timetable example, where, for example, θ
l
1
,
2
n
2
=
6
:
21.Any move along a specific line is not necessarily between two adjacent nodes but may pass through one or more intermediate nodes. Correspondingly,C
|
N
l
|
2 arcs can be generated by line l. The set of these arcs is formulated as A
l
=
{
(
n
i
,
n
j
)
l
∣
0
<
ρ
l
n
i
<
ρ
l
n
j
≤
|
N
l
|
}, where ρ
l
n denotes the sequence number that line l passes through node n. Let ρ
l
n
=
0 if l does not pass through n. Obviously, for any node n, ρ
l
n
∈
{
0,1
,
2
,
…
,
|
N
l
|
}. For example, l
1 of Figure 1 associates with the set of arcs A
l
1
=
{
(
n
1
,
n
2
)
l
1
,
(
n
1
,
n
3
)
l
1
,
(
n
2
,
n
3
)
l
1
}. In this model, it should be noted that only one arc in A
l, rather than two or more connected arcs, is traversed from the traveler’s boarding to alighting a vehicle of line l.Remark 1.
One of the challenges of this problem is the existence of multiple solutions, and it is fairly easily that an algorithm is trapped into some poor local minimums. This Remark elaborates this phenomenon and the solution method. In previous related works, the arcs of a USPT line typically only exist between the adjacent nodes; that is,A
l
=
{
(
n
i
,
n
j
)
l
∣
0
<
ρ
l
n
i
=
ρ
l
n
j
-
1
<
|
N
l
|
}. In practice, the disadvantage is shown as follows by an example. Consider the two USPT network models in Figure 2, where Figure 2(a) shows a previous network model and Figure 2(b) a modified one. A traveler goes from n
1 to n
3 starting at 9:00. There are the following two alternative itineraries.USPT network example.
(a)
(b)Itinerary 1. Wait 5 minutes and start at origin n
1, traveling by l
2 directly to the destination n
3.Itinerary 2. First travel by line l
1 to n
2, and wait 5 minutes and then travel by l
2 to n
4.They both arrive at destination at 9:50, so they are both the least-time itineraries in theory. But real-world traveler typically prefers Itinerary 1, because Itinerary 2 contains a transfer activity. In the model of Figure2(a), a label-setting algorithm (see Dijkstra 1959) will obviously choose Itinerary 2, because 9:25 is earlier than 9:30 regarding node n
2; that is to say, arc
(
n
1
,
n
2
)
l
1 dominates arc
(
n
1
,
n
2
)
l
2. In comparison, executing a label-setting algorithm in the model of Figure 2(b) will lead to the choice of Itinerary 1. In fact, once the arc
(
n
1
,
n
3
)
l
2 is searched, it will never be dominated, because there is no way to reach n
3 earlier than 9:50. It is observed that the aforementioned phenomenon exists comprehensively in our experiments. The results over the modified network model intrinsically have smaller number of transfer times; thus, it is more applicable.In most real-world cases, the destination noden
d cannot be reached by using only one line from the origin node n
o, so transfer is necessary. Transferring does not always occur at just one node; a traveler may have to walk some distance to another node in order to transfer. The tolerable walking distance is constrained by a constant upper bound D. Thus, the set of walking arcs is formulated as A
w
=
{
(
n
i
,
n
j
)
w
∣
n
i
≠
n
j
,
dist
⁡
(
n
i
,
n
j
)
<
D
}. Using the USPT network of Figure 1 as an example, (
n
3
,
n
5
)
w
∈
A
w while (
n
1
,
n
2
)
w
∉
A
w because dist
⁡
(
n
1
,
n
2
)
>
D. For denotation convenience, let USPTservice s denote either a line l or the walk w; that is, s
∈
L
⋃
{
w
}.In summary, with regard to USPT networkG
:
=
(
N
,
A
,
L
), N
=
⋃
l
∈
L
N
l, and A
=
⋃
l
∈
L
A
l
⋃
A
w. In general, anode
n
∈
N in this network represents a bus stop or metro station. An arc
(
n
i
,
n
j
)
s
∈
A shows an available move. In any given specific arc, the arc travel time does not always remain constant, which is actually dependent on the initial start time. This makes the USPT network a single-layer, bimodal, and time-dependent network.


### 2.2. Itinerary Structure and Timing

The Itinerary is represented as a sequence of orderly arcs or nodes in a static network, though there must be some adaptation in a USPT network context. An arc could not describe the temporal factor, so we define the time-label arc in Definition2. An itinerary in a USPT network could be represented as a sequence of time-label arcs.Definition 2.
Atime-label arc(t-arcfor short) is defined as a 4-tuple (
n
i
,
n
j
,
s
i
,
t
i
) link representing a passenger’s move from atail node
n
i to ahead node
n
j by means of atransport service
s
i at a giveninitial time
t
i. This representation is legitimate if and only if there exists an available transport service s
i
∈
L
⋃
{
w
} for a passenger who is located at node n
i
∈
N at time t
i (maybe with some waiting time) to move towards node n
j
∈
N. Using Figure 1 as an example, t
-arc
(
n
1
,
n
2
,
l
1
,
10
) denotes that a passenger arrives at node n
1 at the initial time 7:10:00 and travels to node n
2 by line l
1. In addition, subscripts of the service s
i and the initial time t
i are kept consistent with the tail node n
i. If necessary, superscripts are used to distinguish the different services and initial times.When a passenger travels fromn
o to n
d at a given initial time t
o, there can be numerous eligible itineraries. The set of these itineraries is denoted by P
t
o
(
n
o
,
n
d
), whose elements can be represented by a sequence of connective t-arcs shown in
(1)
p
t
o
(
n
o
,
n
d
)
=
{
(
n
|
p
|
,
n
d
,
s
|
p
|
,
t
|
p
|
)
(
n
o
,
n
2
,
s
o
,
t
o
)
,
(
n
2
,
n
3
,
s
2
,
t
2
)
,
…
,
(
n
|
p
|
,
n
d
,
s
|
p
|
,
t
|
p
|
)
}
,
where |
p
| is the number of t-arcs that compose p
t
o
(
n
o
,
n
d
).A passenger may be concerned about the total travel time of itineraryp
t
o
(
n
o
,
n
d
), which is the accumulated travel time of each component t-arc. The elapsed travel time therefore acts as the cost (weight) of each t-arc. There are three components of travel time as follows:(1)
in-vehicle time—elapsed during vehicular travel on the line,
(2)
walking time—elapsed during walking between two nodes for transfer purposes,
(3)
waiting time—elapsed at node waiting for the arriving transfer vehicle.Letπ be an operator that times each t-arc or itinerary. The computing method to time t-arc (
n
i
,
n
j
,
s
i
,
t
i
) depends on the associated transport service s
i. If s
i
=
w, the t-arc is traversed by walking. It calculates the fixed walking time cost as shown in
(2)
π
(
n
i
,
n
j
,
w
,
t
i
)
=
dist
⁡
(
n
i
,
n
j
)
v
walk
.The arrival time atn
j is then easily calculated in
(3)
t
j
=
t
i
+
π
(
n
i
,
n
j
,
w
,
t
i
)
.Ifs
i
=
l, the t-arc is traversed by line l. Both the in-vehicle time and the waiting time must be considered. Therefore, the associated travel time is not fixed but time dependent, as calculated in
(4)
π
(
n
i
,
n
j
,
l
,
t
i
)
=
θ
l
,
k
n
j
-
t
i
.Because the passenger will board the first arriving vehicle of the transferred linel, k of Formula (4) is determined by Formula (5); the waiting time and the in-vehicle time in this process are θ
l
,
k
n
i
-
t
i and θ
l
,
k
n
j
-
θ
l
,
k
n
i, respectively. The corresponding arrival time at n
j is calculated with Formula (6):
(5)
k
=
arg
{
min
⁡
k
⁡
(
θ
l
,
k
n
i
-
t
i
∣
θ
l
,
k
n
i
-
t
i
>
0
)
}
,
(6)
t
j
=
θ
l
,
k
n
j
.In any specific USPT network, once the initial timet
i of each t-arc (
n
i
,
n
j
,
s
i
,
t
i
) is known, the travel time of this t-arc π
(
n
i
,
n
j
,
s
i
,
t
i
) and the associated arrival time t
j can be easily calculated. With respect to any itinerary p
t
o
(
n
o
,
n
d
), the first initial time t
o is predetermined by the passenger, and the subsequent times can be calculated recursively by Formula (3) or (6). In other words, the initial time of a specific t-arc is equal to the arrival time of the upstream t-arc. In this case, the travel time of the itinerary formulated in Expression (1) can be written as
(7)
π
(
p
t
o
(
n
o
,
n
d
)
)
=
{
(
n
|
p
|
,
n
d
,
s
|
p
|
,
t
|
p
|
)
π
(
n
o
,
n
2
,
s
o
,
t
o
)
+
π
(
n
2
,
n
3
,
s
2
,
t
2
)
+
⋯
+
π
(
n
|
p
|
,
n
d
,
s
|
p
|
,
t
|
p
|
)
}
.Along with spatial and temporal features, practical operability should also be considered from the passenger’s perspective. Some properties of the itinerary that describe operability are given below.Property 1.
Twot-arcs that are traversed by walking cannot be adjacent, due to the hypothesis that a walking distance between two nodes cannot be larger than D. In other words, when s
i
=
w, we have s
i
+
1
≠
w, where i
=
o
,
2
,
…
,
|
p
|
-
1.Property 2.
During the travel process, if a line has been already used as a transport service, a passenger will not likely reuse this line or its inverted line (see Definition3) in his/her subsequent travel process. In other words, when s
i
≠
w, we have s
j
≠
s
i and s
j
≠
s
¯
i, where i
,
j
=
o
,
2,3
,
…
,
|
p
| and i
≠
j.Property 3.
In reality, a passenger is not likely to travel an itinerary that goes through a specific node twice. Therefore, we haven
i
≠
n
j, where i
,
j
=
o
,
2,3
,
…
,
|
p
|, d and i
≠
j.Definition 3.
With regard to a specific linel, there usually exists aninverted line
l
¯ that runs on almost the same road segments of l but in inverted directions. l is also the inverted line of l
¯; that is, l
¯
¯
=
l. Intuitively, l
3 is the inverted line of l
4 in the USPT network shown in Figure 1 (l
3
¯
=
l
4).Take the USPT network of Figure1 as an example, whose associated timetables are provided in Table 1. A passenger arrives at n
2 at 6:10, waits for 4 minutes, takes the first available vehicle trip of l
1 towards n
3, arrives at 6:25, walks to n
6 using 180
m
/
1.5
m
/
s
=
2
(
min
⁡
), waits for 3 minutes, boards the vehicle on the 5th trip of l
4 at 6:30, and finally arrives at n
7 at 6:45. This itinerary is represented by p
10
(
n
2
,
n
7
)
=
{
(
n
2
,
n
3
,
l
1
,
6
:
10
)
,
(
n
3
,
n
6
,
w
,
6
:
25
)
,
(
n
6
,
n
7
,
l
4
,
6
:
27
)
} and consumes 35 minutes in total; thus, π
(
p
6
:
10
(
n
2
,
n
7
)
)
=
35
(
min
⁡
).


### 2.3. Problem Formulation

In any specific USPT network, a passenger decides to travel from an originn
o to a destination n
d, at an initial time t
o. The problem is determining a connected itinerary among the large volume of available choices that requires a minimum of travel time. This can be mathematically formulated as follows:
(8)
min
⁡
π
(
p
t
o
(
n
o
,
n
d
)
)
s.t.
p
t
o
(
n
o
,
n
d
)
∈
P
t
o
(
n
o
,
n
d
)
.The travel time of thet-arc traversed by walking is fixed, while that traversed by a line is time dependent, thus leading to a time-dependent rather than static USPT network. The LTIP-USPT pertains to the least-time itinerary planning problem in a bimodal, time-dependent scheduled network. The traditional shortest path algorithms do not apply. Through the adaptation of the A* algorithm, Section 3 develops an ad hoc Floyd-A* algorithm to address the LTIP-USPT. The following hypotheses are assumed and summarized as follows.(1)
Line vehicles run punctually.
(2)
The vehicle capacities are infinite.
(3)
The road network is noncongested.
(4)
The vehicle departs immediately after arriving at a specific node.
(5)
The origins and destinations are all located just at nodes.
(6)
One walking distance cannot be greater than the tolerable upper boundD.The findings of this research can be widely used; they can assist passengers in arranging their travel and be integrated into traffic assignment models. They can also verify the accessibility of a USPT network and help in the design of timetables, contributing both theoretically and practically.


## 2.1. A Modified Scheduled Network Model

Intuitively, Figure1(a) shows an example of a physical USPT network, and the associated modified network model G
:
=
(
N
,
A
,
L
) is shown in Figure 1(b). The advantage of this model beyond previous scheduled network model can be found in Remark 1. Table 1 gives an associated timetable example.Table 1
A timetable example.
k
n
l
1
l
2
l
3
l
4
l
5
n
1
n
2
n
3
n
4
n
1
n
2
n
4
n
5
n
6
n
7
n
1
n
7
1
6:02
6:14
6:25
6:05
6:18
6:30
6:05
6:15
6:02
6:16
6:00
6:12
2
6:08
6:21
6:31
6:15
6:29
6:40
6:10
6:20
6:10
6:23
6:03
6:15
3
6:13
6:25
6:36
6:25
6:39
6:51
6:15
6:24
6:18
6:32
6:06
6:17
4
6:18
6:29
6:39
6:33
6:46
6:58
6:20
6:30
6:26
6:40
6:09
6:20
5
6:22
6:34
6:44
6:41
6:54
7:07
6:23
6:33
6:30
6:45
6:12
6:24
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮A USPT network example.
(a)
(b)Letl
:
=
(
N
l
,
A
l
,
T
l
)
∈
L denote the scheduled directed USPTlinethat operates on the USPT network. The USPT line typically refers to (but not constrained to) the bus line or metro line that runs on fixed road and runs through a predetermined serious of nodes N
l based on a timetable T
l. There are numerousvehicle trips within a single day. θ
l
,
k
n, element of T
l represents the scheduled time when the kth vehicle trip of l arrives or departs at node n
∈
N
l. Table 1 shows a timetable example, where, for example, θ
l
1
,
2
n
2
=
6
:
21.Any move along a specific line is not necessarily between two adjacent nodes but may pass through one or more intermediate nodes. Correspondingly,C
|
N
l
|
2 arcs can be generated by line l. The set of these arcs is formulated as A
l
=
{
(
n
i
,
n
j
)
l
∣
0
<
ρ
l
n
i
<
ρ
l
n
j
≤
|
N
l
|
}, where ρ
l
n denotes the sequence number that line l passes through node n. Let ρ
l
n
=
0 if l does not pass through n. Obviously, for any node n, ρ
l
n
∈
{
0,1
,
2
,
…
,
|
N
l
|
}. For example, l
1 of Figure 1 associates with the set of arcs A
l
1
=
{
(
n
1
,
n
2
)
l
1
,
(
n
1
,
n
3
)
l
1
,
(
n
2
,
n
3
)
l
1
}. In this model, it should be noted that only one arc in A
l, rather than two or more connected arcs, is traversed from the traveler’s boarding to alighting a vehicle of line l.Remark 1.
One of the challenges of this problem is the existence of multiple solutions, and it is fairly easily that an algorithm is trapped into some poor local minimums. This Remark elaborates this phenomenon and the solution method. In previous related works, the arcs of a USPT line typically only exist between the adjacent nodes; that is,A
l
=
{
(
n
i
,
n
j
)
l
∣
0
<
ρ
l
n
i
=
ρ
l
n
j
-
1
<
|
N
l
|
}. In practice, the disadvantage is shown as follows by an example. Consider the two USPT network models in Figure 2, where Figure 2(a) shows a previous network model and Figure 2(b) a modified one. A traveler goes from n
1 to n
3 starting at 9:00. There are the following two alternative itineraries.USPT network example.
(a)
(b)Itinerary 1. Wait 5 minutes and start at origin n
1, traveling by l
2 directly to the destination n
3.Itinerary 2. First travel by line l
1 to n
2, and wait 5 minutes and then travel by l
2 to n
4.They both arrive at destination at 9:50, so they are both the least-time itineraries in theory. But real-world traveler typically prefers Itinerary 1, because Itinerary 2 contains a transfer activity. In the model of Figure2(a), a label-setting algorithm (see Dijkstra 1959) will obviously choose Itinerary 2, because 9:25 is earlier than 9:30 regarding node n
2; that is to say, arc
(
n
1
,
n
2
)
l
1 dominates arc
(
n
1
,
n
2
)
l
2. In comparison, executing a label-setting algorithm in the model of Figure 2(b) will lead to the choice of Itinerary 1. In fact, once the arc
(
n
1
,
n
3
)
l
2 is searched, it will never be dominated, because there is no way to reach n
3 earlier than 9:50. It is observed that the aforementioned phenomenon exists comprehensively in our experiments. The results over the modified network model intrinsically have smaller number of transfer times; thus, it is more applicable.In most real-world cases, the destination noden
d cannot be reached by using only one line from the origin node n
o, so transfer is necessary. Transferring does not always occur at just one node; a traveler may have to walk some distance to another node in order to transfer. The tolerable walking distance is constrained by a constant upper bound D. Thus, the set of walking arcs is formulated as A
w
=
{
(
n
i
,
n
j
)
w
∣
n
i
≠
n
j
,
dist
⁡
(
n
i
,
n
j
)
<
D
}. Using the USPT network of Figure 1 as an example, (
n
3
,
n
5
)
w
∈
A
w while (
n
1
,
n
2
)
w
∉
A
w because dist
⁡
(
n
1
,
n
2
)
>
D. For denotation convenience, let USPTservice s denote either a line l or the walk w; that is, s
∈
L
⋃
{
w
}.In summary, with regard to USPT networkG
:
=
(
N
,
A
,
L
), N
=
⋃
l
∈
L
N
l, and A
=
⋃
l
∈
L
A
l
⋃
A
w. In general, anode
n
∈
N in this network represents a bus stop or metro station. An arc
(
n
i
,
n
j
)
s
∈
A shows an available move. In any given specific arc, the arc travel time does not always remain constant, which is actually dependent on the initial start time. This makes the USPT network a single-layer, bimodal, and time-dependent network.


## 2.2. Itinerary Structure and Timing

The Itinerary is represented as a sequence of orderly arcs or nodes in a static network, though there must be some adaptation in a USPT network context. An arc could not describe the temporal factor, so we define the time-label arc in Definition2. An itinerary in a USPT network could be represented as a sequence of time-label arcs.Definition 2.
Atime-label arc(t-arcfor short) is defined as a 4-tuple (
n
i
,
n
j
,
s
i
,
t
i
) link representing a passenger’s move from atail node
n
i to ahead node
n
j by means of atransport service
s
i at a giveninitial time
t
i. This representation is legitimate if and only if there exists an available transport service s
i
∈
L
⋃
{
w
} for a passenger who is located at node n
i
∈
N at time t
i (maybe with some waiting time) to move towards node n
j
∈
N. Using Figure 1 as an example, t
-arc
(
n
1
,
n
2
,
l
1
,
10
) denotes that a passenger arrives at node n
1 at the initial time 7:10:00 and travels to node n
2 by line l
1. In addition, subscripts of the service s
i and the initial time t
i are kept consistent with the tail node n
i. If necessary, superscripts are used to distinguish the different services and initial times.When a passenger travels fromn
o to n
d at a given initial time t
o, there can be numerous eligible itineraries. The set of these itineraries is denoted by P
t
o
(
n
o
,
n
d
), whose elements can be represented by a sequence of connective t-arcs shown in
(1)
p
t
o
(
n
o
,
n
d
)
=
{
(
n
|
p
|
,
n
d
,
s
|
p
|
,
t
|
p
|
)
(
n
o
,
n
2
,
s
o
,
t
o
)
,
(
n
2
,
n
3
,
s
2
,
t
2
)
,
…
,
(
n
|
p
|
,
n
d
,
s
|
p
|
,
t
|
p
|
)
}
,
where |
p
| is the number of t-arcs that compose p
t
o
(
n
o
,
n
d
).A passenger may be concerned about the total travel time of itineraryp
t
o
(
n
o
,
n
d
), which is the accumulated travel time of each component t-arc. The elapsed travel time therefore acts as the cost (weight) of each t-arc. There are three components of travel time as follows:(1)
in-vehicle time—elapsed during vehicular travel on the line,
(2)
walking time—elapsed during walking between two nodes for transfer purposes,
(3)
waiting time—elapsed at node waiting for the arriving transfer vehicle.Letπ be an operator that times each t-arc or itinerary. The computing method to time t-arc (
n
i
,
n
j
,
s
i
,
t
i
) depends on the associated transport service s
i. If s
i
=
w, the t-arc is traversed by walking. It calculates the fixed walking time cost as shown in
(2)
π
(
n
i
,
n
j
,
w
,
t
i
)
=
dist
⁡
(
n
i
,
n
j
)
v
walk
.The arrival time atn
j is then easily calculated in
(3)
t
j
=
t
i
+
π
(
n
i
,
n
j
,
w
,
t
i
)
.Ifs
i
=
l, the t-arc is traversed by line l. Both the in-vehicle time and the waiting time must be considered. Therefore, the associated travel time is not fixed but time dependent, as calculated in
(4)
π
(
n
i
,
n
j
,
l
,
t
i
)
=
θ
l
,
k
n
j
-
t
i
.Because the passenger will board the first arriving vehicle of the transferred linel, k of Formula (4) is determined by Formula (5); the waiting time and the in-vehicle time in this process are θ
l
,
k
n
i
-
t
i and θ
l
,
k
n
j
-
θ
l
,
k
n
i, respectively. The corresponding arrival time at n
j is calculated with Formula (6):
(5)
k
=
arg
{
min
⁡
k
⁡
(
θ
l
,
k
n
i
-
t
i
∣
θ
l
,
k
n
i
-
t
i
>
0
)
}
,
(6)
t
j
=
θ
l
,
k
n
j
.In any specific USPT network, once the initial timet
i of each t-arc (
n
i
,
n
j
,
s
i
,
t
i
) is known, the travel time of this t-arc π
(
n
i
,
n
j
,
s
i
,
t
i
) and the associated arrival time t
j can be easily calculated. With respect to any itinerary p
t
o
(
n
o
,
n
d
), the first initial time t
o is predetermined by the passenger, and the subsequent times can be calculated recursively by Formula (3) or (6). In other words, the initial time of a specific t-arc is equal to the arrival time of the upstream t-arc. In this case, the travel time of the itinerary formulated in Expression (1) can be written as
(7)
π
(
p
t
o
(
n
o
,
n
d
)
)
=
{
(
n
|
p
|
,
n
d
,
s
|
p
|
,
t
|
p
|
)
π
(
n
o
,
n
2
,
s
o
,
t
o
)
+
π
(
n
2
,
n
3
,
s
2
,
t
2
)
+
⋯
+
π
(
n
|
p
|
,
n
d
,
s
|
p
|
,
t
|
p
|
)
}
.Along with spatial and temporal features, practical operability should also be considered from the passenger’s perspective. Some properties of the itinerary that describe operability are given below.Property 1.
Twot-arcs that are traversed by walking cannot be adjacent, due to the hypothesis that a walking distance between two nodes cannot be larger than D. In other words, when s
i
=
w, we have s
i
+
1
≠
w, where i
=
o
,
2
,
…
,
|
p
|
-
1.Property 2.
During the travel process, if a line has been already used as a transport service, a passenger will not likely reuse this line or its inverted line (see Definition3) in his/her subsequent travel process. In other words, when s
i
≠
w, we have s
j
≠
s
i and s
j
≠
s
¯
i, where i
,
j
=
o
,
2,3
,
…
,
|
p
| and i
≠
j.Property 3.
In reality, a passenger is not likely to travel an itinerary that goes through a specific node twice. Therefore, we haven
i
≠
n
j, where i
,
j
=
o
,
2,3
,
…
,
|
p
|, d and i
≠
j.Definition 3.
With regard to a specific linel, there usually exists aninverted line
l
¯ that runs on almost the same road segments of l but in inverted directions. l is also the inverted line of l
¯; that is, l
¯
¯
=
l. Intuitively, l
3 is the inverted line of l
4 in the USPT network shown in Figure 1 (l
3
¯
=
l
4).Take the USPT network of Figure1 as an example, whose associated timetables are provided in Table 1. A passenger arrives at n
2 at 6:10, waits for 4 minutes, takes the first available vehicle trip of l
1 towards n
3, arrives at 6:25, walks to n
6 using 180
m
/
1.5
m
/
s
=
2
(
min
⁡
), waits for 3 minutes, boards the vehicle on the 5th trip of l
4 at 6:30, and finally arrives at n
7 at 6:45. This itinerary is represented by p
10
(
n
2
,
n
7
)
=
{
(
n
2
,
n
3
,
l
1
,
6
:
10
)
,
(
n
3
,
n
6
,
w
,
6
:
25
)
,
(
n
6
,
n
7
,
l
4
,
6
:
27
)
} and consumes 35 minutes in total; thus, π
(
p
6
:
10
(
n
2
,
n
7
)
)
=
35
(
min
⁡
).


## 2.3. Problem Formulation

In any specific USPT network, a passenger decides to travel from an originn
o to a destination n
d, at an initial time t
o. The problem is determining a connected itinerary among the large volume of available choices that requires a minimum of travel time. This can be mathematically formulated as follows:
(8)
min
⁡
π
(
p
t
o
(
n
o
,
n
d
)
)
s.t.
p
t
o
(
n
o
,
n
d
)
∈
P
t
o
(
n
o
,
n
d
)
.The travel time of thet-arc traversed by walking is fixed, while that traversed by a line is time dependent, thus leading to a time-dependent rather than static USPT network. The LTIP-USPT pertains to the least-time itinerary planning problem in a bimodal, time-dependent scheduled network. The traditional shortest path algorithms do not apply. Through the adaptation of the A* algorithm, Section 3 develops an ad hoc Floyd-A* algorithm to address the LTIP-USPT. The following hypotheses are assumed and summarized as follows.(1)
Line vehicles run punctually.
(2)
The vehicle capacities are infinite.
(3)
The road network is noncongested.
(4)
The vehicle departs immediately after arriving at a specific node.
(5)
The origins and destinations are all located just at nodes.
(6)
One walking distance cannot be greater than the tolerable upper boundD.The findings of this research can be widely used; they can assist passengers in arranging their travel and be integrated into traffic assignment models. They can also verify the accessibility of a USPT network and help in the design of timetables, contributing both theoretically and practically.


## 3. Floyd-A* Algorithm for LTIP-USPT

To solve the LTIP-USPT efficiently, an ad hoc Floyd-A* algorithm is developed that is composed of two procedures, that is, an A*-based Itinerary Finder and a Floyd-based Cost Estimator. The basic scheme of the Floyd-A* algorithm is shown in Figure3.Figure 3
Scheme of Floyd-A* procedure.TheCost Estimator precalculates the estimated travel times of itineraries between any two nodes in aslacked USPT network, where static arc travel time is given as the lower bound of the associated time-dependent actual travel time. These values are stored in TableH. This is accomplished by a Floyd-based algorithm [26], which is a well-known all-to-all shortest paths algorithm. Once complete, the Cost Estimator is no longer required unless there is an update to the USPT network. The A*-basedItinerary Finder makes use of the TableH obtained by the Cost Estimator as heuristic information, determining the least-time itinerary. In the case that traveler inputs a triad of (
n
o
,
n
d
,
t
o
), only the Itinerary Finder conducts a real-time computation. These two procedures are expounded in detail in Sections 3.1 and 3.2, respectively. Section 3.3 mathematically proves its admissibility and analyzes the corresponding computing efficiency by comparing it with Plain-A* and Dijkstra-like procedures.Remark 4.
Speed-up technologies such as “Avoiding Binary Search” and “Further Speedup When Modeling with Train Routes” discussed in the work of Pyrga et al. [25] may further contribute to a higher efficiency. However, this paper only concerns a more efficient A*-based search (also known as goal-directed search), which could coexist with other speed-up technologies to further speed up computing.


### 3.1. Least-Time Itinerary-Finder Procedure

Assuming that typical readers may not be familiar with the A* algorithm, this searching process will be explained in detail. Given a triad of origin, destination, and initial time(
n
o
,
n
d
,
t
o
) to determine an LT itinerary p
t
o
(
n
o
,
n
d
)
∈
P
t
o
(
n
o
,
n
d
), the Itinerary Finder expands promisingorigin-rooted partial itineraries (partial itineraryfor short) in a node-to-node manner. Beginning with n
o, eachsuccessor
n
o
+ is expanded by searching for each t-arc (
n
o
,
n
o
+
,
s
o
,
t
o
) in the first round. Each of these t-arcs (partial itineraries) may contribute to the LT itinerary. During the second round, we must determine which terminal node of partial itinerary among several candidates is the most promising one.Let each noden
i be associated with a state denoted bystate(n
i). There are three states of node n
i.(1)
NEW: node n
i has not been expanded up to now.
(2)
OPEN: node n
i has been expanded and acts as a candidate to expand to another node in the next searching process. That is to say, for each partial itinerary p
t
o
(
n
o
,
n
i
) thus far,state(n
i) = OPEN.
(3)
CLOSED: node n
i has been expanded and has already expanding to another node. In other words, for any node n
j
≠
n
i that has gone through by any current partial itinerary p
t
o
(
n
o
,
n
i
),state(n
j) = CLOSED.As defined above, the nodes associated with the state OPEN are candidates for expanding partial itineraries. For convenience, we use relative time rather than absolute time hereafter. Using the USPT network of Figure1 as an example, let n
o
=
n
1, n
d
=
n
5 and t
o
=
2 (minutes after 6:00). Figure 4 combined with Table 2 shows part of the searching process.Table 2
The changing labels of nodes associated with Figure4.
Node
Labels
S
t
a
t
e
(
n
)
t
i
=
g
′
(
n
)
+
t
o
g
′
(
n
)
h
′
(
n
)
f
′
(
n
)
P
r
e
(
n
)
Updated
Initialization
n
1
OPEN
2
0
21
21
nil
*√
n
2
NEW
∞
∞
∞
∞
nil
n
3
NEW
∞
∞
∞
∞
nil
n
4
NEW
∞
∞
∞
∞
nil
n
5
NEW
∞
∞
∞
∞
nil
n
6
NEW
∞
∞
∞
∞
nil
n
7
NEW
∞
∞
∞
∞
nil
1st searching round
n
1
CLOSED
2
0
21
21
nil
*
n
2
OPEN
min
⁡
{
14,30
}
=
14
12
11.5
23.5
{
(
n
1
,
n
2
,
l
1
,
2
)
}
*
n
3
OPEN
25
23
1.5
24.5
{
(
n
1
,
n
3
,
l
1
,
2
)
}
*
n
4
NEW
∞
∞
∞
∞
nil
n
5
NEW
∞
∞
∞
∞
nil
n
6
NEW
∞
∞
∞
∞
nil
n
7
OPEN
15
13
10
23
{
(
n
1
,
n
7
,
l
5
,
2
)
}
*√
2nd searching round
n
1
CLOSED
2
0
21
21
nil
n
2
OPEN
14
12
11.5
23.5
{
(
n
1
,
n
2
,
l
1
,
2
)
}
n
3
OPEN
25
23
1.5
24.5
{
(
n
1
,
n
3
,
l
1
,
2
)
}
n
4
OPEN
15
+
1
=
16
14
9
23
{
(
n
1
,
n
7
,
l
5
,
2
)
,
(
n
7
,
n
4
,
w
,
15
)
}
*√
n
5
NEW
∞
∞
∞
∞
nil
n
6
NEW
∞
∞
∞
∞
nil
n
7
CLOSED
15
13
10
23
{
(
n
1
,
n
7
,
l
5
,
2
)
}
*
3rd searching round
n
1
CLOSED
2
0
21
21
nil
n
2
OPEN
min
⁡
{
14,51
}
=
14
12
11.5
23.5
{
(
n
1
,
n
2
,
l
1
,
2
)
}
*√
n
3
OPEN
25
23
1.5
24.5
{
(
n
1
,
n
3
,
l
1
,
2
)
}
n
4
CLOSED
16
14
9
23
{
(
n
1
,
n
7
,
l
5
,
2
)
,
(
n
7
,
n
4
,
w
,
15
)
}
*
n
5
OPEN
30
28
0
28
{
(
n
1
,
n
7
,
l
5
,
2
)
,
(
n
7
,
n
4
,
w
,
15
)
,
(
n
4
,
n
5
,
l
3
,
16
)
}
*
n
6
NEW
∞
∞
∞
∞
nil
n
7
CLOSED
15
13
10
23
{
(
n
1
,
n
7
,
l
5
,
2
)
}
√The node to be COLSED in the next searching round; *The node whose labels are updated in the searching round.Partial searching process by Floyd-A*.
(a)
(b)
(c)
(d)We first initialize the state of originn
1 as OPEN and others as NEW by default (see Figure 4(a)). In the first expansion round (see Figure 4(b)), n
2, n
3, and n
7 are expanded by searching for t-arcs (
n
1
,
n
2
,
l
1
,
2
), (
n
1
,
n
2
,
l
2
,
2
), (
n
1
,
n
3
,
l
1
,
2
), and (
n
1
,
n
7
,
l
5
,
2
). At the same time, n
1 becomes CLOSED; n
2, n
3, and n
7 turn from NEW to OPEN. The next paragraph shows that {
(
n
1
,
n
7
,
l
5
,
2
)
} is the most promising partial itinerary and t
7
=
15; thus, we should continue the second expansion round for the most promising node n
7, and only n
4 is expanded by searching for a t-arc (
n
7
,
n
4
,
w
,
15
). This time, n
7 becomes CLOSED and n
4 turns to OPEN (see Figure 4(c)). The searching process continues by similar means. Note that the state of a node may turn from NEW to OPEN, from OPEN to CLOSED, or remain the same. However, a CLOSED node can never re-OPEN (see Theorem 10), for example, (
n
4
,
n
1
,
l
2
,
16
) is searched in the 3rd searching round (see Figure 4(d)), but the state of n
1 unconditionally remains CLOSED.The exposition above focuses on the changing states of nodes during the expansion of partial itineraries. To determine the most promising OPEN node among several candidates,f
′
(
n
i
) is defined as the estimated travel time of an LT itinerary p
t
o
(
n
o
,
n
i
,
n
d
). For each partial itinerary p
t
o
(
n
o
,
n
i
), the terminal node(s) n
i whose f
′
(
n
i
) is/are the minimum one(s) among those of all OPEN nodes is/are identified as the most promising one(s). If there is more than one, you may choose the first expanded one.The actual travel time of the LT itineraryp
t
o
(
n
o
,
n
i
,
n
d
) can be the summation of two parts calculated as
(9)
π
(
p
t
o
(
n
o
,
n
i
,
n
d
)
)
=
π
(
p
t
o
(
n
o
,
n
i
)
)
+
π
(
p
t
i
(
n
i
,
n
d
)
)
.However, it is difficult to calculateπ
(
p
t
o
(
n
o
,
n
i
)
) and π
(
p
t
i
(
n
i
,
n
d
)
) in real-time within an acceptable computing time. Because of the time-dependence factor, they are not able to be precalculated and stored as fixed values. This is a different situation from a static network context. Therefore, g
′
(
n
i
) and h
′
(
n
i
) are defined to estimate them, respectively. f
′
(
n
i
) is their summation, calculated as
(10)
f
′
(
n
i
)
=
g
′
(
n
i
)
+
h
′
(
n
i
)
.The A*-based Itinerary Finder utilizes the minimum travel time of the partial itineraryp
t
o
(
n
o
,
n
i
), determined to this point as g
′
(
n
i
); the strategy for estimating h
′
(
n
i
) will be addressed in Section 3.2. To illustrate the process for selecting the most promising node, we again use the USPT network of Figure 1 as an example. A traveler first predetermines t
1
=
2. In the first searching round (see Figure 4(b)), π
(
n
1
,
n
2
,
l
1
,
2
)
=
12
(
min
⁡
), π
(
n
1
,
n
2
,
l
2
,
2
)
=
28, π
(
n
1
,
n
3
,
l
1
,
2
)
=
23, and π
(
n
1
,
n
7
,
l
5
,
2
)
=
13 can be easily determined with Formula (4). One can easily determine that g
′
(
n
2
)
=
min
⁡
{
12,28
}
=
12, g
′
(
n
3
)
=
23, and g
′
(
n
7
)
=
13. As for the heuristic information yielded by the Cost Estimator, h
′
(
n
2
)
=
11.5, h
′
(
n
3
)
=
1.5, and h
′
(
n
7
)
=
10. Thus, f
′
(
n
2
)
=
g
′
(
n
2
)
+
h
′
(
n
2
)
=
12
+
11.5
=
23.5. Similarly, we have f
′
(
n
3
)
=
24.5 and f
′
(
n
7
)
=
23. Dijkstra-based approaches only consider the performances of origin-rooted partial itineraries and thus identify {
(
n
1
,
n
2
,
l
2
,
2
)
} as the most promising partial itinerary due to g
′
(
n
2
)
<
g
′
(
n
7
)
<
g
′
(
n
3
). The A*-based approaches, however, are goal-directed by the heuristics, and the Itinerary Finder selects n
7 as a result of f
′
(
n
7
)
<
f
′
(
n
2
)
<
f
′
(
n
3
). Similarly, the second searching round selects the terminal node of {
(
n
1
,
n
7
,
l
5
,
2
)
,
(
n
7
,
n
4
,
w
,
15
)
}, that is, n
4, as the most promising node, and so forth. Note that in the 3rd searching round, the t-arc (
n
4
,
n
2
,
l
2
,
16
) is searched. We have t
2
=
51 calculated by Formula (4), meaning that g
′
(
n
2
) of OPEN node n
2 will be potentially turned to 51
-
t
o
=
49. However, because the previous value of g
′
(
n
2
) is 12 and 49
>
12, the value of g
′
(
n
2
) is not updated but remains 12. In another words, the partial itinerary {
(
n
1
,
n
2
,
l
1
,
2
)
} dominates {
(
n
1
,
n
7
,
l
5
,
2
)
,
(
n
7
,
n
4
,
w
,
15
)
,
(
n
4
,
n
2
,
l
2
,
16
)
}, referring to the partial itinerary from n
1 to n
2. The destination n
5 is also expanded in this searching round; the associated state turns to OPEN. The searching process will continue, however, untilstate(n
5) = CLOSED.Through the scheme that is recursively expanding, comparing, and selecting promising partial itineraries, the algorithm is terminated once the state of destination turns to CLOSED. If an algorithm is guaranteed to determine an optimal itinerary from origin to destination, we designate it asadmissible. The Itinerary Finder is proven to be admissible in Section 3.3. The Itinerary Finder places OPEN nodes in an OPEN list and CLOSED nodes in a CLOSED list. If the state of the node cannot be placed either in the OPEN or CLOSED list it is regarded as NEW as default. In a summary of the above analysis, the outline of the Itinerary Finder is presented in Algorithm 1.Algorithm 1:Procedure of Itinerary Finder (
n
o
,
n
d
,
t
o
).
Step  0. (Initialization):
Set OPEN list =⌀ and CLOSED list = ⌀
Setg
′
(
n
i
)
=
∞
,
h
′
(
n
i
)
=
∞
,
f
′
(
n
i
)
=
∞ and p
r
e
(
n
i
)
=
n
i
l where n
i
∈
N
Addn
o to OPEN list, set g
′
(
n
o
)
=
0
Calculatef
′
(
n
o
)
=
g
′
(
n
o
)
+
h
′
(
n
o
) where h
′
(
n
o
) is pre-calculated by Cost-Estimator
Step  1. (Expanding partial itinerary):
while  OPEN list  ≠
⌀  do
Select any noden
i
∈
{
n
i
∣
min
⁡
(
f
′
(
n
i
)
)
,
s
t
a
t
e
(
n
i
)
=
O
P
E
N
}
if  n
i
=
n
d  then
Go to Step  2
else
Move n
i from OPEN list to CLOSED list
end if
for all  t-arc (
n
i
,
n
i
+
,
s
i
,
t
i
)  do
if   n
i
+ in CLOSED list  then
continue
end if
if  s
i
=
s
i
-
=
w  then// Set s
o
-
=
n
i
l previously
continue
end if
if  s
i
=
s
m or s
i
=
s
i
- where s
m
=
s
o
,
s
o
+
,
…
,
s
i
- then
continue
end if
Calculate π
(
n
i
,
n
i
+
,
s
i
,
t
i
) by formula (2) or (4)
if
g
′
(
n
i
)
+
π
(
n
i
,
n
i
+
,
s
i
,
t
i
)
≥
g
′
(
n
i
+
)  then
continue
else if  n
i
+ not  in OPEN list  then
Add n
i
+ to OPEN list
end if
Calculate corresponding t
i
+ by formula (3) or (6)
Update g
′
(
n
i
+
) with g
′
(
n
i
+
)
+
π
(
n
i
,
n
i
+
,
s
i
,
t
i
)
Calculate f
′
(
n
i
+
)
=
g
′
(
n
i
+
)
+
h
′
(
n
i
+
)
Record p
r
e
(
n
i
+
)
=
{
(
n
i
,
n
i
+
,
s
i
,
t
i
)
}
end for
end while
Step  2. (Reconstructing LT itinerary):
Reconstruct LT itineraryp
t
o
(
n
o
,
n
d
) by recursively recalling p
r
e
(
n
i
) where n
i
=
n
d
,
n
d
-
,
…
,
n
o
+
Returnp
t
o
(
n
o
,
n
d
)If more detailed information (e.g., waiting time, in-vehicle time) is required with respect to a specific arc, this can be obtained by simply adding to pre(n
i) in the associated iteration.


### 3.2. Cost-Estimator Procedure for a Tighter Lower Bound

The Itinerary-Finder procedure must be well informed when making a choice to expand partial itineraries. Expanding an unlikely part of an LT itinerary is a waste of computational time, while missing a promising partial itinerary may lead to a failure in determining the LT itinerary. Therefore, the strategy of estimating the travel time of a destination-ended partial itinerary is viewed as the key to improving the efficiency of the Itinerary Finder. Meanwhile, the estimated travel time must be a lower bound of the real travel time. Note that a tighter lower bound results in higher efficiency.The travel time of an itinerary is composed of the travel time during walking between two nodes, waiting at nodes for a transfer, and traveling in vehicles. The walking time between two specific nodes is fixed. The waiting time varies in different cases. If fortunate, a traveler can transfer without waiting time. The in-vehicle time depends on the timetable of different lines combined with their different vehicle trips. This paper proposes a strategy to estimate the travel time between two nodes as a tight static lower bound of this real time-dependent value. The basic concept is shown by generating an associated slacked network (see Definition5) of the USPT network; the minimum travel time of itinerary in this SUSPT network is the associated estimated value in the USPT network.Definition 5.
A slacked USPT network (SUSPT network for short) is defined to share the same topological structure as the USPT network. However, each arc of the SUSPT network is assigned a static travel time as a lower bound of the associated real travel time of the arc in the USPT network. The arc in the SUSPT network is timed by explicitly slacking the associated real travel time by using the following 3 rules. Figure 5 shows the associated SUSPT network of the USPT network of Figure 1.Figure 5
Associated SUSPT network of the USPT network of Figure1.Rule 1.
Walking times remain the same.Rule 2.
Ignore all waiting times.Rule 3.
Let the minimum travel time among those traversed by different lines combined with different vehicle trips between two specific nodes be the estimated travel time.Obviously, there exist no temporal concepts in the static SUSPT network; therefore, let each initial time oft-arc in the SUSPT network benil. Let π
′ denote the operator to time the t-arc in SUSPT network. Rule 1 can be reflected in Formula (11). Rules 2 and 3 are interpreted in Formula (12):
(11)
π
′
(
n
i
,
n
j
,
w
,
n
i
l
)
=
dist
⁡
(
n
i
,
n
j
)
v
walk
,
(12)
π
′
(
n
i
,
n
j
,
l
,
n
i
l
)
=
min
⁡
k
(
θ
l
,
k
n
j
-
θ
l
,
k
n
i
)
.For this problem, typical all-to-all shortest paths algorithms are qualified. This paper chooses a well-known Floyd algorithm. We assume typical readers have already known the algorithm, so there is no detailed exposition here.The outline of the procedure is shown in Algorithm2.Algorithm 2:Procedure of Cost Estimator.
Step  0. (Initialize the SUSPT network):
for all  n
i
∈
N  do
for all  n
j
∈
N  do
H
(
i
,
j
)
=
mi
n
s
π
′
(
n
i
,
n
j
,
s
,
n
i
l
)
end for
end for
Step  1. (Calculate costs of all-to-all shortest paths):
for all  n
m
∈
N  do
for all  n
i
∈
N  do
for all  n
j
∈
N  do
if  H
(
i
,
j
)
>
H
(
i
,
k
)
+
H
(
k
,
j
)   then
H
(
i
,
j
)
>
H
(
i
,
k
)
+
H
(
k
,
j
)
end if
end for
end for
end forRemark 6.
In this work, the Itinerary Finder obtainsh
′
(
n
i
) from table H outputted by the Cost Estimator, while the previous related works substituted h
′
(
n
i
) with Formula (13), which was calculated in an online way. The strategy proposed in this work is proved to generate a tighter lower bound and thus leads the Floyd-A* algorithm to be more efficient both in theory and in computation experiments (see Sections 3.3, 4.1, and 4.2):
(13)
h
′
(
n
i
)
=
dist
⁡
(
n
i
,
n
d
)
v
max
⁡
.


### 3.3. Admissibility and Efficiency Analysis

The admissibility and efficiency of the Floyd-A* algorithm are discussed in this section. Hart et al. [17] established how to determine the admissibility of an A* algorithm, which is primarily affected by the travel time estimating strategy of the destination-ended partial itineraries shown in Lemma 7. On this basis, Theorem 8 establishes the admissibility of the Itinerary Finder.Lemma 7.
Ifh
′
(
n
i
)
≤
π
(
p
t
i
(
n
i
,
n
d
)
), then A* is admissible [17].Theorem 8.
The Cost Estimator guarantees that the Itinerary Finder is admissible.Proof.
The Itinerary Finder is A*-based, whereh
′
(
n
i
) is computed by the Cost Estimator. To prove Theorem 8, we learn from Lemma 7 that it is equivalent to prove that the Cost Estimator guarantees each h
′
(
n
i
)
≤
π
(
p
t
i
(
n
i
,
n
d
)
).
Letp
t
i
(
n
i
,
n
d
)
=
{
(
n
i
,
n
i
+
,
s
i
,
t
i
)
,
…
,
(
n
d
-
,
n
d
,
s
d
-
,
t
d
-
)
} be a destination-ended partial itinerary of the actual LT itinerary p
t
o
(
n
o
,
n
d
). Therefore,
(14)
π
(
p
t
i
(
n
i
,
n
d
)
)
=
π
(
n
i
,
n
i
+
,
s
i
,
t
i
)
+
⋯
+
π
(
n
d
-
,
n
d
,
s
d
-
,
t
d
-
)
.
p
nil
(
n
i
,
n
d
)
=
{
(
n
i
,
n
i
+
′
,
s
i
′
,
n
i
l
)
,
…
,
(
n
d
-
′
,
n
d
,
s
d
-
′
,
n
i
l
)
} denotes the LT itinerary in the SUSPT network. Note that the topological structures of p
t
i
(
n
i
,
n
d
) and p
n
i
l
(
n
i
,
n
d
) are not necessarily the same.
Ifs
i
=
w, then for any t-arc (
n
i
,
n
j
,
w
,
t
i
), π
′
(
n
i
,
n
j
,
w
,
n
i
l
)
=
π
(
n
i
,
n
j
,
w
,
t
i
);
(15)
otherwise
s
i
=
l
,
π
′
(
n
i
,
n
j
,
l
,
n
i
l
)
=
min
⁡
k
(
θ
l
,
k
n
j
-
θ
l
,
k
n
i
)
.
In contrast,π
(
n
i
,
n
j
,
l
,
t
i
) can be calculated by Formula (4) combined with Formula (5); that is,
(16)
π
(
n
i
,
n
j
,
l
,
t
i
)
=
θ
l
,
k
0
n
j
-
t
i
,
where
(17)
k
0
=
arg
{
min
⁡
k
⁡
(
θ
l
,
k
n
i
-
t
∣
θ
l
,
k
n
i
-
t
i
>
0
)
}
.
Obviously,(18)
π
′
(
n
i
,
n
j
,
l
,
nil
)
=
min
⁡
k
⁡
(
θ
l
,
k
n
j
-
θ
l
,
k
n
i
)
≤
θ
l
,
k
0
n
j
-
θ
l
,
k
0
n
i
≤
θ
l
,
k
0
n
j
-
t
i
=
π
(
n
i
,
n
j
,
l
,
t
i
)
.
In summation, for anyt-arc (
n
i
,
n
j
,
s
i
,
t
i
), π
′
(
n
i
,
n
j
,
s
i
,
n
i
l
)
≤
π
(
n
i
,
n
j
,
s
i
,
t
i
).
Furthermore,(19)
h
′
(
n
i
)
=
π
′
(
p
n
i
l
(
n
i
,
n
d
)
)
≤
π
′
(
p
t
i
(
n
i
,
n
d
)
)
=
π
′
(
n
i
,
n
i
+
,
s
i
,
n
i
l
)
+
⋯
+
π
′
(
n
d
-
,
n
d
,
s
d
-
,
n
i
l
)
≤
π
′
(
n
i
,
n
i
+
,
s
i
,
t
i
)
+
⋯
+
π
(
n
d
-
,
n
d
,
s
d
-
,
t
d
-
)
=
π
(
p
t
i
(
n
i
,
n
d
)
)
.
Thus, Theorem8 is proven.If Inequality (20) is satisfied, we deem this aconsistency assumptionfor the Itinerary Finder. The definition of this assumption helps to explain why the Itinerary Finder never re-OPENs a CLOSED node. The explanation can be found in Theorem 10:
(20)
π
(
n
i
,
n
j
,
s
i
,
t
i
)
+
π
′
(
p
n
i
l
(
n
j
,
n
d
)
)
≥
π
′
(
p
n
i
l
(
n
i
,
n
d
)
)
.Lemma 9.
Assuming that the consistency assumption is satisfied, A* needs never to re-OPEN a CLOSED node [17].Theorem 10.
The Cost Estimator assures that the Itinerary Finder needs never to re-OPEN a CLOSED node.Proof.
To prove Theorem10, we learn from Lemma 9 that it is equivalent to prove that the estimating strategy proposed in the Cost Estimator satisfies the consistency assumption:
(21)
Let
p
n
i
l
(
n
j
,
n
d
)
=
{
(
n
j
,
n
j
+
,
s
j
,
n
i
l
)
,
…
,
(
n
d
-
,
n
d
,
s
d
-
,
n
i
l
)
}
,
and
p
n
i
l
(
n
i
,
n
d
)
=
{
(
n
i
,
n
i
+
,
s
i
,
n
i
l
)
,
…
,
(
n
d
-
′
,
n
d
,
s
d
-
′
,
n
i
l
)
}
.
One can prove thatπ
′
(
n
i
,
n
j
,
s
i
,
n
i
l
)
≤
π
(
n
i
,
n
j
,
s
i
,
t
i
). Thus,
(22)
π
(
n
i
,
n
j
,
s
i
,
n
i
l
)
+
π
′
(
p
n
i
l
(
n
j
,
n
d
)
)
=
π
(
n
i
,
n
j
,
s
i
,
t
i
)
+
π
′
(
n
j
,
n
j
+
,
s
j
,
n
i
l
)
+
⋯
+
π
′
(
n
d
-
,
n
d
,
s
d
-
,
n
i
l
)
≥
π
′
(
n
i
,
n
j
,
s
i
,
n
i
l
)
+
π
′
(
n
j
,
n
j
+
,
s
j
,
n
i
l
)
+
⋯
+
π
′
(
n
d
-
,
n
d
,
s
d
-
,
n
i
l
)
≥
π
′
(
n
i
,
n
i
+
,
s
i
,
n
i
l
)
+
⋯
+
π
′
(
n
d
-
′
,
n
d
,
s
d
-
′
,
n
i
l
)
=
π
′
(
p
n
i
l
(
n
i
,
n
d
)
)
.
In other words, the consistency assumption is satisfied. Theorem 10 is thus proven.Previous related works had developed two variants of Itinerary-Finder procedure, that is, thePlain-A* procedure in which the value h
′
(
n
i
) is revised by calculating in Formula (13) and theDijkstra-like procedure in which h
′
(
n
i
) is replaced by constant 0. Similarly, it is not difficult to prove that the Dijkstra-like and Plain-A* both satisfy the consistency assumption and are thus admissible. We show the comparison among the Floyd-A* and the two procedures as follows.Lemma 11.
Consider the set of lower bounds verifying the consistency assumption. If a node is selected by the A* algorithm for a given lower bound, then this node will be selected by the A* algorithm using any smaller lower bound [18].LetN
DA, N
SA, and N
DL denote the sets of expanded nodes by Floyd-A*, Plain-A*, and Dijkstra-like, respectively. According to Lemma 11, Theorem 12 refers to their relationships.Theorem 12.
N
DA
⊆
N
SA
⊆
N
DL.Proof.
To prove Theorem12, one can equivalently prove that the estimated travel time values of Floyd-A*, Plain-A*, and Dijkstra-like are each a smaller lower bound of the real cost than the next; that is, π
(
p
t
i
(
n
i
,
n
d
)
)
≥
π
′
(
p
n
i
l
(
n
i
,
n
d
)
)
≥
dist
⁡
(
n
i
,
n
d
)
/
v
max
⁡
≥
0.
Theorem8 has proved π
(
p
t
i
(
n
i
,
n
d
)
)
≥
π
′
(
p
n
i
l
(
n
i
,
n
d
)
), and it is obvious that dist
⁡
(
n
i
,
n
d
)
/
v
max
⁡
≥
0 because dist
⁡
(
n
i
,
n
d
) and v
max
⁡ are both positive.
We therefore need only prove that(23)
π
′
(
p
n
i
l
(
n
i
,
n
d
)
)
≥
dist
⁡
(
n
i
,
n
d
)
v
max
⁡
,
where p
n
i
l
(
n
i
,
n
d
)
=
{
(
n
i
,
n
i
+
,
s
i
,
n
i
l
)
,
…
,
(
n
d
-
,
n
d
,
s
d
-
,
n
i
l
)
}.
π
′
(
n
i
,
n
j
,
s
i
,
n
i
l
) can be calculated as len
(
n
i
,
n
j
,
s
i
,
n
i
l
)
/
v
(
n
i
,
n
j
,
s
i
,
n
i
l
).
With regard todist
⁡
(
n
i
,
n
d
)
/
v
max
⁡, the numerator dist
⁡
(
n
i
,
n
d
) is obviously not greater than the real distance of any itinerary from n
i to n
d, and the denominator v
max
⁡ is not less than any velocity observed by walking, bus, and metro. Then,
(24)
π
′
(
p
n
i
l
(
n
i
,
n
d
)
)
=
π
′
(
n
i
,
n
i
+
,
s
i
,
n
i
l
)
+
⋯
+
π
′
(
n
d
-
,
n
d
,
s
d
-
,
n
i
l
)
=
len
(
n
i
,
n
i
+
,
s
i
,
n
i
l
)
v
(
n
i
,
n
i
+
,
s
i
,
n
i
l
)
+
⋯
+
len
(
n
d
-
,
n
d
,
s
d
-
,
n
i
l
)
v
(
n
d
-
,
n
d
,
s
d
-
,
n
i
l
)
≥
len
(
n
i
,
n
i
+
,
s
i
,
n
i
l
)
+
⋯
+
len
(
n
d
-
,
n
d
,
s
d
-
,
n
i
l
)
v
max
⁡
≥
dist
⁡
(
n
i
,
n
d
)
v
max
⁡
.
Thus, the theorem is proven.Corollary 13.
|
N
DA
|
≤
|
N
SA
|
≤
|
N
DL
|.Under the premises of Theorem12, Corollary 13 can be easily determined, meaning that the total number of expanded nodes from the Dijsktra-like, Plain-A*, and Floyd-A* algorithms are each no less than the next. Correspondingly, their efficiencies increase orderly.In summation, the searching scopes of the three procedures intuitively seem to be as shown in Figure6 and their efficiencies are shown as tested in Sections 4.1 and 4.2.Figure 6
Searching scope of three procedures.


## 3.1. Least-Time Itinerary-Finder Procedure

Assuming that typical readers may not be familiar with the A* algorithm, this searching process will be explained in detail. Given a triad of origin, destination, and initial time(
n
o
,
n
d
,
t
o
) to determine an LT itinerary p
t
o
(
n
o
,
n
d
)
∈
P
t
o
(
n
o
,
n
d
), the Itinerary Finder expands promisingorigin-rooted partial itineraries (partial itineraryfor short) in a node-to-node manner. Beginning with n
o, eachsuccessor
n
o
+ is expanded by searching for each t-arc (
n
o
,
n
o
+
,
s
o
,
t
o
) in the first round. Each of these t-arcs (partial itineraries) may contribute to the LT itinerary. During the second round, we must determine which terminal node of partial itinerary among several candidates is the most promising one.Let each noden
i be associated with a state denoted bystate(n
i). There are three states of node n
i.(1)
NEW: node n
i has not been expanded up to now.
(2)
OPEN: node n
i has been expanded and acts as a candidate to expand to another node in the next searching process. That is to say, for each partial itinerary p
t
o
(
n
o
,
n
i
) thus far,state(n
i) = OPEN.
(3)
CLOSED: node n
i has been expanded and has already expanding to another node. In other words, for any node n
j
≠
n
i that has gone through by any current partial itinerary p
t
o
(
n
o
,
n
i
),state(n
j) = CLOSED.As defined above, the nodes associated with the state OPEN are candidates for expanding partial itineraries. For convenience, we use relative time rather than absolute time hereafter. Using the USPT network of Figure1 as an example, let n
o
=
n
1, n
d
=
n
5 and t
o
=
2 (minutes after 6:00). Figure 4 combined with Table 2 shows part of the searching process.Table 2
The changing labels of nodes associated with Figure4.
Node
Labels
S
t
a
t
e
(
n
)
t
i
=
g
′
(
n
)
+
t
o
g
′
(
n
)
h
′
(
n
)
f
′
(
n
)
P
r
e
(
n
)
Updated
Initialization
n
1
OPEN
2
0
21
21
nil
*√
n
2
NEW
∞
∞
∞
∞
nil
n
3
NEW
∞
∞
∞
∞
nil
n
4
NEW
∞
∞
∞
∞
nil
n
5
NEW
∞
∞
∞
∞
nil
n
6
NEW
∞
∞
∞
∞
nil
n
7
NEW
∞
∞
∞
∞
nil
1st searching round
n
1
CLOSED
2
0
21
21
nil
*
n
2
OPEN
min
⁡
{
14,30
}
=
14
12
11.5
23.5
{
(
n
1
,
n
2
,
l
1
,
2
)
}
*
n
3
OPEN
25
23
1.5
24.5
{
(
n
1
,
n
3
,
l
1
,
2
)
}
*
n
4
NEW
∞
∞
∞
∞
nil
n
5
NEW
∞
∞
∞
∞
nil
n
6
NEW
∞
∞
∞
∞
nil
n
7
OPEN
15
13
10
23
{
(
n
1
,
n
7
,
l
5
,
2
)
}
*√
2nd searching round
n
1
CLOSED
2
0
21
21
nil
n
2
OPEN
14
12
11.5
23.5
{
(
n
1
,
n
2
,
l
1
,
2
)
}
n
3
OPEN
25
23
1.5
24.5
{
(
n
1
,
n
3
,
l
1
,
2
)
}
n
4
OPEN
15
+
1
=
16
14
9
23
{
(
n
1
,
n
7
,
l
5
,
2
)
,
(
n
7
,
n
4
,
w
,
15
)
}
*√
n
5
NEW
∞
∞
∞
∞
nil
n
6
NEW
∞
∞
∞
∞
nil
n
7
CLOSED
15
13
10
23
{
(
n
1
,
n
7
,
l
5
,
2
)
}
*
3rd searching round
n
1
CLOSED
2
0
21
21
nil
n
2
OPEN
min
⁡
{
14,51
}
=
14
12
11.5
23.5
{
(
n
1
,
n
2
,
l
1
,
2
)
}
*√
n
3
OPEN
25
23
1.5
24.5
{
(
n
1
,
n
3
,
l
1
,
2
)
}
n
4
CLOSED
16
14
9
23
{
(
n
1
,
n
7
,
l
5
,
2
)
,
(
n
7
,
n
4
,
w
,
15
)
}
*
n
5
OPEN
30
28
0
28
{
(
n
1
,
n
7
,
l
5
,
2
)
,
(
n
7
,
n
4
,
w
,
15
)
,
(
n
4
,
n
5
,
l
3
,
16
)
}
*
n
6
NEW
∞
∞
∞
∞
nil
n
7
CLOSED
15
13
10
23
{
(
n
1
,
n
7
,
l
5
,
2
)
}
√The node to be COLSED in the next searching round; *The node whose labels are updated in the searching round.Partial searching process by Floyd-A*.
(a)
(b)
(c)
(d)We first initialize the state of originn
1 as OPEN and others as NEW by default (see Figure 4(a)). In the first expansion round (see Figure 4(b)), n
2, n
3, and n
7 are expanded by searching for t-arcs (
n
1
,
n
2
,
l
1
,
2
), (
n
1
,
n
2
,
l
2
,
2
), (
n
1
,
n
3
,
l
1
,
2
), and (
n
1
,
n
7
,
l
5
,
2
). At the same time, n
1 becomes CLOSED; n
2, n
3, and n
7 turn from NEW to OPEN. The next paragraph shows that {
(
n
1
,
n
7
,
l
5
,
2
)
} is the most promising partial itinerary and t
7
=
15; thus, we should continue the second expansion round for the most promising node n
7, and only n
4 is expanded by searching for a t-arc (
n
7
,
n
4
,
w
,
15
). This time, n
7 becomes CLOSED and n
4 turns to OPEN (see Figure 4(c)). The searching process continues by similar means. Note that the state of a node may turn from NEW to OPEN, from OPEN to CLOSED, or remain the same. However, a CLOSED node can never re-OPEN (see Theorem 10), for example, (
n
4
,
n
1
,
l
2
,
16
) is searched in the 3rd searching round (see Figure 4(d)), but the state of n
1 unconditionally remains CLOSED.The exposition above focuses on the changing states of nodes during the expansion of partial itineraries. To determine the most promising OPEN node among several candidates,f
′
(
n
i
) is defined as the estimated travel time of an LT itinerary p
t
o
(
n
o
,
n
i
,
n
d
). For each partial itinerary p
t
o
(
n
o
,
n
i
), the terminal node(s) n
i whose f
′
(
n
i
) is/are the minimum one(s) among those of all OPEN nodes is/are identified as the most promising one(s). If there is more than one, you may choose the first expanded one.The actual travel time of the LT itineraryp
t
o
(
n
o
,
n
i
,
n
d
) can be the summation of two parts calculated as
(9)
π
(
p
t
o
(
n
o
,
n
i
,
n
d
)
)
=
π
(
p
t
o
(
n
o
,
n
i
)
)
+
π
(
p
t
i
(
n
i
,
n
d
)
)
.However, it is difficult to calculateπ
(
p
t
o
(
n
o
,
n
i
)
) and π
(
p
t
i
(
n
i
,
n
d
)
) in real-time within an acceptable computing time. Because of the time-dependence factor, they are not able to be precalculated and stored as fixed values. This is a different situation from a static network context. Therefore, g
′
(
n
i
) and h
′
(
n
i
) are defined to estimate them, respectively. f
′
(
n
i
) is their summation, calculated as
(10)
f
′
(
n
i
)
=
g
′
(
n
i
)
+
h
′
(
n
i
)
.The A*-based Itinerary Finder utilizes the minimum travel time of the partial itineraryp
t
o
(
n
o
,
n
i
), determined to this point as g
′
(
n
i
); the strategy for estimating h
′
(
n
i
) will be addressed in Section 3.2. To illustrate the process for selecting the most promising node, we again use the USPT network of Figure 1 as an example. A traveler first predetermines t
1
=
2. In the first searching round (see Figure 4(b)), π
(
n
1
,
n
2
,
l
1
,
2
)
=
12
(
min
⁡
), π
(
n
1
,
n
2
,
l
2
,
2
)
=
28, π
(
n
1
,
n
3
,
l
1
,
2
)
=
23, and π
(
n
1
,
n
7
,
l
5
,
2
)
=
13 can be easily determined with Formula (4). One can easily determine that g
′
(
n
2
)
=
min
⁡
{
12,28
}
=
12, g
′
(
n
3
)
=
23, and g
′
(
n
7
)
=
13. As for the heuristic information yielded by the Cost Estimator, h
′
(
n
2
)
=
11.5, h
′
(
n
3
)
=
1.5, and h
′
(
n
7
)
=
10. Thus, f
′
(
n
2
)
=
g
′
(
n
2
)
+
h
′
(
n
2
)
=
12
+
11.5
=
23.5. Similarly, we have f
′
(
n
3
)
=
24.5 and f
′
(
n
7
)
=
23. Dijkstra-based approaches only consider the performances of origin-rooted partial itineraries and thus identify {
(
n
1
,
n
2
,
l
2
,
2
)
} as the most promising partial itinerary due to g
′
(
n
2
)
<
g
′
(
n
7
)
<
g
′
(
n
3
). The A*-based approaches, however, are goal-directed by the heuristics, and the Itinerary Finder selects n
7 as a result of f
′
(
n
7
)
<
f
′
(
n
2
)
<
f
′
(
n
3
). Similarly, the second searching round selects the terminal node of {
(
n
1
,
n
7
,
l
5
,
2
)
,
(
n
7
,
n
4
,
w
,
15
)
}, that is, n
4, as the most promising node, and so forth. Note that in the 3rd searching round, the t-arc (
n
4
,
n
2
,
l
2
,
16
) is searched. We have t
2
=
51 calculated by Formula (4), meaning that g
′
(
n
2
) of OPEN node n
2 will be potentially turned to 51
-
t
o
=
49. However, because the previous value of g
′
(
n
2
) is 12 and 49
>
12, the value of g
′
(
n
2
) is not updated but remains 12. In another words, the partial itinerary {
(
n
1
,
n
2
,
l
1
,
2
)
} dominates {
(
n
1
,
n
7
,
l
5
,
2
)
,
(
n
7
,
n
4
,
w
,
15
)
,
(
n
4
,
n
2
,
l
2
,
16
)
}, referring to the partial itinerary from n
1 to n
2. The destination n
5 is also expanded in this searching round; the associated state turns to OPEN. The searching process will continue, however, untilstate(n
5) = CLOSED.Through the scheme that is recursively expanding, comparing, and selecting promising partial itineraries, the algorithm is terminated once the state of destination turns to CLOSED. If an algorithm is guaranteed to determine an optimal itinerary from origin to destination, we designate it asadmissible. The Itinerary Finder is proven to be admissible in Section 3.3. The Itinerary Finder places OPEN nodes in an OPEN list and CLOSED nodes in a CLOSED list. If the state of the node cannot be placed either in the OPEN or CLOSED list it is regarded as NEW as default. In a summary of the above analysis, the outline of the Itinerary Finder is presented in Algorithm 1.Algorithm 1:Procedure of Itinerary Finder (
n
o
,
n
d
,
t
o
).
Step  0. (Initialization):
Set OPEN list =⌀ and CLOSED list = ⌀
Setg
′
(
n
i
)
=
∞
,
h
′
(
n
i
)
=
∞
,
f
′
(
n
i
)
=
∞ and p
r
e
(
n
i
)
=
n
i
l where n
i
∈
N
Addn
o to OPEN list, set g
′
(
n
o
)
=
0
Calculatef
′
(
n
o
)
=
g
′
(
n
o
)
+
h
′
(
n
o
) where h
′
(
n
o
) is pre-calculated by Cost-Estimator
Step  1. (Expanding partial itinerary):
while  OPEN list  ≠
⌀  do
Select any noden
i
∈
{
n
i
∣
min
⁡
(
f
′
(
n
i
)
)
,
s
t
a
t
e
(
n
i
)
=
O
P
E
N
}
if  n
i
=
n
d  then
Go to Step  2
else
Move n
i from OPEN list to CLOSED list
end if
for all  t-arc (
n
i
,
n
i
+
,
s
i
,
t
i
)  do
if   n
i
+ in CLOSED list  then
continue
end if
if  s
i
=
s
i
-
=
w  then// Set s
o
-
=
n
i
l previously
continue
end if
if  s
i
=
s
m or s
i
=
s
i
- where s
m
=
s
o
,
s
o
+
,
…
,
s
i
- then
continue
end if
Calculate π
(
n
i
,
n
i
+
,
s
i
,
t
i
) by formula (2) or (4)
if
g
′
(
n
i
)
+
π
(
n
i
,
n
i
+
,
s
i
,
t
i
)
≥
g
′
(
n
i
+
)  then
continue
else if  n
i
+ not  in OPEN list  then
Add n
i
+ to OPEN list
end if
Calculate corresponding t
i
+ by formula (3) or (6)
Update g
′
(
n
i
+
) with g
′
(
n
i
+
)
+
π
(
n
i
,
n
i
+
,
s
i
,
t
i
)
Calculate f
′
(
n
i
+
)
=
g
′
(
n
i
+
)
+
h
′
(
n
i
+
)
Record p
r
e
(
n
i
+
)
=
{
(
n
i
,
n
i
+
,
s
i
,
t
i
)
}
end for
end while
Step  2. (Reconstructing LT itinerary):
Reconstruct LT itineraryp
t
o
(
n
o
,
n
d
) by recursively recalling p
r
e
(
n
i
) where n
i
=
n
d
,
n
d
-
,
…
,
n
o
+
Returnp
t
o
(
n
o
,
n
d
)If more detailed information (e.g., waiting time, in-vehicle time) is required with respect to a specific arc, this can be obtained by simply adding to pre(n
i) in the associated iteration.


## 3.2. Cost-Estimator Procedure for a Tighter Lower Bound

The Itinerary-Finder procedure must be well informed when making a choice to expand partial itineraries. Expanding an unlikely part of an LT itinerary is a waste of computational time, while missing a promising partial itinerary may lead to a failure in determining the LT itinerary. Therefore, the strategy of estimating the travel time of a destination-ended partial itinerary is viewed as the key to improving the efficiency of the Itinerary Finder. Meanwhile, the estimated travel time must be a lower bound of the real travel time. Note that a tighter lower bound results in higher efficiency.The travel time of an itinerary is composed of the travel time during walking between two nodes, waiting at nodes for a transfer, and traveling in vehicles. The walking time between two specific nodes is fixed. The waiting time varies in different cases. If fortunate, a traveler can transfer without waiting time. The in-vehicle time depends on the timetable of different lines combined with their different vehicle trips. This paper proposes a strategy to estimate the travel time between two nodes as a tight static lower bound of this real time-dependent value. The basic concept is shown by generating an associated slacked network (see Definition5) of the USPT network; the minimum travel time of itinerary in this SUSPT network is the associated estimated value in the USPT network.Definition 5.
A slacked USPT network (SUSPT network for short) is defined to share the same topological structure as the USPT network. However, each arc of the SUSPT network is assigned a static travel time as a lower bound of the associated real travel time of the arc in the USPT network. The arc in the SUSPT network is timed by explicitly slacking the associated real travel time by using the following 3 rules. Figure 5 shows the associated SUSPT network of the USPT network of Figure 1.Figure 5
Associated SUSPT network of the USPT network of Figure1.Rule 1.
Walking times remain the same.Rule 2.
Ignore all waiting times.Rule 3.
Let the minimum travel time among those traversed by different lines combined with different vehicle trips between two specific nodes be the estimated travel time.Obviously, there exist no temporal concepts in the static SUSPT network; therefore, let each initial time oft-arc in the SUSPT network benil. Let π
′ denote the operator to time the t-arc in SUSPT network. Rule 1 can be reflected in Formula (11). Rules 2 and 3 are interpreted in Formula (12):
(11)
π
′
(
n
i
,
n
j
,
w
,
n
i
l
)
=
dist
⁡
(
n
i
,
n
j
)
v
walk
,
(12)
π
′
(
n
i
,
n
j
,
l
,
n
i
l
)
=
min
⁡
k
(
θ
l
,
k
n
j
-
θ
l
,
k
n
i
)
.For this problem, typical all-to-all shortest paths algorithms are qualified. This paper chooses a well-known Floyd algorithm. We assume typical readers have already known the algorithm, so there is no detailed exposition here.The outline of the procedure is shown in Algorithm2.Algorithm 2:Procedure of Cost Estimator.
Step  0. (Initialize the SUSPT network):
for all  n
i
∈
N  do
for all  n
j
∈
N  do
H
(
i
,
j
)
=
mi
n
s
π
′
(
n
i
,
n
j
,
s
,
n
i
l
)
end for
end for
Step  1. (Calculate costs of all-to-all shortest paths):
for all  n
m
∈
N  do
for all  n
i
∈
N  do
for all  n
j
∈
N  do
if  H
(
i
,
j
)
>
H
(
i
,
k
)
+
H
(
k
,
j
)   then
H
(
i
,
j
)
>
H
(
i
,
k
)
+
H
(
k
,
j
)
end if
end for
end for
end forRemark 6.
In this work, the Itinerary Finder obtainsh
′
(
n
i
) from table H outputted by the Cost Estimator, while the previous related works substituted h
′
(
n
i
) with Formula (13), which was calculated in an online way. The strategy proposed in this work is proved to generate a tighter lower bound and thus leads the Floyd-A* algorithm to be more efficient both in theory and in computation experiments (see Sections 3.3, 4.1, and 4.2):
(13)
h
′
(
n
i
)
=
dist
⁡
(
n
i
,
n
d
)
v
max
⁡
.


## 3.3. Admissibility and Efficiency Analysis

The admissibility and efficiency of the Floyd-A* algorithm are discussed in this section. Hart et al. [17] established how to determine the admissibility of an A* algorithm, which is primarily affected by the travel time estimating strategy of the destination-ended partial itineraries shown in Lemma 7. On this basis, Theorem 8 establishes the admissibility of the Itinerary Finder.Lemma 7.
Ifh
′
(
n
i
)
≤
π
(
p
t
i
(
n
i
,
n
d
)
), then A* is admissible [17].Theorem 8.
The Cost Estimator guarantees that the Itinerary Finder is admissible.Proof.
The Itinerary Finder is A*-based, whereh
′
(
n
i
) is computed by the Cost Estimator. To prove Theorem 8, we learn from Lemma 7 that it is equivalent to prove that the Cost Estimator guarantees each h
′
(
n
i
)
≤
π
(
p
t
i
(
n
i
,
n
d
)
).
Letp
t
i
(
n
i
,
n
d
)
=
{
(
n
i
,
n
i
+
,
s
i
,
t
i
)
,
…
,
(
n
d
-
,
n
d
,
s
d
-
,
t
d
-
)
} be a destination-ended partial itinerary of the actual LT itinerary p
t
o
(
n
o
,
n
d
). Therefore,
(14)
π
(
p
t
i
(
n
i
,
n
d
)
)
=
π
(
n
i
,
n
i
+
,
s
i
,
t
i
)
+
⋯
+
π
(
n
d
-
,
n
d
,
s
d
-
,
t
d
-
)
.
p
nil
(
n
i
,
n
d
)
=
{
(
n
i
,
n
i
+
′
,
s
i
′
,
n
i
l
)
,
…
,
(
n
d
-
′
,
n
d
,
s
d
-
′
,
n
i
l
)
} denotes the LT itinerary in the SUSPT network. Note that the topological structures of p
t
i
(
n
i
,
n
d
) and p
n
i
l
(
n
i
,
n
d
) are not necessarily the same.
Ifs
i
=
w, then for any t-arc (
n
i
,
n
j
,
w
,
t
i
), π
′
(
n
i
,
n
j
,
w
,
n
i
l
)
=
π
(
n
i
,
n
j
,
w
,
t
i
);
(15)
otherwise
s
i
=
l
,
π
′
(
n
i
,
n
j
,
l
,
n
i
l
)
=
min
⁡
k
(
θ
l
,
k
n
j
-
θ
l
,
k
n
i
)
.
In contrast,π
(
n
i
,
n
j
,
l
,
t
i
) can be calculated by Formula (4) combined with Formula (5); that is,
(16)
π
(
n
i
,
n
j
,
l
,
t
i
)
=
θ
l
,
k
0
n
j
-
t
i
,
where
(17)
k
0
=
arg
{
min
⁡
k
⁡
(
θ
l
,
k
n
i
-
t
∣
θ
l
,
k
n
i
-
t
i
>
0
)
}
.
Obviously,(18)
π
′
(
n
i
,
n
j
,
l
,
nil
)
=
min
⁡
k
⁡
(
θ
l
,
k
n
j
-
θ
l
,
k
n
i
)
≤
θ
l
,
k
0
n
j
-
θ
l
,
k
0
n
i
≤
θ
l
,
k
0
n
j
-
t
i
=
π
(
n
i
,
n
j
,
l
,
t
i
)
.
In summation, for anyt-arc (
n
i
,
n
j
,
s
i
,
t
i
), π
′
(
n
i
,
n
j
,
s
i
,
n
i
l
)
≤
π
(
n
i
,
n
j
,
s
i
,
t
i
).
Furthermore,(19)
h
′
(
n
i
)
=
π
′
(
p
n
i
l
(
n
i
,
n
d
)
)
≤
π
′
(
p
t
i
(
n
i
,
n
d
)
)
=
π
′
(
n
i
,
n
i
+
,
s
i
,
n
i
l
)
+
⋯
+
π
′
(
n
d
-
,
n
d
,
s
d
-
,
n
i
l
)
≤
π
′
(
n
i
,
n
i
+
,
s
i
,
t
i
)
+
⋯
+
π
(
n
d
-
,
n
d
,
s
d
-
,
t
d
-
)
=
π
(
p
t
i
(
n
i
,
n
d
)
)
.
Thus, Theorem8 is proven.If Inequality (20) is satisfied, we deem this aconsistency assumptionfor the Itinerary Finder. The definition of this assumption helps to explain why the Itinerary Finder never re-OPENs a CLOSED node. The explanation can be found in Theorem 10:
(20)
π
(
n
i
,
n
j
,
s
i
,
t
i
)
+
π
′
(
p
n
i
l
(
n
j
,
n
d
)
)
≥
π
′
(
p
n
i
l
(
n
i
,
n
d
)
)
.Lemma 9.
Assuming that the consistency assumption is satisfied, A* needs never to re-OPEN a CLOSED node [17].Theorem 10.
The Cost Estimator assures that the Itinerary Finder needs never to re-OPEN a CLOSED node.Proof.
To prove Theorem10, we learn from Lemma 9 that it is equivalent to prove that the estimating strategy proposed in the Cost Estimator satisfies the consistency assumption:
(21)
Let
p
n
i
l
(
n
j
,
n
d
)
=
{
(
n
j
,
n
j
+
,
s
j
,
n
i
l
)
,
…
,
(
n
d
-
,
n
d
,
s
d
-
,
n
i
l
)
}
,
and
p
n
i
l
(
n
i
,
n
d
)
=
{
(
n
i
,
n
i
+
,
s
i
,
n
i
l
)
,
…
,
(
n
d
-
′
,
n
d
,
s
d
-
′
,
n
i
l
)
}
.
One can prove thatπ
′
(
n
i
,
n
j
,
s
i
,
n
i
l
)
≤
π
(
n
i
,
n
j
,
s
i
,
t
i
). Thus,
(22)
π
(
n
i
,
n
j
,
s
i
,
n
i
l
)
+
π
′
(
p
n
i
l
(
n
j
,
n
d
)
)
=
π
(
n
i
,
n
j
,
s
i
,
t
i
)
+
π
′
(
n
j
,
n
j
+
,
s
j
,
n
i
l
)
+
⋯
+
π
′
(
n
d
-
,
n
d
,
s
d
-
,
n
i
l
)
≥
π
′
(
n
i
,
n
j
,
s
i
,
n
i
l
)
+
π
′
(
n
j
,
n
j
+
,
s
j
,
n
i
l
)
+
⋯
+
π
′
(
n
d
-
,
n
d
,
s
d
-
,
n
i
l
)
≥
π
′
(
n
i
,
n
i
+
,
s
i
,
n
i
l
)
+
⋯
+
π
′
(
n
d
-
′
,
n
d
,
s
d
-
′
,
n
i
l
)
=
π
′
(
p
n
i
l
(
n
i
,
n
d
)
)
.
In other words, the consistency assumption is satisfied. Theorem 10 is thus proven.Previous related works had developed two variants of Itinerary-Finder procedure, that is, thePlain-A* procedure in which the value h
′
(
n
i
) is revised by calculating in Formula (13) and theDijkstra-like procedure in which h
′
(
n
i
) is replaced by constant 0. Similarly, it is not difficult to prove that the Dijkstra-like and Plain-A* both satisfy the consistency assumption and are thus admissible. We show the comparison among the Floyd-A* and the two procedures as follows.Lemma 11.
Consider the set of lower bounds verifying the consistency assumption. If a node is selected by the A* algorithm for a given lower bound, then this node will be selected by the A* algorithm using any smaller lower bound [18].LetN
DA, N
SA, and N
DL denote the sets of expanded nodes by Floyd-A*, Plain-A*, and Dijkstra-like, respectively. According to Lemma 11, Theorem 12 refers to their relationships.Theorem 12.
N
DA
⊆
N
SA
⊆
N
DL.Proof.
To prove Theorem12, one can equivalently prove that the estimated travel time values of Floyd-A*, Plain-A*, and Dijkstra-like are each a smaller lower bound of the real cost than the next; that is, π
(
p
t
i
(
n
i
,
n
d
)
)
≥
π
′
(
p
n
i
l
(
n
i
,
n
d
)
)
≥
dist
⁡
(
n
i
,
n
d
)
/
v
max
⁡
≥
0.
Theorem8 has proved π
(
p
t
i
(
n
i
,
n
d
)
)
≥
π
′
(
p
n
i
l
(
n
i
,
n
d
)
), and it is obvious that dist
⁡
(
n
i
,
n
d
)
/
v
max
⁡
≥
0 because dist
⁡
(
n
i
,
n
d
) and v
max
⁡ are both positive.
We therefore need only prove that(23)
π
′
(
p
n
i
l
(
n
i
,
n
d
)
)
≥
dist
⁡
(
n
i
,
n
d
)
v
max
⁡
,
where p
n
i
l
(
n
i
,
n
d
)
=
{
(
n
i
,
n
i
+
,
s
i
,
n
i
l
)
,
…
,
(
n
d
-
,
n
d
,
s
d
-
,
n
i
l
)
}.
π
′
(
n
i
,
n
j
,
s
i
,
n
i
l
) can be calculated as len
(
n
i
,
n
j
,
s
i
,
n
i
l
)
/
v
(
n
i
,
n
j
,
s
i
,
n
i
l
).
With regard todist
⁡
(
n
i
,
n
d
)
/
v
max
⁡, the numerator dist
⁡
(
n
i
,
n
d
) is obviously not greater than the real distance of any itinerary from n
i to n
d, and the denominator v
max
⁡ is not less than any velocity observed by walking, bus, and metro. Then,
(24)
π
′
(
p
n
i
l
(
n
i
,
n
d
)
)
=
π
′
(
n
i
,
n
i
+
,
s
i
,
n
i
l
)
+
⋯
+
π
′
(
n
d
-
,
n
d
,
s
d
-
,
n
i
l
)
=
len
(
n
i
,
n
i
+
,
s
i
,
n
i
l
)
v
(
n
i
,
n
i
+
,
s
i
,
n
i
l
)
+
⋯
+
len
(
n
d
-
,
n
d
,
s
d
-
,
n
i
l
)
v
(
n
d
-
,
n
d
,
s
d
-
,
n
i
l
)
≥
len
(
n
i
,
n
i
+
,
s
i
,
n
i
l
)
+
⋯
+
len
(
n
d
-
,
n
d
,
s
d
-
,
n
i
l
)
v
max
⁡
≥
dist
⁡
(
n
i
,
n
d
)
v
max
⁡
.
Thus, the theorem is proven.Corollary 13.
|
N
DA
|
≤
|
N
SA
|
≤
|
N
DL
|.Under the premises of Theorem12, Corollary 13 can be easily determined, meaning that the total number of expanded nodes from the Dijsktra-like, Plain-A*, and Floyd-A* algorithms are each no less than the next. Correspondingly, their efficiencies increase orderly.In summation, the searching scopes of the three procedures intuitively seem to be as shown in Figure6 and their efficiencies are shown as tested in Sections 4.1 and 4.2.Figure 6
Searching scope of three procedures.


## 4. Example Illustration and Analysis

A numerical example and a real-world USPT network instance are presented to demonstrate the suitability and efficiency of the proposed Floyd-A* algorithm, as well as the instructive significance for travelers. For this purpose, the experiments are composed of four parts. Section4.1 shows the efficiency of the Floyd-A* algorithm through a numerical example, in comparison with the two other conventional procedures, that is, the Dijkstra-like and Plain-A* procedures. A real-world instance is tested to demonstrate applicability and efficiency of the Floyd-A* algorithm when solving large-scale network instance, which is given in Section 4.2. The experiments on time-dependent nature of the least-time itinerary and the phenomenon “just missing” and “just boarding” cases are presented in Sections 4.3 and 4.4, respectively. The experiments ran in a MATLAB environment on an HP Compaq 8280 Elite CMT PC with Intel Core i5-2400 CPU @3.1G Hz and 4GB memory (RAM).The USPT network of the numerical example shown in Figure7 is formed by 30 nodes and 103 arcs. There are 10 lines, including 2 metro lines and 8 bus lines, where l
4
¯
=
l
8; 10 corresponding timetables are also provided. Node n
5 is traversed by l
1, l
2, and l
3; each of another ten nodes is simultaneously traversed by 2 lines. Specific data are omitted due to the limited space.Figure 7
An USPT network example for illustration.


### 4.1. High Efficiency of the Floyd-A* Algorithm

An itinerary planning assistant is capable of determining the LT itinerary through real-time querying. Efficiency is the ultimate goal. For testing, 1000 triads ofn
o, n
d, and initial time t
o are randomly generated with the distance between each pair of n
o, n
d no less than 5000 meters; all pairs are connectable. Note that in the generating process, cases exist where no itinerary from n
o to n
d was found. Therefore, the Floyd-A* algorithm is capable of verifying the connexity of a USPT network. Given each triad (n
o, n
d, and t
o), each of the three procedures (i.e., Floyd-A*, Plain-A*, and Dijkstra-like aforementioned in Section 3.3) are used to solve the LTIP-USPT. The Dijkstra-like and Plain-A* procedures are traditional methods for solving these types of problems. We utilize two indicators, one averaged the running time during the calculating of the LT itinerary by a specific procedure, and the other averaged the expansion times of nodes during the searching process. Using the performance of Dijkstra-like procedure as a reference, the relative reductions of the two indicators are shown in Table 3 as well. In addition, the results outputted by different procedures in a specific instance are exactly the same. Considering that the three procedures are all admissible, we learn from Table 3 that Floyd-A* procedure reduced the running time by 33.3% and the expansion times of nodes by 61.58% compared with the Dijkstra-like procedure, while the two corresponding values were 12.84% and 25.34% savings from the Plain-A* procedure. Floyd-A* procedure proposed in this paper is superior to both the Plain-A* and the Dijkstra-like conventional procedures in terms of efficiency.Table 3
Efficiency comparison of three procedures for LTIP-USPT in Figure7.
Procedures
Item
Running time (ms)
Relative reduction of running time (%)
Expanding times of nodes (sec.)
Relative reduction of expansion times (%)
Dijkstra-like
2.0422
0
53.64
0
Plain-A*
1.78
12.84
40.049
25.34
Floyd-A*
1.3621
33.3
20.611
61.58


### 4.2. Applicability of the Floyd-A* Algorithm for Real-World Instance

To verify the applicability and efficiency of the Floyd-A* procedure in a real-world network, we implement and test the three procedures in a Visual Studio 2010 environment on the aforementioned PC, using the real-world public transport data of Shenyang City, the central city of northeastern China. The main urban zone of Shenyang City has a size of more than 700 square kilometers, and a population of more than 5 million until the year 2010. There are totally 446 directed USPT lines, which are composed of 2 metro lines and 444 bus lines. The modeled Shenyang City USPT network (within the main urban zone) is formed by 2812 nodes (after aggregating) and 184178 arcs. Similar to the experiments performed in Section4.1, 1000 triads of n
o, n
d, and initial time t
o are randomly generated; the performances are shown in Table 4. The real-world LTIP-USPT can be solved by the Floyd-A* procedure in a more efficient way; it reduces the averaged running time by 63.9% compared with that solved by the Dijkstra-like procedure. Therefore, we concluded that the Floyd-A* procedure is significantly superior to the previous related work, that is, both the Plain-A* and the Dijkstra-like procedures, with reference to efficiency.Table 4
Efficiency comparison of three procedures for LTIP in Shenyang City USPT network.
Procedures
Item
Running time (ms)
Relative reduction of running time (%)
Dijkstra-like
43.5
0
Plain-A*
34.2
21.4
Floyd-A*
15.7
63.9In reality, faced with such a large network, local citizens and tourists are difficult to determine an optimal itinerary without an itinerary planning system. To benefit the travelers, the Floyd-A* algorithm module is implemented and embedded in a Shenyang City Public Transport Query System, shown in Figure8. The system is implemented in a Visual Studio 2010 environment, combined with the geography information system TransCAD. In a case that a traveler wants the least-time travel from the Bainaohui Stop to the Wanquan Park Stop given the initial starting time 9:10, the system returns the solution that the traveler should cost 24 minutes (including in-vehicle time and waiting time) traveling from the Bainaohui Stop to the EPA Stop by Line 222, walking 1 minute to another EPA Stop, and finally arriving at the Wanquan Park Stop by Line 118 in 15 minutes. Note that the two EPA Stops are geographically different but close. The interface and the LT itinerary of the example are given as shown in Figure 8. It appears to be applicable and efficient after numerous experiments. It finally turns out that Floyd-A* can potentially be used into many large-scale real-world USPT networks for LT itinerary planning use. Note that it also has the potential to be applied in interurban context, given that all services are schedule-based.Figure 8
An example of system interface of LT itinerary planning in USPT network.


### 4.3. Time-Dependent Nature

In a static public transport network that does not consider a timetable, it is obvious that, given an origin and destination pair, the optimal itinerary (also referred as path) will consider objectives such as the least transfer time and the lowest financial expense. In other words, the solution does not depend on the departure time, while the situation is different when considering a timetable.In the case of a specified origin and destination, when given different initial timet
o, the proposed computation method returns a different LT itinerary p
t
o
(
n
o
,
n
d
) and corresponding travel time π
(
p
t
o
(
n
o
,
n
d
)
). Using the USPT network of Figure 7 as an example, n
o
=
n
1 and n
d
=
n
24 are predetermined; when given a different initial time, for example, t
o
=
55 and t
o
=
60, the itinerary p
55
(
n
1
,
n
24
) and itinerary p
60
(
n
1
,
n
24
) found with the Itinerary-Finder procedure are LT itineraries in these two cases, respectively. These results are shown in Figure 9, where the horizontal axis represents the time of day and the vertical axis represents the accumulated travel distance of the itinerary. The circles represent nodes and the links are explained in the legend. It is not difficult to see that the slope of the link represents the corresponding velocity and the curve must be monotonically increasing:Figure 9
Two LT itineraries with different initial times.p
55
(
n
1
,
n
24
)
=
{
(
n
1
,
n
3
,
l
1
,
55
)
,
(
n
3
,
n
15
,
w
,
70
)
,
(
n
15
,
n
18
,
l
6
,
71.3
)
,
(
n
18
,
n
24
,
w
,
84
)
} costs 33.1 minutes, traveling 12336 meters; the itinerary p
60
(
n
1
,
n
24
)
=
{
(
n
1
,
n
2
,
l
1
,
60
)
,
(
n
2
,
n
10
,
l
5
,
69
)
,
(
n
10
,
n
24
,
w
,
95
)
} costs 37.6 minutes, traveling 11974 meters.TheSpatial itinerary is defined as an itinerary with the temporal factors deleted. The spatialitineraries of itineraries p
55
(
n
1
,
n
24
) and p
60
(
n
1
,
n
24
) are represented as sp
1
(
n
1
,
n
24
)
=
{
(
n
1
,
n
3
,
l
1
)
,
(
n
3
,
n
15
,
w
)
,
(
n
15
,
n
18
,
l
6
)
,
(
n
18
,
n
24
,
w
)
} and sp
2
(
n
1
,
n
24
)
=
{
(
n
1
,
n
2
,
l
1
)
,
(
n
2
,
n
10
,
l
5
)
,
(
n
10
,
n
24
,
w
)
}, respectively, as shown in Figure 10. If we neglect the waiting time at transfer, the static itinerary sp
1
(
n
1
,
n
24
) intuitively appears more likely to cost less time than sp
2
(
n
1
,
n
24
) because about half the distance of sp
1
(
n
1
,
n
24
) is traversed by the metro, which is much faster than a bus and the total distances of the two itineraries are very close. How can sp
2
(
n
1
,
n
24
) sometimes cost less time than sp
1
(
n
1
,
n
24
), for example, when t
o
=
60?Figure 10
Two static itineraries.To answer this question, the corresponding itineraries ofsp
1
(
n
1
,
n
24
) and sp
2
(
n
1
,
n
24
), both given an initial time of 60, are compared in Figure 11. The waiting time of the former itinerary is 3.7 minutes longer than the latter one, while the value of total travel time is only 2.4 minutes longer. Similar results can be found in other cases. Therefore, we conclude that the complex timetables that lead to waiting times during transfers are variable and almost uncontrollable, primarily resulting in the time-dependent nature of an LT itinerary in a USPT network. Obviously, these results could not be determined without considering timetables.Figure 11
Two different itineraries with the same initial time.


### 4.4. Just Missing and Just Boarding

Recall that the USPT lines are assumed to run punctually. In this premise, the phenomena of “just missing” and “just boarding” can be evaluated with the proposed algorithm. Again, we letn
o
=
n
1 and n
d
=
n
24. When t
o
=
98 (a “just boarding” case) and t
o
=
98
+
ξ (a “just missing” case), the approach determines LT itineraries p
98
(
n
1
,
n
24
) and p
98
+
ξ
(
n
1
,
n
24
), respectively, as shown in Figure 12. There is no waiting time at n
1 associated with p
98
(
n
1
,
n
24
) while with p
98
+
ξ
(
n
1
,
n
24
) the traveler must wait for 6 minutes to board the vehicle of l
1. Furthermore, we learn that when t
o varies in a continuous interval (
98
,
104
], the solutions are nearly the same, only differing in waiting time at n
o. For example, p
98
+
ξ
(
n
1
,
n
24
) costs 40 minutes to get to n
24, while it only costs 34 minutes in p
104
(
n
1
,
n
24
). They both arrive at n
24 at 138 but experience different waiting times at n
1. If these results are preknown by the traveler, he might adjust earlier to t
o
=
98 and take 32 minutes to arrive at n
d or postpone to t
o
=
104. In fact, the waiting time for transfer between two lines is almost uncontrollable, depending entirely on complex timetables, while the time spent at n
o is controllable, depending on both t
o and the timetable. These findings can significantly help travelers determine an ideal initial time to begin travel by meeting a “just boarding” case and avoiding a “just missing” case, thereby saving time. These two categories of special cases could not be determined without considering a timetable.Figure 12
“Just missing” and “just boarding” cases.


## 4.1. High Efficiency of the Floyd-A* Algorithm

An itinerary planning assistant is capable of determining the LT itinerary through real-time querying. Efficiency is the ultimate goal. For testing, 1000 triads ofn
o, n
d, and initial time t
o are randomly generated with the distance between each pair of n
o, n
d no less than 5000 meters; all pairs are connectable. Note that in the generating process, cases exist where no itinerary from n
o to n
d was found. Therefore, the Floyd-A* algorithm is capable of verifying the connexity of a USPT network. Given each triad (n
o, n
d, and t
o), each of the three procedures (i.e., Floyd-A*, Plain-A*, and Dijkstra-like aforementioned in Section 3.3) are used to solve the LTIP-USPT. The Dijkstra-like and Plain-A* procedures are traditional methods for solving these types of problems. We utilize two indicators, one averaged the running time during the calculating of the LT itinerary by a specific procedure, and the other averaged the expansion times of nodes during the searching process. Using the performance of Dijkstra-like procedure as a reference, the relative reductions of the two indicators are shown in Table 3 as well. In addition, the results outputted by different procedures in a specific instance are exactly the same. Considering that the three procedures are all admissible, we learn from Table 3 that Floyd-A* procedure reduced the running time by 33.3% and the expansion times of nodes by 61.58% compared with the Dijkstra-like procedure, while the two corresponding values were 12.84% and 25.34% savings from the Plain-A* procedure. Floyd-A* procedure proposed in this paper is superior to both the Plain-A* and the Dijkstra-like conventional procedures in terms of efficiency.Table 3
Efficiency comparison of three procedures for LTIP-USPT in Figure7.
Procedures
Item
Running time (ms)
Relative reduction of running time (%)
Expanding times of nodes (sec.)
Relative reduction of expansion times (%)
Dijkstra-like
2.0422
0
53.64
0
Plain-A*
1.78
12.84
40.049
25.34
Floyd-A*
1.3621
33.3
20.611
61.58


## 4.2. Applicability of the Floyd-A* Algorithm for Real-World Instance

To verify the applicability and efficiency of the Floyd-A* procedure in a real-world network, we implement and test the three procedures in a Visual Studio 2010 environment on the aforementioned PC, using the real-world public transport data of Shenyang City, the central city of northeastern China. The main urban zone of Shenyang City has a size of more than 700 square kilometers, and a population of more than 5 million until the year 2010. There are totally 446 directed USPT lines, which are composed of 2 metro lines and 444 bus lines. The modeled Shenyang City USPT network (within the main urban zone) is formed by 2812 nodes (after aggregating) and 184178 arcs. Similar to the experiments performed in Section4.1, 1000 triads of n
o, n
d, and initial time t
o are randomly generated; the performances are shown in Table 4. The real-world LTIP-USPT can be solved by the Floyd-A* procedure in a more efficient way; it reduces the averaged running time by 63.9% compared with that solved by the Dijkstra-like procedure. Therefore, we concluded that the Floyd-A* procedure is significantly superior to the previous related work, that is, both the Plain-A* and the Dijkstra-like procedures, with reference to efficiency.Table 4
Efficiency comparison of three procedures for LTIP in Shenyang City USPT network.
Procedures
Item
Running time (ms)
Relative reduction of running time (%)
Dijkstra-like
43.5
0
Plain-A*
34.2
21.4
Floyd-A*
15.7
63.9In reality, faced with such a large network, local citizens and tourists are difficult to determine an optimal itinerary without an itinerary planning system. To benefit the travelers, the Floyd-A* algorithm module is implemented and embedded in a Shenyang City Public Transport Query System, shown in Figure8. The system is implemented in a Visual Studio 2010 environment, combined with the geography information system TransCAD. In a case that a traveler wants the least-time travel from the Bainaohui Stop to the Wanquan Park Stop given the initial starting time 9:10, the system returns the solution that the traveler should cost 24 minutes (including in-vehicle time and waiting time) traveling from the Bainaohui Stop to the EPA Stop by Line 222, walking 1 minute to another EPA Stop, and finally arriving at the Wanquan Park Stop by Line 118 in 15 minutes. Note that the two EPA Stops are geographically different but close. The interface and the LT itinerary of the example are given as shown in Figure 8. It appears to be applicable and efficient after numerous experiments. It finally turns out that Floyd-A* can potentially be used into many large-scale real-world USPT networks for LT itinerary planning use. Note that it also has the potential to be applied in interurban context, given that all services are schedule-based.Figure 8
An example of system interface of LT itinerary planning in USPT network.


## 4.3. Time-Dependent Nature

In a static public transport network that does not consider a timetable, it is obvious that, given an origin and destination pair, the optimal itinerary (also referred as path) will consider objectives such as the least transfer time and the lowest financial expense. In other words, the solution does not depend on the departure time, while the situation is different when considering a timetable.In the case of a specified origin and destination, when given different initial timet
o, the proposed computation method returns a different LT itinerary p
t
o
(
n
o
,
n
d
) and corresponding travel time π
(
p
t
o
(
n
o
,
n
d
)
). Using the USPT network of Figure 7 as an example, n
o
=
n
1 and n
d
=
n
24 are predetermined; when given a different initial time, for example, t
o
=
55 and t
o
=
60, the itinerary p
55
(
n
1
,
n
24
) and itinerary p
60
(
n
1
,
n
24
) found with the Itinerary-Finder procedure are LT itineraries in these two cases, respectively. These results are shown in Figure 9, where the horizontal axis represents the time of day and the vertical axis represents the accumulated travel distance of the itinerary. The circles represent nodes and the links are explained in the legend. It is not difficult to see that the slope of the link represents the corresponding velocity and the curve must be monotonically increasing:Figure 9
Two LT itineraries with different initial times.p
55
(
n
1
,
n
24
)
=
{
(
n
1
,
n
3
,
l
1
,
55
)
,
(
n
3
,
n
15
,
w
,
70
)
,
(
n
15
,
n
18
,
l
6
,
71.3
)
,
(
n
18
,
n
24
,
w
,
84
)
} costs 33.1 minutes, traveling 12336 meters; the itinerary p
60
(
n
1
,
n
24
)
=
{
(
n
1
,
n
2
,
l
1
,
60
)
,
(
n
2
,
n
10
,
l
5
,
69
)
,
(
n
10
,
n
24
,
w
,
95
)
} costs 37.6 minutes, traveling 11974 meters.TheSpatial itinerary is defined as an itinerary with the temporal factors deleted. The spatialitineraries of itineraries p
55
(
n
1
,
n
24
) and p
60
(
n
1
,
n
24
) are represented as sp
1
(
n
1
,
n
24
)
=
{
(
n
1
,
n
3
,
l
1
)
,
(
n
3
,
n
15
,
w
)
,
(
n
15
,
n
18
,
l
6
)
,
(
n
18
,
n
24
,
w
)
} and sp
2
(
n
1
,
n
24
)
=
{
(
n
1
,
n
2
,
l
1
)
,
(
n
2
,
n
10
,
l
5
)
,
(
n
10
,
n
24
,
w
)
}, respectively, as shown in Figure 10. If we neglect the waiting time at transfer, the static itinerary sp
1
(
n
1
,
n
24
) intuitively appears more likely to cost less time than sp
2
(
n
1
,
n
24
) because about half the distance of sp
1
(
n
1
,
n
24
) is traversed by the metro, which is much faster than a bus and the total distances of the two itineraries are very close. How can sp
2
(
n
1
,
n
24
) sometimes cost less time than sp
1
(
n
1
,
n
24
), for example, when t
o
=
60?Figure 10
Two static itineraries.To answer this question, the corresponding itineraries ofsp
1
(
n
1
,
n
24
) and sp
2
(
n
1
,
n
24
), both given an initial time of 60, are compared in Figure 11. The waiting time of the former itinerary is 3.7 minutes longer than the latter one, while the value of total travel time is only 2.4 minutes longer. Similar results can be found in other cases. Therefore, we conclude that the complex timetables that lead to waiting times during transfers are variable and almost uncontrollable, primarily resulting in the time-dependent nature of an LT itinerary in a USPT network. Obviously, these results could not be determined without considering timetables.Figure 11
Two different itineraries with the same initial time.


## 4.4. Just Missing and Just Boarding

Recall that the USPT lines are assumed to run punctually. In this premise, the phenomena of “just missing” and “just boarding” can be evaluated with the proposed algorithm. Again, we letn
o
=
n
1 and n
d
=
n
24. When t
o
=
98 (a “just boarding” case) and t
o
=
98
+
ξ (a “just missing” case), the approach determines LT itineraries p
98
(
n
1
,
n
24
) and p
98
+
ξ
(
n
1
,
n
24
), respectively, as shown in Figure 12. There is no waiting time at n
1 associated with p
98
(
n
1
,
n
24
) while with p
98
+
ξ
(
n
1
,
n
24
) the traveler must wait for 6 minutes to board the vehicle of l
1. Furthermore, we learn that when t
o varies in a continuous interval (
98
,
104
], the solutions are nearly the same, only differing in waiting time at n
o. For example, p
98
+
ξ
(
n
1
,
n
24
) costs 40 minutes to get to n
24, while it only costs 34 minutes in p
104
(
n
1
,
n
24
). They both arrive at n
24 at 138 but experience different waiting times at n
1. If these results are preknown by the traveler, he might adjust earlier to t
o
=
98 and take 32 minutes to arrive at n
d or postpone to t
o
=
104. In fact, the waiting time for transfer between two lines is almost uncontrollable, depending entirely on complex timetables, while the time spent at n
o is controllable, depending on both t
o and the timetable. These findings can significantly help travelers determine an ideal initial time to begin travel by meeting a “just boarding” case and avoiding a “just missing” case, thereby saving time. These two categories of special cases could not be determined without considering a timetable.Figure 12
“Just missing” and “just boarding” cases.


## 5. Conclusions and Future Work

This paper has presented an ad hoc Floyd-A* algorithm to determine the least-time itinerary from origin to destination in an urban scheduled public transportation network when given initial time to start the travel. A modified representation of the USPT network and the travel itinerary was proposed. The itinerary in a bimodal, time-dependent USPT network was composed of time-label arcs, whose timing method was explicitly specified. Traveler operability was given to constrain the itinerary structure. A methodology to estimate travel time between two nodes as a sufficiently tight static lower bound of the corresponding real travel time was proposed as a key contribution for high efficiency. The ad hoc Floyd-A* procedure was mathematically proven to be correct and more efficient than the Plain-A* and Dijkstra-like procedures, which appeared in previous related works. Meanwhile, through an illustrated example and a real-world example, we showed that the Floyd-A* algorithm appears to be very suitable and efficient for LTIP-USPT. These results reflect the time-dependent nature of the least-time itinerary in a scheduled network and can serve as guidance for travelers in predetermining an ideal initial time by meeting “just boarding” cases while avoiding “just missing” cases in the premise that lines run punctually. The efficiency performance was numerically tested to be superior to both Plain-A* and Dijkstra-like procedures.It should be noted that the proposed approach for LTIP-USPT is primarily based on the hypothesis that vehicles of lines run in absolute compliance with their timetables. However, it is evident that early arrivals or delays can occur at each node during vehicle trips, and the uncertainties are dynamically revealed. One way to mitigate these uncertain effects is to consider the stochastic optimization or robust optimization methodologies. Floyd-A* may not be suitable for direct application at that time, but its adaptation (maybe with a parallel program) should be considered. These topics certainly constitute a motivation for future works.



---

*Source: 185383-2014-04-27.xml*