why do we need the custom DistanceUpdater ?
Yang Yang
Stefan Schröder
You are
correct. It should just illustrate how you can add your own constraint.
For your understanding:
To define a custom business constraint, you need smth that manages this
constraint, at least somewhere the constraint must live. jsprit uses a ConstraintManager
for this. Currently, the contraints allow you to control the insertion process
and thus they are only called when trying to insert a job. Note that the
overall algorithm basically consists of two steps: ruin (where jobs are removed
from an existing solution) and recreate (where the removed jobs are re-inserted
into the existing solution) (see https://github.com/jsprit/jsprit/wiki/Walkthrough---Algorithm).
When re-inserting the jobs, you can check whether your business constraints hold. There are basically two type of contraints: Hard/SoftRouteConstraint and Hard/SoftActivityConstraint.
HardRouteConstraint: https://github.com/jsprit/jsprit/blob/master/jsprit-core/src/main/java/jsprit/core/problem/constraint/HardRouteConstraint.java
HardActivityConstraint: https://github.com/jsprit/jsprit/blob/master/jsprit-core/src/main/java/jsprit/core/problem/constraint/HardActivityConstraint.java
If you follow the above links, you find a javadoc that should give you more information. The differences between both types are basically related to the level. A route constraint just lets you detect that a constraint cannot be met at an earlier stage (before diving into the activities of this route) and hence, if you can check your constraint at route level, do it, it is just faster. However, some constraint can only be evaluated when looking at particular activity sequences, e.g. actA must occur before actB.
Let me add one thing in regards to ActivityConstraints, if you implement a Hard/SoftActivityConstraint you need to calculate the arrival time at newAct, i.e. the activity to be inserted, with the departureTimeAtPreviousAct (which is another parameter of the method). You CANNOT just retrieve arrTime and depTime from newAct since it just does not have an arrTime or depTime yet. You also need to recalculate the arrTime at nextAct again considering the insertion of newAct. This might be inconvenient, however, what you basically do here, is to check whether it is a good position to insert newAct (which is a whole new scenario). ArrTime and DepTime in prevAct and nextAct are related to the existing route (without newAct).
When it comes to the StateManager, it is important to know that you do not necessarily need states and the StateManager respectively. However, checking constraints is very time consuming, especially when it come to constraints at activity level. Thus, checking them in constant time (by just looking at prevAct, newAct and nextAct) is nice when it comes to the overall computation time (have in mind that activityConstraints might be evaluated million times). For most constraints you require more information to evaluate them than just prevAct, newAct and nextAct. If you have, for example, a capacity constraint, you need to know how much capacity is still available in your vehicle to evaluate the insertion of newAct. There are two alternatives now: either you calculate the available capacity here (which means that you need to loop over the activities of your route again and sum up the consumed capacity) or you just look up the available capacity in your stateManager. The first alternative is very inefficient, since if your route has m activities and thus m-1 positions to insert a newActivity, you have m*(m-1) operations to just check the load constraint. The second alternative can do it with m-1 operations. However, for the latter alternative to work, you need to define a state. In this example, you might name your state ‘loadInRoute’ or smth like that. To be as efficient as possible, you need to recalculate the state ONLY if the state has changed. And a state change happens for example if your route has changed because you inserted a new activity. Therefore, a StateUpdater updates states once states changed. Since for some states you need to loop forward through the route, there is an ActivityVisitor. For other states, you need to loop backwards through your route. Here you can use ReverseActivityVisitor. The StateUpdater interface is just to mark an ActivityVisitor as StateUpdater, since not every ActivityVisitor must be a StateUpdater.