The following is a variation of the multiple traveling salesman problem (MTSP) where the salesman begin at different locations:
There are $S$ sites in a city at different fixed geo locations $(a_i,a_i), 1 \le i \le S$ that needs to a inspected by an inspector. There are $I, I < S$ inspectors at different locations $(x_i,y_i), 1 \le i \le I$ in the city who need to go an inspect these sites. The objective is to assign the sites to the inspectors in such as way that the total traveling distance of inspector to the sites in minimized.
Question: In my work, we need to develop an application that allocates sites to inspectors. I understand that MTSP is computationally a very hard problem and therefore the runtime of the optimal solution may not be practical for a mobile app where you need to give the output within 2 or 3 seconds. Therefore I am looking for an non-optimal solution which is still reduces the total distance compared to a random allocation, even though it may not be the minima.
I have tried some rule based approaches using the Rearrangement Inequality. Any suggestions would be very helpful.