An isochrone in a spatial network is the minimal, possibly disconnected subgraph that covers all locations from where a query point is reachable within a given time span and by a given arrival time [5]. A novel approach for computing isochrones in multimodal spatial networks is presented in this paper. The basic idea of this incremental calculation is to reuse already computed isochrones when a new request with the same query point is sent, but with di erent duration. Some of the major challenges of the new calculation attempt are described and solutions to the most problematic ones are outlined on basis of the already established MINE and MINEX algorithms. The development of the incremental calculation is done by using six di erent cases of computation. Three of them apply to the MINEX algorithm, which uses a vertex expiration mechanism, and three cases to MINE without vertex expiration. Possible evaluations are also suggested to ensure the correctness of the incremental calculation. In the end some further tasks for future research are outlined.
H.2.8 [Database Applications]: Spatial databases and GIS
isochrone, incremental calculation
Throughout the past years interactive online maps have become a famous tool for planning routes of any kind. Nowadays everybody with access to the internet is able to easily get support when travelling from a given point to a speci c target. The websites enabling such a navigation usually calculate routes using e cient shortest path (SP) algorithms. One of the most famous examples of these tools is Google's map service named GoogleMaps1. For a long time it was possible to calculate routes using one transportation system (by car, by train or by bus) only. This is known as routing within unimodal spatial networks. Recent developments enabled the computation combining various transportation systems within the same route, even if some systems are bound to schedules. This has become popular under the term \multimodal routing" (or routing in multimodal spatial networks).
Less famous, but algorithmic very interesting, is to nd
the answer to the question where someone can travel to in
a given amount of time starting at a certain time from a
given place. The result is known as isochrone. Within
multimodal spatial networks it has been de ned by Gamper et
al. [
One major advantage of isochrones is that they can be
used for reachability analyses of any kind. They are
helpful in various elds including city planning and emergency
management. While some providers, like SimpleFleet and
Mapni cent, enable the computation of isochrones based on
pre-calculated information or with heuristic data, the
calculation of isochrones is a non-trivial and time-intense task.
Although some improvements to the algorithms that can be
used for isochrone computation have been published at the
Free University of Bozen-Bolzano in [
This paper presents the calculation of incremental isochrones in multimodal spatial networks on top of already developed algorithms and cached results. It illustrates some ideas that need to be addressed when extending the algorithms by the incremental calculation approach. The remainder of this paper is structured as follows. Section 2 includes related work. Section 3 is split into three parts: the rst part describes challenges that will have to be faced during the implementation of incremental isochrones. Possible solutions to the outlined problems are also discussed shortly here. The second part deals with di erent cases that are regarded during computation and how these cases di er, while the third part points out some evaluations and tests that will have to be performed to ensure the correctness of the implementation. Section 4 consists of a conclusion and lists some possible future work.
The calculation of isochrones in multimodal spatial
networks can be done using various algorithms. The method
introduced by Bauer et. al [
There are some more routing algorithms that do not load
the entire network into the main memory. One well-known,
which is not speci c for isochrone calculation, but for query
processing in spatial networks in general, called Incremental
Euclidean Restriction (IER), has been introduced by
Papadias [
In 2013 similar ideas have been applied to MINEX and
resulted in an algorithm called Multimodal Range Network
Expansion (MRNEX). It has been developed at the Free
University of Bozen-Bolzano by Innerebner [
Recently the term \Optimal location queries" has been
proposed by some researches like Chen et al. [
In this paper the MINE and MINEX algorithms are extended by a new idea that is de ned as \incremental calculation". This allows the creation of new results based on already computed and cached isochrones with di erent durations, but with the same query point q (de ned as baseisochrones). This type of computation is complex, since it is not su cient to extend an isochrone from its border points. In theory it is necessary to re-calculate the isochrone from every node in the spatial network that is part of the baseisochrone and connected to other nodes. Although this is 4http://pgrouting.org 5http://postgis.net true for a highly connected spatial network it might not be the only or even best way for a real-world multimodal spatial network with various transportation systems. The isochrone calculation based on already known results should be doable with respect to all the isochrone's border points and all the public transportation system stations that are part of the base isochrone. These network hubs in reality are the only nodes, which can cause new, possibly disconnected areas to become part of an isochrone with di erent travelling time.
As it is important for the incremental calculation, the
vertex expiration that is introduced by Gamper et al. in [
There are some challenges that need to be addressed when implementing an incremental calculation for the MINE and MINEX algorithm. The most obvious problem is related to the vertex expiration of the MINEX algorithm. If nodes already expired, they will not be available to the calculation of isochrones with di erent durations. To take care of this problem all nodes n that are connected to other nodes which are not in the direct neighbourhood of n are added to a list l_hubs. These nodes are the ones we referred to as network hubs. Besides the hub node n itself, further information is stored in this list: the time t of arrival at the node and the remaining distance d that can be used. With this information it is possible to continue computation from any hub with a modi ed travelling time for the algorithms.
The list l_hubs needs to be stored in addition to the isochrone's maximal travelling time and the isochrone result itself, so that it can be used for incremental calculation. None of this information needs to be held in memory during computation of the base isochrone itself and is only touched on incremental calculation. Therefore, runtime and memory consumption of the isochrone algorithms will not be in uenced much.
Other problems include modi cations to the spatial network in combination with incremental isochrones. If there is some change applied to the underlying network, all the base isochrones can not be used for incremental calculation any more. It can not be guaranteed that the network modi cation does not in uence the base isochrone. Changes in the schedules of one or more modalities (for example the public transportation systems) could cause problems as well, as they would also in uence the base isochrone. Schedule alternations can be triggered by a service provider. Tra c jams and similar factors can lead to delays in the transportation system and thus also have to be considered. Although it should be possible to overcome both limitations or at least limit their impact, it will not be further discussed in this paper. 3.2
There are six di erent cases that have to be kept in mind when calculating an isochrone with travelling time dmax using a base isochrone with duration dmax_base: three applying to algorithms without vertex expiration and three cases for the ones using vertex expiration. 3.2.1
Cases dmax = dmax_base
The rst two and most simple cases for the MINE and MINEX algorithm, are the ones where dmax is equal to dmax_base. In these cases it is obvious that the calculation result can be returned directly without any further modi cation. It is not needed to respect expired nodes, since no (re)calculation needs to be performed. 3.2.2
Cases dmax < dmax_base
The third, also simple case, is the one where dmax is less than dmax_base for algorithms without vertex expiration. In this situation all nodes can be iterated and checked for suitability. If the duration is less or equal to dmax, then the node also belongs to the new result, otherwise it does not. In the fourth case, where the duration is less than dmax_base and nodes were expired (and therefore are not available in memory any more), the isochrone can be shrunk from its borders. The network hubs do not need any special treatment, since no new areas can become part of the result if the available time decreased. The only necessary task is the recalculation of the durations from the query point to the nodes in the isochrone and to possibly reload expired nodes. It either can be done from the query point or from the border points. The duration d from the query point q to a network node n is then equal to (assuming that the border point with the minimal distance to n is named bp): d(q; n) = d(q; bp) d(bp; n) 3.2.3
Cases dmax > dmax_base
The remaining two cases, where dmax_base is less than dmax, are much more complex. They di er in the fact that new, possibly disconnected areas can become part of the result and therefore it is not su cient to look at all the base isochrones border points. The new areas become available as a result from connections caused by network hubs that often are bound to some kind of schedule. A real-world example is a train station where a train is leaving at time t_train due to its schedule and arriving at a remote station at or before time dmax (in fact any time later than dmax_base is feasible). The time t_train has to be later than the arrival time at the station (and after the isochrones starting time).
Since all network hubs are saved with all the needed information to the list l_hubs it is not of any interest if the algorithm uses vertex expiration or not. The points located at the isochrone's outline are still in memory. Since only network hubs can create new isochrone areas it is su cient to grow the isochrone from its border and all the network hubs located in the isochrone. The only e ect that vertex expiration causes is a smaller memory footprint of the calculation, as it would also do without incremental calculation.
In table 1 and in table 2 the recently mentioned calculation types are summarised shortly. The six di erent cases can be distinguished with ease using these two tables.
dmax < dmax_base iterating nodes from base isochrone checking if travel time is <= dmax dmax = dmax_base no change dmax > dmax_base extend base isochrone by
border points and with list l_hubs
Although the di erent types of computations are introduced using the MINE and MINEX algorithms they also apply to the MRNEX method. When using MRNEX the same basic idea can be used to enable incremental calculations. In addition the same advantages and disadvantages apply to the incremental calculation using MRNEX compared to MINEX that also apply to the non-incremental setup. 3.3
The evaluations that will need to be carried out to ensure the correctness of the implementation can be based on freely available datasets, such as OpenStreetMap6. Schedules from various public transportation systems could be used and since they might be subject of licensing it is planned to create some test schedules. This data can then be used as mockups and as a replacement of the license-bound realworld schedules. It is also planned to realise all the described tests in the context of a continuous integration setup. They will therefore be automatically executed ensuring the correctness throughout various software changes.
The basic idea of the evaluation is to calculate incremental isochrones on the basis of isochrones with di erent durations and to compare them with isochrones calculated without the incremental approach. If both results are exactly the same, the incremental calculation can be regarded as correct.
There will be various tests that need to be executed in order to cover all the di erent cases described in section 3.2. As such, all the cases will be performed with and without vertex expiration. The durations of the base isochrones will cover the three cases per algorithm (less than, equal to and greater than the duration of the incremental calculated isochrone). Additional tests, such as testing for vertex expiration of the incremental calculation result, will be implemented as well. Furthermore, the calculation times of both - the incremental and the non-incremental approach - will
be recorded to allow comparison. The incremental calculation can only be seen as successful, if there are situations where they perform better than the common calculation. As mentioned before, this is expected to be true for at least large isochrone durations, since large portions of the spatial network does not need to be loaded then.
Besides these automatically executed tests, it will be possible to perform manual tests using a graphical user interface. This system is under heavy development at the moment and has been named IsoMap. Regardless of its young state it will enable any user to calculate isochrones with and without the incremental approach and to visually compare the results with each other. 4.
In this paper an approach to enable the calculation of isochrones with the help of already known results was presented. The necessary steps will be realised in the near future, so that runtime comparisons between incremental calculated isochrones and such created without the presented approach will be available shortly. The ideas developed throughout this paper do not in uence the time needed for calculation of base isochrones by far. The only additional complexity is generated by storing a list l_hubs besides the base isochrone. However, this is easy to manage and since the list does not contain any complex data structures, the changes should be doable without any noticeable consequence to the runtime of the algorithms.
Future work will extend the incremental procedure to further calculation parameters, especially to the arrival time, the travelling speed and the query point q of the isochrone. Computations on top of cached results are also realisable for changing arrival times and/or travel speeds. It should even be possible to use base isochrones with completely di erent query points in the context of the incremental approach. If the isochrone calculation for a duration of twenty minutes reaches a point after ve minutes the 15-minute isochrone of this point has to be part of the computed result (if the arrival times are respected). Therefore, cached results can decrease the algorithm runtimes even for di erent query points, especially if they are calculated for points that can cause complex calculations like airports or train stations.
Open elds that could be addressed include the research of incremental calculation under conditions where public transportation system schedules may vary due to trouble in the tra c system. The in uence of changes in the underlying spatial networks to the incremental procedure could also be part of future research. It is planned to use the incremental calculation approach to calculate city round trips and to allow the creation of sight seeing tours for tourists with the help of isochrones. This computation will soon be enabled in cities where it is not possible by now.
Further improvements regarding the calculation runtime of isochrones can be done as well. In this eld, some examinations with di erent databases and even with di erent types of databases (in particular graph databases and other NoSQL systems) are planned.