Chapter 5 —
Transport Data

Data on the road

As we have discussed in the previous chapter, it is difficult to draw the line between transport data and non transport data. Even merely administrative datasets such as the alteration of a streetname, may at some point become useful for a route planning algorithm. We first discuss, within the field of Intelligent Transport Systems (its), what the constraints should be for an information system, in order to share transport data world-wide.

Constraints for a large-scale its data-sharing system

Within the domain of its, the its directive helped popularizing publicly sharing data. For example, with a delegated regulation elaborating on a European Access Point for Truck Parking Data, it regulates sharing the data through a national access point similar to the inspire directive, a directive for sharing data within the geo-spatial domain.

When creating a system to distribute data within our own domain – for the many years to come – an important requirement is that this data policy needs to scale up efficiently. When more datasets are added, when more difficult questions need to be answered, when more questions are asked, or when more user agents come into action, we want our system to work without architectural changes. Furthermore, the system should be able to evolve while maintaining backwards-compatibility, as our organization is always changing. Datasets that are published today, still have to work when accessed when new personnel is in place. Such a system should also have a low entry-barrier, as it needs to be adopted by both developers of user agents as well as data publishers.

A use case in Ghent

The mobility organization of Ghent was given the task to build a virtual traffic centre. The centre should inform Ghentians with the latest up to date information about mobility in the city. As the city is in a transition, banning cars from the city centre, this is a project with high expectations. Information to build this traffic centre comes from existing geospatial layers, containing the on-street parking zones with, among others, their tariffs, all off-street parking lots, all streets and addresses, and all traffic signs. Also real-time datasets are available, such as the sensor data from the induction loops, bicycle counters, thermal cameras, and the availability of the off-site parking lots. Third parties also contribute datasets, such as the public transit time schedules and their real-time updates, and traffic volumes in, to and leaving the city. In order to bring these datasets from various sources together, and analyse them, both the semantics as the queryability is lacking.

The city of Ghent allowed us to define a couple of uris for parking sites. In this city, a uri strategy is in place to negotiate identifiers since 2016. The uri strategy defines a base uri at “https://stad.gent/id/”. Using this strategy, the city introduced uris for each parking site, similar to the examples above. When we now would point our browser to https://stad.gent/id/parking/P1, we will be directed to a page about this parking space. Furthermore, this identifier is interoperable across different systems, as when we would get this uri from a computer program, I can negotiate its content type, and request an rdf representation of choice.

As there are only a couple of parking sites at the city of Ghent, describing this amount of parking sites easily fits into one information resource identified by one url, for instance, http://linked.open.gent/parking/. When the server does not expose the functionality to filter the parking sites on the basis of geolocation, all user agents that want to solve any question based on the location of parking sites, have to fetch the same resource. This puts the server at ease, as it can prepare the right document once each time the parking sites list is updated. Despite the fact that now all parking sites had to be transferred to the user agent, and thus consumed more bandwidth, also the user agent can benefit. When a similar question is executed from the same device, the dataset will already be present in the user agent’s cache, and now, no data at all will need to be transferred. This raises the user-perceived performance of a user interface. When now the number of end-users increases by a factor of thousand per second – not uncommon on the Web – it becomes easier for the server to keep delivering the same file for those user agents that do not have it in cache already. When it is not in the user agents own cache, it might already be in an intermediate cache on the Web, or in the server’s cache, resulting in less cpu time per user. Caching, another one of the rest constraints, thus has the potential to eliminate some network interactions and server load. When exploited, a better network efficiency, scalability, and user-perceived performance can be achieved.

Without the cors header, a resource is by default flagged as potentially containing private data, and cannot be requested by in-browser scripts at a different domain. More information at enable-cors.org In a test environment, we published a Linked Data document at http://linked.open.gent/parking/, by transforming the current real-time xml feeds using a php script. First, this script adds metadata to this document indicating this data has an open license, and thus becomes legally interoperable with other Web resources. Next, we added http headers, indicating that this document can be used for Cross Origin Resource Sharing (cors), as well as an http header that this document can be cached for 30 seconds. Finally, we also added a content negotiation for different rdf representations.

As we would like to solve Basic Graph Patterns (bgp) queries, we added the hypermedia controls requested by the Triple Pattern Fragments (tpf) specification, which details how to filter the triples in this document based on their subject and/or predicate and/or object [4]. As the number of data facts that need to be published is small enough, we directed all controls to the main document, and did not expose extra server functionality. The latest version of the Triple Pattern Fragments hypermedia specification can be found at https://www.hydra-cg.com/spec/latest/triple-pattern-fragments/.

Following these steps, we made the data queryable through clients that can exploit the Triple Pattern hypermedia controls, such as the Linked Data Fragments client available at http://client.linkeddatafragments.org. This client is able to query over multiple Triple Pattern Fragments interfaces at once, and thus answer federated queries by following hypermedia controls. The following query selects the name, the real-time availability, and the geolocation from Open Street Map (Linked Geo Data) of a parking lot in Ghent with more than 200 spaces available: http://bit.ly/2jUNnES. This demonstrates that complex questions can still be answered over simple interfaces. The overall publishing approach is cost-efficient and stays as close as possible to the http protocol as a uniform interface. The only part where an extra technical investment was needed, was in documenting the definitions of the new uris for the parking sites.

Public Transit Time Schedules

Computation of routes within road networks and public transport networks are remarkably different: while some speed up methods work well for the former, they do not for the latter [5]. In this chapter, we will focus on public transit route planning, further on referred to as route planning.

A public transit network is considered, in its most essential form, to consist of stops, connections, trips, and a transfer graph [6]:

• A stop p is a physical location at which a vehicle can arrive, drop off passengers, pick up passengers and depart;
• A connection c represents a vehicle driving from a departure stop at a departure time, without intermediate halt, to an arrival stop at an arrival time;
• A trip is a collection of connections followed by a vehicle;
• A transfer is when a passenger changes a vehicle at the same stop, or a nearby stop with a certain path in between.

For future reference, an arrival and a departure are two concepts defined by a location and a timestamp. A departure at a certain stop, linked to an arrival at a different stop can thus create a connection.

Route planning queries

We differentiate various types of queries over public transport networks [9]:

• An Earliest Arrival Time (eat) q is a route planning question with a time of departure, a departure stop, and an arrival stop, expecting the earliest possible arrival time at the destination;
• The Minimum Expected Arrival Time (meat) is similar to an eat, yet it takes into account the probability of delayed or canceled connections;
• Given departure stop, a profile query computes for every other stop the set of all earliest arrival journeys, for every departure from the departure stop;
• The multi-criteria profile query calculates a set of journeys that each are not outbettered in arrival time or number of transfers, also called a set of Pareto optimal journeys.

Other queries

Within any of the given problems, a user may need extra personal features, such as the ability to request journeys that are wheelchair accessible, journeys providing the most “happy” route [2], journeys where the user will have a seat [1], or journeys with different transfer settings depending on, e.g., reachability by foldable bike or criminality rates in a station.

Unrelated to the previous problems is that end users also still want answers to other questions without a route planning algorithm to be in place, such as getting a list of the next departures and arrivals at a certain stop, all stops a certain trip contains, or a list of all stops in the area.

Route planning algorithms

Only in the last decade, algorithms have been built specifically for public transit route planning [10]. Two models were commonly used to represent such a network: a time-expanded model and a time-dependent model [11]. In a time-expanded model, a large graph is modeled with arrivals and departures as the nodes, and edges to connect a departure and an arrival together. The weights on these edges are constant. In a time-dependent model, a smaller graph is modeled in which vertices are physical stops and edges are transit connections between them. The weights on these edges change as a function of time. On both models, Dijkstra and Dijkstra-based algorithms can be used to calculate routes [11].

Raptor [7] was the first base algorithm to disregard Dijkstra-like graph algorithms and instead exploit the basic elements of a public transit network. It does this by studying the routes within a network. In each round, it computes the earliest arrival time for journeys with a per round increasing number of transfers. It looks at each route in the network at most once per round. Using simple pruning rules and parallelization with multiple cores, the algorithm can be made even faster. It is currently the algorithm behind software like Open Trip Planner, or Bliksemlabs’ RRRR software.

Trip-based route planning [8] uses the same ideas as Raptor and works with an array of trips. In a preprocessing phase, it links trips together when there is a possibility to transfer at a certain stop. During query execution, it can take into account the data generated during the preprocessing phase.

Transfer Patterns [10] preprocesses a timetable such that at execution time, it is known which transfers can be used at a certain departure stop and departure time. The preprocessing requires by design more cpu time and memory than the preprocessing of trip-based route planning. Scalable Transfer Patterns [12] enhances these results by reducing both the necessary time and space consumption by an order of magnitude. Within companies that have processing power of idle machines to their disposal, the latter is a desired approach, which makes it the current algorithm behind the Google Maps public transit route planner according to its authors.

Finally, the Connection Scan Algorithm (csa) is an approach for planning that models the timetable data as a directed acyclic graph [9]. By topologically sorting the graph by departure time, the shortest path algorithm only needs to scan through connections within a limited time window. csa can be extended to solving problems where it also keeps the number of transfers limited, as well as calculating routes with uncertainty. The ideas behind csa can scale up to large networks by using multi-overlay networks [6].

It is a challenge to compare route planning algorithms as they are often built for answering slightly different questions and are executed on top of different data models. When studying the state of the art in order to find a suitable data publishing model, we were looking for the smallest building block needed for both preprocessors as actual query execution algorithms (with and without preprocessed data).

Exchanging route planning data over the Web

The General Transit Feed Specification (gtfs) is a framework for exchanging data from a public transit agency to third parties. gtfs, at the time of writing, is the de-facto standard for describing and exchanging of transit schedules. It describes the headers of several csv files combined in a zip-file. Through a calendar.txt file, you are able to specify on which days of the week a certain entry from service.txt is going to take place during a part of the year. In a calendar_dates.txt file, you are able to specify exceptions on these calendar.txt rules for example indicating holidays or extra service days. Using these two files, periodic schedules can be described. When an aperiodic schedule needs to be described, mostly only the calendar_dates.txt file is used to indicate when a certain service is running. A gtfs:Service contains all rules on which a gtfs:Trip is taking place, and a gtfs:Trip is a periodic repetition of a trip as defined earlier. Trips in gtfs contain multiple gtfs:StopTimes and/or gtfs:Frequencies. The former – mind the difference with a connection – describes a periodic arrival time and a departure time at one certain gtfs:Stop. The latter describes the frequency at which a gtfs:Trip passes by a certain stop. gtfs also describes the geographic shape of trips, fare zones, accessiblity, information about an agency, and so forth.

Other specifications exist, such as the European cen specification Transmodel, the Dutch specification bison, the Belgian specification bltac and the specification for describing real-time services The Service Interface for Real Time Information (siri). They each specify a serialization specific format for exchanging data, and some specify the questions that should be exposed by a server.

Up to date, route planning solutions exist as services, such as Navitia.io or Plannerstack, in end-user applications such as CityMapper, Ally or Google Maps, or as open source, such as Open Trip Planner or Bliksemlabs RRRR. Other common practices include that an agency, such as a railway company exposing a route planner over http themself. Each of these route planners however have the disadvantage that they do not allow querying with an open world assumption: each response is final and is not supposed to be combined with other response documents.

We have given uris to the terms in the gtfs specification through the Linked gtfs (base uri: http://vocab.gtfs.org/terms#) vocabulary. The definitions of the above terms can be looked up by replacing gtfs: by the base uri.

Conclusion

If we may conclude anything from our first proof of concept within the city of Ghent, it is that the field of transport data is not much different than Open Data in general. If we want automated reuse of datasets within route planners, we still need to get some minimum requirements accepted in the entire transport domain. These requirements are situated on the same interoperability levels those we were already discussing. We have done this for both datex2 as gtfs. For the domain specific parts, we also need to get more specifications to become Web specifications and define uris for their terms.

One challenge which we were able to overcome, is to publish real-time data over http. The approach was again not much different for static documents, only now we need to ensure the latency with the back-end system is minimized, while setting the right caching headers. Real-time data can be put in fragments as well, allowing multiple observations to be stored in a page. This can be annotated by using a named graph and the prov-o vocabulary. The dataset of parking lots, published as illustrated in Figure 1, is now available at https://linked.open.gent/parking.

Finally, today one can see clear evidence of the two extremes on the ldf axis – applied to route planning in Figure 2 – within public transit timetables. In the next chapter, we will explore different trade-offs on this axis.