Tuesday, April 30, 2013

Solving the Brooding Goose Problem

The 'Travelling Salesman Problem' is a well known routing problem. Basically the travelling salesman problem is: "Given a list of destinations, what is the shortest possible route that visits each destination exactly once and returns to the original starting point?"

The latest Google Maps based solution to the travelling salesman problem that I've found is Speedy Route. Speedy Route is a world-wide route planner that integrates with Google Directions to find the shortest route for a number of planned destinations.

Beginning at your start location, Speedy Route calculates a route that visits every other location you provide exactly once, before finally returning to your start location to finish, all by the shortest and quickest route possible. Speedy Route also provides the driving directions as supplied by Google Directions for the entire calculated route.

I have been wondering for a while, however, about what the opposite routing problem is called. What if you need to find a route that avoids certain locations along a planned route? In honour of the University of Waterloo, I'm calling this the 'Brooding Goose Problem'.

The University of Waterloo set themselves the problem of devising a campus routing solution that shows the quickest route between two locations that avoids the known locations of goose nests on the campus.

To help students and staff who are frightened of geese the university have created the Goose Nest Avoider. Using ESRI Maps the Goose Nest Avoider allows users to select a starting point and a destination from two drop down menus and then displays an optimal route that steers clear of any nesting geese.

1 comment:

Josh said...

Nice, I like your name for this routing problem.

Just as an FYI, note that for the Traveling Salesman problem, the Google Maps API itself allows you to optimize the waypoints by adding "optimize:true" to your directions request.

See http://googlegeodevelopers.blogspot.com/2010/03/good-day-for-salesmen-that-travel-on.html for a demo, and https://developers.google.com/maps/documentation/directions/#Waypoints for a code example.

Also https://plus.sandbox.google.com/+ResearchatGoogle/posts/fcDYLZjHnRj for extra credit if you're interested in how it's done.