# Research on the connectivity of public transportation network based on set method.

Abstract A connectivity judgment method for public transportation network based on set idea is studied in this article. Set is successfully applied to solve the problem of connectivity judgment on multi-vertex and multi-edge situation. Search level control strategy is adapted to control the search level of route, and three buffer tables are designed to improve the search speed and reduce the complexity of the algorithm.Keywords Traffic management, connectivity, transportation network, search level control.

[section] 1. Introduction

Public transport is the main travel way for urban civilians and it is also a way advocated by many governments and organizations under the environmental protection concept. On one hand, along with the rapid construction of urban traffic, public travel becomes more and more convenience; on the other hand, problems come forth with multi-route selection. The civilians had to balance among fee, time cost, distance and some other areas, especially those in large cities or metropolis. And all this must be built on the basis of the pathway connectivity judgment, which are the major problem, as well as the common pathway connectivity judgment and optimization strategy under the circumstances of huge number of bus stations and bus lines, discussed in this article.

[section] 2. Some known results

2.1. Problem description

The pathway connectivity discussed in this article means the connectivity between one station and another, directly or through a third or more other stations, then find out the routes and the shortest one if they are interlinked.

Basically, there are three types of public transport network distribution which include, all stations on the up-run line and down-run line are the same (also called Bidirectional Lines, part of the stations are the same (also called Unilines) and Loop Lines. Meanwhile there are two types of fee system known as Flat Fare and Sectional Fare. Following are three lines' information of a city's public transport system.

[l.sub.135], Bidirectional Line; Sectional Fare.

[s.sub.0417] - [s.sub.0272] - [s.sub.3425] - [s.sub.3476] - [s.sub.2974] - [s.sub.0234] - [s.sub.0521] - [s.sub.3806] - [s.sub.1682] - [s.sub.3559] - [s.sub.0928] - [s.sub.3564] - [s.sub.0079] - [s.sub.3175] - [s.sub.2866] - [s.sub.3172] - [s.sub.3269] - [s.sub.3603] - [s.sub.1633] - [s.sub.2578] - [s.sub.2579] - [s.sub.2576] - [s.sub.2577]

[l.sub.181], Uniline; Flat Fare.

Up-Run Line:

[s.sub.0238] - [s.sub.0540] - [s.sub.0542] - [s.sub.3024] - [s.sub.0494] - [s.sub.0973] - [s.sub.3077] - [s.sub.2082] - [s.sub.2213] - [s.sub.2210] - [s.sub.3332] - [s.sub.3351] - [s.sub.1414] - [s.sub.0228] - [s.sub.0916] - [s.sub.2811] - [s.sub.0019] - [s.sub.0966]

Down-Run Line:

[s.sub.0966] - [s.sub.0019] - [s.sub.2811] - [s.sub.0916] - [s.sub.0228] - [s.sub.1414] - [s.sub.3351] - [s.sub.3332] - [s.sub.2210] - [s.sub.2213] - [s.sub.2082] - [s.sub.3077] - [s.sub.0973] - [s.sub.0494] - [s.sub.3024] - [s.sub.0542] - [s.sub.0541] - [s.sub.0152] - [s.sub.1765] - [s.sub.3506] - [s.sub.0238]

[l.sub.590], Loop Line; Flat Fare.

[s.sub.3295] - [s.sub.3265] - [s.sub.1334] - [s.sub.1333] - [s.sub.2285] - [s.sub.1341] - [s.sub.0327] - [s.sub.0317] - [s.sub.0325] - [s.sub.0532] - [s.sub.1734] - [s.sub.0314] - [s.sub.1749] - [s.sub.1831] - [s.sub.1337] - [s.sub.0705] - [s.sub.0704] - [s.sub.3295]

Where [l.sub.n] is the n-th line's No. of the city and [s.sub.m] is the m-th station of the city.

2.2. Specialties of the problem

Algorithm for connectivity of graph (include Breadth First Search and Depth First Search, adjacency matrix and genetic algorithm are all popular methods adopted to judge pathway connectivity [1]. Outwardly, public transport network can be convert to a digraph whose vertexes are stations and edges are lines between two stations. However there are actually more than one line that go through each station in the transport network, namely, there are unfixed number of edges between two adjoining vertexes. Therefore, the commonly used router algorithms for connectivity of graph are inapplicable since the time complexity and space complexity increase rapidly, for instance, there are more than 850 bus lines and more than 6400 bus stations in city Beijing [2], since the transport network is a n-th Iterated Line Digraphs [3].

Moreover, on one hand, because of the characteristics of intersecting and overlapping, there are always more than one line between two adjoining stations. On the other hand, even if there are route between two stations, it may need ongoing transferring, however, it is contrary to the public's travel habits which are the less transferring, the better. According to the experience of livelihood, the public trend to reduce their transferring frequency when other factors' (such as cost, time, etc.) difference is not very significant. That is, if there are more than one route between two stations, direct line has priority over transferring and transferring once has priority over transferring more times and so on, and other factors will be taken into considering only when transferring frequencies are equal. Therefore, the following discussing was based on the public's travel habits.

[section] 3. Set method for connectivity

3.1. Set description

Provide elements [l.sub.i], [s.sub.j] and sets [L.sub.i], [S.sub.j], [A.sub.j], [B.sub.(j,i)], which are

[l.sub.i]: Element that indicate line No. i;

[s.sub.j]: Element that indicate station No. j;

[L.sub.i]: Set of all lines that pass through station [s.sub.i];

[S.sub.j]: Set of stations that line [l.sub.j] pass through;

[A.sub.j]; Set of stations that can be reached start from [s.sub.j];

[B.sub.(j,i)]: Set of all stations that can be reached with line [l.sub.i] start from station [s.sub.j];

The following expressions can be drown out:

1). Direct Line: the following expression is obtained if there have direct line run from start station [s.sub.start] to destination station [S.sub.dest]:

[S.sub.start] [right arrow] [S.sub.dest] [??] {[S.sub.start], [S.sub.dest]} [subset or equal to] [A.sub.start] [intersection] [A.sub.dest]. (1)

Where [s.sub.start] [right arrow] [s.sub.dest] indicate there are direct line run from [s.sub.start] to [s.sub.dest].

Therefore, when {[s.sub.start], [s.sub.dest]} [subset or equal to] [A.sub.start] [intersection] [A.sub.dest] is establish, namely, there are direct line run from [s.sub.start] to [s.sub.dest], the collection C of all direct lines are the intersection of set [L.sub.start] whose elements are lines that run through start and set [L.sub.dest] whose elements are lines that run through [s.sub.dest]:

C = [L.sub.start] [intersection] [L.sub.dest]. (2)

2). Transfer Once: The circumstance of transfer once from [s.sub.start] to [s.sub.dest] can be converted to the iterate of two direct lines, that is, the direct line from the start station [s.sub.start] to the transfer station [s.sub.transfer] and the direct line from the transfer station [s.sub.transfer] to the destination station [s.sub.dest]. Therefore the set D of transfer stations is:

D = [A.sub.start] [intersection] [A.sub.dest]. (3)

3). Transfer multi-times: Similarly, The circumstance of transfer n-times from [s.sub.start] to [s.sub.dest] can be converted to the iterate of (n + 1) direct lines.

Direct line and transfer-needed circumstances are schematically shown in Fig 1.

[FIGURE 1 OMITTED]

3.2. Optimization of algorithm

As has been analyzed that the public always trend to choose routes with less transferring frequencies, therefore, direct lines should be searched in top priority; deepen search level when direct lines are not available, and so on and so forth, until searching accomplished (succeed or failed [4]. In addition, three memory tables known as line-station hash table, line-station searching linked-list and station-line searching linked-list are designed to improve the searching speed and reduce the searching complexity.

3.2.1. Route searching strategy

Search-level control strategy was introduce to integrate the Breadth-First Search method (BFS) and Depth-First Search method (DFS). The concrete steps are list in the following:

1). Construct set [L.sub.start], [L.sub.dest], and [A.sub.dest] for [s.sub.start] and [s.sub.dest].

2). Figure out the intersection of [L.sub.start], and [L.sub.dest], [L.sub.start] [intersection] [L.sub.dest]. Then find out all identical elements in both set [L.sub.start] and set [L.sub.dest] via BFS, thus the result C is the set of all direct lines.

a). If C is not empty, record all elements in C which are all direct lines.

b). If C is empty, deepen the search levels and continue with step 3);

3). Figure out the intersection of [A.sub.start] and [A.sub.dest], [A.sub.start] [intersection] [A.sub.dest]. Then find out all identical elements in both set [A.sub.start] and set [A.sub.dest] via DFS, thus the result set D is the set of all transfer stations.

a). If D is not empty, record all elements in D which are all transfer stations. Then search direct lines with [s.sub.start] and D, [s.sub.dest] and D, respectively.

b). If D is empty, keep on deepening the search levels.

3.2.2. Hash table structure of line-station

Hash table structure of line-station stores the relationship of lines and stations. When the hash value, which are corresponded a line and a station, is "1", the corresponding line runs through the corresponding station, and "0" , doesn't. The hash table structure of line-station is schematically shown in Fig. 2.

As can be clearly seen from Fig. 2 that row direction of the hash table represents the lines and column direction, the stations. Moreover, the hash value "1" in row direction marks all stations that the corresponding line runs through, and in column direction marks all lines that run through the corresponding station. As is known to all that the time complexity of search algorithm using hash table structure is the constant of O(1) [5].

Two important logic relationships are implicated in the above halt table structure, known as:

1). There are direct line between every two stations whose hash value is "1" in the same row.

2). Transfer is available between every two lines whose hash value is "1" in the same column.

Actually, the purpose of constructing the hash table of line-station is to perform high speed search utilizing these two relationships.

3.2.3. Line-station searching linked-list

Line-station searching linked- list stores the stations that every line runs through successively in a duplex linked- list. The list is sorted by line NO. to locates elements with binary search. Line-station search list structure is schematically shown in Fig. 3.

[FIGURE 3 OMITTED]

Since the time complexity of binary search is O(log(n)) , the total time complexity of the line-station duplex searching linked-list is

O(log(m)) + O(log(max(spl))), (4)

where m is the count of all lines; max(spl) is the max count of stations that a line runs through.

3.2.4 Station-line searching linked-list

The station line searching linked-list is also designed as a duplex linked- list, every of whose nodes stores all lines that run through the station. The list is sorted by station NO. to locates elements with binary search. Line-station search list structure is schematically shown in Fig. 4.

[FIGURE 4 OMITTED]

Similarly, the total time complexity of the station-line duplex searching linked-list is O(log(n)) + O(log(max(lps))) (5)

where n is the count of all stations; max(lps) is the max count of lines that runs through a station.

3.3. Implementation of algorithm

The following route searching steps are acquired with integrated consider of search-level control strategy and optimization methods:

With regard to the start station [s.sub.start] and the destination station [s.sub.dest]

1). Set [L.sub.start] and set [L.sub.dest] are obtained from station-line searching linked-list by binary searching and select the one with less elements, that is min([L.sub.start], [L.sub.dest]).

2). Pick out all elements from min([L.sub.start], [L.sub.dest]) one by one and search for [s.sub.start] or [s.sub.dest] in line-station searching linked-list (If min([L.sub.start], [L.sub.dest]) = [L.sub.start], search for [s.sub.start], else search for [s.sub.dest), record matched lines and store them in set [L.sub.match];

a). If [L.sub.match] [not equal to] [empty set], output all elements in [L.sub.match] which are direct lines;

b). Else if [L.sub.match] = [empty set], deepen the search levels and continue with step 3);

3). Figure out D = [A.sub.start] [intersection] [A.sub.dest]

a). If D [not equal to] [empty set] and D = {[d.sub.1], [d.sub.2], ... [d.sub.n]}, then [d.sub.1], [d.sub.2], ... [d.sub.n], are transfer stations. Go to step 1), perform direct-line searching with [s.sub.start] and elements in D, as well as elements in D and [s.sub.dest] respectively.

b). Else if D = [empty set] deepen the search levels and continue with step 4);

4). Pick out [s'.sub.start] and [s'.sub.start] from [A.sub.start] and [A.sub.dest] respectively, then set the searching level to 1 and continue with step 1), namely transform the problem to search for direct-line between [s'.sub.start] and [s'.sub.dest].

[section] 4. Summary

Because of the characteristics of intersecting and overlapping, the commonly used router algorithms based on Graph Theory or Genetic Algorithm are inapplicable in the public transport network; therefore, a set-based connectivity judging method was proposed in this article. Search level control strategy is adapted to resolve the graph problem with huge number of vertexes and edges and a hash table and two duplex linked-list are designed to improve the searching speed and reduce the searching complexity.

References

[1] Yuanzuo Li, Dishan Qiu, Properties of Generalized Connectedness of Graph and Commonly-Used Connecting Structures, Journal of Systems Engineering, 15(2000), No.3, 1-6.

[2] Public Transportation Technology Forum of China, Beijing Public Transport Statistics, http://www.tranbbs.com/Html/TechArticleData/185141316.htm, 2005-1-6.

[3] Zhao Zhang, Fengxia Liu, Jixiang Meng, Super-Connected n-th Iterated Line Digraphs, Operations Research Transactions, 9(2005, No.6, 35-39.

[4] Zhao Zhang, Jixiang Meng, Super Edge Connectivity of Inifnite Circulants, Mathematica Applicata, 15(2002) (supplement), 68-71.

[5] Weimin Yan, Weimin Wu, Data Structure, Beijin, Tsinghua University Press, 1997, 251-256.

Chumming Lin ([dagger]), Wansheng He ([double dagger]), Hongming Xia ([double dagger]) and Zhongshe Gao ([double dagger])

([dagger]) Department of Computer Science and Technology, Tianshui Normal University Tianshui, Gansu, 741001, P. R. China

([double dagger]) School of Mathematics and Statistics, Tianshui Normal University Tianshui, Gansu, 741001, P. R. China

E-mail:cucmeLiu@gmail.com

Figure 2: Schematic view of the hash table structure of line-station [s.sub.1] [s.sub.2] [s.sub.3] [l.sub.1] 0 1 0 [l.sub.2] 1 0 0 [l.sub.3] 0 0 1 ... [l.sub.m-1] 0 1 0 [l.sub.m] 0 0 1 ... [s.sub.n-1] [s.sub.n] [l.sub.1] ... 1 0 [l.sub.2] ... 1 0 [l.sub.3] ... 0 1 ... ... [l.sub.m-1] ... 1 1 [l.sub.m] ... 0 1

Printer friendly Cite/link Email Feedback | |

Author: | Liu, Chumming; He, Wansheng; Xia, Hongming; Gao, Zhongshe |
---|---|

Publication: | Scientia Magna |

Article Type: | Report |

Geographic Code: | 9CHIN |

Date: | Sep 1, 2008 |

Words: | 2595 |

Previous Article: | On the continued fractions and Dirichlet L-functions. |

Next Article: | On the property of the Smarandache-Riemann zeta sequence. |

Topics: |