I just went through one example of jsrpit to check. Is that really check all combination but I found out some combination it missed.
Is that really true?
Please @Balage1551, @jie31best, @stefan
Not. Can’t. 
VRP is an NP-hard problem, so solving by checking all possible routes is, in most of the cases, impossible. Just think of an extremly easy TSP (traveling salesman problem) which is a simplified, one vehicle, special case of the MVRPTW problems Jsprit aims to solve. Let it have only 10 nodes to visit. Even now we have 10! = 3.628.800 possible solutions! Without time windows, capacities to take into account. It is obvious that any direct solving attempt is impossible.
The Jsprit is a genetic algorithm, which works just like evolution: there is an initial solution built up randomly, then it mutate it and checks if the new “entity” is viable and is better than the current best one. (This mutation is done randomly – but guidedly – removing jobs from the solution and trying to inserting them into the solution again. Genetic algoritms are better than some direct converging methods, because mutation is less fragile to stuck in a local minimum.
In one word, the algorithm doesn’t guarantie to find best solution only a convergation toward it.
How good the result will be? Either pretty good or awful. It strongly depends on several factors:
- Size of the problem
- Iteration count
- Freedom of the problem (how wide the TWs, are they overlaped, etc.)
- The ruin and instertation strategies
- The cost funtion
- Luck
3 Likes
I do find out some problem.
I’m talking about the class ServiceInsertionCalculator
.
When I got the best result of job sequence like 1-> 2->3->4 from my hard constraint but it’s come. It will do override my job sequence order and give the output 1-> 4->3->2.
So what is the way to prevent this happen?
Please @jie31best, @braktar, @stefan @Balage1551
Well, I can’t say I completely understand you, but I’ll do to make the best guess about the meaning of your example.
Do you mean you have a hard constraint which should ensure (force) the order of the jobs as 1->2->3->4 ?
And your problem is that the algorithm gives you an invalid job order?
If this is the case, there are several topics about the problem that the ruin strategy doesn’t honor hard constraints (only insert strategies takes them into account) which leads to broken constraints in solution. This is a problem many of us have already faced and at the moment there is no easy solution: you has to create your own ruin strategy.
What is the solution? Either to write ruin strategy to take the constraints into account, or if your intetion is to keep the order of these jobs and it is ok to force the algoritm to assign all the jobs to the same vehicle, you may give a try to the new, custom jobs. But be warned! This feature is already in incubation and will be available only in the new major version of Jsprit. Also there are not too much documentation on how to use it, yet.
If you decide to give it a try, here you find it: Jsprit job activity refactor branch. To start with, take a look at the class com.graphhopper.jsprit.core.problem.job.CustomJob.
Note, that this is stable, but incubating version, so it may change in the future.
1 Like
Yes![quote=“Balage1551, post:4, topic:1985”]
the hard constraint which should ensure (force) the order of the jobs as 1->2->3->4?And your problem is that the algorithm gives you an invalid job order?
[/quote]
Yes! That the problem.[quote=“Balage1551, post:4, topic:1985”]
ruin strategy
[/quote]
Could you explain a little bit I do not get completely get it?Mean how internally work.[quote=“Balage1551, post:4, topic:1985”]
Jsprit job activity refactor branch.
[/quote]
I did clone.It seems lots of updates.
Also a lot of getting the error.
Can you please explain how to go about ruin stretegy it?
Hi @jsroyal,
You do not necessarily have to build your own ruin strategy or use CustomJob.
It might be possible that it is not ruin strategy which is giving you infeasible solution but there is some broken link in your constraint implementation. So I suggest check that first before taking a difficult route.
Try to think of it in this way:
You have a feasible solution and you randomly remove some nodes out of it, does removal of any combination of these nodes violate your constraint?
If your answer is NO then ruin strategy is not a culprit here.
1 Like