Test jsprit on homberger benchmark

[miandai]

I tested jsprit on homberger benchmark dataset. The result is not optimistic. jsprit is much worse than optaplanner.

For example, in C1_10_2.TXT, OptaPlanner use 100 vehicles and 42545 distance cost. But jsprit use 110 vehicles and 61153 distance cost. The gap is too big.

I am confused. It must be something wrong. Has anyone else done this experiment?

[jcoupey]

First you need to keep in mind that direct comparisons are only meaningful if the optimization objectives are the same. For example, the usual best known solutions for the Homberger benchmarks are reported using a hierarchical objective: 1) Minimize number of vehicles 2) Minimize total distance.

Then there is probably a matter of tuning: search depth, termination policy, timeouts etc. The same approach can yield totally different solutions with different settings. For example, using vroom (optimizing on distance only) on instance c1_10_2, the "fastest" solution has 100 vehicles and cost 42885 while the "slowest/best" solution has 98 vehicles and cost 42125.

[miandai]

First you need to keep in mind that direct comparisons are only meaningful if the optimization objectives are the same. For example, the usual best known solutions for the Homberger benchmarks are reported using a hierarchical objective: 1) Minimize number of vehicles 2) Minimize total distance.

Then there is probably a matter of tuning: search depth, termination policy, timeouts etc. The same approach can yield totally different solutions with different settings. For example, using vroom (optimizing on distance only) on instance c1_10_2, the "fastest" solution has 100 vehicles and cost 42885 while the "slowest/best" solution has 98 vehicles and cost 42125.

Thanks for your reply @jcoupey .

There is probably a matter of tuning. But I don't know how to tune. I used SolomonExample to do test Homberger dataset directly. I have little experience in jsprit. Looking forward someone to correct me.

If someone have done the same experiment. I need your advice. Thanks very much.

[oblonski]

Thanks for your "benchmark". @jcoupey wrote what needs to be said. There is nothing left to be added. Thanks a lot @jcoupey.

BTW: I get 97 vehicles and 42224 with my very first trial (source code attached). I am sure it can be improved further by tuning the algo with regards to computation time and solution quality (as @jcoupey pointed out). I am pretty sure that this is also valid for optaplanner and vroom.

VehicleRoutingProblem.Builder vrpBuilder = VehicleRoutingProblem.Builder.newInstance();
new SolomonReader(vrpBuilder).read("input/C1_10_2.txt");
VehicleRoutingProblem vrp = vrpBuilder.build();
Jsprit.Builder builder = Jsprit.Builder.newInstance(vrp);
builder.setProperty(Jsprit.Parameter.CONSTRUCTION, Jsprit.Construction.BEST_INSERTION.toString());
builder.setProperty(Jsprit.Parameter.FAST_REGRET, "true");
VehicleRoutingAlgorithm vra = builder.buildAlgorithm();
vra.setMaxIterations(20000);
Collection<VehicleRoutingProblemSolution> solutions = vra.searchSolutions();
VehicleRoutingProblemSolution solution = Solutions.bestOf(solutions);
SolutionPrinter.print(vrp, solution, SolutionPrinter.Print.CONCISE);

Please let us move this discussion to https://discuss.graphhopper.com/c/jsprit.

[miandai]

Thans for your code @oblonski . I added the code:

Jsprit.Builder builder = Jsprit.Builder.newInstance(vrp); builder.setProperty(Jsprit.Parameter.CONSTRUCTION, Jsprit.Construction.BEST_INSERTION.toString()); builder.setProperty(Jsprit.Parameter.FAST_REGRET, "true"); VehicleRoutingAlgorithm vra = builder.buildAlgorithm();

Now the result is very good. For C1_10_2.TXT, jsprit use 98 vehicles and 42857 distance cost. Thanks again.

[AlexStanovsky]

@miandai can you share the running times of this solution (with the machine) ?