Monday, 13 February 2017

A piece of operational research (and graph theory) trivia

Graph theory was "born" with Euler's problem of the seven bridges of Königsberg.

Those seven bridges were named: Krämer, Schmiede, Holz, Hohe, Honig, Köttel and Grüne.


Tuesday, 7 February 2017

Improving the Urban Environment

"What would you do if you had a million pounds to spend on improving Exeter for cyclists?"

It was a strange question to be thrown at me in a discussion about recruiting an operational research scientist for a local enterprise.  Out of the blue I had been invited to the offices of a hi-tech company on the business park east of Exeter.  Someone there had read this blog and knew that I was interested in O.R. and lived locally, and that there are not many O.R. specialists in the city - or its environs.  The organisation wants (as of the date of writing) to recruit a modeller for sustainable transport planning, with an ambitious project in mind which would help improve the environment in various ways.  So we were talking about transport models, and the problems of a medieval city with a road system that is little changed over many years.  On top of this historic legacy, Exeter has a catchment area which stretches across a radius of 20-25 miles - and these commuters bring their cars into a city which is close to gridlock.  So obviously, making Exeter even more cycle-friendly is important, but the question came quite suddenly.  I wrote about this topic from a different perspective in this article.

I wondered if it was one of those searching interview questions that are used to see how well a candidate can think "outside the box", rather like those reputedly asked at interviews for Oxbridge colleges, or to work for dotcom giants like Google. 

So how might I spend a million pounds on improvements for cyclists?

My gut reaction was that the arterial roads should be made more cycle-friendly.  I had ridden my bicycle to the meeting, and the route-finder had shown what I already knew, that if I followed cycle-paths and quiet roads, it would be more than 10% longer in time and distance than the arterial road which is more direct.  The downside of going direct was the large number of vehicles, but I accepted that.  For some journeys in Exeter, following cycle-paths and quiet roads can be significantly longer than the direct route; sometimes it is worth it.  However I am not sure how much could be achieved with one million.

The next reaction was to use the money to provide locked cycle storage at the "Park-and-Ride" car parks on the edge of the city.  Buses run from these car parks to the city centre, and one or two major employers, but they are not convenient for everyone.  Hence offering an option for cycling rather than bus-riding.  As an extra for this, one could have bike-hire stands at the car parks; already, Exeter has some bike-hire points with electric bikes (and no doubt I will write about these in the near future).

Tina and I ran the question past each other in the evening, once I had dried out from cycling home through a storm.  Thinking outside the box, our first idea was to use the money to impose a 20mph speed limit across the whole city, which would make travel by bicycle almost as rapid as by car or bus.  We decided that an outright ban on cars would not be feasible, and too low a speed limit would annoy the motorist.

Then we proposed that the city council should send out a £25 voucher to every household in the city, to be redeemed in cycle shops for equipment - and every voucher would also qualify for as many free hi-viz jackets and sets of cycle lamps as the householder had bicycles.  (there are about 40,000 homes in the city).

Our third proposal was to require that every new house or flat should have covered storage for bicycles as a local by-law.  Here, new properties must have either a garage or a dedicated parking space.   The former would offer space for cycles, the latter would not. 

With these three off-the-wall ideas, we started to consider another aspect of the commuters into the city.  In various places in the Exeter catchment area there are ad hoc car-sharing schemes, whereby two or more drivers agree to meet at a convenient place to leave cars for the day and share the remainder of the journey.  Some of the trysting places are the park-and-ride sites which are free to use (you pay for the bus fare), some are lay-bys near road junctions, some are on patches of waste ground.  (In some countries, planners deliberately create such places to park at intersections.)  Bureaucracy has closed one local site, by imposing a two-hour maximum stay on vehicles using a lay-by.  And that is a shame.  However, we realised that several local dormitory towns have out-of-town supermarkets with car parks.  Only customers are allowed to use these spaces, and the shop imposes penalties for those who stay too long.  Some, I suspect, monitor the parking with CCTV as well as patrols.  But, suppose Exeter City Council negotiated with the store to provide a limited number of spaces for park-and-share commuters.  There would be a charge, and users would have a permit to display, but many supermarket car parks are over-designed. 

And all these thoughts stem from that one quick question.  If you are coming to Exeter for an interview about working in O.R. and sustainable transport, this may have spoilt the surprise.  But there will be others, and the bigger question - can you handle the proposed project?


Wednesday, 1 February 2017

Games that Trees Play

I never expected to find the term "Game theory" in a book about trees, but - I was wrong.  Reading Max Adams' "The Wisdom of Trees" I read the following:
Seeds and their germination ... are hailed as an example of so-called game theory, whereby (in its biological context) evolution tests all possibilities to find successful strategies for an optimum number of best-fit species. (page 59)
I'm not happy with "so-called" applied to game theory - users of the subject know what it is, and because of my faith, I would be inclined to apply the mind of God to evolution as well, but the idea is intriguing.  Adams lists six characteristics of the seeds of trees which vary to fill niches in ecology: seed size; quantity of seeds; age of first production; method or means of distribution; how the seed germinates; frequency of seed production.  The OR person spots that four of those are numerical, even if slightly fuzzy. 

The author goes on to discuss some of the varied combinations of those six characteristics which may be observed with different species.  An oak tree produces medium to large seeds, in a quantity which is somewhere between the fine dust of tens of thousands of hazel seeds and the dozens of giant nuts of a coconut palm, and starts to produce when the tree is forty years old or more - while the fruit trees in my garden produce their first crop after four or five years.

The qualitative characteristics are extremely varied.  Seed that is spread by the wind, by birds which bury the nuts and forget (or die), by being buried until there is a fire or a flood.  There are so many possibilities, and so many subtle differences between them.  As a challenge, consider two native trees that you know growing close together, and see how they compete to survive.  (Theey ought to be native, because imported plants may not fit the ecological niche here that they belong to at home.)

Adams goes on to discuss yet another dimension to ecological niches; the variation from year to year in the number of edible seeds produced by trees.  This leads into another topic from OR - predator-prey models.  If a tree species produced the same number of seeds every year, then the population of a bird or animal that fed on those seeds would tend to a stable value by Lotka–Volterra models.  The predator would consume the harvest and there would be very few seeds left to be the potential for the next generation.  So trees do not yield similar crops every year.  In some years there is a bumper harvest for future plants and the predator species, in others, the predator may be starved.  The plum trees in my garden vary in their yield, partly through natural variation from the species, partly through my intervention in pruning, and partly through the random effect of climate at the time of the plum blossom.  And my story could be repeated over countless orchards and plantations of fruit. 

Now, what is the game theory approach to weeding my garden?