A small vrp with the break feature not returning optimal solution

jsprit
1

Hi,

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

The small vrp is defined at the end of the post. Basically what I am trying to test is that, when both travel distance and waiting time impose cost, the vehicle with the break (v2) should take the route because the service time for the break does not have any cost and the total cost is 15. However the solution is that the other vehicle (v1) takes the route and the total cost is 20.

Interesting thing is that, if I change the start location of v1 from (6, 8) to (0, 0), it will not change the cost if v1 takes the route, but the solution will be that v2 takes the route.

Why is that? Am I missing something? Thanks in advance.

Best regards,
He

    VehicleTypeImpl type = VehicleTypeImpl.Builder.newInstance("type")
            .setCostPerWaitingTime(1)
            .build();
    VehicleImpl v1 = VehicleImpl.Builder.newInstance("v1")
            .setType(type)
            .setReturnToDepot(false)
            .setStartLocation(Location.newInstance(6, 8))
            .build();
    VehicleImpl v2 = VehicleImpl.Builder.newInstance("v2")
            .setType(type)
            .setReturnToDepot(false)
            .setStartLocation(Location.newInstance(0, 0))
            .setBreak(
                    Break.Builder.newInstance("break")
                            .setServiceTime(5)
                            .addTimeWindow(10, 15)
                            .build()
            )
            .build();

    Service s1 = Service.Builder.newInstance("s1").setLocation(Location.newInstance(6, 8)).build();
    Service s2 = Service.Builder.newInstance("s2").setLocation(Location.newInstance(8, 6))
            .addTimeWindow(20, 100)
            .build();

    VehicleRoutingProblem problem = VehicleRoutingProblem.Builder.newInstance()
            .addJob(s1).addJob(s2)
            .addVehicle(v1)
            .addVehicle(v2)
            .setFleetSize(VehicleRoutingProblem.FleetSize.FINITE)
            .build();

    Collection<VehicleRoutingProblemSolution> allSolutions = Jsprit.createAlgorithm(problem).searchSolutions();
    VehicleRoutingProblemSolution solution = Solutions.bestOf(allSolutions);
    SolutionPrinter.print(problem, solution, SolutionPrinter.Print.VERBOSE);
2

Btw, originally I was trying to define the vehicle type as follows but it did not work as expected:

    VehicleTypeImpl type = VehicleTypeImpl.Builder.newInstance("type")
            .setCostPerWaitingTime(1)
            .setCostPerDistance(0)
            .setCostPerTransportTime(1)
            .build();

The transport time did not impose any cost. Why?

EDIT:

hmm, simply because the CrowFlyCosts calculator does not consider transport time cost.

1 Like
3

Does this also solve the first post?

4

Ah, no. This is just a “btw”, not really related. Probably I should not have put it here, sorry about the confusion.

5

now a related issue:

when I change the latest start time of the break of v2 to something greater than or equal to 20 (the earliest start time of s2), v2 will not take the break and the cost of it taking the route increases to 20 (would be 15 if it takes the break).

It seems Jsprit tends to avoid break when possible, even though taking it will lead to smaller cost?

EDIT:

Indeed, Jsprit tries to add break only when the route end time (without break) is later than break latest start time.

6

Hi @stefan,

Have you been able to reproduce the issue in the OP? What do you think? Thanks.

Best regards,
He

7

Hi He,
Ok. I run your problem and see your point. Still, I do not know a good explanation for that … need to look further.
Best, Stefan

8

Cool, thanks. Please kindly let me know when you look into this further. :slight_smile: