1
$\begingroup$

Let's imagine a situation in order to fully understand the problem : let's say a lone human is walking back home at a very late time. He needs to find the safest path home. He naturally use the GPS with a start point A and a destination point B. Now the data I have may be GPS locations with an information stating the danger of that location, and those datas are usually available for the whole city. How can I actually plot the safest and also (if possible) fastest route from A to B using my datas ?

I actually looked for the way google maps plot it's routes and I understood it used the Dijkstra's algorithm, but it doesn't seem to be adapted to my problem.

I believed google maps could actually send me back every possible routes from A to B, then I could use my datas to calculate the safest route using a TSP algorithm (probably the ACS applied to the TSP) in order to optimize the use of the datas and with edge weights corresponding to the associated safety of the sub-path ?

Or maybe another algorithm should be used ?

Improve this question
$\endgroup$
4
  • $\begingroup$ What is "safest"? $\endgroup$
    – Yuval Filmus
    Commented Nov 16, 2017 at 21:02
  • $\begingroup$ Just noticed it could cause confusion. "Safest" here means the route which is the less dangerous for the person to take. $\endgroup$
    – naifmeh
    Commented Nov 16, 2017 at 21:03
  • 1
    $\begingroup$ This begs the question. Given two routes, which is more dangerous? $\endgroup$
    – Yuval Filmus
    Commented Nov 16, 2017 at 21:06
  • $\begingroup$ To me, a route is more dangerous when it's danger level is high and the distance between A and B is high as well. Let's take two routes, one that has a danger level of 10 and one of 8. First's distance is 10 km and second is 100 km. To me the second one would be the most dangerous. $\endgroup$
    – naifmeh
    Commented Nov 16, 2017 at 21:20

1 Answer 1

Reset to default
2
$\begingroup$

The answer depends on what you mean by "safest".

According to one interpretation, each short stretch of the route has a "danger" rating, and the overall danger of a route is the sum of the dangers of the individual stretches. In this case your problem is just shortest path in disguise – given each edge a weight according to its danger. If you want to consider both the danger level and the length, assign the weights as some linear combination of the two.

According to another interpretation, the danger of a route is the maximum of the dangers of the individual stretches. In this case you can use binary search to reduce your problem to shortest path. Given a danger level $D$, you can compute the shortest distance that only goes through edges of danger at most $D$. In this way you can find the minimal $D$ for which it is possible to get from A to B, as well as (for example) the minimal $D$ for which it is possible to get from A to B using a path at most twice the distance from A to B.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Actually the closest interpretation to my problem would be the first which makes it sound pretty easy to solve. But what if I have more than 5000 individual data points and need to find both a "rational" route - i.e a route that may actually be provided by a reliable gps service provider such as Google Maps - and at the same time the "safest" path. Because with 5000 points that are disposed all around the city, I could end up with a simple itinerary such as going from a point A to B that could be done in five minutes, being really complex. $\endgroup$
    – naifmeh
    Commented Nov 16, 2017 at 21:18
  • $\begingroup$ Routes provided by "reliable GPS service providers" (by the way, the only GPS service provider is the US government) are often also circuitous. Perhaps you can make the route more "reasonable" using postprocessing, but it's very hard to solve real-world engineering problems on this platform, especially if they aren't really well-defined. $\endgroup$
    – Yuval Filmus
    Commented Nov 16, 2017 at 21:27
  • $\begingroup$ What about using Dikstra's algorithm in order to find multiples shortest routes (eliminating one route after the finding and resolving the algorithm again for N routes) then using a "shortest path algorithm" to solve the problem ? One of the issue here would be the really high computing time but that could be optimized. $\endgroup$
    – naifmeh
    Commented Nov 16, 2017 at 21:50
  • $\begingroup$ Your problem isn't well-defined, so doesn't have any "correct" solution. You should just experiment with a few alternatives to see what seems to work best. $\endgroup$
    – Yuval Filmus
    Commented Nov 16, 2017 at 22:06
  • $\begingroup$ That's what I will do ! Thank you for your time ! $\endgroup$
    – naifmeh
    Commented Nov 16, 2017 at 22:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.