32 counties

ted9308

Hi there I was considering proposing an act for charity.Cycling through the 32 counties in a minimum time possible.Obviously I'd want to want to minimize distance travelled.I believe this to be quite a complex problem.What would be the best way to go about this?Would it be to pick a spot in every county and apply Dijksta's algorithm?

Amirani

It probably makes sense picking the most interior point in each coastal county and applying the Dijskta algorithm. Obviously it's worth considering changes in altitude etc.

Are you willing to try some software based approach? In this case you could try use a Nearest neighbour search along with your original suggestion?

ted9308

Do you know of any such software packages?

Amirani

You could do it in R - http://www.r-project.org/

R has a fairly steep learning curve though and your problem may be difficult to model. My suggestion is more of a hunch than anything, so I'd wait for further offers before going and buying a book about machine learning.

ZorbaTehZ

Using Mathematica, the shortest tour of counties comes out as: Carlow, Kildare, Laois, Offaly, Tipperary, Cork, Kerry, Limerick, Clare, Galway, Mayo, Sligo, Donegal, Leitrim, Roscommon, Longford, Westmeath, Cavan, Monaghan, Louth, Meath, Dublin, Wicklow, Wexford, Waterford, Kilkenny.

I attach the code (change the extension to .nb). The accuracy relies on how accurate the Wolfram database GPS information is.

Sheldons Brain

ZorbaTehZ wrote: »

Using Mathematica, the shortest tour of counties comes out as: Carlow, Kildare, Laois, Offaly, Tipperary, Cork, Kerry, Limerick, Clare, Galway, Mayo, Sligo, Donegal, Leitrim, Roscommon, Longford, Westmeath, Cavan, Monaghan, Louth, Meath, Dublin, Wicklow, Wexford, Waterford, Kilkenny.

This isn't all the counties. Also it probably used centroids for the counties which is not optimal.

The problem in general is a generalised travelling salesman problem where you want to visit one of a set of points in each county. One thing you need to consider is whether you want a closed loop or not. If you only want to visit each county then in one big county you could start at either end of it, e.g. in Cork start near the Kerry/Limerick border and return to Cork at the Waterford border.

ZorbaTehZ

Sheldons Brain wrote: »

This isn't all the counties.

The problem in general is a generalised travelling salesman problem where you want to visit one of a set of points in each county. One thing you need to consider is whether you want a closed loop or not. If you only want to visit each county then in one big county you could start at either end of it, e.g. in Cork start near the Kerry/Limerick border and return to Cork at the Waterford border.

It isn't all the counties because Wolfram database has no GPS information for 4/6 counties of northern ireland. If someone makes a list of the counties with GPS info. then I will run it again. Also, note that he never mentioned a hamiltonian cycle, he just want's a tour.

ZorbaTehZ

You should ignore my previous answer, I have looked at the Wolfram data again and it is much too coarse to be of any use.

I tried using the data from http://www.thegpscoordinates.com/ instead and this is what I got (included are the coordinates being used)

{{Carlow, {52.7196, -6.84598}}, {Wexford, {52.4388, -6.50166}}, {Wicklow, {52.9597, -6.4029}}, {Dublin, {53.3528, -6.32633}},
{Kildare, {53.2887, -6.70611}}, {Meath, {53.6667, -6.66667}}, {Louth, {53.8683, -6.44713}}, {Monaghan, {54.1945, -6.87477}},
{Cavan, {53.9482, -7.33607}}, {Westmeath, {53.5517, -7.40277}}, {Longford, {53.7083, -7.6783}}, {Roscommon, {53.7167, -8.20802}},
{Leitrim, {54.2007, -8.17658}}, {Donegal, {54.972, -7.86349}}, {Sligo, {54.1678, -8.64597}}, {Mayo, {53.9722, -9.48627}},
{Galway, {53.3264, -8.79137}}, {Clare, {52.8334, -9.}}, {Limerick, {52.4483, -8.97009}}, {Kerry, {52.0614, -9.52646}},
{Cork, {51.9668, -8.58335}}, {Waterford, {52.1601, -7.58783}}, {Tipperary, {52.6964, -7.90691}}, {Offaly, {53.2501, -7.50018}},
{Laois, {52.9476, -7.35393}}, {Kilkenny, {52.5699, -7.19766}}}

Sheldons Brain

The gold plated approach to this problem, probably more than is needed than the OP, is to use a GIS to identify the points at which roads cross county boundaries and the this feed this data into a network algorithm of choice using a road distance matrix.

ZorbaTehZ

As far as I can see something like that cannot be automated though. The most feasible way imo would be to deform county borders into reasonably simple polygons and then make a graph where each county vertex is the set of elements of vertices of the borders, and modify your distance function appropriately. I looked at the google maps API and it doesn't seem useful for this. So I guess anyone who is going to tackle this problem is at some stage going to have to do a lot of tedious work getting hold of lots of GPS information.

Sheldons Brain

It can be done in a fairly straightforward way with a powerful GIS like ArcGIS. Not sure I have time to do it right now though.