Publishing public transport data on the Web with the Linked Connections framework

2.1.Public transport data models

TriMet (Portland, Oregon) became the first pt operator to integrate its schedules into Google Maps in 2005. This collaboration fostered the creation of the General Transit Feed Specification44 (gtfs), which at the time of writing, is regarded as the de facto standard for sharing pt data. gtfs defines the headers of 17 types of CSV files and a set of rules that describe how they relate to each other (see Fig. 1). The most important files within gtfs can be listed as follows:

Fig. 1.

The gtfs data model and its primary relations.

The European Committee for Standardization created the Transmodel55 standard and its implementation NeTEx,66 to provide a description of conceptual models that facilitate exchanging pt network infrastructure topology and timetable data, among others. NeTEx was selected by the European Union, for the provision of an EU-wide multimodal travel information service, where every member state will publish their pt-related datasets through a National Access Point (nap). The official list of naps can be found online,77 however to this date only a few member states shared their data in NeTEx format, which could be attributed to the difficulty for pt operators to express their networks information in a new format and data model. Recent work by Scrocca et al. [46] relies on semantic web technologies to ease the transition of EU operators towards NeTEx.

Efforts to semantically describe the different concepts, properties and relations defined by the aforementioned data models, were made for the case of gtfs with the Linked GTFS vocabulary88 and for Transmodel with the Transmodel Ontology [11]. A comprehensive survey on semantic data models and vocabularies for the transport domain was performed by Katsumi et al. [37]. This survey does not focus only on pt but also includes other related aspects such parking and road traffic. The existence of so many different pt data models, sheds light on the lack of interoperability of the pt domain, but it also shows the efforts being made both from industry and public authorities to converge on well defined standards. Given it is mainly focused on modeling the concepts around pt planned schedules and that most pt data is available as such, we reuse Linked GTFS terminology in our approach to semantically describe pt important concepts such as stops, trips and routes. However, we take a different approach to model the granular behavior of individual trips. We pair together departure and arrival events into connections, in contrast to Linked GTFS that describes these events individually as a gtfs:StopTime. The reason for this is to facilitate the interpretation of these events to clients when evaluating route planning queries. Further details of our modeling approach are shown in Section 3.

2.2.Public transport Web interfaces

Public transport data are often found on the Web as data dumps or through apis. Static data dumps contain extensive planned schedules, which scale proportionally to the size and complexity of the transport network [27]. Most currently available dumps on the Web follow the gtfs model.99

Public transport apis on the other hand, can be found online spanning a wide spectrum in terms of openness, features and data structures. From the paid Google Directions1010 and CityMapper1111 apis, going over the freemium Navitia.io1212 api, to the completely free and open source routing engine OpenTripPlanner.1313 pt data interfaces in the wild are mostly available for route planning use cases, each with their own set of features and ad-hoc data structures. Some undergoing efforts from MaaS communities are trying to define standard api interfaces (e.g. MaaS Global1414 or TOMP1515 APIs) to harmonize data access when building MaaS applications. However, despite their heterogeneity in terms of data structures and semantics, a common pattern on their architecture design can be seen across all available apis: the servers of api providers are responsible for handling all the computational processing burden when evaluating queries, leading in practice to feature and access-restricted apis. We propose an alternative approach where servers only are responsible of publishing self-descriptive and departure time-sorted fragments of planned schedules, through a uniform interface and data model. This approach delegates the processing of queries to the client, in a more computational load-balanced architectural setup, that ultimately lowers the costs for data publishers and brings more flexibility over the data to client applications.

2.3.Formal representation of public transport networks

Beyond the standards and interfaces used to describe and share pt data, is also important to consider the different formal representations that have been proposed to analyze and understand pt networks. Traditionally, pt networks have been defined through formalisms from graph theory and complex network science [9], with different levels of abstraction that include among others, undirected graphs [30,54], weighted and directed graphs [13,50], time-expanded graphs [28], and time-varying graphs [29]. Across formalisms, vertexes normally represent physical stations in the network, and edges may represent different things depending on what is intended by the topology analysis [38]. When starting from timetable (i.e., planned schedule) data, edges are usually defined to represent connections among stops. In other words, an edge is present when there is at least one vehicle that stops consecutively in two stations, when following a predetermined route [22,47,48,57].

Different metrics have been proposed to analyze and obtain insights of pt networks. General graph theory-based metrics such as average degree [26], graph density [54], clustering coefficient [50], and also pt domain-specific metrics such as average connection duration [28] or directness of service [23] have been used to derive conclusions on the behavior of pt networks. For example, higher degree networks are typically associated with higher levels of network reliability [54], and higher clustering coefficients reflect higher accessibility among stations [40]. Hong et al. [35] present a compilation of studies that apply complex network metrics over different pt networks. However, even though graph metrics have been correlated to process performance in different application domains, for example to assess data quality change on dynamic knowledge graphs [31], to the best of our knowledge there are no studies that investigate potential relations of network graph characteristics and route planning query performance. We perform an evaluation in this direction and analyze how specific pt network graphs characteristics may influence route planning performance.

2.4.Route planning algorithms

From a traveler’s perspective, route planning is the most popular use case over pt data and thus has been extensively studied throughout the years. Bast et al. [3] and Pajor [42] present a comparative analysis of multiple route planning algorithms over pt networks, road networks and combination thereof. Most pt algorithms are defined as extensions of Dijkstra’s algorithm [25] using graph-based formalizations such as time-dependent [10] and time-expanded [43] graphs to model networks. Other alternative approaches such as raptor [19], csa [24], Transfer Patterns [4] and Trip-based routing [58] exploit the basic elements of pt networks to calculate routes directly on the planned schedules.

A pt route planning query can be further specified into more concrete problems depending on the concrete use case. The literature defines different types of route planning query problems, usually defined in terms of Pareto-optimizations, that require specific algorithm implementations with varying levels of complexity [20,24]. The simplest and most common one is the Earliest Arrival Time problem, where given an origin, destination and a departure time τ, an algorithm should render a journey departing no earlier than τ and arriving as soon as possible. Other common problems include the Profile problem variants, to calculate the set of possible journeys within a time range or the Multi-Criteria problem for considering additional optimization criteria over the resulting Pareto set (e.g., maximum number of transfers or transport modes).

Each algorithm requires specific data structures and indexes in order to find possible routes over pt schedules. The time-based sorted structure of our publishing approach fits the requirements for executing route planning algorithms based on the Connection Scan Algorithm (csa). In our evaluation, we take an implementation of csa to a client-side application and use it to evaluate Earliest Arrival Time queries.

2.5.Live and historical data on the Web

Live data is critical for supporting practical use cases that are useful in real scenarios. It is particularly important for pt route planning given that in practice, schedules change due to unforeseen delays and cancellations, which could render calculated routes unfeasible. gtfs-realtime1616 and siri,1717 are among the main reference standards for live schedule updates and vehicle positions. Both define protocols to exchange live updates for planned schedules, modeled using gtfs and Transmodel standards respectively. Most currently available pt live data on the Web use the gtfs-realtime standard [1].

In the same way, historical data is fundamental for some use cases in the pt domain. Machine learning-based algorithms require training data that closely reflect reality to make predictions on a certain scenario [33]. pt operators require to perform statistical analyses based on accurate data of past events to asses the performance of their networks [5]. Such data may already exist within operators information systems, but unfortunately is not commonly made public for third party reuse. The unavailability of public historical data may be motivated by operators strategic business choices or simply by the inherent costs of maintaining a dedicated public API for this purpose. Either way limiting the development of novel use cases. An example of public historical information can be found by accessing the Belgian trains delays and disruptions site1818 through the wayback machine service of the Internet Archive initiative. However besides not being machine readable data, this does not constitute a reliable source as snapshots are not consistently archived.

In an effort to standardize the way historical information is accessed on the Web the ietf published the RFC 7089,1919 also known as the Memento framework [51]. Memento defines a protocol over http to perform time-based content negotiation of Web resources among clients and servers. The latest version of a resource is defined as the original resource uri-r. Previous versions of uri-r are defined as Mementos uri-m_i with i=1,…,n and can be accessed by negotiating with a Time Gate uri-g.

The idea of accessing and querying historical versions of data through time-based content negotiation, has been already explored by Taelman et al. for the case of time-annotated knowledge graphs [53]. In our approach we apply this principle to provide access to the history of changes of pt network schedules, which are also represented as knowledge graphs in the form of rdf. In this way we bring together both (versions of) planned and live update data, which can be queried in a cost efficient way. Design and implementation details are presented in the next section.

Fig. 2.

Depiction of chronologically ordered linked data documents containing lc (represented by the blue blocks). Each document contains links (hydra:next labeled links) to the previous and next document in the collection, that can be traversed by clients to found routes across the pt network. The green blocks represent the departure and arrival connections of an hypothetical route planning query and the thinner links comprise the route solution that will be computed by scanning the collection.

3.1.Linked Connections specification

We created a specification that describes the different requirements to implement a lc data publishing interface and a set of considerations for client applications implementing route planning solutions.

lc uses Connections as the fundamental building block of pt data. A connection describes a departure-arrival event between given two stops, that occurs at a certain point in time and without intermediary halts. In other words, a connection must contain the definition of at least a departure stop, an arrival stop, departure time and an arrival time. Additionally, a connection is related to a specific trip. This is important for client applications to interpret sets of connections as part of independent trips during route plan calculations.

We define connections as rdf graphs, following the Linked Data principles. lc data interfaces should therefore publish data, in at least one of the rdf compliant serializations (e.g., turtle, JSON-LD, N-Triples, etc). Connections are described by means of the linked connections ontology and also with terms from the Linked GTFS vocabulary. The main concepts to semantically model and represent connections are the lc:Connection rdf class, together with the predicates that reference departing and arrival stops and times. Table 1 describes these terms and Listing 1 shows an example of a lc using the JSON-LD serialization.

Listing 1.

LC formatted in JSON-LD. The properties departureDelay and arrivalDelay indicate that live data is available for this Connection

Listing 2.

Hydra search form defining a uri template for accessing lc documents with connections departing no earlier than the requested time. It explicitly defines how clients can request specific documents and the variables they are allowed to use. In this case the only variable is the departureTime

A lc data interface publishes pt network schedules as a chronologically ordered paged collection of connections over http. This particular design is motivated to support the execution of csa-based algorithm implementations on the client side. The reason for choosing csa as the main supported route planning algorithm is related to the relative simplicity of publishing csa’s required data structure, namely a chronologically ordered collection of lc:Connections, compared to more complex structures and set of indexes required by other state of the art route planning algorithms. The semantic definitions provided by Linked Connections could still be reused to publish the same data, organized in different structures, to enable clients performing other algorithms. For example, by exposing the ordered set of lc:Connection’s per gtfs:Trip, a client could independently implement the raptor algorithm.

Each lc document should be served with the appropriate headers to enable both server and client-side caching. High cacheability of data is one of the biggest advantages of the lc approach, in terms of cost-efficiency and scalability for data publishing interfaces. Document responses require also to enable cors (Cross-Origin Resource Sharing), given that data will be accessed by clients from multiple origins. Furthermore, lc defines semantically annotated hypermedia controls as part of every document’s metadata. The purpose is to allow clients to discover and automatically navigate the pt schedules. The hypermedia controls are defined using the Hydra vocabulary,2121 including the following terms:

Fig. 3.

Reference architecture for lc-based systems.

3.2.Linked Connections reference architecture

A lc system’s main purpose is to publish pt schedules as a chronologically ordered collection of vehicle departures over http, while taking into account live updates to the original schedules and keeping historical data available for later querying. To this end we define a reference architecture (see Fig. 3) with three main modules that generate, store and serve lc. We also provide a complete and open-source reference implementation of this architecture as a Node.js application.2222

LC Generator This module is responsible for creating lc. It takes gtfs (planned schedules) and gtfs-realtime (live updates) data sources as input, given that most pt data is available in these formats. We provide implementations for both modules through the gtfs2lc2323 and gtfsrt2lc2424 Node.js libraries. However, thanks to the modular nature of the architecture, it is possible to replace these modules with any other interfaces capable of creating lc from different data sources (e.g., Transmodel, apis, etc). One of the most important aspects that need to be considered when creating lc is the provision of a stable identification (uri) strategy that remains valid across versions of the data sources. We make possible to define such strategy using uri templates as defined by the RFC 6570 specification.2525

Data Storage The output of LC Generator is received by this module, which proceeds to fragment and store the data according to a given fragment size. Static lc (i.e. data coming from a planned schedules) are stored as individual files that correspond to the documents of the time-ordered lc collection. Additionally, files containing the set of stops and routes of the pt network are kept to be served as static documents too, since they are usually needed by route planning applications. Live updates are also stored as files following a log-like approach, where delays, ahead of time and cancellation reports for every single connection are written down. Files in both cases are named using the first departure datetime they contain to facilitate later connection lookups.

Web Server This module defines the interfaces through which lc and other related pt data may be accessed by client applications. The http interfaces supported by the lc Web server are as follows:

The Web Server module also contains submodules responsible for resolving lc documents requests in an efficient way. Particularly the architecture defines three specific submodules for supporting requests that include live data, historical data and also static data. The live data manager submodule takes care of serving lc documents that include the latest connection updates. A detailed reference implementation of this submodule is presented later in Section 3.3. In the same way, the historical data manager handles serving previous versions of lc documents through http time-based content negotiation using the Memento protocol. A reference implementation is detailed in Section 3.4. Lastly, the static data manager handles requests for static resources, namely stops, routes and the server’s dcat metadata.

3.3.Serving live Linked Connections

Managing and serving live schedules updates, without sacrificing the cost-efficiency of the data publishing interface, constitutes one of our main contributions in this paper. In previous work we studied pushing (server-sent events) and polling (http) interfaces to exchange live pt data with client applications and keep route planning results updated in a cost-efficient way. We found that a polling approach consumes less resources on the data publishing side and clients only experience a slightly higher bandwidth consumption, compared to a pushing approach [44]. However, our implementation for serving live lc was done in a naive way. We merged scheduled lc documents with their latest updates on request time, with significant negative impact on response times.

We introduce a more elaborated approach to reduce response times of lc document requests without compromising cost-efficiency. The set of departure time-sorted Linked Connections C=[c0,c1,…,cn] where dtk is the departure time of ck and dtk⩽dtk+1, is modeled as an AVL tree [49] (see Fig. 4). AVL trees are self-balancing binary search trees, where at any time, the height difference between two child subtrees of any node is not bigger than 1. Insert and delete operations are performed in logarithmic time and the strict balancing ensures consistent response times on data lookups. We implemented an AVL tree in our lc architecture represented by the live data manager submodule in Fig. 3. The tree creates a time window view over the lc collection, spanning from the current time until a configurable time in the future. This time window is periodically adjusted by shifting forward in time, based on the assumption that most route planning queries will request future routes and also to avoid unnecessary memory consumption by keeping old connections. In practice, the tree is built by loading in memory scheduled lc documents, starting from the one that contains connections departing on the current time and periodically rebuilding the tree to shift forward the time window. However, data outside the time window can still be provided by merging scheduled documents and their updates on request time. The AVL tree data structure is updated accordingly (i.e. adding, removing and reorganizing connections) upon reception of schedule update reports. This allows for fast lc document responses containing the latest schedules updates. Figure 4 shows an example of an AVL tree of lc and how the tree is adjusted when a connection is reported to have departure delay.

Fig. 4.

Depiction of the lc AVL tree reacting to a schedule update. In this example, c2’s departure time is dtk+2 at ti. A moment later at ti+1, c2’s departure time is reported to be increased by a delay δ, making c2’s departure time to be later in time than c3’s departure time. This schedule update triggers a reorganization of the AVL tree to maintain the chronological ordering of the collection.

The AVL tree is initially generated by scanning over the scheduled lc, kept by the Data Storage module on server boot time. Once created, the live update logs are constantly monitored and trigger tree reorganizations when new reports are received.

3.4.Serving historical Linked Connections

Another important contribution of this paper, is providing the ability for serving historical lc data. We allow querying not only for past planned schedules but also for historical live data reports. This means it is possible to obtain the actual vehicle departures as they were reported at different points in time. For example, we could request for the departures of yesterday at 08:00 h as they were expected to be yesterday at 07:00 h and also later at 07:50 h, seeing possibly that a connection that was on time at 07:00 h was later reported to be delayed at 07:50 h. In this way is possible to reproduce the stream of events of a pt network at a granularity given by the frequency of live update reports. Access to this data could support analytical studies to better understand the behavior of pt networks and also other use cases that rely on historical information of trips to provide recommendations to travelers [12].

We make this possible through the http Memento protocol. Given the document-based nature of lc, it is possible to request past versions of a specific document, as it was at a certain point in time. Memento defines different patterns to perform time-based content negotiation. We implemented pattern 1.1 where uri-r = uri-g and 302-style negotiation is performed. This means that the original resource acts as its own time gate and clients receive a 302 http response containing a Location header with the uri of the Memento. An example get request is shown in Listing 3, asking for connections departing from 08:00 h as they were reported at 07:35 h. The specific version time is given through the Accept-Datetime header, as defined by the Memento protocol.

Performing these kind of queries is possible thanks to the way lc are stored in the Data Storage module, as separate sets for both scheduled and live update data. When a Memento request is received, the system gets first the lc fragment containing the originally scheduled connections. This first step may seem trivial but is necessary to consider that there may be multiple versions of overlapping planned schedules. Therefore, the system needs to select the version issued closest to the specified Accept-Datetime date, before integrating live reports. Then the system goes over the live update logs for this specific lc document, retrieving and merging all the updates received up until the Accept-Datetime date. As mentioned in Section 3.3 this could be considered as a naive approach which may increase response times of individual lc fragments. However we part from the assumption that historical data queries are not as performance-critical as live data queries for route planning purposes, and can still be resolved within reasonable time following this approach.

Listing 3.

Hydra uri template for accessing lc documents containing connections with departure times equal or bigger than the requested time

3.5.Linked Connections client

The chronological ordered collection of connections defined by a lc system, is a fitting data structure to perform the Connection Scan Algorithm (csa), proposed by Dibbelt et al. [24]. Given a departure stop, arrival stop and departure time, csa will go over the collection of connections, progressively building a minimum spanning tree of reachable destinations. The algorithm performs this process until it reaches the desired arrival stop, rendering in this way, the earliest arrival journey possible (if any). This provides a solution for the Earliest Arrival Time problem. In the case of lc, a client performing the csa algorithm can scan through the collection of connections by downloading lc documents and following the defined hypermedia controls to traverse it. We provide an implementation of csa on the Planner.js JavaScript library,2626 which can be used both on server (Node.js) and client-side applications.

5.1.Preliminaries

We ran the experiments on one machine acting as server and one or more machines acting as clients. All machines had identical characteristics: 2x Quad core Intel E5520 (2.2 GHz) CPU with 16 threads and 12GB of RAM.

One important variable to consider, is the latency of the network. Given that we measure query response times, which largely depend on the amount of required http request-response cycles, network latencies may have a significant impact in particular for smaller fragmentation sizes, for which large number of requests are usually needed. However, latency in real scenarios is highly heterogeneous and depends on multiple factors (e.g., geographical location, network traffic and bandwidth) [6], making it difficult to predict reference values for it. Therefore, we perform our evaluations in a local network to eliminate the influence of variable latencies on the results. We deem out of scope for this paper, investigating how latencies may impact measured optimal fragment sizes. Our results may be considered as a reference point that could be adjusted when expected latencies are known in advance. For reproducibility and transparency, we made available the original data sources, query sets, tools and obtained results of these evaluations.2727

Two main tasks were completed before running the experiments, namely generating multiple fragmentation sets with varying size and producing a route planning query set for each considered pt network. We describe next how were these tasks completed.

5.1.2.Route planning queries

Performance of route planning query evaluation not only depends on how the data is structured and published but also on the type of queries that need to be processed. The literature defines different classes of problems for the route planning use case that involve a varying number of variables. To minimize the number of variables that may influence our performance measures, we selected the simplest type of problem, namely the Earliest Arrival Time (eat) problem. We focused our evaluations on this particular problem only, considering that in the literature, more complex route planning scenarios are often addressed as extensions of the eat problem. Therefore optimizing our approach to handle eat queries would consequently improve also the performance of more complex route planning query processing over lc interfaces. The goal in the eat case, is to find the journey with the shortest travel duration between origin and destination, given a minimum departure time. Processing of these queries focuses only on optimizing the arrival time, disregarding other common variables such as maximum number of transfers or transportation modes.

In our test case, transfers are possible but constrained only to a maximum walking time of 10 minutes at an average speed of 3 km/h (500 meters). Transfers are computed on the fly using the Haversine formula2929 and are modeled as additional connections. We assumed a restricted walking scenario based on a realistic heuristic to avoid the complexity of unrestricted walking calculations having an influence in the results. eat queries can be processed easily over lc interfaces via the csa algorithm. The algorithm can perform a single scan over the lc collection until it finds a complete journey (if any), which is guaranteed to be the earliest arrival thanks to the chronological ordering of the lc collection.

Query selection for each pt network in our evaluation was performed at random, for origin-destination stop pairs at any time of the day. We randomly generated 100 (solvable) queries for each network. We counted the number of connections that csa had to process to evaluate each individual query and called this the number of Scanned Connections needed by the Query (scq). The counting was done within csa’s execution loop to avoid fragment sizes having an influence on the count. E(SCQ) then denotes the expected value or average, of the number of connections for the query set and its standard deviation is denoted by σ. Both metrics not only provide insights on the query set, but also on the network itself. For example, lower values of E(SCQ) could mean the presence of shorter eat route queries, i.e., csa needs to scan only a few connections to evaluate the queries. It could be also an indication of fewer simultaneous trips in the network, which allows csa to find a route without having to scan many connections from other irrelevant trips that happen elsewhere on the network at the same time.

Table 3

Average number of connections (E(SCQ)) scanned to process the randomized query set of each pt network and its standard deviation (σ). The barchart is a representation of the density distribution of SCQ. On the X axis we have 10th, 20th, 30th, etc percentiles with respect to the highest SCQ of the query set. For example, if the highest SCQ of the query set is 1000 connections the 10th percentile is 100 connections, the 20th percentile is 200 connections, etc. On the Y axis we show the percentage of queries in the set that belong to each percentile

Table 3 shows a summary of E(SCQ), σ and a visualization of the scq distribution in the form of a bar chart for each query set. The values of E(SCQ) show that the lowest value belongs to Netherlands-Waterbus with an average of 120 connections per query, and the highest to Flanders-De Lijn with an average of 322,000 connections per query. These values are aligned with Netherlands-Waterbus being one of the smallest and Flanders-De Lijn being one of the biggest networks in terms of both stops and connections (see Table 2). σ and the distribution reflect the random nature of the query sets. We see the tendency of having more balanced query sets when σ is closer to E(SCQ)/2.

5.2.Experiment 1: Optimal lc fragmentation size

In this first experiment we deployed an instance of the lc Server3030 in one of our test machines. We configured it to publish the planned schedules of every pt network, using the predefined fragmentation sizes. We enabled only one network with one fragmentation at a time. For the client we deployed in a different test machine, one instance of Planner.js3131 and configure it to replay (3 times) each respective query set against the lc Server instance. We registered the average query response time of Planner.js for every pt network, using each predefined fragmentation size.

5.3.Experiment 2: Correlation of graph metrics and query performance

To analyze the potential correlations between the intrinsic graph characteristic of each pt network and their route planning query performance, we first measured the defined set of graph metrics (Section 4) for each of the considered pt networks. The calculation of the metrics was performed over the TVG derived from the connections belonging to the busiest day of each network (see the results in Table 2). We relied on the graphology3232 JavaScript library and in our own implementation3333 to calculate the metrics. For the route planning query performance, we took the best average query response time of each pt network, measured during Experiment 1 (see Section 5.2).

The correlation analysis was made by calculating the Pearson Correlation Coefficient (r), Covariance (cov) and Coefficient of Determination (R2) of every considered graph metric vs the average query response time of the best fragmentation of each pt network. We also visualized a linear regression model including the 95% confidence interval for each pair of variables. We used NumPy3434 and Seaborn3535 Python libraries for the statistical calculations.

5.4.Experiment 3: Cost-efficiency of the lc approach

For measuring the relative cost-efficiency of our approach, we performed two main evaluations: (i) lc Server vs OpenTripPlanner with planned schedules; and (ii) lc Server with live and historical schedules vs lc Server with planned schedules only. We were not able to directly compare our approach with OpenTripPlanner handling live and historical data because OpenTripPlanner does not support route planning querying based on historical data (e.g., calculate a route from A to B considering the schedule reports of 30 minutes ago is not supported). In the case of live data, we had access to the gtfs-realtime stream containing live schedule updates from the Belgium-NMBS pt network, but OpenTripPlanner failed to integrate this data source with errors regarding the integrity of the data. Next we describe these two experimental setups.

6.1.Experiment 1: Optimal lc fragmentation size

Figure 6 presents an overview of the results obtained from the route planning performance evaluation, over different sets of lc data fragmentation.

Fig. 6.

Average response time of route planning queries (ms) vs fragment sizes (connections) for each pt network. pt networks with similar total number of connections (see Table 2) are grouped together to facilitate visualizing the results. We labeled the lowest point of each curve where best performance is achieved. Axes use logarithmic scales.

The top left plot in Fig. 6, shows the results for the three smallest networks in terms of total connections (<1,100). Fragmentation was only possible until 500 connections/fragment for Netherlands-Waterbus and Sydney-Trainlink, and until 1,000 connections/fragment for Thailand-Greenbus. Bigger fragmentation for these networks would mean that the entire collection of connections would fit in only one fragment. Netherlands-Waterbus shows its best performance (27 ms) with a fragmentation of 100 connections/fragment. Sydney-Trainlink’s best performance (45.81 ms) was achieved with 500 connections/fragment, while Thailand-Greenbus (36.27 ms) was achieved at 1000 connections/fragment. Netherlands-Waterbus shows faster query responses compared to both Sydney-Trainlink and Thailand-Greenbus, which may be explained by the higher number of connections per query (E(SCQ)) that these networks require to be processed (Table 3). For Netherlands-Waterbus we see that 100 connections/fragment appears to be its optimal fragment size, with smaller and bigger fragments rendering worse performance. In the cases of Sydney-Trainlink and Thailand-Greenbus, the biggest possible fragment for this evaluation (which considers only the network’s busiest day) renders the best performance. Bigger fragmentation would be possible when considering the full schedule spanning over multiple days. However, assuming that most queries would be solved within the span of a single day, we could expect that bigger fragments would render worse performance for these networks.

The top right plot in Fig. 6, brings together 6 different networks with total amounts of connections ranging between 5,000 and 8,000. Optimal fragmentation values are different for each network, except for Auckland-Waiheke and San Francisco-BART both with 100 connections/fragment. Despite having the same optimal point and similar amout of connections, they show a significant difference in terms of response time, with 283.67 and 49.84 ms respectively. Referring to Table 2, we can see that both networks differ significantly for K and D: San Francisco-BART(K=9.28 and D∗1000=63.14) and Auckland-Waiheke (K=0.15 and D∗1000=0.41). Where San Francisco-BART has much higher values. San Francisco-BART has also 3 times more trips but less than half of the stops than Auckland-Waiheke. In general we observe the trend of degraded performance as fragmentation moves away from the found optimal point, but with varying degrees of degradation. For example in the case of Nairobi-SACCO where almost no degradation is perceived and for Spain-RENFE with its best performance (154.23 ms) at the biggest fragmentation possible.

In the bottom left plot of Fig. 6, we have a set of 8 pt networks with total amounts of connections ranging between 51,000 and 350,000. Most networks show an optimal fragmentation of 500 and 1,000 connections/fragment, with the exceptions of Brussels-STIB and EU-Flixbus with 300 and 3,000 connections/fragment respectively. New Zealand-Bus shows significanlty worse performance than the rest of the networks, followed by New York-MTABC and Brussels-STIB. Comparing them to the more performant Belgium-NMBS and London-Tube we can see that the less performant networks have higher amount of stops and a lower values for K and D.

Lastly, on the bottom right plot in Fig. 6 we see the results for the remaining 5 networks. These are the biggest networks in the set with total number of connections ranging from 689,000 to 1.2 million. In this case we see a generally degraded performance for all networks. Only Madrid-CRTM and Chicago-CTA show an optimal fragmentation point on 1000 and 300 connections/fragment respectively. The rest of the networks show their best performance with their smallest fragmentation possible which only degrades further with bigger fragments.

Fig. 7.

Measured average response time in milliseconds for the fragmentation that rendered the best performance for each pt network. X-axis uses a logarithmic scale.

In Fig. 7 we present the average query response times, measured using the optimal fragmentation found for each network (as seen on Fig. 6). An annotation can be seen next to every network’s bar indicating the average time (in ms) needed to answer the queries of the query sets. At first glance we can see that bigger networks in terms of total number conenctions and stops are less performant. However, London-Tube and New Zealand-Bus stand as execptions on both sides of the spectrum for this trend. London-Tube is a relatively big network (321,000 connections) with subsecond performance and New Zealand-Bus is a medium size network (153,000 connections) with much worse performance (16.3 s) compared to networks of similar size.

6.2.Experiment 2: Correlation of graph metrics and query performance

Results on how the different graph network metrics relate with route planning query performance can be seen on Fig. 8. Correlation measures (Pearson Coefficient,3939 Covariance4040 and Coefficient of Determination4141) of each metric are also shown in Table 4.

Fig. 8.

pt network metrics compared with route plannning query performance. Each sub-graph compares one of the metrics to the best query evaluation performance measured for each network (see Fig. 7.) Axes are set in logarithmic scale.

The correlation measures (Table 4) related to number of stops (|V|), show a strong and direct correlation with query response time, which is also evident in Fig. 8 (upper left). This means that networks with higher amounts of stops, render higher query response times. A similar strong and direct correlation can be observed for number of connections (upper right in Fig. 8). More connections also means worse performance with a few outlier exceptions. London-Tube (n9) and to a lesser extent Belgium-NMBS (n8), show better performance than other networks with similar or even less amount of connections. The opposite behavior is seen on both Nairobi-SACCO (n10) and New Zealand-Bus (n18) with significant worse performance compared with their peers.

Weak and inverse correlations can be observed for both D (center right) and ACD (lower right). Networks with lower values of D∗1000 (<1) show worse query performance, with the exceptions of Sydney-Trainlink (n2) and Auckland-Waiheke (n7). In the case of ACD, networks with the worst performance (> 10 s) always show relatively low ACD (<3 min). The opposite can also be seen, where most networks with high ACD (> 10 min) show subsecond performance with the exceptions of EU-Flixbus (n11) and France-SNCF (n12) with close performance values of 2.2 s each.

Lastly, no correlation can be seen for the cases of K and C, both with Pearson coefficients close to zero and showing high disperssion for query performance.

6.3.Experiment 3: Cost-efficiency of the lc approach

Next we present the results of our two experimental setups for measuring the cost-efficiency of our solution.

6.3.1.lc vs OpenTripPlanner

In Fig. 9 we present the server-side CPU and RAM use for both OpenTripPlanner and the lc Server, while supporting route planning query solving for an increasing amount of concurrent clients. We can see that CPU use for OpenTripPlanner increases proportionally to the number of clients and is also related to the size of the networks (in terms of stops), with bigger networks consuming more processing capacity. The lc Server presents a stable CPU consumption as the number of clients increases, with all networks requiring around 20% of the processor capacity.

In the case of RAM consumption, both OpenTripPlanner and the lc Server remain constant for all networks regardless of the amount of concurrent clients. For all networks, the lc Server does not exceed 10% of RAM use, while OpenTripPlanner reaches up to 70%. In general, the lc Server consumes less CPU and RAM resources and shows a better scalability than OpenTripPlanner.

Fig. 9.

CPU (left column) and RAM (right column) usage under an increasing amount of concurrent clients of OpenTripPlanner and the lc Server for 16 different pt networks. Each row groups 4 networks of similar amount of stops, with smaller networks at the top and bigger networks at the bottom. Dotted lines represent measurements for OpenTripPlanner and continous lines represent measurements for the lc Server.

Figure 10 presents the obtained results on average query response time for both OpenTripPlanner and the lc Server. The average query response time increases proportionally to the number of concurrent clients for OpenTripPlanner, which reflects the behaviour observed in Fig. 9 regarding CPU use. Response times over the lc Server are also aligned to its CPU use and remain relatively stable when the number of clients increases. In terms of absolute numbers, the lc Server completely outperforms OpenTripPlanner for the smallest pt networks of the set (first row) and San Francisco-BART (second row). In contrast, OpenTripPlanner significantly outperforms the lc Server for the biggest networks (last row), although response times become similar with 20 and 50 concurrent clients. In the case of middle size pt networks, OpenTripPlanner shows better perfomance for low amount of concurrent clients (<10). However, the lc Server shows similar or in some cases better performance for higher amount of concurrent clients (⩾10), as is the case of Belgium-NMBS, Amsterdam-GVB, London-Tube, Brussels-STIB and New York-MTABC.

Fig. 10.

Average route planning query response times for OpenTripPlanner (left column) and the lc Server (right colum) with an increasing amount of concurrent clients. Each row groups 4 networks of similar amount of stops, with smaller networks at the top and bigger networks at the bottom.

6.3.2.Live and historical data with lc

Figure 11 presents the CPU (left) and RAM (center) use, and the average response time of route planning queries (right) of the lc Server when publishing planned schedules only, live schedules updates and historical schedules. In terms of CPU consumptions we see similar behavior for all configurations ranging between 5–38% and having the live updates setup as the most demanding one. RAM consumption remains stable as the number of clients increases and has the historical setup as the most demanding with 4%. In terms of query response times, both planned only and live updates configuration perform similarly. Query response times over historical data on the other hand, show a significant performance degradation, being 50 times slower.

Fig. 11.

On the left plot is the CPU usage of the lc Server publishing planned only, live updates and historical pt schedules under an increasing amount of concurrent clients. The center plot shows the RAM use for each publishing configuration. The left plot shows the average route planning query response times for each publishing setup of the lc Server.

7.1.Optimal lc fragmentaion size

Our evaluation showed that for each pt network the best performance is achieved with a certain fragmentation size. This constitutes an important finding for data publishers that may be considered when designing pt data apis. Results also showed that for most networks, either increasing or decreasing the fragmentation size, degrades performance of route planning query evaluation. Smaller fragmentation than the optimal point, degraded performance due to the higher number of http request-response cycles needed with smaller fragments. Larger fragment sizes require clients to perform fewer cycles but need to process increased number of irrelevant connections for each query. Exceptions occured on some of the smallest networks having their optimal fragmentation at the biggest possible size, and for some of the biggest networks having their optimal fragmentation at the smallest possible size. One particular case can be observed for Spain-RENFE, a medium size network (in terms of stops) whose optimal fragment size was found on its biggest fragmentation possible (5000 connections/fragment). Such behavior of Spain-RENFE may be explained by a high value of E(SCQ) (4100) with respect to the total number of connections (6159). This means that with a fragment size of 5000 connections/fragmentation most queries would be solved with only one fragment request and smaller fragmentation would always require more http requests.

Another important finding of this evaluation is the fact that for several networks, this approach results impractical for real scenarios. Response times on the order of seconds and even tens of seconds per query are unacceptable for user-oriented applications. However is important to mention that for this particular evaluation we did not use any form of caching (server nor client-side), which is one of the fundamental features of publishing pattern-based fragmented datasets. Our goal was to study the impact that data fragmentation has on query performance. Different fragmentation setups influence the effort that server-side data interfaces make to respond to data fragment requests, as well as the effort made by client-side route planners for evaluating queries. We wanted to quantify these efforts and both server and client-side caches would have hidden the effect of any fragmentation. A server-side cache frees the data interface of having to retrieve, parse and format data fragments more than once across queries, while a client-side cache makes unecessary to request data fragments fetched on previous queries. Therefore, the results of this evauation may be considered as worst-case scenario values and it could be expected that in practice query response times will be improved.

7.2.Correlation of graph metrics and query performance

When looking at the topological properties of every pt network and the calculated correlation indicators (Table 4), we observe the existence of a strong and direct correlation between the size of the network, both in terms of stops and connections and the query response time. This is not a surprising result since is expected that in the presence of more connections, route planning algorithms would need to process more data during query evaluations. Yet, it is interesting to look into individual cases that differ significantly (for better or worse) in query evaluation performace, compared to networks of similar characteristics. Examples of this atypical behavior in the case of total number of connections are London-Tube or Belgium-NMBS for better performance and Nairobi-SACCO or New Zealand-Bus for worse performance.

Weak and inverse correlations are observed for the cases of density (D) and average connection duration (ACD) with respect to query response times. Most networks with high values of ACD show lower response times compared with networks with lower ACD. An explanation for this behavior could be given from the fact that lower connection duration is usually a reflection of more closely located stops, as it is for urban networks. This causes an extra processing load during the algorithm execution, that needs to calculate more walking transfer connections for each nearby stop and include them as the potential alternatives for route solutions. London-Tube stands as an exception to this pattern. The reason for this is that this network groups multiple passanger boarding platforms as single stops, which facilitates transfer calculations for the algorithm and also serves as an explanation of the high values measured on all metrics for this network.

Lastly, we observe no correlation for the cases of average degree (K) and clustering coefficient (C), both with Pearson’s coefficients close to zero, which suggests that these properties do not influence route planning performance.

7.3.Cost-efficiency of the lc approach

We considered OpenTripPlanner as a traditional route planning reference solution, to compare against our proposed approach. However, as remarked in Section 5.4, we were not able to compare against OpenTripPlanner considering live and historical data. Thus, we performed the comparison with OpenTripPlanner with planned schedules only and for live and historical data, we measured the added costs of our proposed extensions to the lc approach.