Media Coverage
July 2011
Turning Bikes into Mountain Goats
It’s 1932, and Robert E. Martin - writer for the Popular Science magazine - is at an official motorcycle meet to cover an up-and-coming sport. And while the, quote, “Motorcycles, many of them carrying girls with gay knickers and wind-tanned faces”, may prove somewhat distracting, his attention is on the small group of determined bikers gathering at the bottom of an extremely steep incline made of loose dirt, dust, gravel and a defiance of gravity.
As the first modified motorcycle roars up the slope – chained back-tyre churning the surface into a fine brown haze – and, almost at the apex of the climb, dramatically flips both itself and driver backwards into the air, he thinks that maybe this “hill-climbing” thing might not be such a dud assignment after all.
Fearless Riders Turn Motor Bikes into Mountain Goats , Popular Science, August 1932
Martin’s article heading –having liberally stolen it for this month’s column - is an apt one; the idea of turning bikes into mountain goats is quite an appealing analogy to hill-climbing. It’s taking a potential solution, perhaps not ideally fit for traversing a particular space, and optimising it as best as possible for that space, and still offers one of the easiest and quickest means of providing solutions to routing problems within the vehicle routing space.
Some of these questions will no doubt be familiar to users of vehicle routing software:
- Why can’t I get the most optimal solution?
- Why is it that I can’t get the exact same schedule twice?
- Why are some schedules so much better than others for the same scenario?
- Why has Windows crashed again?
The last is a question of the ages, one of the great unanswered mysteries of our times which Microsoft will work out any day now, I’m sure. All the rest can be answered by describing the hill-climbing algorithm. Let’s take that hill bikers would be forced to climb and represent it as a mesh with various latitudes and longitudes. The peak is the destination, and the bottom of the hill is the start. Also, in the spirit of making everything extreme nowadays, all of our bikers are blindfolded.
The goal is to get to the highest peak as quickly as possible. Assuming all of the bikes travel at the same speed, it makes sense that the steepest ascent would be the quickest to the top. So the biker will attempt to make steps from their chosen point at the bottom of the hill that takes him along the steepest route.
Hill-climbing has several problems. If the hill is made up of two smaller hills, one higher than the other, our blinded bikers would have no way of knowing that the hill they’re climbing is not the most optimal. Since he’s going from point to point trying to maximise his ascent, anything that would take him downwards – but closer to the real highest hill – would seem like a step backwards. Another issue is any plateau where the changes are incrementally small. If it seems nominally flat all around, then the biker may ride for ages before finding the next decent ascent.
This is why the solution is never the same twice, why the optimal solution is often out of reach, and why one schedule can be many times better than a previous schedule for the same scenario – in order to guarantee better odds at finding the best solution, the typical vehicle hill-climbing algorithm will randomise both the path of the bikers and the starting point of the bikers to get a wider spread of results. This is known as shotgun hill-climbing, an event which fortunately doesn’t have a real-world counterpart.
So why use it, if it comes with these disadvantages? Time. Hill-climbing is useful in that it starts with a solution and tries to optimise that solution, rather than seek out ALL possible solutions before giving you an answer. You can be guaranteed a solution from the moment you start scheduling, and the more time you allow it, the better it gets. In transportation management, time is money, and anything that gives marginally small losses for more time is a bonus.If you have any comments or questions, please e-mail me at rick.de.klerk@opsi.co.za.
