Open Source Routing Machine: Difference between revisions

Revision as of 16:02, 5 June 2012

Latest revision as of 23:46, 3 May 2025

(60 intermediate revisions by 41 users not shown)

Line 1:

{{Infobox software

{{tocright}}

| name = Open Source Routing Machine

The '''Open Source Routing Machine''' or '''OSRM''' is a [[C++]] implementation of a high-performance routing engine for [[shortest path]]s in [[road]] [[network]]s. Licensed under the [[Affero General Public License]], OSRM is a free network service.

| logo = Open Source Routing Machine logo.png

| logo size = 220px

| screenshot = OSRM screenshot.png

| screenshot size = 220px

| caption = Demo site as of 2014

| collapsible =

| author = Dennis Luxen, Christian Vetter

| developer =

| latest release version = {{wikidata|property|edit|reference|P348}}

| latest release date = {{start date and age|{{wikidata|qualifier|P348|P577}}}}

| operating_system = [[Linux]], [[FreeBSD]], [[OS X]], [[Microsoft Windows|Windows]]

| programming_language = [[C++]]

| genre = [[Route planning software]]

| license = [[BSD licenses#2-clause license ("Simplified BSD License" or "FreeBSD License")|Simplified BSD License]]<ref>{{Cite web | url=https://github.com/Project-OSRM/osrm-backend/blob/master/LICENSE.TXT |title = osrm-backend/LICENSE.TXT at master · Project-OSRM/osrm-backend · GitHub |website = [[GitHub]] |date = 26 April 2020}}</ref>

| website = {{ConditionalURL}}

}}{{More citations needed|date=May 2021}}

The '''Open Source Routing Machine''' (abbreviated '''OSRM''') is an [[Open-source software|open-source]] [[Journey planner|route plan]]ning [[Library (computing)|library]] and [[network service]]. Written in high-performance [[C++]], OSRM runs on the Linux, FreeBSD, Windows, and macOS platforms. It is designed for compatibility with [[OpenStreetMap]]'s road network data. FOSSGIS operates a free-to-use server that powers walking, cycling, and driving directions on OSM's homepage.

==Overview==

It combines sophisticated [[routing algorithm]]s 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 miliseconds, whereby the pure route computation takes much less time. Most effort is spent in annotating the route and transmitting the geometry over the network.

==History==

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. OSRM is under active development.

OSRM powered [[Mapbox]]'s navigation offerings during the 2010s.<ref>{{cite web|title=Smart Directions Powered by OSRM’s Enhanced Graph Model|first=Dennis|last=Luxen|work=maps for developers|publisher=Mapbox|___location=Washington, D.C.|date=30 January 2014|accessdate=3 May 2025|url=https://blog.mapbox.com/smart-directions-powered-by-osrms-enhanced-graph-model-3ae226974b2}}</ref> OSRM participated in the 2011 [[Google Summer of Code]].<ref>{{cite web |url=http://www.google-melange.com/gsoc/project/google/gsoc2011/bharathv/13001 |title=Improvements to the Open Source Routing Machine (OSRM). |url-status=dead|archive-url=https://web.archive.org/web/20131219012603/http://www.google-melange.com/gsoc/project/google/gsoc2011/bharathv/13001|archive-date=2013-12-19 }}</ref> In February 2015, OSRM was integrated into OpenStreetMap's homepage alongside two other routing engines, [[GraphHopper]] and Valhalla.<ref>{{Cite news |last=Filney |first=Klint |title=Out in the Open: How to Get Google Maps Directions Without Google |url=https://www.wired.com/wiredenterprise/2013/11/osrm |access-date=11 November 2013 |newspaper=[[Wired (magazine)|Wired]] |date=11 November 2013 |archive-date=11 November 2013 |archive-url=https://web.archive.org/web/20131111175911/http://www.wired.com/wiredenterprise/2013/11/osrm/ |url-status=live }}</ref><ref>{{Cite web |title=Routing on OpenStreetMap.org|work=OpenStreetMap Blog|publisher=OpenStreetMap Foundation|___location=Cambridge|url=https://blog.openstreetmap.org/2015/02/16/routing-on-openstreetmap-org/ |url-status=live |archive-url=https://web.archive.org/web/20150301204509/https://blog.openstreetmap.org/2015/02/16/routing-on-openstreetmap-org/ |archive-date=1 March 2015 |access-date=28 April 2015}}</ref> In 2025, a team at [[Roskilde University]] and the [[University of Waterloo]] used OSRM to solve the [[travelling salesman problem]] for a dataset of 81,998 bars from South Korea's [[National Police Agency (South Korea)|National Police Agency]], breaking a record set in 2021.<ref>{{cite web|title=korea81998|work=Traveling Salesman Problem|publisher=[[University of Waterloo]]|___location=Waterloo, Ontario|date=9 April 2025|accessdate=3 May 2025|url=https://www.math.uwaterloo.ca/tsp/korea/}}</ref>

==Architecture==

OSRM was part of the 2011 [[Google]] [[Summer of Code]] class.<ref>[http://www.google-melange.com/gsoc/project/google/gsoc2011/bharathv/13001 "Improvements to the Open Source Routing Machine (OSRM)."] [http://www.google-melange.com Google Summer of Code 2011]. Accessed May 2012.</ref>

ItOSRM combinesimplements sophisticatedmultilevel [[routingDijkstra's algorithm]]s with(MLD) theas openwell andas freeanother road[[routing network data of thealgorithm]], [[OpenStreetMapcontraction hierarchies]] (OSMCH), which is better suited for very large distance projectmatrices. Shortest path computation on a continental sized network can take up to several seconds if it is done without a so-called speedup-technique. OSRMVia usesthe anCH implementationpreprocessing ofpipeline, [[ContractionOSRM Hierarchies]] and is able tocan compute and output a shortest path between any origin and destination within a few milisecondsmilliseconds, whereby the pure route computation takes much less time. Most effort is spent in annotating the route and transmitting the geometry over the network. This high performance facilitates use cases such as user-interactive route manipulation.

In addition to solving the [[shortest path problem]] for [[road network]]s, OSRM also includes a [[map matching]] service and a [[travelling salesman problem]] solver for generating [[Distance matrix|distance matrices]].

==Features==

* 'Click-to-Drag' dynamic routing, ala [[Google Maps]].

* [[Free and Open Source]] under the [[Affero General Public License]].

==See also==

{{ports|align=left|Computing}}

{{-}}

==References==

{{reflist}}

:{{Dual|source=Open Source Routing Machine|sourcepath=http://project-osrm.org/|date=201218 May 182012}}

===Additional sources===

* {{de icon}} {{cite web | url=https://www.legato.net/download/attachments/2555944/2011_FOSSGIS_Tagungsband.pdf#page=41 | title=MoNav & OSRM: 1 Jahr später | publisher=[https://www.legato.net Legato.net] | date=2011 | accessdate=May 16, 2012 | author=Christian Vetter, Dennis Luxen | pages=42-43}}

==Further reading==

* {{de icon}} {{cite web | url=http://andreas-hubel.de/ba/ba_V2.0.pdf#page=17 | title=Webbrowserbasierte Indoor-Navigation für mobile Endgeräte auf Basis der OpenStreetMap | publisher=[http://andreas-hubel.de Andreas-hubel.de] | date=November 15, 2011 | accessdate=May 16, 2012 | author=Hubel, Andreas | pages=7-8}}

* {{cite web | url=https://www.legato.net/download/attachments/2555944/2011_FOSSGIS_Tagungsband.pdf#page=41 | title=MoNav & OSRM: 1 Jahr später | website=Legato.net | year=2011 | access-date=May 16, 2012 | last1=Vetter | first1=Christian | last2=Luxen | first2=Dennis | pages=42–43 | language=de | archive-url=https://web.archive.org/web/20141005085133/https://www.legato.net/download/attachments/2555944/2011_FOSSGIS_Tagungsband.pdf#page=41 | archive-date=October 5, 2014 | url-status=dead }}

* {{de icon}} {{cite web | url=http://www.andreas-hubel.de/ba/ba_V2.0.pdf#page=17 | title=Webbrowserbasierte Indoor-Navigation für mobile Endgeräte auf Basis der OpenStreetMap | publisherwebsite=[http://andreas-hubel.de Andreas-hubel.de] | date=November 15, 2011 | accessdateaccess-date=May 16, 2012 | authorlast1=Hubel, | first1=Andreas | pages=77–8 | language=de | archive-8url=https://web.archive.org/web/20151222105921/http://www.andreas-hubel.de/ba/ba_V2.0.pdf#page=17 | archive-date=December 22, 2015 | url-status=dead }}

* {{cite book | chapter-url=http://dl.acm.org/citation.cfm?id=2094062 | chapter=Real-time routing with OpenStreetMap data | publisher=[[Association for Computing Machinery]] | date=November 6, 2011 | access-date=February 5, 2013 | last1=Vetter | first1=Christian | last2=Luxen | first2=Dennis | title=Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems | pages=513–516| doi=10.1145/2093973.2094062 | isbn=9781450310314 | s2cid=7289832 }}

==External links==

* [http://project-osrm.org/ Project homepage]

** [http://map.project-osrm.org/ Demonstration from the project's homepage]

* [https://github.com/DennisOSRM/{{Github|Project-OSRM Project-OSRM at Github]}}

* {{Twitter}}

* [https://twitter.com/#!/ProjectOSRM Project-OSRM at Twitter]

{{OpenStreetMap}}

[[Category:Routing software]]

[[Category:RoutingFree software programmed in C++]]

[[Category:OpenStreetMap]]

[[Category:RoutingRoute planning software]]

[[Category:Web mapping]]

[[Category:Software using the BSD license]]

{{Free-software-stub}}

:{{Dual|source=Open Source Routing Machine|sourcepath=http://project-osrm.org/|date=2012 May 18}}