Question on break activity location when inserting a regular job activity


When inserting a regular job activity into a route which contains a break activity, during the evaluation, the location of the break activity is fixed. Will this possibly lead to sub-optimal solution?

An illustrative example is given below, and analysis follows next.

Best regards,

    VehicleTypeImpl type = VehicleTypeImpl.Builder.newInstance("type")
    VehicleImpl v1 = VehicleImpl.Builder.newInstance("v1")
        .setStartLocation(Location.newInstance(0, 0))
                .addTimeWindow(1, 6)
    Delivery s0 = Delivery.Builder.newInstance("X")
        .setLocation(Location.newInstance(1, 3))
        .addTimeWindow(2, 4)
    Delivery s1 = Delivery.Builder.newInstance("A")
        .setLocation(Location.newInstance(1, 0))
        .addTimeWindow(1, 1)
    Delivery s2 = Delivery.Builder.newInstance("C")
        .setLocation(Location.newInstance(5, 0))
    VehicleRoute initialRoute = VehicleRoute.Builder.newInstance(v1)
    VehicleRoutingProblem vrp = VehicleRoutingProblem.Builder.newInstance()

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

In the above example, when trying to insert new activity X, the current route contains 3 tour activities in sequence ABC, where B is a break activity, and the location of B is the same as that of A at this point. The locations of A, B and X are different. Insertion of X before A or after C is not possible due to time window constraint. Thus, only two possible insertion positions for X are to be evaluated, i.e., 1) b/w A and B; and 2) b/w B and C.

  1. insertion of X b/w A and B is not allowed, because, otherwise, the sequence would be AXBC, the arrival time of B would be 7 (because the location of B is fixed and the same as that of A, even though X is between A and B now) and outside the time window of the break;

  2. insertion of X b/w B and C is also not allowed, because, otherwise, the sequence would be ABXC, the arrival time of X would be 5, which is outside the time window of X.

Thus, the returned solution would be that Delivery X is unassigned.

However, the sequence of AXBC should be perfectly fine (because the location of B should not be the same as that of A in this situation, instead, it would be the same as the location of X). The arrival times at AXBC would be 1, 4, 5, and 11, respectively, all inside corresponding time windows.