Open Source Routing Machine

Last updated
Open Source Routing Machine (OSRM)
Original author(s) Dennis Luxen, Christian Vetter
Stable release
5.27.1 [1]   OOjs UI icon edit-ltr-progressive.svg / 14 October 2022;22 months ago (14 October 2022)
Repository
Written in C++
Operating system Linux, FreeBSD, OS X, Windows
Type Route planning software
License Simplified BSD License [2]
Website project-osrm.org OOjs UI icon edit-ltr-progressive.svg

The Open Source Routing Machine or OSRM is a C++ implementation of a high-performance routing engine for shortest paths in road networks. Licensed under the permissive 2-clause BSD license, OSRM is a free network service. OSRM supports Linux, FreeBSD, Windows, and Mac OS X platform.

Contents

Overview

It combines sophisticated routing algorithms with the open and free road network data of the OpenStreetMap (OSM) project. Shortest path computation on a continental sized network can take up to several seconds if it is done without a so-called speedup-technique. OSRM uses an implementation of contraction hierarchies and is able to compute and output a shortest path between any origin and destination within a few milliseconds, whereby the pure route computation takes much less time. Most effort is spent in annotating the route and transmitting the geometry over the network.

Since it is designed with OpenStreetMap compatibility in mind, OSM data files can be easily imported. A demo installation is sponsored by Karlsruhe Institute of Technology and previously by Geofabrik. The screen shot image shown is since September 2015 out of date with loss of attendant routing service features.

OSRM was part of the 2011 Google Summer of Code class. [3]

Features

Screenshot showing a route with multiple waypoints T0611 route.png
Screenshot showing a route with multiple waypoints

See also

Related Research Articles

<span class="mw-page-title-main">Minix</span> Unix-like operating system

MINIX is a Unix-like operating system based on a microkernel architecture. Since version 2.0, it has been POSIX compliant.

The MIT License is a permissive software license originating at the Massachusetts Institute of Technology (MIT) in the late 1980s. As a permissive license, it puts very few restrictions on reuse and therefore has high license compatibility.

<span class="mw-page-title-main">Apache License</span> Free software license

The Apache License is a permissive free software license written by the Apache Software Foundation (ASF). It allows users to use the software for any purpose, to distribute it, to modify it, and to distribute modified versions of the software under the terms of the license, without concern for royalties. The ASF and its projects release their software products under the Apache License. The license is also used by many non-ASF projects.

<span class="mw-page-title-main">Scsh</span> Unix shell

Scsh is computer software, a type of shell for an operating system. It is a Portable Operating System Interface (POSIX) application programming interface (API) layered on the programming language Scheme, in a manner to make the most of Scheme's ability for scripting. Scsh is limited to 32-bit platforms but there is a development version against the latest Scheme 48 that works in 64-bit mode. It is free and open-source software released under the BSD-3-Clause license.

<span class="mw-page-title-main">Far Manager</span> File and archive manager for Microsoft Windows

Far Manager is an orthodox file manager for Microsoft Windows and is a clone of Norton Commander. Far Manager uses the Win32 console and has a keyboard-oriented user interface.

<span class="mw-page-title-main">BitlBee</span> Open-source cross-platform IRC gateway

BitlBee is a cross-platform IRC instant messaging gateway, licensed under the terms of the GNU General Public License.

Portable Batch System is the name of computer software that performs job scheduling. Its primary task is to allocate computational tasks, i.e., batch jobs, among the available computing resources. It is often used in conjunction with UNIX cluster environments.

SIMH is a free and open source, multi-platform multi-system emulator. It is maintained by Bob Supnik, a former DEC engineer and DEC vice president, and has been in development in one form or another since the 1960s.

The Ruby License is a Free and Open Source license applied to the Ruby programming language and also available to be used in other projects. It contains an explicit dual licensing clause, stating that software subject to its terms may be distributed under either the terms included in the Ruby License itself or under those of either the GNU General Public Licence v2, or the two-clause BSD License.

Enthought, Inc. is a software company based in Austin, Texas, United States that develops scientific and analytic computing solutions using primarily the Python programming language. It is best known for the early development and maintenance of the SciPy library of mathematics, science, and engineering algorithms and for its Python for scientific computing distribution Enthought Canopy.

BSD licenses are a family of permissive free software licenses, imposing minimal restrictions on the use and distribution of covered software. This is in contrast to copyleft licenses, which have share-alike requirements. The original BSD license was used for its namesake, the Berkeley Software Distribution (BSD), a Unix-like operating system. The original version has since been revised, and its descendants are referred to as modified BSD licenses.

Mapnik is an open-source mapping toolkit for desktop and server based map rendering, written in C++. Artem Pavlenko, the original developer of Mapnik, set out with the explicit goal of creating beautiful maps by employing the sub-pixel anti-aliasing of the Anti-Grain Geometry (AGG) library. Mapnik now also has a Cairo rendering backend. For handling common software tasks such as memory management, file system access, regular expressions, and XML parsing, Mapnik utilizes the Boost C++ libraries. An XML file can be used to define a collection of mapping objects that determine the appearance of a map, or objects can be constructed programmatically in C++, Python, and Node.js.

In computer science, the method of contraction hierarchies is a speed-up technique for finding the shortest-path in a graph. The most intuitive applications are car-navigation systems: a user wants to drive from to using the quickest possible route. The metric optimized here is the travel time. Intersections are represented by vertices, the road sections connecting them by edges. The edge weights represent the time it takes to drive along this segment of the road. A path from to is a sequence of edges ; the shortest path is the one with the minimal sum of edge weights among all possible paths. The shortest path in a graph can be computed using Dijkstra's algorithm but, given that road networks consist of tens of millions of vertices, this is impractical. Contraction hierarchies is a speed-up method optimized to exploit properties of graphs representing road networks. The speed-up is achieved by creating shortcuts in a preprocessing phase which are then used during a shortest-path query to skip over "unimportant" vertices. This is based on the observation that road networks are highly hierarchical. Some intersections, for example highway junctions, are "more important" and higher up in the hierarchy than for example a junction leading into a dead end. Shortcuts can be used to save the precomputed distance between two important junctions such that the algorithm doesn't have to consider the full path between these junctions at query time. Contraction hierarchies do not know about which roads humans consider "important", but they are provided with the graph as input and are able to assign importance to vertices using heuristics.

<span class="mw-page-title-main">OsmAnd</span> Offline maps & navigation Android and iOS app

OsmAnd is a map and navigation app for Android and iOS. It uses the OpenStreetMap (OSM) map database for its primary displays, but is an independent app not endorsed by the OpenStreetMap Foundation. It is available in both free and paid versions; the latter unlocks the download limit for offline maps and provides access to Wikipedia points of interest (POIs) and their descriptions from within the app. Map data can be stored on the device for offline use. Using the device's GPS capabilities, OsmAnd offers routing, with visual and voice guidance, for car, bike, and pedestrian. All of the main functionalities work both online and offline.

Mapbox is an American provider of custom online maps for websites and applications such as Foursquare, Lonely Planet, the Financial Times, The Weather Channel, Instacart, Strava and Snapchat. Since 2010, it has rapidly expanded the niche of custom maps, as a response to the limited choice offered by map providers such as Google Maps.

<span class="mw-page-title-main">GraphHopper</span>

GraphHopper is an open-source routing library and server written in Java and provides a routing API over HTTP. It runs on the server, desktop, Android, iOS or Raspberry Pi. By default OpenStreetMap data for the road network and elevation data from the Shuttle Radar Topography Mission is used. The front-end is open-source too and called GraphHopper Maps.

The following table compares notable software frameworks, libraries and computer programs for deep learning.

<span class="mw-page-title-main">RocksDB</span> Embedded key-value database

RocksDB is a high performance embedded database for key-value data. It is a fork of Google's LevelDB optimized to exploit multi-core processors (CPUs), and make efficient use of fast storage, such as solid-state drives (SSD), for input/output (I/O) bound workloads. It is based on a log-structured merge-tree data structure. It is written in C++ and provides official language bindings for C++, C, and Java. Many third-party language bindings exist. RocksDB is free and open-source software, released originally under a BSD 3-clause license. However, in July 2017 the project was migrated to a dual license of both Apache 2.0 and GPLv2 license. This change helped its adoption in Apache Software Foundation's projects after blacklist of the previous BSD+Patents license clause.

Open Service Mesh (OSM) was a free and open source cloud native service mesh developed by Microsoft that ran on Kubernetes.

References

  1. "Release 5.27.1". 14 October 2022. Retrieved 24 October 2022.
  2. "osrm-backend/LICENSE.TXT at master · Project-OSRM/osrm-backend · GitHub". GitHub . 26 April 2020.
  3. "Improvements to the Open Source Routing Machine (OSRM)". Archived from the original on 2013-12-19.

As of 18 May 2012, this article is derived in whole or in part from Open Source Routing Machine . The copyright holder has licensed the content in a manner that permits reuse under CC BY-SA 3.0 and GFDL. All relevant terms must be followed.

Further reading