Returning non-optimal solution when vehicle start/end locations are not the same

jsprit
1

Hi,

I have come across a vrp for which Jsprit does not return optimal solution. The code is attached at the end of the post.

Basically I have two vehicles: v1 starts from (0, 0) and needs to return to the end location (2, 0), and v2 starts from (0, 0) and does not need to return to any depot. And there is a service at (1, 0). Thus, if v1 takes the route, the cost will be 2, while, if v2 takes it, the cost will be 1. However, the solution Jsprit returns is that v1 takes it.

Interesting thing is, if I change the end location of v1 to (0, 0) - the same as the start location, the costs won’t change, but the solution will be that v2 takes the route.

Is this a bug?

Best regards,
He

    VehicleTypeImpl type = VehicleTypeImpl.Builder.newInstance("type")
            .build();
    VehicleImpl v1 = VehicleImpl.Builder.newInstance("v1")
            .setType(type)
            .setReturnToDepot(true)
            .setStartLocation(Location.newInstance(0, 0))
            .setEndLocation(Location.newInstance(2, 0))
            .build();
    VehicleImpl v2 = VehicleImpl.Builder.newInstance("v2")
            .setType(type)
            .setReturnToDepot(false)
            .setStartLocation(Location.newInstance(0, 0))
            .build();
    Service s1 = Service.Builder.newInstance("s1")
            .setLocation(Location.newInstance(1, 0))
            .build();
    VehicleRoutingProblem vrp = VehicleRoutingProblem.Builder.newInstance()
            .addVehicle(v1)
            .addVehicle(v2)
            .addJob(s1)
            .setFleetSize(VehicleRoutingProblem.FleetSize.FINITE)
            .build();
1 Like
2

Hi He,
Thanks for detecting. I opened an issue for that.
Best,
Stefan

3

Hi Stefan,

Do you think this different locations for multiple vehicles thing might be the reason for the issue reported in this post?

Best regards,
He

4

It might be related to that. I am not sure. If states are vehicle dependent, I always update states for each vehicle type - similar to the vehicle type dependent time window update. If you need to constraint distance in route by setting max distance then you obviously need to look at each vehicle type having a different start/end location independently (or - as you also found out already, you need to prohibit vehicle switches, i.e. once a route is conducted by vehicle A, it will always be conducted with vehicle A. thus you would save looking at other vehicles here).

5

I think I have found the cause of this bug. This one is not due to the different vehicle issue I reported here.

The reason is this line:

Consider evaluating the insertion of service s1 into an empty route, and if v1 is the new vehicle, then totalCosts will be 2, and oldCosts will also be 2 due to the aforementioned line, thus the returned cost is 0; on the other hand, if v2 is the new vehicle, then the returned cost will be 1 (due to this line). Thus, the returned solution will be that v1 takes the route (which is not the optimal solution).

When I change the end location of v1 to (0,0), then the returned cost in the above case will be 2, because oldCosts will be 0. Thus the returned solution will be that v2 takes the route (which is the optimal solution).

So perhaps the aforementioned line should set tp_costs_prevAct_nextAct to 0 in that case?

@stefan what do you think?

Best regards,
He

EDIT:

a unit test for LocalActivityInsertionCostsCalculator (applies to AdditionalTransportationCosts too):

@Test
public void whenVehStartEndLocDiff_costMustBeCorrect() {
    VehicleImpl v = VehicleImpl.Builder.newInstance("v")
            .setStartLocation(Location.newInstance(0, 0))
            .setEndLocation(Location.newInstance(20, 0))
            .build();
    Pickup p = Pickup.Builder.newInstance("p")
            .setLocation(Location.newInstance(10, 0))
            .build();
    VehicleRoutingProblem vrp = VehicleRoutingProblem.Builder.newInstance()
            .addVehicle(v)
            .addJob(p)
            .build();
    VehicleRoute route = VehicleRoute.emptyRoute();
    JobInsertionContext jobInsertionContext =
            new JobInsertionContext(route, p, v, null, 0);
    LocalActivityInsertionCostsCalculator localActivityInsertionCostsCalculator =
            new LocalActivityInsertionCostsCalculator(
                    vrp.getTransportCosts(),
                    vrp.getActivityCosts(),
                    new StateManager(vrp));
    double cost = localActivityInsertionCostsCalculator.getCosts(
            jobInsertionContext,
            new Start(v.getStartLocation(),0,Double.MAX_VALUE),
            new End(v.getEndLocation(),0,Double.MAX_VALUE),
            vrp.getActivities(p).get(0),
            0);
    assertEquals(20., cost, Math.ulp(20.));
}
1 Like
6

Thanks a lot, He. I ll check this asap. it would be even better you wrote a unit test, fixed it with your solution and made a pull request? Also you sent me a unit test via discuss which is great. Thanks a lot for it, but why dont you add the unit test to your fork of jsprit and make a pull request. This is much easier for me to keep track and to fix this asap. If you need help with regard to pull request etc., just let me know. I can help :slight_smile:.