Finding the Spectacle

Part of the issue of conveying how interesting routing and scheduling can be, is that routing and scheduling problems – and the mathematical challenges involved in solving them - don’t lend themselves to spectacle, especially when in placed in the context of trucks and parcels.

The more interesting reason is that it is innate to human beings to try and find the shortest route that ensures maximum benefit. It is so common that any discussion related to it seems elementary. ‘There are no shortcuts’, people say, yet we try to find them regardless, and the dual nature of this drive has brought out the worst and the best in us.

It also means that you will see the same routing problems fleet managers, planners and controllers tackle on a professional basis are often being similarly approached - on an amateur but no less dedicated level - in other areas.

When searching for route optimisation news online, I stumbled across a forum post discussing the Travelling Salesmen Problem. Nothing new, really – we’ve discussed it previously in this column - but what made this interesting was that it was in the context of a massively multiplayer online game, EVE Online. EVE Online is an intergalactic space simulation where nearly 300 000 players can fight, explore and trade with each other between prolific galaxies and star systems.

Curious, I decided to delve into it a little more. It became apparent that a core component of the game was trading between amongst individual players, corporations and factions, and that the players took it seriously enough that virtual wars were often fought over the well-known profitable routes and newly discovered paths where jealously guarded from prying eyes.

The in-built route mapping system for players uses a modified version of Dijkstra's algorithm: a method of calculating the shortest route between all the nodes on a graph.

However, enterprising players have created their own route finders that feature varying algorithms and search methods, such as A* and Breadth-First, and also factor in various variables – the hold capacity of their star ships, the maximum warp jump distances their fleets are capable of, the choice to minimise the number of jumps against the distance between way points and the security rating of the route, amongst others.

Some of the players demonstrate a good understanding of the algorithms that drive these route finders, but many have designed or created applications or spreadsheets with seemingly no prior knowledge or background in this area of research.

That they are tackling concepts we deal with on a day-to-day basis - often unknowingly employing quite complicated algorithms to do so - for no purpose other than enjoyment (and to gain an edge) in a game is inspiring and instructive. While you might not have anything as grand as intergalactic ascendance to spur you on, fleet managers, planners and controllers can benefit from taking a time out, stepping back from their workplace and exploring freely.

Contributed by: Rick de Klerk, Technical Writer, Opsi Systems