Tuesday, April 03, 2018

The Brooding Goose Routing Problem

The Traveling Salesman Problem (TSP) is a well known routing problem. The TSP asks: "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 Brooding Goose Problem (BGP) is a little known routing problem. The BGP asks: "Given a list of places to avoid what is the shortest possible route from A to B which doesn't visit any of the places to avoid."

In its simplest form the BGP can be expressed as:

  • How do you get from A to B, while avoiding C. 
  • Where C = geese.

An example of the Brooding Goose Problem would be a university with a number of aggressive nesting geese dotted around the campus. In spring these brooding geese often get aggressively protective of their nests and can be known to attack students and staff who wander too near a nest. The university therefore needs an interactive routing map which can help students navigate around campus while avoiding the said brooding geese.

Back in 2013 the University of Waterloo devised an interactive map that included a solution to the Brooding Goose Problem. Their map allowed students to find the quickest route between two locations on campus while avoiding the known locations of all nesting geese.

The University of Waterloo's GooseWatch is now back for the sixth consecutive year. This year's map shows the locations of all known nesting geese. It also allows you to view the locations where geese have been known to nest in previous years. At the heart of the interactive map is the BGP routing engine which helps you avoid the brooding geese. The search engine even allows you to define how scared of geese you are - which it then takes into consideration when suggesting a requested route around campus.

No comments: