(1)
This difference makes the movement of persons and vehicles in public transport systems more difficult to model than in individual systems.
The duration of a travel in a public transport system (the travelling
time) is defined as the sum of the terms waiting time, in-vehicle
travel time and interchange time (1).
|
|
(1)
|
Conventional models of public transport systems do not take the exact absolute time into consideration and therefore only average values of travelling times can be calculated. Furthermore these models can neither take connection correspondences nor connection frequency distribution in time into account. A conventional model can hence not be used to answer questions like Which is the fastest way to go from A to B, Wednesday morning at 8:17?
To do this, a model of a more complex topological nature is required. Complex networks of this kind have been rather difficult to represent in a GIS prior to ArcInfo 7.1. However, using the data structure proposed in this paper, the new topological features of the ArcInfo 7.1 NETWORK module provide a simple way of solving this problem.
Figure 1 shows two transit lines serving seven stops in all. Line 1
starts at A, ends at E and visits the stops B, C and D. Line 2 starts at
I, ends at H and also visits the stops B, C and D. The representation is
not directed, each line on the figure and accordingly in the model represents
both directions of that line. To represent the two transit lines in the
figure, eight links are needed in the model.
Figure 1: The traditional way of modelling public transport in a
transport model
These links have feature attributes describing the in-vehicle travel time and the frequency by which the service of transport is provided. The frequency is calculated for the period of time the model is valid, e.g. the morning rush or the whole day. The commonly known transport models EMME/2 and TRIPS both follow this principle. [Ortúzar et al. (1994), HTM (1996)]
The in-vehicle travelling times are taken directly from the link attributes, waiting and interchange times at the stops are calculated from the link frequencies. However, since the frequencies represent the number of connections between stops for a certain period of time, the calculated waiting and interchange times are correspondingly average values for that specific period of time.
Neither can a model of this type take correspondences between transit connections into account. Therefore, models of this type often lead to particularly inaccurate results when used in transit systems with low frequencies, i.e. in rural areas where the few connections often are equally well co-ordinated to correspond with each other.
Furthermore, a model of this type can not take the frequency distribution in time into account. If the model covers the whole day, the travelling times calculated with the model will correspondingly be average travelling times over the day. Typically, the waiting and interchange times in the rush hour are shorter due to the high frequencies with which the services are provided than for example in the evening. Equally the in-vehicle travel times are typically longer in the rush hour due to congestion.
The idea behind the proposed model is to represent time as the third
dimension, and to take each physical vehicle running on the transit lines
into consideration. Each vehicle is then represented by a link between
points not only in the plane but also in time. The concept of the proposed
data model is shown in figure 2.
Figure 2: The proposed 3D vehicle run representation of modelling
public transport
The lower part of figure 2 shows the maps of the bus lines from figure 1. Above this map a grid of dotted lines is spanned. The perpendicular lines in this grid represent the same position in the plane, the horizontal lines the same position in time.
In this grid the links of three different vehicle runs are shown. A vehicle run is defined as the movement of a physical vehicle (train, bus, etc.) in one direction from the first stop the vehicle visits to the last. The links thus represent the physical movement of the individual vehicles in time and space.
Due to the fact that one link is needed for each vehicle run between two stops, a total of twelve links is needed to model these three vehicle runs. As opposed to the model shown in figure 1, the proposed model is a so called directed graph as all links are one-way links. [Cormen et al. (1989)]
For reasons of simplicity only the vehicle runs in the general direction of the X-axis are shown in figure 2, in reality vehicles would be running in both directions on each particular line. Note that the direction of the time axis on figure 2 is down, so that the only possible direction of movement is downward.
In figure 2 line 1 runs from A to E via B, C and D and vice versa. The bus connection with the vehicle run number 1a, departs from A at 8 o'clock and arrives at H at 8:20. On the way the stops D, C and B are visited at 8:05, 8:10 and 8:15 respectively.
If a passenger wants to travel from A to I, and arrives at the stop at A at 8:05, he or she has to wait five minutes before the first bus is departing from the stop at 8:10. This bus has vehicle run number 1b and arrives at B at 8:25. Here the passenger has to wait five minutes until a connection to I is provided at 8:30. This connection arrives at I at 8:35. The total travelling time is thus 30 minutes, of which five minutes are waiting time, five minutes interchange time and 20 minutes in-vehicle travel time. The same journey could also be accomplished by changing busses at D or C instead of B.
In conventional models for public transport systems, each stop is represented by one node, in some models by one node for each line serving the stop. In the proposed model however, there is one node for each unique point of time at which a vehicle arrives or departs from the stop. A transit stop is then represented by a group of nodes as shown in figure 3.
Figure 3: The representation of a transit stop in the proposed model
as a group of nodes
As shown in figure 4, the representation of interchange links in a model
like the one proposed can be accomplished using several principles.
Figure 4: Different principles of representing the interchange links
(grey) at each stop
a) The arriving and departing links can be coupled in a combinatorial
manner, so that each arriving link is connected to all of the departing
links. If n denotes the number of arriving links, and m the
number of departing ones, this results in a total number of interchange
links i given by (2).
 |
(2)
|
 |
(3)
|
 |
(4)
|
 |
(5)
|
The number of necessary interchange links from the different principles
of representation can be seen in figure 6. As seen, it is associated with
significant advantage to chose the last representation principle, as the
number of necessary interchange links only increases proportionally to
the number of arrivals. Using the first two representation principles the
number of necessary interchange links increases with the square of the
number of arrivals.
Figure 6: The number of interchange links needed (i) for the different
types of interchange link representation as a function of the number of
arrivals to a stop (n)
The PATH command of ArcInfo uses the modified Dijkstra path finding
algorithm with a binary heap priority queue. According to Cormen et al.
(1989), the complexity of this algorithm for sparse graphs is given by
(5), where P is the number of points (nodes) in the graph, E
the number of edges (links) and O the order of complexity.
 |
(6)
|
Principle c) however, has a small disadvantage due to its serial nature. The disadvantage is, that a path finding algorithm will need slightly more iterations to find a path, because an interchange in the model may be represented by a series of several links. This is seen from figure 5. Using principle a) and b) each change is represented by a unique link.
For practical reasons, the interchange links are represented as spirals, which when projected onto the plane as on figure 7 below, become circles.
Figure 8a shows the two types of connection links to zone nodes (grey)
in the model: The arriving links to the zone node (dark red) and the departing
links from the zone node (dark green). Figure 8b shows the interchange
links (puple) and figure 8c all the link types in the model around a stop
attached to a zone node (zone centroid).
Figure 8: Link types of the proposed model
The link impedances on the connection links going from the zone node to the departing links are calculated dynamically according to the exact time at which the travel starts, i.e. the time the passenger wants to travel. The travel start time is subtracted from the departure time of the nodes of the departing links. The result of this subtraction is the time the passenger has to wait from the travel start time until each vehicle departs. The impedance of the connection links is thus the waiting time. If the waiting time for a particular departure is negative, that departure has already left the stop, and the link can not be traversed.
The objective of the model is to calculate travelling times corresponding to a set of survey travel data (trips). These travelling times are then used to calibrate an econometric transport mode choice and trip length generation model to investigate political instruments that can lead to change of transport behaviour, and the environmental changes as a result hereof.
The third dimension in the model is established through this topological capability. Line topology is built with the RENODE command using elevation items from the arc attribute table (AAT). Thus, the departure time for each link (arc) in the model is used as from-elevation-item and the arrival time as to-elevation-item.
Due to the fact, that arcs of zero planar length are not permitted in ArcInfo coverages, the interchange links can not be implemented as straight arcs from one node to the next in 3D. Therefore the interchange links are generated as circles. These circles however, represent the projection of 3D spirals onto the plane.
Figure 9 shows a 3D view of the proposed model for a stop with four
arriving vehicles and four departing ones. To model the interchange possibilities
at the stop, a total of seven interchange links is needed. The green lines
show the projection of the model onto the plane represented by the rectangle.
.
Figure 9: 3D view of the proposed model showing vehicle run and interchange links
The projection of the model onto the plane (i.e. the green lines on the figure) is the only visible part of the model when seen from inside ArcInfo as a line coverage. Figure 9 was created using an AML-program to extract the data from the line coverage and attribute table using the UNGENERATE and CURSOR commands to generate a data file. This data file was then plotted with the plotting program GnuPlot.
Figure 10: Data flow in the implemented model for the calculation
of travelling times
The different data sets seen on figure 10 are shown in the following section 3.3.
The following pseudo code describes the constructing of the public transport
network model:
| For each transport company timetable database
For each vehicle run For each segment between two stops Transform timetable data using the appropriate timetable database interpreter Find the shortest path between stops on appropriate road or railroad network Convert the shortest path route feature to arc feature Join departure and arrival times from timetable to the arc attribute table Next segment Next vehicle run Next transport company timetable database For each stop
Select stops that are to be connected to zones
Select stops that are to be connected with connection links (stations
and bus stops)
Build line topology using departure and arrival time as elevation
items
|
| Build internal network in ArcPlot using arc traversing time as
impedance item
For each trip in the travel data Select all connection links (arcs) from the origin zone node Calculate the waiting time on currently selected links (arcs) Update internal network with waiting times for currently selected links (arcs) Find shortest path from origin zone node to destination zone node Next trip For each route in the shortest path route system
|
At present the model has only been implemented for half of the country due to lack of data. The estimated total number of arcs for the complete implementation is 2,500,000.
The upper left corner of figure 11 shows the road network. This data set is managed by the Danish State Road Directorate and the National Survey and Cadastre and contains different line attributes, e.g. road type, width and speed limit. The road network consists of about 85,000 arcs.
In the upper right corner of Figure 11 the railroad network used for
the implementation is shown. This data set is managed by the Danish National
Survey and Cadastre, however, the data set contains no attributes.
Figure 11: The road map, the railroad map, the public transport
stop map and the transport analysis zone map. The extracts of maps belonging
to The National Survey and Cadastre are reproduced according to the agreement
G18/1997
The two maps shown in the lower part of figure 11 are maps digitised by NERI itself. The destination map (left) consists of about 3,200 destinations (bus stops and train stations) and the transport analysis zone map (right) consists of about 1,500 zones.
Figure 12 shows an example of the timetable data used in the project.
Totally, the five different database types contain about 50 MB of timetable
data from 17 different transport companies.
Figure 12: A simplified example of the time table data
The timetable database interpreters are implemented using SQL-queries in ORACLE 7.3.2.2.1 and MS Access 7.0.
The digitising of destinations and transport analysis zones has been performed using ArcView 3.0a and ArcInfo 7.1.2.
The model itself is implemented in ArcInfo 7.1.2 using Arc, ArcEdit, ArcPlot, Tables, AML and the NETWORK module.
The first approach was to use turntables to model the interchange possibilities at each stop. Using turntables however, the number of turn records increases with the square of the number of arcs at each node. Given the size of the model, an excessive number of turns thus had to be calculated. The potential turntable was so large that it exceeded the limitations of available soft and hardware. For this reason the approach failed and the method was given up.
The next approach was to implement a model with 2D line topology without the use of turntables. This meant that all arcs representing vehicle runs had to be separated from each other, so that no coincident nodes existed, i.e. so that all nodes were dangling nodes.
The separation of arcs was first performed using the ArcEdit MOVE PARALLEL command. However, given the size of the model and the number of vertices per arc, this process was so time consuming that other methods had to be investigated.
The next method investigated was to use the UNGENERATE command to generate a text file containing the arc geometry and then altering only some of the arc geometry using AML text file functions. This method proved much faster than the MOVE PARALLEL method. However, the problem of ensuring no coincident nodes was still consuming an unacceptable amount of time.
Several ways of solving this problem were investigated, including the building of spatial indices outside the ArcInfo coverage data model. The fastest method investigated was to implement a random generator in AML and to move the nodes a distance chosen at random. This method ensured that only a few nodes were coincident after moving them all the first time.
The resulting model of these investigations is seen on figure 13, showing
the interchange links of a bus terminal of a provincial town using principle
b) for the representation of interchange links as described in section
2.2.
Figure 13: An early 2D version of the model
The implementation of the proposed 3D model proved no analogous problems using the new features in the ArcInfo 7.1 NETWORK module.
With this in mind it may be concluded that there are considerable advantages associated with modelling public transport using a 3D approach in which time is represented as the third dimension rather than trying to force an equivalent model type into only two dimensions.
The most obvious disadvantage of the implemented model however, is still the model data requirements and processing time.
With the present hardware (described in section 3.4.) the model can calculate travelling times at a speed of about 2,000 travels (trips) pr. hour, which is acceptable for most modelling purposes. With the size of the present travel data this is equal to a total processing time of 50 hours to calculate travelling times for all trips in the data set.
The construction process of the model (described in section 3.3.) however still demands considerable processing time. For this reason several optimisation strategies must be investigated in the future. The processing time benefits of using Esri's Spatial Database Engine (SDE) for the storage of data is one of these.
Nevertheless the implemented model will found the basis of several NERI
transportation research projects in the near future including projects
involving scenario analyses, benchmarking indicators in public transport
and others.
I addition I would like to thank Peter Ohm and Kurt Andersen from Informi GIS for their persistent technical support in the initial, somewhat problematic phase of the project.
The various tips and tricks of Andreas Bærentzen have been greatly appreciated.
The extracts of maps belonging to The National Survey and Cadastre are reproduced according to the agreement G18/1997.
Hansen (1996 ); Comparing the Accessibility Patterns for Public Versus Private Transport Networks, Henning Sten Hansen; In: Rumor, M., McMillan, R. & Ottens, H.F.L. (eds.): Geographical Information. From Research to Application through Cooperation. Volume 1. Second Joint European Conference & Exhibition on Geographical Information, Barcelona, Spain, 1996. IOS Press. pp. 703-707.
Harris et al. (1992); Transit Network Modelling - A New Approach, Nigel Harris, London Underground Ltd., Martin Bach, MVA Systematica; In: Proceedings of the 4th International Conference on Microcomputers in Transportation, Baltimore 1992
HTM (1996); Hovedstadstrafikmodel Version 3.0 - Beskrivelse af døgntrafikmodel, Firma Anders Nyvig A/S, København 1996 (Danish)
Spiegel (1968); Mathematical Handbook of Formulas and Tables, Murray R. Spiegel, McGraw-Hill Publishing Company, New York 1968