-1

I have a list (say 300) of customers (lat,long)- and a list (say 10) of service engineers (lat,long). I need to assign a service engineer for each customer in an optimal way. To reduce his travel and increase his capacity of attending customers. Assume he has to attend all customers on a regular basis. Trying for a K means clustering , which should divide the customers into 10 clusters and assign the service engineer for each customer. Any hint is appreciated.

bithom
  • 186
  • 2
  • 14
  • 2
    While this is far from definitive, it looks like the authors of [this final project](https://www.math.cmu.edu/~af1p/Teaching/OR2/Projects/P12/2010FinalProject.pdf) found clustering to not be the best approach to the multiple travelling salesmen problem. I would look for a metaheuristic approach – evan.oman Nov 17 '16 at 23:26
  • 2
    See more discussion [here](http://stackoverflow.com/questions/6239148/travelling-salesman-with-multiple-salesmen) – evan.oman Nov 17 '16 at 23:26
  • 1
    [Another approach](http://www.naturalspublishing.com/files/published/00r020bk1121qr.pdf) – evan.oman Nov 17 '16 at 23:30

1 Answers1

0

Clustering is totally the wrong approach here. It does not balance the sets, but rather if 99% of your customers are close to each other, they will be assigned the same cluster. Furthermore, k-means cannot use geo distances, and assumes your center can move to any desired location.

Rather than looking at clustering, you need to look at resource allocation, for example the famous hungarian algorithm.

Has QUIT--Anony-Mousse
  • 76,138
  • 12
  • 138
  • 194