Another bug with the vehicle break?

jsprit
1

Hi,

I am still testing with the break feature and have encountered the following issue.

The small vrp is defined at the end of the post. Basically I have 1) one vehicle with time window 0~25, start location (1,0) and open route; and 2) 20 services with no time window and each with service time 1, and 10 of them are at location (0,0) while the other 10 are at location (0,1). The vehicle has a break with time window 10~10 and service time 1.

Obviously the optimal solution would be to firstly travel to (0,0) and serve the 10 jobs there (take the break after the 9th job), and then travel to (0,1) and serve the other 10 jobs there and stop. The cost would be 2.

However, the solution I got was to travel to (0,1) first and serve the 10 jobs there, and then travel to (0,0) and serve the other 10 jobs there and stop. The cost was 2.414. The detailed solution is attached at the end after the code of constructing the vrp.

There are two issues with the solution:

  1. Obviously this is not the optimal solution; and

  2. The vehicle takes unnecessary waiting before the break.

What do you think? Is this also a bug?

Best regards,
He

P.S.

Two further findings:

  1. If I set a waiting cost to the vehicle type, e.g., .setCostPerWaitingTime(0.001), the solution would be correct: no unnecessary waiting, and the vehicle travels to (0,0) first and then (0,1);

  2. If I increase the vehicle end time to 28, the solution would return the optimal sequence (i.e., go to (0,0) first), but still with unnecessary waiting.

     VehicleTypeImpl type = VehicleTypeImpl.Builder.newInstance("type")
     .build();
 VehicleImpl v1 = VehicleImpl.Builder.newInstance("v1")
     .setType(type)
     .setReturnToDepot(false)
     .setStartLocation(Location.newInstance(1, 0))
     .setEarliestStart(0)
     .setLatestArrival(25)
     .setBreak(
         Break.Builder.newInstance("break")
             .setServiceTime(1)
             .addTimeWindow(10, 10)
             .build()
     )
     .build();

 List<Service> serviceList = new ArrayList<>();
 for (int i = 0; i < 10; i++) {
     Service service = Service.Builder.newInstance("s" + i)
         .setLocation(Location.newInstance(0, 0))
         .setServiceTime(1)
         .build();
     serviceList.add(service);
 }
 for (int i = 10; i < 20; i++) {
     Service service = Service.Builder.newInstance("s" + i)
         .setLocation(Location.newInstance(0, 1))
         .setServiceTime(1)
         .build();
     serviceList.add(service);
 }

 VehicleRoutingProblem vrp = VehicleRoutingProblem.Builder.newInstance()
     .addAllJobs(serviceList)
     .addVehicle(v1)
     .setFleetSize(VehicleRoutingProblem.FleetSize.FINITE)
     .build();

 VehicleRoutingAlgorithm algorithm = Jsprit.Builder.newInstance(vrp).buildAlgorithm();
 VehicleRoutingProblemSolution s = Solutions.bestOf(algorithm.searchSolutions());
 SolutionPrinter.print(vrp, s, SolutionPrinter.Print.VERBOSE);

±---------------------------------------------------------+
| solution |
±--------------±-----------------------------------------+
| indicator | value |
±--------------±-----------------------------------------+
| costs | 2.414213562373095 |
| noVehicles | 1 |
| unassgndJobs | 0 |
±---------------------------------------------------------+
±-------------------------------------------------------------------------------------------------------------------------------+
| detailed solution |
±--------±---------------------±----------------------±----------------±----------------±----------------±----------------+
| route | vehicle | activity | job | arrTime | endTime | costs |
±--------±---------------------±----------------------±----------------±----------------±----------------±----------------+
| 1 | v1 | start | - | undef | 0 | 0 |
| 1 | v1 | service | s17 | 1 | 2 | 1 |
| 1 | v1 | service | s16 | 2 | 3 | 1 |
| 1 | v1 | service | s12 | 3 | 4 | 1 |
| 1 | v1 | service | s11 | 4 | 5 | 1 |
| 1 | v1 | service | s10 | 5 | 6 | 1 |
| 1 | v1 | service | s13 | 6 | 7 | 1 |
| 1 | v1 | service | s14 | 7 | 8 | 1 |
| 1 | v1 | break | break | 8 | 11 | 1 |
| 1 | v1 | service | s19 | 11 | 12 | 1 |
| 1 | v1 | service | s15 | 12 | 13 | 1 |
| 1 | v1 | service | s18 | 13 | 14 | 1 |
| 1 | v1 | service | s5 | 15 | 16 | 2 |
| 1 | v1 | service | s3 | 16 | 17 | 2 |
| 1 | v1 | service | s0 | 17 | 18 | 2 |
| 1 | v1 | service | s1 | 18 | 19 | 2 |
| 1 | v1 | service | s4 | 19 | 20 | 2 |
| 1 | v1 | service | s8 | 20 | 21 | 2 |
| 1 | v1 | service | s6 | 21 | 22 | 2 |
| 1 | v1 | service | s2 | 22 | 23 | 2 |
| 1 | v1 | service | s9 | 23 | 24 | 2 |
| 1 | v1 | service | s7 | 24 | 25 | 2 |
| 1 | v1 | end | - | 25 | undef | 2 |
±-------------------------------------------------------------------------------------------------------------------------------+

1 Like
2

Can you put it on the issue tracker as well. Just add it to your last entry. I am looking at this asap.
Thanks for detecting. Best, Stefan

3

a temporal fix for this issue would be to force a waiting cost for break, for example, add the following to WaitingTimeCosts:

if (tourAct instanceof BreakActivity)
    waiting += 0.001 * Math.max(0., tourAct.getTheoreticalEarliestOperationStartTime() - arrivalTime);

but I have not yet figured out why in the original case the break would change the sequence.

@stefan what do you think?