The National Trust and the Travelling Salesperson — #TSP #Data #NationalTrust @NationalTrustNI #R #RLang

I’ve not had to change much of my routine when it comes to self isolation, I work from home anyways. Saying that with all my speaking engagements cancelled (and rightly so) my brain needed something else to do…..

The Travelling Salesperson problem has fascinated me for years but I’ve never had the time to really sit down with it.

Welcome to TSP!

The Travelling Salesperson problem is this.

“Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?”

What we have here is a graph problem, each location is a node and the route connecting each node are the edges.

There are a number of algorithms that have been devised over the years to calculate the optimum shortest route, it’s the sheer number of permutations to calculate the problem that makes me interested. For now the thing to keep in mind is this….

More on this in a moment, right now I need some locations to test all this out. If I pick a high number it’ll take for ever to calculate a route. I’m going to use R, the Google Maps API and the TSP R Library to see if I can plot a route of some nodes. I need a decent dataset, the one I have in mind is massive so let’s take a subset instead…

The National Trust NI Locations.

The National Trust NI Sites

There’s a nice number of National Trust properties in Northern Ireland. I could have chosen pubs but that’s not what I really do, so as the card carrying member I will do my bit to support the cause.

Here’s my list of locations, I’ve pulled the address data from a combination of the National Trust website and Google Maps:

ADDRESSES = c( "Carrick-a-Rede, 119a Whitepark Road, Ballintoy, County Antrim, BT54 6LS", "The Crown Bar, 46 Great Victoria Street, Belfast, County Antrim, BT2 7BA", "Divis and Black Mountain, Divis Road, Hannahstown, near Belfast, County Antrim, BT17 0NG", "Dunseverick Castle, Causeway Road, Bushmills", "Fair Head, Fairhead Road, Ballyvoy, Ballycastle,BT54 6RD", "Giant's Causeway, 44 Causeway Road, Bushmills, County Antrim, BT57 8SU", "Patterson's Spade Mill, 751 Antrim Rd, Templepatrick, Newtownabbey, Ballyclare BT39 0AP", "Ardress House, 64 Ardress Road, Annaghmore, Portadown, County Armagh, BT62 1SQ", "Coney Island, Lough Neagh, Dungannon, BT71 6PA", "Derrymore House, Bessbrook, Newry BT35 7EF", "Castle Ward, Strangford, Downpatrick BT30 7BA", "Mount Stewart, Portaferry Rd, Newtownards BT22 2AD", "Murlough Nature Reserve, Keel Point, Dundrum, Newcastle BT33 0NQ", "Rowallane Garden, Crossgar Rd, Saintfield, Ballynahinch BT24 7LH", "Castle Coole, Castlecoole Rd, Enniskillen BT74 6JY", "Crom Estate, Newtownbutler, Enniskillen BT92 8AJ", "Springhill, 20 Springhill Rd, Moneymore, Magherafelt BT45 7NQ", "Downhill Estate, Mussenden Rd, Castlerock, Coleraine BT51 4RP", "Hezlett House, 107 Sea Rd, Castlerock, Coleraine BT51 4TW", "Portstewart Strand, 118 Strand Rd, Portstewart BT55 7PG", "Gray's Printing Press, 49 Main St, Strabane BT82 8AU", "Wellbrook Beetling Mill, 20 Wellbrook Rd, Corkill Rd, Cookstown BT80 9RY" )

The ! means factorial and it means the product of a number. eg 1 x 2 x 3…..

3! is 6 for example 1 x 2 x 3.

7! is 5,040, 1 x 2 x 3 x 4 x 5 x 6 x 7.

With 21 Trust properties in NI, it’s going to be a large number. The equation though has a few more bits to it, I’m already at my starting point so I can take that one away and I’m only going in one direction so I divide the answer by 2.

How many permutations are there to start at each point and figure out every possible route?

(21-1)!/2 = 1,216,451,004,088,320,000 
Or.... 
20 x 19 x 18 x 17 x 16 x 15 x 14 x 13 x 12 x 11 x 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 
divided by 2 as we're only going one way.....

We could be here for a while with a quintillion routes to calculate. That’s the brute force method, using the other algorithms will make life much easier. Ever more so, I’m not going to waste my time writing new code when someone has already done it.

Andrew Collier (@datawookie) already has the code done for us …. thanks Andrew. His marvellous code will figure out all the positions in the map, work out the optimum route and then generate a Google Map for me. Brilliant!

In the time it took for Andrew’s TSP code to work out a route, I’d made a cup of tea. That’s good going and this is what was waiting for me when I got back…..

Lovely isn’t it?

So What’s the Route?

So the shortest route is 417.5 miles altogether and a total driving time of just over 11 hours, the algorithm started me off at Dunseverick Castle and suggested this shortest route:

Dunseverick Castle > Giant’s Causeway > Portstewart Strand > Hezlett House > Downhill Estate > Gray’s Printing Press > Castle Coole > Crom Estate > Wellbrook Beetling Mill > Springhill > Coney Island > Ardress House > Derrymore House > Murlough Nature Reserve > Castle Ward > Rowallane Garden > Mount Stewart > Crown Bar > Divis and Black Mountain > Patterson’s Spade Mill > Fair Head > Carrick-a-Rede

Interesting that the shortest route also means you can put that fear of heights well to the back of your mind until you are on the final leg of the journey (I’ve still not gone over that bridge).

Now all I need to know which properties have second hand bookshops in them.

With the Northern Ireland locations figured out, and that quintillion number firmly lodged in my head as it’s a rather large number, it merely brings me on to the next question in my mind.

How Many Permutations to Visit ALL the National Trust Properties?

The things that keep my mind occupied. We know the brute force calculation of the NI properties is (21–1)!/2, there are 1500 National Trust properties in the UK. I’m really curious now how that looks…… how many permutations are there?

Back to that factorial again. (1500–1)!/2

160399926559325828672233003119379326061160268022420460271028531372101 917296670318637640768617355779506228213365397811950646840303748727220 900904939604644438105426542700999480497779296815631318368290559599231 084345664901559430781330877755152176202495350252487889761078688818307 591803733611460289091231259625586667371351061600814514024732016213923 2331686047840739961706485632803190198184986301818944059...

That’s only the first 400 digits of it, there are 4112 digits in the actual number. Even Wolfram Alpha won’t tell me the full answer in one go so I’ll have to pad it out…. If I fill in the remaining numbers with zeroes (no way I’m going to guess) this is the sort of number we’re dealing with.

Ready?

16039992655932582867223300311937932606116026802242046027102853137210191729667031
86376407686173557795062282133653978119506468403037487272209009049396046444381054
26542700999480497779296815631318368290559599231084345664901559430781330877755152
17620249535025248788976107868881830759180373361146028909123125962558666737135106
16008145140247320162139232331686047840739961706485632803190198184986301818944059
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000

Sorry, I’m not typing the commas in for this one….. you’ll just have to imagine. As an educated guess it would take estimated 2 CPU years time to figure out the optimum route using Concorde TSP algorithm.

Originally published at https://dataissexy.wordpress.com on March 14, 2020.