Repairmen and Trees

I think I have finally found a problem that has not been studied and is important.  I’m calling it the K-D-Traveling Repairman Problem.  K, the number of repairmen, D, the number of types of repairmen.  The repairman problem is a NP-hard problem and therefore heurstics are used to solve it.  The Predictics group at CMU used Machine learning to approximate solutions to the TRP.  I’ve found one other author that has looked at the K-TRP problem.  I can’t find anyone that has looked at the K-D-TRP.  This is a heterogeneous extension.  Basically I’m saying that there are different types of repairmen that may need to overlap at nodes such in order to perform the repair.

Another interesting extension is a dynamic graph.  Also, I’m interested in looking at saturation levels of repairmen.  Non-deterministic repair times would also be another aspect to look at.  The nice thing with this problem is that it is based on a real world problem that really needs to be solved.

Also, want to look Game theory, optimization theory and expander graphs seem like they will be useful in the theoretic aspect of the problem.  I want to then develop a multi-agent learning algorithm where the agents learn how to solve the problem.

Also, I have been reading about some cool trees: KD-Trees and KD-B-Trees.  They are pretty cool.