Knowledge Platform

Route search algorithms try to find unique, optimal paths, from origin to destination. For the simple shortest path search problem formulation, the network is usually represented as a directed graph. The most important algorithms for solving this problem are listed below: 
 Dijkstra algorithm [1] solves the problem of finding the shortest path from a point in a graph (the source) to a destination. The algorithm finds the shortest paths from a start point to every other point in the graph, producing a shortest path tree. The algorithm, at each step examines the node with the lowest distance from the start. The node is marked "closed", and all nodes adjacent to it are added to the open set if they have not already been examined. The process ends as soon as a path to the destination has been found. 
 Bi-directional search is a graph search algorithm that finds a shortest path from an initial point to a goal point in a directed graph. It runs two simultaneous searches: one forward from the start, and one backward from the goal, stopping when the two meet in the middle [2]. 
 A* is a computer algorithm that is widely used in path finding. A* solves problems by searching among all possible paths to the solution for the one that incurs the smallest cost (least distance travelled, shortest time, etc.), and among these paths it first considers the ones that appear to lead most quickly to the solution. A* assigns A* assigns a weight to each open node equal to the weight of the edge to that node plus the approximate distance between that node and the finish. The approximate distance is found by the heuristic, and represents a minimum possible distance between that node and the end. When the heuristic evaluates to zero, A* is equivalent to Dijkstra's algorithm [3]. 

For multi-objective optimization problems, such as the multi-modal routing problem, there is usually no single optimal solution. Instead, such problems tend to be characterized by a set of alternative solutions, which should be considered equivalent in the absence of further information regarding the relative importance of each objective in the solution vectors. The purpose of multi-modal route planning is to provide the traveller with an optimal, feasible, and personalized route between origin and destination, which may involve public and private transportation modes. The problem of efficiently computing multi-modal journeys, presents several algorithmic challenges and has been an active area of research in recent years due to a strong practical interest and an increasing data availability. The Multi-Objective Path Search Problem is based on the simple shortest path search but it considers not only one weight label, but a weight vector for each link. Due to the presence of many criteria that might come into conflict with each other, not only one optimal path is searched, but a set of paths with acceptable trade-offs among the routing criteria. Multi-objective path search problem is an application topic of Multi-objective optimization theory. Known algorithms for the Multi-Objective Path Search Problem cannot resolve the optimal solutions set in polynomial time, as it is a NP complete problem. In fact, it is intractable because the size of the Pareto frontier grows exponentially with the number of nodes of the network [4]. In this sense, Multi-Objective Optimization algorithms do not intend to build a complete optimal set, but an approximation of it, that represents the whole range of choices [5]. 

The Multi-Objective Transit Routing is an application case of the Multi-objective path search problem in the area of transportation systems. It consists in finding optimal paths for passengers traveling along a public transport network. Passengers’ preferences and the characteristics of the specific public transport system must be considered. Thus, typically the optimal transit route search deals with the problem of giving the passenger a solution that represents a tradeoff between different objective functions. Common considered objective functions to minimize in optimal transit routing studies are travel time, number of transfers, walk time, and, in some cases, the fare cost. 

In computer science and operations research, a genetic algorithm (GA) is a meta-heuristic inspired by the process of natural selection that belongs to the larger class of evolutionary algorithms (EA). The genetic algorithm repeatedly modifies a population of individual solutions relying on bio-inspired operators, such as mutation, crossover, and election [6]. The EA are commonly used to generate high-quality solutions to optimization and search problems. Genetic algorithms (GA) were proposed in order to solve the multi-modal route planning problem [7]. Variable length chromosomes with several parts (subchromosome) are utilized to represent routes in multi-modal travel environment, where each part describes a kind of transportation mode. Crossover and mutation operators are redefined in single mode; two new operators, hypercrossover and hypermutation, are defined as inter-mode operation. A multi-criteria evaluation method using a p dimensional vector to represent multiple criteria is adopted in the fitness function for selecting the optimal solutions. The multi-objective ranking method usually consumes much running time. The performance of the proposed approach in dynamic environment has not been tested. 

Delling et al [8] studied multi-criteria journey planning in metropolitan multimodal networks. The authors argued that users of such networks optimize three criteria: arrival time, costs, and convenience. The proposed algorithms compute a full Pareto set and then score the solutions in a post-processing step, using techniques from fuzzy logic, which can quickly identify the most significant journeys. The full Pareto set is too large and includes many unnatural journeys. Multi-criteria heuristics can be used in order to find similar journeys. The experiments showed that this approach enables the computation of high-quality multimodal journeys on large metropolitan areas, and is fast enough for practical applications. 

Müller-Hannemann and Weihe [9] carried out a study on bi-criteria shortest path search on a scenario with real schedule information of the German train system. The objective was to determine if the Pareto optimal set size could be set to a polynomial size or not. The approach identifies key characteristics on the scenario that lead to a smaller number of optimal solutions which practically makes the problem tractable, instead of getting an exponentially growing solution size in the worst case. The method sets restrictions to paths according to an edge model classification and discards node labels that are dominated by labels at the destination node. Subsequently, a prototype solution based on a multi – criteria generalization of Dijkstra’s algorithm has been implemented and tested on the German train system time – depended network [10], providing fair average execution time (below 1sec). In this implementation, nodes have multidimensional labels which can be expanded multiple times during the path search. Each label represents an optimization objective and includes a reference to its predecessor on the path. New labels are compared to the complete list of previously revised node labels, a list of non-dominated labels is updated, and dominated labels are removed. 

Furthermore, Müller-Hannemann and Schnee [11] presented a model with three main optimization objectives: travel time, fare, and transfer number minimization. This model introduces the concept of Relaxed Pareto Dominance, in order to find potentially attractive routes without discarding “near optimal” solutions. A relaxation function is applied, accounting other travel aspects, not originally considered in the main optimization objectives. Routes that are attractive in respect to these travel aspects are set incomparable. In that way, these attractive routes are not suppressed by the normal route dominance comparison. The reported performance surpasses the journey planner of the Deutsche Bahn AG, which collaborated for the scenario of the German public railroad network. 

In a similar way, Delling et al.[12] presented a routing algorithm for flight networks (with nodes representing airports) which reduces the network complexity in comparison to road (or railway) networks. In contrast to railway networks, fight networks contain (almost) exclusively direct connections between airports (unlike trains, planes do not stop at many airports on a route). Because of this fact, all routes between airports are conveniently pre-calculated and stored in tables (queries retrieve routes in microseconds). 

The classic Dijkstra’s algorithm has poor performance on very large graphs such as continent – size road networks, thus, several speedup techniques have been proposed based on graph preprocessing. Such an algorithm is SHARC [13] and its extension for multi-criteria routing [14]. SHARC creates graph partitions and pre-calculates paths to them with a generalized Dijkstra method. Then, links that lead to certain partitions are flagged. After that, an iterative process contracts the graph selecting only relevant nodes. Finally, the arc-flags refinement introduces several reasonable constraints to prune unattractive paths, both during pre-processing and queries. The Multi-Objective Path Search approach includes the following: A multi-criteria version of Dijkstra algorithm operates on the prepared graph. In order to be able to reduce the Pareto set and so also to deal with real big scenarios, travel time is set as main dominance criterion. Other paths are considered in the optimal set, only if they do not represent a big bad impact on time optimization. The effect of speed-up techniques on performance is reported in a Western Europe network scenario test, in which pre-processing lasted for 5 hours, and a route query was resolved in 8 ms. 

During the last decade, novel graph preprocessing techniques have been proposed, such as contraction hierarchies [15], transit node routing [16], and Hierarchical Hub Labeling [17], thus, providing enormous speedup for both data pre-processing and query execution time (for European size continental road graph combining of tens of millions of nodes and edges, we can achieve pre-processing time less than 2 hours and query execution time less than 10ms. Their potential extension for supporting the multi-criteria routing problem, could over-perform typical (without pre-processing) path finding methods, and be capable of handling continental size transport networks for multimodal journey planning. 

[1] Dijkstra, E. W. (1959). "A note on two problems in connexion with graphs" (PDF). Numerische Mathematik. 1: 269–271. 
[2] View at https://en.wikipedia.org/wiki/Bidirectional_search 
[3] View at https://en.wikipedia.org/wiki/A*_search_algorithm 
[4] Raith and M. Ehrgott. A comparison of solution strategies for biobjective shortest path problems (2007). 
[5] Diakonikolas and M. Yannakakis. Small approximate pareto sets for biobjectiveshortest paths and other problems (2009). 
[6] Mitchell, Melanie (1996). An Introduction to Genetic Algorithms. Cambridge, MA: MIT Press. ISBN 9780585030944 
[7] A multimodal route planning approach with an improved genetic algorithm. Haicong Yu*, Feng Lu. The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol. 38, Part II. 
[8] Computing and Evaluating Multimodal Journeys. Daniel Delling, Julian Dibbelt, Thomas Pajor, Dorothea Wagner, and Renato F. Werneck 
[9] M. Müller-Hannemann and K. Weihe. On the cardinality of the pareto set in bicriteria shortest path problems (2006). 
[10] Y.Disser - M. Müller-Hannemann and M. Schnee. Multi-criteria Shortest Paths in Time-DependentTrain Networks (2008). 
[11] M. Müller–Hannemann and M. Schnee. Finding all attractive train connectionsby multi-criteria pareto search (2007). 
[12] D. Delling, T. Pajor, D. Wagner, and C. Zaroliagis. Efficient route planning inflight networks. 2009 
[13] D. Delling Time-Dependent SHARC-Routing. 2009 
[14] D. Delling and D. Wagner. Pareto paths with SHARC. 2009 
[15] R. Geisberger, P. Sanders, D. Schultes, and D. Delling. Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks. 2008 
[16] H. Bast,S.Funke and D. Matijevic. TRANSIT Ultrafast Shortest-Path Queries with Linear-Time Preprocessing. 2006 
[17] Abraham, D. Delling, A.V. Goldberg and R.F. Werneck. Hierarchical Hub Labelings for Shortest Paths. 2012