Your problem has a complicated dynamics: new jobs arrive continuously; travelling and/or completing jobs can take more time or less time than expected; the number of active employees can change due to sickness; etc. I think the best approach to handle dynamics is that each time a new job arrives, an employee finishes a job, or the number of active employees changes (etc.), the planning software redistributes every known job among active employees, and redetermines their path for all the jobs assigned to them (for several days in advance if there are so many jobs). And this must be done in an optimal way (see below).
Now we have a simpler problem: distributing all jobs among all employees, and determining paths for them optimally at a given point of time. The planning software knows the cities where the employees are, and where the unfinished jobs located, and is able to calculate the optimal path between any pair of these cities. By "optimal" I mean the one which has the minimum cost to take, which is not always the shortest one. The cities and the optimal paths between them form a weighted graph: cities are the nodes, paths are the edges. Edges have a positive cost (price of travel) and nodes have a negative cost (income after each job at a given city).
Imagine we've got the recalculated plan, it's been sent to the employees, and they start to carry it out. What do they do? Some of them may have unfinished jobs at their actual location, some of them will travel to the next city, to complete jobs there. Note that the execution of the plan is continuous: at a given moment, those employees who are working on a job, generate negative cost, and those who are travelling generate positive cost. The rate at which each employee generates cost can be easily calculated: for working employees, it's
-[income after actual job] / [time required to complete the job], for travelling employees, it's
[cost of travel] / [travel time] (for longer plans, the inactive periods: that is, nights, weekends and holidays should also be taken into account - these are cost generators, too, like traveling). At a given moment of time, the total cost generation rate (TCGR) is the sum of the cost generation rate of all employees. The total cost of a plan is the integral of the TCGR over the total time span of the plan (TTSP). I guess the most reasonable aim would be to minimize the fraction
TCGR / TTSP, that is, to find the plan with minimal average TCGR (ATCGR).
How should the planning software determine the plan with minimal ATCGR?
- For every possible plan, the software can calculate the ATCGR
easily, so the brute force approach seems to be an option.
Unfortunately you have 25 employees and 2000 pending jobs, which
means that there are too many possibilities to find the optimal plan
with brute force in reasonable time.
- Another simple option is the
greedy approach: when calculating ATCGR, take into account only the part of the plan from the beginning of the plan to
the moment of the first replanning. Note that the software will recalculate the
plan each time one of the employees finishes a job, so in case of the greedy approach there are much
shorter possible plans, and therefore much less possibilities. I'm sure the greedy solution can be found by brute force.
- I believe there is no method to find an exact solution to this
problem other than the brute force approach, but applying brute
force is impossible (see above). If you are not satisfied with the
greedy approach, and would prefer an approximate solution of the
whole problem instead, than you can develop an algorithm which is
similar to the approximate algorithms developed for the
travelling salesman problem (TSP). This is not easy, because you have a multiple "salesmen" for the same set of cities.