Open Source Routing Machine: Difference between revisions

Revision as of 23:33, 3 May 2025

Latest revision as of 23:46, 3 May 2025

(4 intermediate revisions by the same user not shown)

Line 1:

{{Infobox software

| name = Open Source Routing Machine (OSRM)

| logo = Open_Source_Routing_Machine_logoOpen Source Routing Machine logo.png

| logo size = 220px

| screenshot = OSRM screenshot.png

Line 18:

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

The '''Open Source Routing Machine''' (abbreviated '''OSRM''') is an [[Open-source software|open-source]], high-performance[[Journey planner|route plan]]ning [[Library (computing)|library]] and [[network service]] for finding [[Shortest path problem|shortest paths]] in [[road network]]s. 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.

==History==

During the 2010s, 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 implements multilevel [[Dijkstra's algorithm]] (MLD) as well as another [[routing algorithm]], [[contraction hierarchies]] (CH), which is better suited for very large distance matrices. Shortest path computation on a continental sized network can take up to several seconds if it is done without a so-called speedup-technique. Via the CH preprocessing pipeline, OSRM can 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. 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]].

==References==

Line 44:

* {{Twitter}}

{{OpenStreetMap}}

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

[[Category:OpenStreetMap]]