Senji (senji) wrote,

  • Mood:

Map Annealing

diziet and emperor were talking about Simulated Annealing as a tool in Automatic Graph Drawing Algorithms on Monday night, and it's just struck me that a similar process seems to operate in finding routes between places.

This map shows routes from Girton (off the top left) to the Grafton Centre, in Cambridge.
(1) is my initial "naïve" route; which is probably the shortest, but one runs into too many pedestrians and traffic-lights.
(2) is my first revision, based mainly on the fact that I tend to turn down Oxford Road to get to a lot of other places, but as is clearly visible from the map (if not my head) it's much further).
(3) describes a simple optimisation to (2) that turns out to be generally helpful.
(4) was the next approach, but I quickly realised that the optimisation (5) that I used to use from Darwin Drive was still applicable.
(6) is the route I currently use, I think it's probably the most optimal, particularly since if the traffic is heavy at the turn-off point you can revert to (5).
(7) is a rejected optimisation to (2) that experimentally took longer than the original.

  • Post a new comment


    default userpic
    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.