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

Question

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.

Answer 1

It's at least as hard as the "Traveling Salesman" problem, that is NP complete: TSP asks whether a salesman can visit n towns while travelling a distance ≤ K. Take the special case of one worker, who can do n jobs in a day if and only he travels a distance ≤ K, then the question "can the single available worker do all jobs in one day" is equivalent to TSP. But that is an extreme case.

Even an approximation is difficult. I assume each worker goes from company office to location 1 to location 2 ... to location n to company office. I'd try to group far away locations into clusters so that a worker can do a complete cluster and not be left with a single job in a cluster; doing half a cluster one day and the other half the next day would be fine, or picking jobs up on the way. Problem changes if each worker starts at home and ends up at home, then you'd want each one to do jobs near his home.

In reality, you will have new jobs coming in every day, so you need a solution for one day, and then recalculate the next day. Plus take into account that customers waiting a long time will get angry.