Jsprit v1.6.3 gives longer distance solutions than v1.6.2 in a specific application

pieter · March 27, 2016, 2:16am

First, thanks to Stefan and other contributors for Jsprit. I find it very useful and very good indeed.

Then I want to share my experience with an application:
There is a TSP application where I find it very difficult to repeat the shortest distance result I got using v1.6.2 in v1.6.3.
I’m using the OSM road distances, and with the peculiar roads for this application, the solution given by v1.6.2 crosses over, but is shorter than the distance given by v1.6.3. Sure, the route given by v1.6.3 “looks” nicer, there is no cross-over, but the distance is longer. I calculate the OSM road distances separately and read the distance matrix from an external file.

I’m simply using “VehicleRoutingAlgorithm vra = Jsprit.createAlgorithm(vrp);” in both cases. I have tried many different algorithms in v1.6.3, but could not get a distance as short as the distance I got using v1.6.2.

It almost looks like v1.6.3 enforces a rule that a route is not allowed to crossover, even though the distance is smaller.

The lat longs are:
Depot1-Start -25.74413983 28.27358442
Depot1-End -25.74413983 28.27358442
1 -25.783715 28.25301
2 -25.921961 28.158033
3 -25.761031 28.238162
4 -25.757255 28.21375
5 -25.782711 28.349189
6 -25.760424 28.258933
7 -25.779394 28.26029
8 -25.754201 28.207041
9 -25.775553 28.254814
10 -25.772694 28.226639
11 -25.782614 28.264433
12 -25.776285 28.26892
13 -25.776265 28.26891
14 -25.763007 28.264499

The OSM road distances I used are:
from to distance
0 1 0
0 2 7467
0 3 25985
0 4 7140
0 5 9425
0 6 10836
0 7 4888
0 8 6167
0 9 9343
0 10 5973
0 11 9123
0 12 5812
0 13 6432
0 14 6432
0 15 4184
1 0 0
1 2 7467
1 3 25985
1 4 7140
1 5 9425
1 6 10836
1 7 4888
1 8 6167
1 9 9343
1 10 5973
1 11 9123
1 12 5812
1 13 6432
1 14 6432
1 15 4184
2 0 7523
2 1 7523
2 3 24635
2 4 3621
2 5 5722
2 6 13289
2 7 3788
2 8 1882
2 9 6460
2 10 1682
2 11 3768
2 12 2675
2 13 5507
2 14 5507
2 15 3712
3 0 26936
3 1 26936
3 2 25291
3 4 23870
3 5 24522
3 6 39432
3 7 25028
3 8 23098
3 9 23781
3 10 23779
3 11 21938
3 12 21946
3 13 22873
3 14 22871
3 15 21961
4 0 7142
4 1 7142
4 2 3621
4 3 23266
4 5 2935
4 6 22932
4 7 2754
4 8 3712
4 9 3671
4 10 3085
4 11 1983
4 12 4505
4 13 6338
4 14 6338
4 15 3229
5 0 9420
5 1 9420
5 2 5722
5 3 24337
5 4 2969
5 6 27976
5 7 5032
5 8 5814
5 9 748
5 10 5187
5 11 2601
5 12 6606
5 13 11396
5 14 11392
5 15 10482
6 0 10832
6 1 10832
6 2 13210
6 3 39432
6 4 22932
6 5 27976
6 7 9842
6 8 11468
6 9 29356
6 10 11716
6 11 25309
6 12 10721
6 13 9926
6 14 9926
6 15 9138
7 0 4866
7 1 4866
7 2 3788
7 3 26017
7 4 2751
7 5 5036
7 6 9838
7 8 2699
7 9 5772
7 10 2155
7 11 4734
7 12 3096
7 13 4397
7 14 4397
7 15 953
8 0 6236
8 1 6236
8 2 1882
8 3 22412
8 4 3712
8 5 5814
8 6 11512
8 7 2741
8 9 6551
8 10 888
8 11 4374
8 12 795
8 13 3731
8 14 3731
8 15 2425
9 0 8892
9 1 8892
9 2 6464
9 3 23589
9 4 3710
9 5 741
9 6 29356
9 7 5773
9 8 6555
9 10 5928
9 11 3342
9 12 11854
9 13 12782
9 14 12780
9 15 11868
10 0 6029
10 1 6029
10 2 1682
10 3 23094
10 4 3085
10 5 5187
10 6 11795
10 7 2155
10 8 888
10 9 5924
10 11 3747
10 12 1681
10 13 4013
10 14 4013
10 15 2218
11 0 9073
11 1 9073
11 2 3768
11 3 21283
11 4 1931
11 5 2591
11 6 25309
11 7 4685
11 8 4322
11 9 3329
11 10 3695
11 12 5115
11 13 8731
11 14 8729
11 15 7819
12 0 5793
12 1 5793
12 2 2675
12 3 21946
12 4 4505
12 5 6606
12 6 10741
12 7 2993
12 8 795
12 9 11854
12 10 1681
12 11 5167
12 13 3354
12 14 3354
12 15 2678
13 0 4976
13 1 4976
13 2 3284
13 3 22873
13 4 4159
13 5 11396
13 6 10318
13 7 2265
13 8 1541
13 9 12782
13 10 1790
13 11 8731
13 12 1165
13 14 0
13 15 1949
14 0 4976
14 1 4976
14 2 3284
14 3 22871
14 4 4159
14 5 11392
14 6 10318
14 7 2265
14 8 1541
14 9 12780
14 10 1790
14 11 8729
14 12 1165
14 13 0
14 15 1949
15 0 4509
15 1 4509
15 2 3791
15 3 21961
15 4 3205
15 5 10482
15 6 9481
15 7 953
15 8 2491
15 9 11868
15 10 2297
15 11 7819
15 12 2889
15 13 4189
15 14 4189

stefan · April 1, 2016, 6:07am

Hello Pieter, What is actually your solution value? Best, Stefan

pieter · April 1, 2016, 10:50am

Hello @stefan, Thanks for the question - it pointed me to the error in my code.

I’ve fixed it and it’s working fine now.

Just for completeness, let me share what I’ve done wrong:

In v1.6.2 I used “VehicleRoutingTransportCostsMatrix.Builder matrixBuilder = VehicleRoutingTransportCostsMatrix.Builder.newInstance(false);”

In v1.6.2 I used “FastVehicleRoutingTransportCostsMatrix.Builder matrixBuilder = FastVehicleRoutingTransportCostsMatrix.Builder.newInstance(numberOfLocations,false);”

This should of course also work, but here is what I did wrong:
In v1.6.2 I had the line “vrpBuilder.setRoutingCost(matrixBuilder.build());” before the line “VehicleRoutingProblem vrp = vrpBuilder.build();” and this line was missing in v1.6.3 with the result that I did not build the vrp with the road distances, but only with the straight line distances.

I have now copied the code exactly from v1.6.2 to v1.6.3 and the results are exactly the same

I should have picked it up if I looked at the cost calculated by Jsprit, but I did not.

I’m using an excel interface that I hacked together myself and I do my cost calculations in there and did not compare the Jsprit calculated costs,

The reason I use the excel calculated cost is because I give my customers the option to change the routing in excel if there are a specific reason for them to do it, so it useful for me to calculate the cost in excel.

But after this exercise I am of course going to be more careful.

Thanks again for the help by asking the right question.