When vehicle switch is allowed, constraints and cost calculators might need to take it into account

jsprit
1

Hi,

When iFacts.getNewVehicle() and iFacts.getRoute().getVehicle() are not the same, i.e., they might differ in start/end location, departure time, returnToDepot, etc., in the constraints and cost calculators, we might need to be careful when calculating the distance/cost from prevAct to nextAct as old distance/cost, because they might be inconsistent with iFacts.getRoute().getVehicle().

For example, nextAct could be End, iFacts.getNewVehicle().isReturnToDepot() could be true, and iFacts.getRoute().getVehicle().isReturnToDepot() could be false. See here for a list of possible cases.

I think AdditionalTransportationCosts and LocalActivityInsertionCostsCalculator would need to be looked into for this issue due to the calculation of tp_costs_prevAct_nextAct, and there might be others.

And I think this is related to the bug I reported here.

This one might also be related.

Best regards,
He

2

EDIT: the previous version was not correct, and below is the updated one.

Please kindly find below a test to illustrate the bug:

There are two vehicles and two pickups in the vrp:
vehicle v1 starts at (0,0) and needs to return to (0,0);
vehicle v2 starts at (0,0) and does not need to return to depot;
pickups p1 and p2 both locate at (10,0).

The route is with v2 and p2.
The insertion is to insert p1 between p2 and End and v1 takes the route.
Want to test the marginal cost. Expected value would be 10, but returned value would be 0, for both LocalActivityInsertionCostsCalculator and AdditionalTransportationCosts. Thus test fails.

@Test
public void whenNewVehDiffFromRouteVeh_costMustBeCorrect() {
    VehicleImpl v1 = VehicleImpl.Builder.newInstance("v1")
            .setStartLocation(Location.newInstance(0, 0))
            .setEndLocation(Location.newInstance(0, 0))
            .build();
    VehicleImpl v2 = VehicleImpl.Builder.newInstance("v2")
            .setStartLocation(Location.newInstance(0, 0))
            .setReturnToDepot(false)
            .build();
    Pickup p1 = Pickup.Builder.newInstance("p1")
            .setLocation(Location.newInstance(10, 0))
            .build();
    Pickup p2 = Pickup.Builder.newInstance("p2")
            .setLocation(Location.newInstance(10, 0))
            .build();
    VehicleRoutingProblem vrp = VehicleRoutingProblem.Builder.newInstance()
            .addVehicle(v1).addVehicle(v2)
            .addJob(p1).addJob(p2)
            .build();
    VehicleRoute route = VehicleRoute.Builder.newInstance(v2)
            .addPickup(p2)
            .build();
    JobInsertionContext jobInsertionContext =
            new JobInsertionContext(route, p1, v1, null, 0);
    LocalActivityInsertionCostsCalculator localActivityInsertionCostsCalculator =
            new LocalActivityInsertionCostsCalculator(
                    vrp.getTransportCosts(),
                    vrp.getActivityCosts(),
                    new StateManager(vrp));
    double cost = localActivityInsertionCostsCalculator.getCosts(
            jobInsertionContext,
            vrp.getActivities(p2).get(0),
            new End(v1.getEndLocation(),0,Double.MAX_VALUE),
            vrp.getActivities(p1).get(0),
            0);
    assertEquals(10., cost, Math.ulp(10.));
    AdditionalTransportationCosts additionalTransportationCosts =
            new AdditionalTransportationCosts(
                    vrp.getTransportCosts(),
                    vrp.getActivityCosts());
    cost = additionalTransportationCosts.getCosts(
            jobInsertionContext,
            vrp.getActivities(p2).get(0),
            vrp.getActivities(p1).get(0),
            new End(v1.getEndLocation(),0,Double.MAX_VALUE),
            0);
    assertEquals(10., cost, Math.ulp(10.));
}
1 Like