GraphHopper.com | Forum | GitHub | Maps | Blog

Why transport time is not considered in solution?


#1

Hey, I use jsprit to solve CVRPTW, and I think I have found a bug with transport time.
I have 7 services, when I solve vrp with these services I have such solution:

| route   | vehicle                           | activity              | job                               | arrTime | endTime | costs   |
+---------+----------------------+-----------------------+-----------------+-----------------+-----------------+-----------------+
| 1       | wTTMQzKoMMe5uLSjJ    | start                  | -                                  | undef     | 0           | 0          |
| 1       | wTTMQzKoMMe5uLSjJ    | service              | T62KP2yuAFKqsiScQ   | 0           | 160       | 0          |
| 1       | wTTMQzKoMMe5uLSjJ    | service              | G4ZAjHjzTQjATcaMx    | 160       | 170        | 0        
....

As we see here end time of the first service is 160, and the arrival time of the second is 160, but there is 3 km between these 2 services, our driver can’t teleport from one location to another. my time units measured in minutes, distance in meters, I expect to see that arrival time of the second service would be 175, end time 185.
Here is my code:

VehicleRoutingProblem.Builder vrpBuilder = VehicleRoutingProblem.Builder.newInstance();
vrpBuilder.addAllJobs(services);
vrpBuilder.addAllVehicles(vehicles);
EuclideanCosts costs = new EuclideanCosts();
// Here I tried 0, 1000, 50, 20, nothing changes
costs.speed = 500;
vrpBuilder.setRoutingCost(costs);
vrpBuilder.setFleetSize(FleetSize.FINITE);
VehicleRoutingProblem vrp = vrpBuilder.build();
VehicleRoutingAlgorithm vra = Jsprit.Builder.newInstance(vrp) .setProperty(Jsprit.Parameter.FAST_REGRET, “true”)
.setProperty(Jsprit.Parameter.THREADS, “4”)
.buildAlgorithm();
Collection tempSolutions = vra.searchSolutions();

I am sorry for bad formatting:
https://pastebin.com/JdWDQzZA
Here is the highlighted code


#2

if you try logging the following five variables after the build of the vrp:

    costs.getTransportCost(s1.getLocation(), s2.getLocation(), 160, null, v1);
    costs.getTransportTime(s1.getLocation(), s2.getLocation(), 160, null, v1);
    costs.getDistance(s1.getLocation(), s2.getLocation(), 160, v1);
    vrp.getTransportCosts().getTransportCost(s1.getLocation(), s2.getLocation(), 160, null, v1);
    vrp.getTransportCosts().getTransportTime(s1.getLocation(), s2.getLocation(), 160, null, v1);

where s1 is service T62KP2yuAFKqsiScQ, s2 is service G4ZAjHjzTQjATcaMx, and v1 is vehicle wTTMQzKoMMe5uLSjJ.

what does it log?


#3

@jie31best It’s definitely a bug, look at this case -> https://pastebin.com/4j6RLLM0
This shows me that transport time between s1 and s2 is 8 minutes, link above 18-22 lines.
BUT, solution is printed as https://pastebin.com/rjsUpiSE
Here end time of the first service is 10, and arrival time of the second is 10, but should be I think 18, or 20.
Possible solution: use transport time and distance matrix instead, look at this:
https://pastebin.com/tZmVjaBT
Solution is correct:
https://pastebin.com/3cbHaEfU

I am sorry for the external links to pastebin, I can’t find out how to correctly format code here.


#4

lines 18-22 output the following:

0.042301999999999396
8.460399999999879E-4
0.02068499999999318
4.1369999999986363E-4

it shows that the transport time between s1 and s2 is 8.460399999999879E-4, not 8 (suppose you use minute as time unit).

btw, when dealing with lat/lng, you might want to use GreatCircleCosts instead of ManhattanCosts.


#5

I’ve converted to integer, and said 8 minutes. But in the solution we don’t have any transport time between services.
I’ll try GreatCircleCosts later, thanks.


#6

Exactly, in the printed solution it shows integer values only. When the transport time in your example is converted to integer, it becomes 0, and so you don’t see any transport time between services, but actually there is.

For example, if you output the end time of the first activity in the solution like following:

    double firstActEndTime = bestSolution.getRoutes().iterator().next().getActivities().get(0).getEndTime();
    System.out.println(firstActEndTime);

you will get 10.033180000000002, though you see 10 in the printed solution.

The same with the cost. In the printed solution you see 0 as the cost at each activity, but actually the total cost of the solution is 0.12033199999999056.


#7

@jie31best I am sorry it was my mistake, my time and speed units were not consistent, I have fixed this and implemented MatrixBuilder that builds VehicleRoutinTransportCostsMatrix with the graphhopper integration and everything works great. We can close this topic.