search

Project-OSRM / osrm-backend

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

Shortest path through specified points (that are unordered) #1704

Closed vladim1 closed 8 years ago

vladim1 commented 8 years ago

I have a source and destination points (A and B) and a few intermediate points (C, D, E, F, J...) that an object has to visit. Is there an opportunity to build a route that will calculate an optimal (shortest) route through this points if there is no order of visiting points? As I understand Dijkstra algorithm can be used to resolve this issue

daniel-j-h commented 8 years ago

This sounds similar to the Traveling Salesman Problem. With the latest v4.8.0 release we expose the trip plugin that can solve exactly those questions. The API looks like the following:

http://localhost:5000/trip?loc=52.51642978796417,13.441085815429688&loc=52.51601193890388,13.448638916015625

/cc @chaupow

vladim1 commented 8 years ago

@daniel-j-h Thanx for the response. And yes, Traveling Salesman Problem is very similar to specified issue except the fact, that the destination point differs from the start point. But I need a case with Traveling Salesman Problem also. Is there any information, when the version 4.8.0 is going to be released? As I can see all issues are already closed for this milestone.

emiltin commented 8 years ago

4.8.0 is already released.

vladim1 commented 8 years ago

Where can I find more documentation about the trip plugin? BTW, I have tried to use the link on the demo server and it didn't work.

http://router.project-osrm.org/trip?loc=52.51642978796417,13.441085815429688&loc=52.51601193890388,13.448638916015625

But then I have tried to use the link on localhost and I have gotten some result. but I don't know how to use it. So I am looking for more docs.

daniel-j-h commented 8 years ago

@TheMarex just added initial docs for the trip plugin to the Wiki, take a look: https://github.com/Project-OSRM/osrm-backend/wiki/Server-api#service-trip

The demo router at project-osrm.org currently runs on stale data and does not yet have the latest release. Bringing @freenerd into this ticket: he is currently working on resolving this; should be done in the next days.

vladim1 commented 8 years ago

OK, thanks. This is a great announcement!!

freenerd commented 8 years ago

The project-osrm.org demo server should be fixed soon again (run on develop branch with recent OSM dataset). Only waiting on @DennisOSRM here to switch the domain to new infrastructure.

TheMarex commented 8 years ago

This should be good now.