Transcript Slides (PPT 6.03Mb)

Air Miles
Find the best route
Maths and transport
• Planning the best routes for
your company to fly or drive
• Detecting when people
pose a threat to security on
the Tube - CCTV analysis
• Designing new technologies
to make transport faster
and more energy efficient
The travelling salesman problem
Given a number of cities
and the costs of
travelling from any city to
any other city, what is
the least-cost round-trip
route that visits each of
the cities?
Air miles
Scaling up
• With these nine cities it’s not too hard to
work out some possible cheapest routes.
• With 90 cities you’d use a computer, but
how long would it take?
• For 9 cities, 362 880 possible routes.
• For 90 cities, 90! = 90 x 89 x 88 x … x 1
= 1.49 x 10138 routes.
A “good enough” answer
• When you were choosing
your route you didn’t have
time to check every route
• Instead, you may have tried
a route which looked
sensible and made small
changes to see if they made
a cheaper route
Computer methods
• Modern methods can find
solutions for extremely large
problems – millions of cities!
– within a few minutes.
• Such solutions have a high
probability of being just two
or three percent away from
the best solution.
Biology, physics and all that jazz
• What makes a good method
for solving problems like
finding the cheapest route?
• Mathematicians have taken
inspiration from biology,
physics and even jazz music
to find good methods.
Method 1: Survival of the Fittest
• Pick some routes at random
• Keep the best of those
• Create a new generation by
breeding routes together
• Throw away the bad routes
• Have some random
mutations each generation
• Thousands of generations
later, you get good routes!
Method 2: Simulated annealing
• Annealing: heat a material
like steel or glass and then
cool it, to make it softer.
• Simulated annealing
exposes a "solution" to
"heat" and cools producing
a better solution.
Method 3: Harmony search
• In jazz music each musician
tunes their notes to find a
best harmony all together.
• You can imagine each city
having preferred previous
and next destinations that
“sound better”.
• It’s possible to make this
work mathematically!
Where’s this maths used?
•
•
•
•
•
•
•
Water distribution
Computer network design
Environmental projects
Design of traffic networks
Music composition
Sudoku puzzle solving
Timetabling software