We now have wonderful mapping tools with
Google Maps and the likes, GPS units in our cars, or mapping programs we can install on our computers. But I've never been really satisfied with those tools when it comes to planning a trip and choosing a route...
Those tools generally offer control on whether you want the shortest or the quickest route, with or without highways, but that's pretty much all... Google Maps now offers one or two alternative routes, which is a good step, but I still think it's not enough.
Let's take an example... To go from Antibes to Méribel-Les-Allues (in the French Alps, approx 206 km from Antibes on straight line, but with the mountains in between), there are many possible routes. The shortest one is 385 km, for a duration of 6h49. The quickest one lasts 5h19, for 566 km. Most GPS units will be able to give you those two routes, but there are many others...
Wouldn't it be nice if, after giving those two routes, the unit would ask you if you want to look for a compromise between the two? This should give you a route that's shorter than 566 km, and quicker than 6h49, if there are some. It could e.g. give you the route that's 405 km for 5h57.
Those three routes would be displayed in a table, ordered by distance or by duration, to your choice. For each couple of consecutive routes, you could ask the unit to look for another compromise between the two selected routes, and this would display a new route in the table, with both the distance and the time in the interval defined by the two previously selected routes. Or, if there is no such route, this pair would not be selectable any more.
You would end up with a set of routes that represent different ways to compromise between the two inherently conflicting goals that are distance and duration... For my example trip, such a table would have entries like :
| 566 km | 5h19 |
| 530 km | 5h34 |
| 405 km | 5h57 |
| 385 km | 6h49 |
A route that is 512 km and lasts 6h03 would not be displayed: its distance is between the pair 530...405, but it's duration is larger than both: it's clearly not a good compromise in terms of time and distance...
Of course, the nec-plus-ultra would be to compute the cost of the trip, rather than the distance, taking distance, fuel consumption and tolls into account. One site I know that computes such costs is
ViaMichelin. In this case, the quickest route costs 98€, and the economical route costs 42€. But am I ready to spend 1h30 more in my car, for a total of more than 7 hours? Not sure, if the kids are in the car... And that's when I'd really like to know if there is a route that's much less expensive than the quickest one, for only slightly more time...
All the data is there... Why don't we get those informations?
Finding the compromisesFinding the best route in terms of distance
or time is known as solving a
Shortest Path Problem. In our case, we want to simultaneously take into account two conflicting objectives, so we have a
Multi-Objective problem. Sophisticated techniques have been devised for such problems, but maybe we can limit ourselves to a simple one...
Let's suppose that, for each route segment, we know the time and the distance. We can then compute any combination of the two. Let
x be a number between
0 and
1. For each route segment, let's denote
t the time it takes, and
d its distance. Instead of either the distance
d or the time
t, let's now give, as input to the shortest path algorithm, the value
x.t + (1-x)d. For
x=0, the result is the shortest path. For
x=1, the result is the quickest path. For any value in between, the result is either the shortest path, or the quickest one, or a compromise between both.
To each value of
x, we can thus associate a route. The unit first computes the routes for for
x=0 and
x=1. When the user asks for a compromise between two routes, those two routes define the interval
x1..x2 that the unit must explore with a dichotomy. We start with
(x1+x2)/2, and see which route this gives. If it's the same than for
x1, we know that the compromize we want, if it exists, is between
(x1+x2)/2 and
x2. If it's the same than for
x2, we know that we have to look between
x1 and
(x1+x2)/2. If it's neither, then we've just found a new route that we can display to the user. If the interval between the two values becomes too small, then we can stop the search and notify that it was not possible to find a compromise between the two routes.
Pretty simple, no?
And given the fact that recent computers can compute routes between any two points on a continent in around 1/10th of a second, it should be possible to answer in less than one second for each compromize sought... A GPS unit would probably need more time, but only the users willing to wait would have to...
In a few seconds, the user would get a list of possible compromise, and would be in the position to choose with much more informations...
