jsprit does not seem to generate reproducible results

[oblonski]

this can be a pain sometimes thus it should be changed

[oblonski]

according to these test 5f0fee3
jsprit generates reproducible results!

Thus as long as anyone prove the opposite (with a proper test case), I assume it can generates reproducible results.

[levelibeeka]

I thought it's normal behavior and it's because of the nature of the problem... E.g. if I run Jsprit for 2 minutes, it produces a solution that's (e.g.) 95% of the theoretical best result. If I repeat the same test, I may get a significantly different result after 2 minutes. Why? Because search space is inhomogeneous and huge.
Is my reasoning incorrect?
We wanted to use Jsprit in a project for real-time planning, and we came to the conclusion that it's not possible, because if we run Jsprit again and again and again, the car drivers will always be rerouted because Jsprit always generates a so much different solution.

[oblonski]

If you take a time value as termination criterion, you can hardly
reproduce the results. Since what the algorithm can do in 2 minutes is
very much dependent on the load of your cpu. Thus, you can't always
ensure that 2 minutes correspond to x iterations. Therefore, use
iterations as termination criterion.

Am 24/04/15 um 17:49 schrieb levelibeeka:

I thought it's normal behavior and it's because of the nature of the
problem... E.g. if I run Jsprit for 2 minutes, it produces a solution
that's (e.g.) 95% of the theoretical best result. When I repeat the
same test, I may get a significantly different result after 2 minutes.
Why? Because search space is inhomogeneous and huge.
Is my reasoning incorrect?
We wanted to use Jsprit in a project for real-time planning, and we
came to the conclusion that it's not possible, because if we run
Jsprit again and again and again, the car drivers will always be
rerouted because Jsprit always generates a so much different solution.

—
Reply to this email directly or view it on GitHub
#156 (comment).

[levelibeeka]

I think I got the same results when I used iterations as termination result, but I cannot prove it at this moment.
Do you think it's theoretically impossible that randomness causes Jsprit to produce different results after the same number of iterations on really large datasets?

[oblonski]

I would estimate the average number of iteration that can be done in two minutes and adapt the termination criterion accordingly.

@real time planning: interesting. can you give me some more information about your setup? just to find out why jsprit generate so many different solutions

[oblonski]

As I just tested with
5f0fee3
it is reproducible. This means that if you solve the same problem with the same algorithm, you should always get the same results.

However, you need to make sure that you always start the algorithm with the exact same random seed.

[oblonski]

jsprit use this as default random number generator:
https://github.com/jsprit/jsprit/blob/master/jsprit-core/src/main/java/jsprit/core/util/RandomNumberGeneration.java

[oblonski]

and 4711L as seed

[oblonski]

If you run the a new algorithm over and over again within the same jvm, you need to make sure each algorithm run gets a new number generator. I will check how and whether it is possible.

[levelibeeka]

Well, the situation was that we wanted to continuously generate up to date results using Jsprit as our vehicles are moving, to accommodate to traffic conditions, delays, etc.
We had a large number of custom constraints (e.g. some deliveries allowed more delay than others).
We experienced that if we do it, the vehicles are continuously rerouted, and the drivers go crazy.

'and 4711L as seed': so are you saying that our problem was caused by our custom constraints, and the solutions we got were actually valid?

[oblonski]

It is hard to judge without knowing your problem. But when vehicles are
moving and new orders come in then you have a new problem that might be
solved such that the solution vary significantly from previous
solutions. You probably need to ensure that certain parts of the route
keep stable. I dont know ... Never used it in real time planning yet.

Am 24/04/15 um 18:13 schrieb levelibeeka:

Well, the situation was that we wanted to continuously generate up to
date results using Jsprit as our vehicles are moving, to accommodate
to traffic conditions, delays, etc.
We had a large number of custom constraints (e.g. some deliveries
allowed more delay than others).
We experienced that if we do it, the vehicles are continuously
rerouted, and the drivers go crazy.

'and 4711L as seed': so are you saying that our problem was caused by
our custom constraints, and the solutions we got were actually valid?

—
Reply to this email directly or view it on GitHub
#156 (comment).

[oblonski]

If you do not run the algorithms concurrently, you can just reset the RandomNumberGenerator.reset(). Otherwise,i.e. in case of concurrent calculations, to ensure reproducibility each algorithm requires an own random number generator. I will check this.

[oblonski]

When using multiple threads, results are still not reproducible.

[anjy-07]

I am getting the same issue, I am using a separate random instance every time with a single vrp, in a controlled environment (fixed number of iterations, 100, with BestInsertsion Search Strategy). I am getting different results with each run.