﻿ Graph algorithm and theories for logistic application?

# 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.

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).