Idea: hard constraints and ruin strategies

This is not a proposal at the moment, only an idea to think of.

The problem with many of the hard constraints that ruin doesn’t honor them. The most common case when two or more jobs are interrelated by the constraint, because the ruin strategies removes the jobs individually. Detecting these inter-job relations can’t be fully automated (or not cost effective) because of the freedom of the constraint implementation.

An easy solution would be if the hard constraint could do the detection itself. (After all it is the only class knowing what it is doing. ;-)) The hard constraint interface could get a new optional function. This function would receive a route and a job. It would return a set of jobs: all the jobs that should be removed to keep the constraint valid. The default implemetation should return a one-item set of the job received as parameter, making the change backward compatible.

A ruin strategy, when it is about to remove a job, calls this function of each constraints and takes the union of all the returned sets. This should be done repeatedly while new jobs are added to the set (transitivity). Then it could decide to remove all these jobs or keep them.

This is not a perfect solution and can’t handle all the possible constraints, but most of the time it would work. Also, by providing the default behavoiur, it could be implemented backward compatibly.

Performance issues: When there are several constraints and they are weaves through the jobs complexly, it would need several iterations to map all dependencies, and could cause a kind of freeze, because too many jobs should be removed together. But most of the cases, when only “A depends on B” or “NOT(A XOR B)” constraints are there (which is the case most of the time), it would work fast and would keep the constraints intact.

Special case: The new function could return an empty set (not including even the job in question) which is a way to implement fixed, unmovable jobs.

4 Likes

Thanks for bringing this idea. I am of the view that just as we can constraint the insertion of job in Route by HardActivityConstraint or HardRouteConstraint, we should also have some mechanism to constraint whether or not a job can be removed from route during ruin operation. It so happens that removal of job from route in ruin process can itself some time leads to infeasible route.