Single-mode routing is a database integration problem.
\nMultimodal routing is a search engine problem.<\/p><\/blockquote>\n
Multimodal routing<\/h3>\n
An effective travel routing and planning system must be able to find the best possible route by combining segments of different transportation modes. This constitutes a challenge because timetable and other information are stored in different databases, often heterogeneous. Applying parallel querying doesn\u2019t provide the required functionality, while serial querying of individual multi-modal segments leads to exceedingly long response times. Additionally, a serial architecture has no deterministic means of finding the best route according to specified criteria (e.g., travel time, walking distance), leading to low-quality results.<\/p>\n
An effective solution for providing fast responsiveness is to integrate the information from the separate sources into a unique and uniform database, serving as routing index. An Integration Engine makes sure that the unified database is always updated, and is able to add new data sources as they become available.<\/p>\n An effective routing and planning system must be able to automatically choose the best combinations of travel segments following specified criteria (e.g., travel time, number of stops). To enable this, the information relevant to the criteria must be stored for each segment. In a relational database model, this information would be stored in a table specific to each travel node type. While searching for the best combination, this table would need to be queried at each iteration, leading to excessively long computation times for large datasets.<\/p>\n To maintain performance and scalability, the information about the search criteria must be readily available at each node. The graph database model features this fundamental characteristic, directly and physically containing a list of relationships to other nodes. Edge Weighted Directed Graphs<\/em> are particularly well-suited for multi-modal transportation networks, easily enabling multi-criteria searches without significant loss of performance<\/p>\n Graph databases need one query for all modes of a segment, taking less time than relational databases<\/p>\n Segment interruptions are a daily occurrence in the transportation business. Much effort goes in the prevention, detection, information, and resolution of exceptions. When searching the best route from A to B, interruptions must be integrated as soon as possible to avoid providing travel information that does not correspond to reality. Additionally, interruptions must not reduce the performance of the routing system. An ideal architecture therefore uses a combination of graph and relational databases. Relational databases contain the comprehensive, rich information, while graph databases contain the essential information to efficiently perform multi-modal routing.<\/p>\n The Swiss-wide Door-to-Door transportation network comprises more than 700\u2019000 geospatial points.The Swiss transportation network comprises rail, light rail, cable cars, shared cars, ships, and more. When choosing the best route from station to station, all possible stations must be considered. Their number is impressive: On the Swiss rail network, there are more than 1’300 stations, and many more are present at the regional level (more than 2’700 in the Zurich region alone). While this order of magnitude appears manageable in the context of an IT-based solution for travel planning, the number of data points grows by a factor of 100-10’000 when considering walking and cycling on roads. In Switzerland, there are more than 70’000 km of roads, and subsampling, as an example, with an average density of 10 m results in 7’000’000 geospatial points. The computational implications of such a high number of points to be considered are considerable, and require careful attention for the choice of technology<\/p>\n While relational databases are the powerhouse of information technology since the 80s, and the best choice for many applications, they present some fundamental limits when it comes to calculate multi-modal relationships following different search criteria. These limits concern mainly the poor scalability of the required explicit joins between waypoint tables, and the lack of efficient dynamic queries and efficient routing algorithms in SQL. In a relational database, connections between discrete data is more challenging to store and slow to query. The Swiss-wide Door-to-Door transportation network comprises more than 700\u2019000 geospatial points. To scale routing to many transportation modes, a graph database model is the best choice.<\/p>\n A graph database is an online (“real-time”) database management system with CRUD (Create, Read, Update, and Delete) methods that expose a graph data model. A graph is a representation of a set of objects where some pairs of objects are connected by links (e.g., a train network of stations connected by rail segments). Graph databases are generally built for use with transactional (OLTP) systems. Accordingly, they are normally optimised for transactional performance, and engineered with transactional integrity and operational availability in mind.<\/p>\n Several leading organizations rely on Graph Databases. For instance: Lufthansa Systems, Lockheed Martin, Adobe, Hewlett-Packard, SFR, Cisco, Deutsche Telekom, Telenor, Accenture, Google. The reason why these organizations chose Graph Databases are the following.<\/p>\n The graph data model reduces the impedance mismatch, thereby reducing the development overhead of translating back and forth between an object model and a tabular relational model. More importantly, the graph model reduces the impedance mismatch between the technical and business domains: subject matter experts, architects, and developers can talk about and picture the core domain using a shared model that is then incorporated into the application itself.<\/p>\n Successful applications rarely stay still; changes in business conditions, user behaviors, and technical and operational infrastructures drive new requirements. In the past, this has required organizations to undertake careful and lengthy data migrations that involve modifying schemas, transforming data, and maintaining redundant data to serve old and new features. The schema-free nature of a graph database coupled with the ability to simultaneously relate data elements in lots of different ways allows a graph database solution to evolve as the business evolves, reducing risk and time-to-market.<\/p>\n Data is important: when employed in a business-critical application, a data technology must be robust, scalable, and more often than not, transactional. Graph databases are newer than relational databases, but they provide ACID (Atomic, Consistent, Isolated, Durable) transactionality, high-availability, horizontal read scalability, and storage of billions of entities. The performance and flexibility to handle a vast number of entities has become a standard requirement for large enterprises today. This has been an important factor leading to the adoption of graph databases by organizations: not merely in modest offline or departmental capacities, but in ways that can truly change the business.<\/p>\n Query performance and responsiveness are at the top of many organizations\u2019 concerns with regard to their data platforms. Online transactional systems, large web applications in particular, must respond to end users in milliseconds if they are to be successful. In the relational world, as an application\u2019s dataset size grows, join pains begin to manifest themselves, and performance deteriorates. Using index-free adjacency, a graph database turns complex joins into fast graph traversals, thereby maintaining millisecond performance irrespective of the overall size of the dataset.<\/p>\n Geospatial is the original graph use case: Euler solved problem of the Seven Bridges of K\u00f6nigsberg<\/a> by positing a mathematical theorem that later came to form the basis of graph theory. Geospatial applications of graph databases range from calculating routes between locations in an abstract network such as a road, rail network or logistical network to spatial operations such as find all points of interest affected by an accident outage and calculate under-utilised or under-served areas. Geospatial applications of graph databases are today particularly relevant in the areas of travel, logistics, travel, timetabling, and route planning<\/p>\n![\"\"](\"https:\/\/exmitalia.it\/wp-content\/uploads\/2016\/02\/1600x300-Key-challenge-1-mixed-mode-routing.jpg\" "\\"\\"")
<\/a><\/p>\n<\/a><\/p>\nMulti-Criteria Travel Planning<\/h3>\n
<\/a><\/p>\n<\/a><\/p>\nSegment-wise Control<\/h3>\n
\nIn a graph database model, exceptions can be easily integrated as a lightweight overlay database on top of the network nominal state. This configuration allows for fast modifications of individual segments \u2014even for just subsets of users\u2014 without perturbation of the nominal performance.<\/p>\n<\/a><\/p>\nPerformance considerations in the Swiss context<\/h3>\n
<\/a><\/p>\n
\nThese limits indicate the need for a mixed solution: an efficient index optimised for routing, and relational databases to store the large amount of data. While it could be argued that relational databases are not strictly necessary, their near ubiquity make them the natural choice to avoid further short-term costs. For what concerns the index, graph database models provide an effective solution for routing applications<\/p>\nGraph Database Models<\/h3>\n
\n
“Minutes to milliseconds” performance<\/h3>\n
Extreme business responsiveness<\/h3>\n
Drastically accelerated development cycles<\/h3>\n
Enterprise ready<\/h3>\n
Data Representation for Multimodal Routing<\/h3>\n