search

Project-OSRM / osrm-backend

Open Source Routing Machine - C++ backend
http://map.project-osrm.org
BSD 2-Clause "Simplified" License
6.19k stars 3.29k forks source link

Why OSRM implemented Contraction Hierarchies and MLD instead of A* or something? #5443

Closed rachha closed 5 years ago

rachha commented 5 years ago

I'm going through the OSRM implementation; they implemented routing algorithms CH and MLD. I wanted to know the motivation behind it to use these algorithms. This question not supposed to post here, but I didn't get any responses in StackOverflow, so.

danpat commented 5 years ago

@rachha OSRM was originally build by @DennisOSRM, I believe alongside his research work into CH networks. Initially, it only had a CH implementation. Since then, many features have been added, including the MLD graph. Nobody needed A*, so it was never added. 🤷‍♂

@TheMarex worked on a proof-of-concept A* implementation here - https://github.com/Project-OSRM/osrm-backend/tree/algorihm/astar, but it never made it into the mainline.