The Problem Lies with the Selection of Weights!
It has been a solid week of work. The stage has been set and the journey has already begun towards building a customised running App for the city of Ghent. Following the initial iterations based on the meeting with the partners, the focus of LopenInGent has slightly shifted gears into building a solid technical solution for our Running application.
Although there are a number of route generation applications, one of the major areas of interest we are working on is customisation of the route generation process based on user preferences. Essentially we are aiming at dynamically generating routes, that could safely route the user through specified Points of Interest (or POI’s).
There was an interesting bug while implementing our algorithm for which Peter Stroobant from Gent University gave a fitting explanation and a way to solve the problem. The problem and the explanation goes like this:
Our primary algorithm uses the shortest path algorithm to calculate both the forward path and the return path. The most straightforward way to influence the resulting routes is by making roads with POI’s more attractive, that is, by decreasing the weight associated with these roads. When thinking about assigning weights to these roads based on certain features (such as the presence of a forest, POI’s), you should always ask yourself the following question: ‘Is my weight assigning scheme independent of the number of nodes/edges used to represent a road?‘. The weight selection and assignment scheme MUST have this property, otherwise the routing algorithm will systematically favour tours with more/less edges over tours with less/more edges!.
Both of these graph representations represent the same real-world situation (they represent the same path along the river), so the weight of the edge in the left situation should equal the combined weight of the three edges in the right situation. What does this teach us?
Let’s say that we want to incorporate the effect of being close to a waterway. Note that this property is shared by all three edges on the right. This means that we cannot decrease the weight of an edge by a constant number if the edge is close to water. If we would do this, the three edges on the right would be more attractive than the single edge on the left. In fact, the only way that we can incorporate this property is by making the change in weight proportional to the length of the edge.
For a POI on the other hand, the situation is very different. If there was for example a chapel halfway along this path, then in the right diagram, only the middle edge would have the ‘chapel’ property. This means that the effect of a POI must be a constant change of the edge weight.
It was an important lesson learnt that helped us shape our algorithm to generate routes through a given set of POI list.