# Grouping n points into groups of size m with objective to have least traveling distance in each group

Assumptions:
• There are "n" jobs which are distributed over the city.
• Company has "k" available workers.
• Each worker can do "x" jobs per day.
• "x" is dependent to the worker skills and the distance he travels each day so it's not a constant.
• Workers have no initial traveling distance.
• "s" is a set that shows each workers can do how many jobs based on the distance he travels
• "d" is the number of days that takes for company to do all the jobs.

Objective: Minimize the "d"

I know this problem is probably NP-hard so I don't need the exact answer. I think it's kinda a variation of Traveling salesman problem combining with scheduling and assignment problems.

My algorithm for this problem is to "some how" efficiently ( of course not the most efficient way ) grouping the jobs based on their traveling distance in the groups in to groups of "m" which is the mean of set "s". Then after each day rerun the algorithm to get better results.

My question is what is the best way to do that grouping? Anyway if you know a better algorithm I would be more than happy to know them.

• You may want to start by clustering the jobs using something like k-means(++). After that, try to shuffle individual jobs between the clusters to meet the workload < x condition. – Albjenow Nov 14 '19 at 13:21