Optaplanner VRP ChainedGraph Value Range on PlanningEntity

Question

I have a variant of a VRP Routing problem in which I would like to make use of Optaplanners(v6.4) ValueRangeProvider feature. However I am a little confused as to how it works in some cases. My understanding is that If I chose a set of items as the value range for a Customer Object, that customer instance's previousStandStill may only be a StandStill in that Range.

In my case I have a Some customers that might have already been Assigned. I would like to limit the search Space such that Assigned Trips don't waste time getting matched to other Vehicles. Im expecting a Large number of Customer so I am looking to increase performance as much as possible.

I defined the previousStandStill Range as Follows

@PlanningVariable(
        valueRangeProviderRefs = {"possibleVehicles", "possibleCustomersInSameVehicle"},
        graphType = PlanningVariableGraphType.CHAINED)
public Standstill getPreviousStandstill() {
    return previousStandstill;
}

• Assigned Customers "possible Vehicles" will only return the Vehicles they are Assigned to possible Customers will be a List of of All Customers Assigned to the same Vehicle + All Unassigned Customers
• Unassigned Customers will have every vehicle & every Customer in their range.

This seemed to work fine, but there were a couple questionable cases that occurred that gave me a few questions.

1. I modified the data set for one Assigned Customer such that its load was very large (100) when the Capacity of the Vehicle is only 7. My final Solution resulted in a solution Where an Assigned Customer was assigned to a vehicle not in its ValueRange, it was that Vehicles NextCustomer. This obviously broke the Value Range that I set for that Assigned Customer so Im not sure how this Occurred. My only guess is that an Unassigned Customer was Assigned as the FirstCustomer in the Vehicle, followed by the Assigned Customer (UnAssigned is in Value Range). The Unassigned was later moved to a different vehicle thus leaving the Assigned Customer directly after the Vehicle. My Question is will ValueRange allow this to happen is valueRange ever ignored?

2. I ran the same problem by Using the default value range for the VRP problem, but added a rule to penalize when an Assigned Customer is in the Wrong Vehicle. Both solutions resulted in the same answer however this solution seemed to work faster even though the Search Space should have been much larger. Not sure if bug in my code or if this was the case because of a small Test Case was able to be pruned faster.

3. Lastly The Current Value Range technically will allow an Assigned Customer to be assigned after an Unassigned Trip even if the unAssigned is in another Vehicle. is there Any way to model the problem such that The ValueRange is on the Vehicle. So we say this Vehicle may only contain a list of NextCustomers from The Assigned List + Anyone from the UnassignedList?

4. Is value Range checked before each Move is made? Can it be updated while solving?

Answer 1

Correct me if i'am wrong but OptaPlanner User Guide for 6.4.0 Final in the end of "4.3.5.2.3. ValueRangeProvider on the Planning Entity" is a Warning "A ValueRangeProvider on the planning entity is not currently compatible with a chained variable." You should use filter for chained variable to limit the search space.