Faster and increasingly individual
© Shutterstock
September 2017

Faster and increasingly individual

Route planning seems to be a problem that has long been resolved. Yet traffic jams, blocked roads and the combination of various means of transportation can turn this simple task into a complex one. Computer scientists are working on solutions enabling us to find the fastest way even in tricky surroundings.

​Maps the size of kitchen tables, road atlases several inches thick and railroad timetables listing departure and arrival times in endless columns – it was not uncommon for travelers planning a trip in the pre-computer age to require space, plenty of patience and a little luck because “it really wasn’t possible to tell if a route tediously selected by hand and apparently suitable was in fact the fastest one because information about the time required to travel the various stages simply wasn’t available in those days,” says Dorothea Wagner, a professor for theoretical computer science at Karlsruhe Institute for Technology (KIT). If a traveler additionally encountered a traffic jam or blocked section of a road mobility would soon turn into an involuntary adventure. Fortunately, the situation today is different. Travelers wishing to find the fastest way to get from A to B just turn on their satellite navigation systems or their smartphones to ask Google Maps or apps provided by their local transit system operators.

We owe the fact that mobility has become so much faster, comfortable and individual today to the availability of precise data from digital maps and, above all, to modern route planning algorithms. Their success story began with the shortest path algorithm developed by the Dutchman Edsger Wybe Dijkstra as far back as in 1959. The current schedule information systems and route planners essentially still work with the so-called Dijkstra algorithm. However, because the original algorithm, in order to determine the shortest path between city A and city B, calculates the connections to all cities on the map, practically searching the entire map, it has difficulties coping with large data sets. “The Dijkstra algorithm requires more than one second in the case of a digitized road map of all of Europe – and that’s too slow today,” says Wagner, because when thousands of such queries – as is typically the case today – are simultaneously sent to a server from smartphones and computers, the seconds aggregate and thus become the crux of the calculation.

Calculations in milliseconds

“Therefore, calculations that can be performed within a few milliseconds are necessary for such scenarios,” says Wagner. Consequently, the Dijkstra algorithm had to be accelerated considerably in the past decades. “Principally, calculations that enhance the map in advance with information are used for this purpose in order to be able to logically exclude as many paths as possible when processing a query,” explains Olaf Meng, Product Manager Traffic at Garmin, the world market leader for navigation solutions based in Switzerland. The methods used, though, are a business secret because the algorithms which are consistently being optimized by hundreds of engineers are the company’s most valuable know-how. However, they function in similar ways as the simple and commonly known solution of dividing a map into square regions. With the benefit of knowing in advance where a destination city is located, all the calculation steps for cities which are not located in the destination region can be omitted. Scientists like Wagner refer to a “reduction of the search space” when discussing such methods.

Faster and increasingly individual© Shutterstock

For route planning which does not include any current components such as traffic jams or road blocks due to accidents, the calculation is fast enough today, according to Wagner. “An intriguing situation arises when we look at real-time data and more complex scenarios such as intermodal mobility. In that case, the algorithms are often not fast enough yet,” says the scientist. The reason is that when planning a route that includes any possible means of transportation, from walking, riding a bicycle, a bus, train or taxi through to car sharing systems and flying, you immediately encounter all the problems that exist within the single solutions. “Consequently, the mathematical effort involved in finding the optimum route here is considerably higher as well,” says Wagner.

Data volume is (still) an issue

As a result, the existing offerings that include other transportation systems, such as the Qixxit app of Deutsche Bahn (“German Rail”) or Daimler’s Moovel app, do not yet have a truly independent algorithmic solution. Typically, they still combine the route retroactively from the separately queried transportation systems, Wagner explains. The computer scientist adds that the calculation is slow and does not necessarily deliver the fastest connection from A to B because such apps only work together with selected partner companies and not really with all existing transportation service operators. Consequently, a number of faster alternatives might be excluded as an option to begin with.

One reason for this selective approach is to prevent promoting competitors. For instance, Daimler’s app Moovel only integrates the company’s own car sharing service Car2Go, but not BMW’s DriveNow. Another reason for limiting the service to just a few partners is the extremely high increase of the data volume even when just a small selection is involved. Therefore, the search space for the algorithms is limited wherever this is possible. for instance restricts the radius of walking routes to a specific maximum. Although this omits connections in which a longer walking distance might lead to a faster overall route, the omission, says Wagner, is practically done in self-defense because the data volume would immediately explode if the radius for walking routes were extended.

The computer science professor adds that efforts to resolve these challenges are in progress everywhere. Just a week ago, for example, a Ph.D. student at her institute had submitted a paper on this topic. “The intermodal offerings are becoming faster step by step and I’m expecting really good results in three to five years,” says Wagner. Particularly exciting as well, says Garmin’s executive Meng, is route planning for electric vehicles in which case power consumption and the distribution of charging stations have to be considered as well. Wagner is working on this topic too. In the future, she says, route planning will generally offer more individual setting options that will quickly and reliably deliver routes tailored to meet the user’s needs. These solutions will include additional filters for criteria such as the views to be enjoyed on the route, intermediate stops at specific restaurants and preference of backroads over highways.

For her personal mobility needs, Wagner, by the way, has already found the optimum solution. She rides her bicyle to work on the same route every day. “The calculation time is zero in this case,” she says.

Faster and increasingly individual
Cloud-based condition monitoring: High-tech solutions analyze conditions of components and issue warnings before a defect occurs© Schaeffler
This is how Schaeffler feeds algorithms with data

Many of Schaeffler’s products today are able to gather data from which important information is derived using real-time analyses and cognitive systems.

The electromechanical roll stabilizer is a good example. It is able to acquire driving dynamics data that may be used for networked driving in diverse ways. Sensor systems which Schaeffler offers for rail applications are diligent data gatherers as well. In cloud-based condition monitoring, such high-tech solutions analyze the condition of a component based on various parameters such as temperature, vibration and speed, and issue warnings before a defect results in failure. The wheelset generator as an autonomous and very reliable electric energy supply system for rail freight cars makes it possible to extend the digitization approaches that have already been realized today.

However, experts from Schaeffler monitor the conditions of thousands of stationary machines and equipment as well. Measured data is edited via flexible interfaces or the Schaeffler pre-processing unit and can be transmitted to the Schaeffler cloud. New algorithms and cognitive methods are used for analysis, prediction and optimization. Irregularities and required actions are indicated and appropriate actions initiated.

How algorithms guide us

We all use them in our everyday lives, yet hardly any of us are aware of how omnipresent and powerful today’s computation rules are. Here’s a selection.

Alongside Facebook’s, the Google algorithm is the most frequently used one on our planet. The things we’ve searched and clicked in the past are supposed to have a bearing on the search results displayed just like the user’s location and the trustworthiness of the results. Critics warn that a manipulation of the results list may influence our decisions. Furthermore, our lives might become more predictable if we only do what algorithms suggest to us.

Today, a computer decides if we can get a loan or a cell phone plan approved, or open a checking account. Credit scores are calculated from data about previous loan agreements, late payments or unpaid bills. Some companies also use Facebook profiles to assess the credit worthiness of their clients.

Nicola Casagli, a geologist at the University of Florence, combines weather data, amounts of precipitation, satellite pictures and information about slope gradients in a region to predict landslides. In areas that are particularly risk-prone, Casagli additionally uses high-precision ground radar that registers even the slightest earth movements. People living in areas concerned can be warned in time by the ­algorithm.

So-called predictive policing algorithms use data pertaining to the scenes and times of crimes committed, the types of items stolen and modus operandi to predict the probability of burglaries occurring in the neighborhood of the most recently known offenses. As a result, police presence increases in high-risk areas. However, whether a decline in burglary crime rates can actually be attributed to the use of such algorithms is disputed.

Undisputed, though, is the fact that algorithms can decide whether or not we’ll get a job we’re applying for. Online application portals use them to check if applications have been fully completed and to run searches for keywords. By the way, an application on paper is not immune from such practices as it can be digitized as well and subsequently analyzed by an algorithm.

Denis Dilba
Author Denis Dilba
Following his research of route planning algorithms, Denis Dilba has come to appreciate the navigation apps on his smartphone even more than before. On hiking tours, though, the journalist specializing in science and technology topics, always takes a map and a compass along to be on the safe side: because they never run out of juice.