I need help regarding a graph problem. I'm looking for and existing solution or algorithm instead of implementing my own, If there is one, please help me out. I tried googling without success.
My problem is: I have several locations to visit, and each one of theses locations have deadlines. Usually, I can never get to visit them all and aways exceed the deadlines. I Also have also have a limited time to visit them, for example 8 hours a day. I'm looking for an algorithm that can reach the minimum delay after the dealine. For Example, I have location A, B and C. Location A is 1h30 delayed and location B and C are 1h delayed each. If I go to location A, I'm unable to visit locations B and C, but if I visit location B I can go to location C and vice versa. The algorithm should tell me to "go to B and C", because then I'm removing a 2h delay from my list and only keeping the 1h30 hour delay to the next shift I have.
I really don't understand graphs to much, so I don't know where else to look. Thanks in advance.
This is a planning problem and to be more exact: It's a vehicle routing problem (with a time-window), because the constraint is to "maximize the tour in a time-window" + "minimize the delay-time".
The following toolkits will help: