Graph algorithm and theories for logistic application?

Well, that's quite a complex issue but i'll try to describe my goals.

Objective: Given a set of n geolocated nodes (jobs) i must to distribute it to y employees (sub-graphs?), daily.

The complexity comes when i must consider the restrictions below to perform this task:

  1. Each employee has a load limitation (considering proficiency and workhours)

  2. Each job (node) has load values associated such as priority and time spend to be executed.

  3. Not all jobs would be executed on a given day. So, some of them must be excluded to favor must important ones (even if those were more distant).

  4. A search for the most optimal distance (or cover area) to attend this jobs must be taken in account.

  5. The overlapping of 2 employee covering areas must be avoided.

Scope: the universe is about 350 income jobs daily, reaching aprox. 2.000 jobs in standing by, with 25 employess and covering a very large area of about 1.500.000 m2.

I've some basic knowledge in graph theory such as Djistra's shortest path, and some Knapsack problems, post man problem, etc... But this is a much more complex issue.

So any direction or suggestion is appreciated. For that i mean wich theory(s) i must study/implement to achieve these goals?

PS: I was not sure if that question should be asked here or in mathematics stack exchange, but since i guess there's a lot of algorithm involved i decided to post it here. Also i must remark that i've been googling but there are so many graph theory names and until now i've found none that fits my problem.

Best Regards, Paulo Bueno.


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?

  1. 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.
  2. 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.
  3. 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.


 ? Relationship between BFS and topological sort
 ? topological sort subset of nodes in graph
 ? What algorithm do I use to calculate voltage across a combination circuit?
 ? Complex conveyor capacity calculation (graph) - fun game algorithm
 ? Efficient way to find degrees of separation between two nodes in a graph
 ? Graph search with weight limit
 ? calculate the degree of separation between two nodes in a connected graph
 ? Sparse Graph Implementation & Performance in C++
 ? Finding path with maximum minimum capacity in graph
 ? Disconnecting a connected graph