best possible implementation of the travelling salesman / vehicle routing use case

Question

I recently came across a case in interview when use case which was asked to be solved belongs to travelling salesman problem / vehicle routing problem. I was able to tell them what the actual problem is and what maths is involving in the problem. I did explained how below mentioned use case can also be solved using MapReduce paradigm part of Hadoop. ( explained how multiple map reduce jobs will be able to solve the problem ) using Graph algorithm mentioned in this book Data-Intensive Text Processing with MapReduce" by Jimmy Lin and Chris Dyer.

Out of curiosity I did some research on google and i can see lot of implementation and research has been done for this problem in different flavors. Problem i was asked has coordinates of city mentioned in (x,y) format and many solutions i saw on google consider some other factors like unit distance, negative/positive units of measurement and so on. So in short more i did research and reading i got more confused.

My question here is for below use case what can be possible solutions and what will be best solution among them. If some experienced person can put some lights on this it will be helpful to clear my confusion and understanding the solution in better way. or if someone can direct me to right direction ( so that i don't get more confused exploring whole ocean of solutions )

Use case asked in interview:

A company is trying to find best possible optimal solution for servicing his customer base of 300 with 12 employee. They want a technology solution that tells how they will be able to meet customer requirement as business will grow and other changes like location of customer changes, new locations added and so on.

Problem is basically a form of Travelling Salesman Problem ( TSP ) or Vehicle Routing problem ( VSP ). Following things need to be completed here.

Starting coordinates are (0,0) and city coordinates example are mentioned below. Here are coordinates with which working solution is expected provided in a text file as input:

X coordinate    Y Coordinate 
420 278 
421 40 
29  178 
350 47 
298 201 
417 186 
378 134 
447 239 
42  114 
45  199 
362 195 
381 243 
429 1 
338 209 
176 9 
364 26 
326 182 
500 129 
190 51 
489 103 
368 142 
132 260 
305 200 
446 137 
375 154 
440 190 
9   118 
437 32 
383 266 

1. What can be right way to handle this NP-hard problem or if not right way what can be different approaches with their pros/cons.

2. Since its more of analysis based problem can some kind of visualization be done to solve this. Like some graph or use of R/analytic tools

Let me know if you need more details or if you can suggest where i can read and understand more.

Thanks in advance

Answer 1

There's no right way of solving a NP problem. Since complexity is exponential it's going to take a very long time for anything other than trivial examples.

However, there are approximations that can get fairly close to the real answer and might be sufficiently good for your application (as in, it's not the shortest path, but it's within some relative range of it).

Check out the wikipedia page. They even have some examples.