Consider negative values for dropoffs

jsprit
1

I have implemented two state updaters and a constraint to handle that never should a route’s load go under zero. Currently, if a route has load 0 and get a new job with negative load it allows inserting and the load remains on zero.

My implementation works most of the times but there are a couple of edge cases where I would love a second opinion.

My updaters set, per activity, the minimum load, both future and past. The constraint is a HardActivityConstraint.

My problem is that assuming I have 4 services

Service 1 and 3 has load 1
Service 2 and 4 has load -1

My vehicle has load 1 as well. There are more jobs and vehicles in my edge case examples but this is the important part.

At one point of the algorithm calculations, the algorithm creates for the constraint, the route 1,2,4 which is invalid because at one point it does have negative load so I should reject it, but the job getting inserted is job 3 at index 0 so it fixes the route because there is no longer a negative load.

The problem is that if I mark it as fulfilled then not only does the problem assumes that 3,1,2,4 is a successful route but also 1,2,4. In the end the 3 is assigned to another route and I’m left with 1,2,4 which is incorrect.

Is this the correct approach or would it be wiser to user other type of constraint? I can share source code but it is in Kotlin.

Thanks in advance for any input.

2

I’ve tried a few times to get my head around this in the context of a real-world problem but failed. Negative load is not allowed normally, so you’ve overridden jsprit core? What is the actual issue you are trying to solve?

which is invalid because at one point it does have negative load so I should reject it

This would be the case in a standard pickup/delivery problem. Can you elaborate on the use case?

3

I handle this when a pickup/dropoff activity do not have a one to one relationship. Let’s say your warehouses around a city have stock limit of 5 items, each must be delivered to a specific location. So a car picks them up with a capacity of 5.

The driver should only be able to do no more than 5 dropoffs, if he tries to 6 or more it should be invalid since they only had 5 packages to deliver.

In this case it could be wise to model it as 5 shipments but my real-life use case considers multiple pickup places. I managed to model it, for the moment with HardActivityConstraint while updating a MIN_LOAD state so it doesn’t fall beneath zero.

4

I’m afraid I still don’t understand the deviation from a normal pickup/delivery scenario. The vehicle departs the initial depot with its initial load and treats every other depot like a customer (where you can have one-to-many relationship between pickup and delivery in the same location). There should be no need to implement any constraints over the jsprit baseline.