Few ideas where to start:
Disclaimer: I am not an expert in this field and I don't know this particular problem that well so I will be only answering based on your question. However I like graphs and like to think about them once in a while. That being said, here we go.
First, there are two things that would be useful to clarify since these will impact the way you approach the problem:
- Does sending two robots to a single task lower the completion time to half, or is there any other progression depencency?
- Is there a limit to how many robots you can send to a task?
Since I don't know the answer yet I will now list few ideas that I would probably try to go and poke around if this was my thesis:
- I would try to find and possibly prove whether it is advantageous to send more robots to a single task. If yes, under what configuration. If not, why is that so?
For example in the simplest case of two robots who can repair 1 unit of damage, two tasks with cost 2 and a zero travel distance it definitely is advantageous to first finish first task, then the second one. The total repair time will be the same, however the total latency will be lower(3 vs 4). - I would try to poke around network flows and other graph algorithms in general. There might be some interesting insights. However since your selected problem is NP-hard, there likely won't be a direct path to the solution. NP problems are such a party-killers.
- I would look at the original problem before the generalization. Maybe your case can be reduced to the simpler version by clever reformulation?
Now that I think about it - every task has a cost. If we assume this cost to be an integer and the robot's repair capacity to be 1, replacing every task with a cluster of tasks that have their respective distance zero is most likely a sufficient reduction to the un-generalized and well researched problem.Thesis solved. Cough. - That being said, exploring the heuristic for the original problem is definitely a starting point. Trying out few different ones to compare them and learn to reason about your problem will most likely be useful.
- Are the heuristics not sexy enough? Using a neural network to approximate the solution could be interesting. Too centralized for your liking? Multi-agent system with rewarding the repairmen for finished tasks could be a way for an anarchist.
Once more, cheers and good luck.
Shamis, I can not thank you enough for your effort! The first two points you raise are essentially the two questions at the center of my thesis. I will be implementing a function which gives the completion time per site given the number of robots, which will stop increasing after having reached a certain number, when sending more would just be superfluous. As for the rest of your points, the problem is indeed NP-hard, and there exist some heuristics but I think the focus of my thesis will be optimization and comparing existing algorithms. I will definitely look into the ones you mention!
Finally, the point about reducing my problem is very interesting, but not applicable to my problem I am afraid. The completion function mentioned before will be a rather complicated one I am afraid, depending on various parameters and can not be boiled down or divided into integers and clusters. At this point, I cannot explain more about my topic and the problem to be solved, as it concerns sensitive information of the business I am writing my thesis at, I am sorry. I would like to thank you once more, please let me know if you have any questions.