# Time-Dependent Route Planning for the Highways in the Czech Republic

Radek Tomis, Jan Martinovič, Kateřina Slaninová, Lukáš Rapant, Ivo Vondrák

► To cite this version:

Radek Tomis, Jan Martinovič, Kateřina Slaninová, Lukáš Rapant, Ivo Vondrák. Time-Dependent Route Planning for the Highways in the Czech Republic. 14th Computer Information Systems and Industrial Management (CISIM), Sep 2015, Warsaw, Poland. pp.145-153, 10.1007/978-3-319-24369-6_12. hal-01444461

HAL Id: hal-01444461

https://inria.hal.science/hal-01444461

Submitted on 24 Jan 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Time-Dependent Route Planning for the
Highways in the Czech Republic

Radek Tomis, Jan Martinovič, Kateřina Slaninová,
Lukáš Rapant and Ivo Vondrák

VŠB - Technical University of Ostrava,
IT4Innovations,

17. listopadu 15/2172, 708 33 Ostrava, Czech Republic
(radek.tomis,jan.martinovic,katerina.slaninova,
lukas.rapant,ivo.vondrak)@vsb.cz

**Abstract.** This paper presents an algorithm for dynamic travel time computation along Czech Republic highways. The dynamism is represented by speed profiles used for computation of travel times at specified time. These speed profiles have not only the information about an optimal speed, but also a probability of this optimal speed and the probability of the speed which represents the possibility of traffic incident occurrence. Thus, the paper is focused on the analysis of paths with the uncertainty created by traffic incidents. The result of the algorithm is the probability distribution of travel times on a selected path. Based on these results, it is possible to plan a departure time with the best mean travel time for routes along the Czech Republic highways for a specified maximal acceptable travel time. This method will be a part of a larger algorithm for dynamic traffic routing.

**Keywords:** time-dependent route planning, speed profiles, uncertainty, traffic events, floating car data

# 1 Introduction

Finding the fastest paths by travel time is a common feature of navigation ser-
vices, because the efficient route planning on a road network saves time and
money of drivers. Traffic data about road networks can be used to obtain more
accurate results. However, most navigation services use only simple statistical
aggregates of historic travel times on roads for computation of the paths, even
though this is not sufficient if there are traffic incidents on the roads, so likely
on real road networks.

Finding the best route within the real road network is affected by a departure
time of the vehicle. Some roads can be congested at the time of rush hours, which
leads to larger delays. In such environment, route planning can be modelled as
time-dependent shortest path problem [14] with variable travel times as edge
weights. The resulting path is then determined by the departure time.
Dijkstra's algorithm [6] solves this problem if the non overtaking property is guaranteed [4], stating that later departure can not lead to earlier arrival. There are many adaptations and extensions of time-dependent Dijkstra's algorithm, for example Contraction Hierarchies [1] and SHARC [5]. These algorithms use some precomputed information to speed up the shortest path queries.

The main disadvantage of time-dependent route planning is that it does not take uncertain events into account. Travel times on the edges are computed as aggregates of available traffic data [15], even though this is not sufficient in many cases [7, 9]. For example, if there are irregular but recurrent traffic congestions at some road, we should consider it in computation of the path and try to find another route [12]. Even though the probability of the congestion can be very low, the delay in the case the congestion happens can be very long. For this reason, we have to consider uncertain traffic events and their probabilities in the computation of the path [13, 17].

Traffic incidents and congestions cause uncertainty of travel times. The main idea of this paper is to analyze paths with the uncertainty created by traffic incidents. Some paths are driven through more frequently than others and therefore it is desirable for drivers to know how travel times on these paths are affected by the traffic incidents. To achieve this, we need to extract information about the traffic incidents from the traffic data. The process of incident extraction as well as our algorithm and its continuity on traffic routing is described at section 3. Section 4 presents experiments of our algorithm.

We use the road network created from Traffic Message Channel (TMC) segments in the Czech republic, because it represents the backbone of the real road network and it covers the whole Czech republic evenly. TMC is also a standard used in GPS navigations.

## 2 Time-Dependent Route Planning with Probability

Some algorithms [10, 3, 2, 16] try to find a solution for time-dependent shortest path problem in uncertain networks from the global point of view. The algorithms work on the whole network and try to minimize travel time with a set probability or to maximize the arrival probability with a set travel time. However, even in case of small traffic networks, the global approach is very time demanding. In the case of very large networks, it is impossible to compute all the possibilities across all the possible paths. There are broadly two approaches how to deal with this problem.

The first one is to use some form of precomputed results [17, 11]. We do not consider this approach attractive. Thanks to the access to all sensors on Czech Republic highways, we can recompute speed profiles quite often, depending on the situation on the road. For example, it is sensible to recompute these profiles when the highway is undergoing reconstruction. Such frequent speed profile re-computation compromises all the performance advantages of routing based on pre-computation.
Therefore, we propose to use the second possible approach. This approach is based on some form of the problem simplification. It does the same as other algorithms, but from the different point of view. In the first step of our algorithm, several time-dependent shortest paths between two vertices are found (without their travel time uncertainty). In the second step, a probability function of travel time is computed on these paths. As the next step, we can analyze these results, compare them with each other, and suggest detours by identification of edges with the biggest travel time slow down or the arrival probability decrease. The choice of the best path can be based on various characteristics, like mean travel time or its variance. The progress of the algorithm can be summarized into the following steps:

1. Input origin, destination and desired departure time.

2. Perform deterministic dynamic routing to receive *n* best paths.

3. Perform probabilistic travel time computation on these paths.

4. Analyse received paths and their travel times to propose improvements (short detours or better departure time).

5. Recommend the best route and departure time based on preferred criterion.

The main aim of this paper is to propose a solution to the third step of the algorithm (highlighted by the bold font). The rest of the algorithm is currently under the development and will be published in the near future.

# 3 Probabilistic Travel Time Computation

The focus of this paper is on the computation of travel times and their probabilities on the selected path. Let $G = \{V, E\}$ be a directed graph created from a road network, where vertices represent intersections and edges represent roads. Our selected path starts at a vertex $u$ and ends at a vertex $v$. We choose departure time $t_d$ and compute time-dependent shortest path with optimal speed profiles as edge weights to obtain optimal path $P_o = \{u = v_0, e_0, v_1, e_1, ..., v_{n-1}, e_{n-1}, v_n = v\}$ by travel time for $t_d$, let's denote travel time of this path as $t_o$. Then we compute travel times and their probabilities for other combinations of speed profiles, which means travel times and their probabilities grow as binary tree with root node represented by $u$, leaf nodes represented by $v$ and each path between $u$ and $v$ represents one specific combination of speed profiles. Binary tree is a tree data structure in which each node has at most two children. There can be any number of nodes in between $u$ and $v$ and exact number depends on a number of speed profiles.

The tree can be very large, so we have to introduce some constraints. We choose $s$ as a percentage constraint of a maximum allowed slow down of computed paths compared to $t_o$. The computation of travel times and their probabilities is based on depth-first search on the sequence of edges $e_0, e_1, ..., e_{n-1}$ and at each vertex $v_i: i = 1, 2, ..., n$, we compute the actual travel time $t_a$ to this vertex. Then we compute the remaining optimal time $t_r$ as optimal time from $v_i$ to $v$. The computation of the path for some given combination of speed
<figure><img src="image_2.png" /><figcaption>Fig. 1. Example of the specific travel time tree</figcaption></figure>

profiles can be stopped if $t_a + t_r > (1 + s)t_o$, which means the tree does not have to be expanded at these vertices and is effectively truncated. The example of travel time tree is presented on Fig. 1. Some nodes are not expanded because they do not satisfy certain slow down condition $s$. See Algorithm 1 for pseudo code of our algorithm.

**Algorithm 1** Compute travel time probabilities for given array of edges, departure time and slow down

1: **procedure** TRAVELTIMEPROBABILITIES(*edges*, *t*<sub>*d*</sub>, *s*)
2:     *t*<sub>*m*</sub> = maximum allowed time for given *edges*, *t*<sub>*d*</sub> and *s*
3:     push to stack {*edge* = *edges*[0], *time* = *t*<sub>*d*</sub>, *probability* = 1}
4:     **while** stack is not empty **do**
5:         *actual* = pop from stack
6:         *edgeResults* = GetTravelTimeProbabilities(*actual*)
7:         **for** *r* in *edgeResults* **do**
8:             ▷ *r* is a pair of *t*<sub>*a*</sub> and *probability*
9:             *t*<sub>*r*</sub> = optimal remaining time from *actual* to end
10:         *t* = *r* → *t*<sub>*a*</sub> + *t*<sub>*r*</sub>
11:     **if** *t* < *t*<sub>*m*</sub> **then**
12:         **if** *actual* → *edge* is last edge **then**
13:             add *r* to result
14:             **else**
15:                 push to stack {*actual* → *nextEdge*, *r* → *t*<sub>*a*</sub>, *r* → *probability*}
16:             **end if**
17:         **end for**
18:     **end while**
19: **end procedure**
The sum of all the leaf node probabilities is always 1. The probability of the situation in which the slow down is exceeded can be calculated as the sum of probabilities of the nodes not expanded to the end of the path.

# 4 Experiment

The experimental results of presented algorithm and their evaluation are presented in this section. The path from Praha to Brno along the highway D1 was chosen, because it is known that there are many traffic incidents on the highway D1, especially during its reconstruction. The path is composed of 84 road segments which means there are 84 edges on the path. Visualization of the path is presented on Fig. 2.

<figure><img src="image_3.png" /><figcaption>Fig. 2. Selected path from Praha to Brno</figcaption></figure>

The speed profiles used in our experiments were computed from data, which was obtained due to online traffic monitoring by viaRODOS system [8]. The experimental set of data was extracted from two months (October and November 2014) with traffic work on the highway D1. Speed profiles contain sets of pairs of data in 15 minutes interval for each day of the week and each measured place. The first pair contains average speed from values equal or higher than 50 percent of LoS (Level-of-Service - the measured speed divided by the normal free flow speed) and probability of the occurrence of this state. The second pair is computed by the similar way, but from the values under 50 percent of LoS. The values with reliability equal to 0 were excluded from the speed profiles computation. You can see probability intensity computed from values under 50 percent LoS (traffic problems) in the Fig. 3.

Table 1 shows the comparison of our algorithm for three different departure times on Wednesday with maximum slowdown $s = 0.9$. The percentage of acceptable travel times indicates travel times lower than $(1 + s)t_o$. The expected
<figure><img src="image_4.png" /><figcaption>Fig. 3. Probability Intensity for values < 50% LoS</figcaption></figure>

value E and the standard deviation σ are computed only for acceptable travel times. As expected, E is higher at peak hours and higher values of σ points out to a bigger number of traffic incidents at that time.

<table><caption>**Table 1.** Comparison of Different Departure Times</caption><thead><tr><th rowspan="2">Travel Time</th><th colspan="3">Departure Time</th></tr><tr><th>8:00</th><th>14:00</th><th>20:00</th></tr></thead><tbody><tr><td>Acceptable [%]</td><td>89.3</td><td>67.7</td><td>100.0</td></tr><tr><td>Unacceptable [%]</td><td>10.7</td><td>32.3</td><td>00.0</td></tr><tr><td>E [min]</td><td>105.1</td><td>107.5</td><td>101.4</td></tr><tr><td>σ [min]</td><td>3.5</td><td>3.4</td><td>0.6</td></tr></tbody></table>

Figures 4, 5 and 6 show probability distributions of acceptable travel times for previously mentioned departure times. We can observe that the distribution of probability is dependent on the departure time. As we can see in Fig. 5, bigger portion of probability is located around lower travel times. It is obvious that during afternoon is much higher traffic flow which often cause traffic incidents than in the morning or in the evening. Fig. 6 shows that evenings are much suitable for travelling.

# 5 Conclusion

In this paper, the method for time-dependent route planning with probability was presented. This method is based on the computation of the truncated binary tree. While it would be nigh impossible to compute the full binary tree for
<figure><img src="image_5.png" /><figcaption>Fig. 4. Travel time probability distribution for departure time 8:00</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>Fig. 5. Travel time probability distribution for departure time 14:00</figcaption></figure>

any sensible number of road segments, this truncation allows us to compute it
efficiently even for long highways with many road segments. Our experiments
on the D1 highway from Praha to Brno proved, that our algorithm is able to
swiftly compute the percentage of arrivals faster than the threshold and presents
their probability distribution. This algorithm has two main applications. It can
either serve as a stand alone module for dynamic route planning or it can be a
part of a larger dynamic routing algorithm, which is our goal for a near future.
We are also planning to compare the results of our algorithm with Monte Carlo
simulation, which seems to be a feasible solution to this problem.

Acknowledgment

This work was supported by the European Regional Development Fund in the
IT4Innovations Centre of Excellence project (CZ.1.05/1.1.00/02.0070) and the
<figure><img src="image_7.png" /><figcaption>Fig. 6. Travel time probability distribution for departure time 20:00</figcaption></figure>

national budget of the Czech Republic via the Research and Development for Innovations Operational Programme, by the project New creative teams in priorities of scientific research (reg. no. CZ.1.07/2.3.00/30.0055), supported by Operational Programme Education for Competitiveness, and co-financed by the European Social Fund and supported by "Transport Systems Development Centre" co-financed by Technology Agency of the Czech Republic (reg. no. TE01020155) and by the internal grant agency of VŠB Technical University of Ostrava, Czech Republic, under the project no. SP2015/157 'HPC Usage for Transport Optimization based on Dynamic Routing.

## References

1. G. Batz, R. Geisberger, S. Neubauer, and P. Sanders. Time-dependent contraction hierarchies and approximation. In *Experimental Algorithms*, volume 6049 of *Lecture Notes in Computer Science*, pages 166–177. Springer Berlin Heidelberg, 2010.

2. B. Chen, W. Lam, A. Sumalee, Q. Li, H. Shao, and Z. Fang. Finding reliable shortest paths in road networks under uncertainty. *Networks and Spatial Economics*, 13(2):123–148, 2013.

3. B. Y. Chen, W. H. K. Lam, A. Sumalee, Q. Li, and M. L. Tam. Reliable shortest path problems in stochastic time-dependent networks. *Journal of Intelligent Transportation Systems*, 18(2):177–189, 2014.

4. K. L. Cooke and E. Halsey. The shortest route through a network with time-dependent internodal transit times. *Journal of Mathematical Analysis and Applications*, 14(3):493–498, 1966.

5. D. Delling. Time-dependent sharc-routing. In D. Halperin and K. Mehlhorn, editors, *Algorithms - ESA 2008*, volume 5193 of *Lecture Notes in Computer Science*, pages 332–343. Springer Berlin Heidelberg, 2008.

6. E. Dijkstra. A note on two problems in connexion with graphs. *Numerische Mathematik*, 1(1):269–271, 1959.

7. Y. Fan, R. Kalaba, and I. Moore, J.E. Arriving on time. *Journal of Optimization Theory and Applications*, 127(3):497–513, 2005.
8. D. Fedork, T. Kocyan, M. Hjek, D. Szturcov, and J. Martinovi. viarodos: Monitoring and visualisation of current traffic situation on highways. In K. Saeed and V. Snel, editors, *Computer Information Systems and Industrial Management*, volume 8838 of Lecture Notes in Computer Science, pages 290–300. Springer Berlin Heidelberg, 2014.

9. A. Hofleitner, R. Herring, P. Abbeel, and A. Bayen. Learning the dynamics of arterial traffic from probe data using a dynamic bayesian network. *Intelligent Transportation Systems, IEEE Transactions on*, 13(4):1679–1693, Dec 2012.

10. M. Hua and J. Pei. Probabilistic path queries in road networks: traffic uncertainty aware path selection. In *Proceedings of the 13th International Conference on Extending Database Technology*, pages 347–358. ACM, 2010.

11. S. Lim, C. Sommer, E. Nikolova, and D. Rus. Practical route planning under delay uncertainty: Stochastic shortest path queries. In *Robotics: Science and Systems*, volume 8, pages 249–256, 2013.

12. E. Miller-hooks. Adaptive least-expected time paths in stochastic, time-varying transportation and data networks. *Networks*, pages 35–52, 2000.

13. E. Nikolova, M. Brand, and D. R. Karger. Optimal route planning under uncertainty. In *ICAPS*, volume 6, pages 131–141, 2006.

14. A. Orda and R. Rom. Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length. *J. ACM*, 37(3):607–625, July 1990.

15. J. Rice and E. Van Zwet. A simple and effective method for predicting travel times on freeways. *Intelligent Transportation Systems, IEEE Transactions on*, 5(3):200–207, 2004.

16. S. Sun, Z. Duan, S. Sun, and D. Yang. How to find the optimal paths in stochastic time-dependent transportation networks? In *Intelligent Transportation Systems (ITSC), 2014 IEEE 17th International Conference on*, pages 2348–2353. IEEE, 2014.

17. B. Yang, C. Guo, C. S. Jensen, M. Kaul, and S. Shang. Multi-cost optimal route planning under time-varying uncertainty. In *Proceedings of the 30th International Conference on Data Engineering (ICDE), Chicago, IL, USA*, 2014.