Pinning chained entites

[Frank Förster]

Hi Optaplanners,

I need to fix a planning entity to a certain root in a chained problem.
In VRP words: A customer shall be visited by a certain vehicle. The position (previous/next) of the customer in the chain is not relevant and may be changed by the solver.
Does anyone know if I can use the @PlanningPin to ensure this?

Thx,

Frank

[Jiří Locker]

I'm afraid that's not possible because if you pin a customer in a chained model, it will only become pinned to the previous customer. To make it pinned to a vehicle, you'd have to pin the entire subchain between the vehicle and the customer that you actually want to pin and that's probably not what you want.

But I think you could achieve that using constraints. You can add a "Vehicle preferredVehicle;" field on the Customer and penalize a situation where the preferred vehicle is set and differs from the customer's anchor vehicle.

HTH,

Jiri

[holger brandl]

Thanks Jiri for the details and Frank for the great question.

In case a constraint is not desired, the API docs suggest in https://docs.optaplanner.org/6.2.0.Final/optaplanner-docs/html/ch05.html#buildInHardConstraint to use filtered selection to implement a built-in hard constraint.

Interestingly this part of the manual was revised and does not include this insight any longer, see https://docs.optaplanner.org/9.37.0.Final/optaplanner-docs/html_single/index.html#buildInHardConstraint . Not sure why.

So given the original question, where would one need to adjust selectors to enforce a built-in hard constraint in a chained model (e.g. enforcing that a customer is visited by a certain car in VRP)? Naively I'd think that somehow the construction would first need to be guided to prevent illegit entity2anchor assignments (via the chain) to happen in the first place, and later during LS a SelectionFilter could help to prevent any moves that would violate the built-in hard-constraint.

Would this approach be feasible with API? If so, could you help by sketching out the required configuration to construction heuristic and LS? Or is there maybe some existing example I could learn from?

Thanks & Kind regards,

Holger

[Kent Zhang]

I have another approach to implement in this case. But I don't know if is there any problem with it.
define the value range provider in the planning entity, and filter it in the getter method, such as:

@ValueRangeProvider
 public List<Vehicle> getPossibleVehicleList() {
      return possibleVehicleList;
 }

// Save the vehicles that can access this customer.
public void setPossibleVehicleList(List<Vehicle> possibleVehicleList) {
     this.possibleVehicleList = possibleVehicleList;
}

About the value range provider in planning entity, see this chapter:
https://docs.optaplanner.org/9.37.0.Final/optaplanner-docs/html_single/index.html#valueRangeProviderOnPlanningEntity

In some cases, the solver needs to get some solutions that break hard constraints temporarily to escape local optima. So this approach may have an impact on the quality of the solution.

Best regards.
Kent

[holger brandl]

Thanks Kent,

value range provides do not work for chained models afaik (see thread above and docs).

Any other advice on what selectors and/or filters would need to be implemented to enable a built-in assignment constraint as described above for a chained model?

Kind regards,

Holger