Is it possible that a route (list of activities) which fails HardActivityConstraint be part of the final response? I’m currently am experiencing this issue and would like to know if it’s my dab or the library’s.
I’ve made sure every time a route with an specific list of activities goes through a certain constraint it fails, even singled out the shape of it. But it continues to appear.
The other case are routes which never pass by the constraints end up being part of the result.
Hi @aj1310,
According to my experiences, it is likely that your constraint does not consider all possible situations.
For example, if you would like to make a constraint that the delivery of Shipment A must be right after its pickup, then you need:
but this is not sufficient, and you need the following too (which is more likely to be missing):
Hopefully my example is valid and reflects your case.
Best regards,
He
My example does not consider shipments and right now I’m just telling the constraint that a route with ids 1,2,3 is not acceptable but it remains as an answer.
Maybe I’m incorrect but if at least one constraint fails, shouldn’t the route be considered invalid?
The shipment example was just an example to show that a constraint needs to consider all possible situations.
Maybe you can paste your code here and let’s see what the problem is?
Best regards,
He
Hi jie31best,
I too observed that some of the routes of VehicleRoutingProblemSolution does not respect the constraint. In my case, I was trying to implementing the problem in which there were some delivery locations and some pickup locations and some bikes. Constraint was that volume picked between two delivery locations must be less than some number(call it X). Same goes also for, between Start and first delivery location and last delivery location and End. Also I did not force that delivery locations have to be visited, which I ensured by not adding penalty for unassigned delivery jobs in solutions cost calculator. If delivery has to (depending on optimization process and objective function) occur then the above constraint is considered.
Now the interpretation,
Each delivery location comprises of job which contains time window(predefined) in which some bigger vehicle is going to be at that location. Volume to be delivered is considered is zero. Penalty is set to zero which implies that bike does not have to visit these places.
X is actually the bike capacity.
To solve the problem, I considered the bikes to have infinite capacity. Then forced the constraint above mentioned(setting X to be actual bike capacity). Now I also added that between two delivery points, picked volume must be greater than “some value” which I call threshold.
I found that there are cases in which, drop locations are consecutively visited which violates the constraint that picked volume must be greater that some threshold value.
Note that I did not use Delivery Object for locations representing delivery as Delivery Object is made for different purpose.
All object are of Kind Service. I used getName() method to distinguish the deliveries(I named “drop” for deliveries)
Here is the code:
public class ConstraintA implements HardActivityConstraint {
private final int VEHICLE_CAPACITY , THRESHOLD;
public ConstraintA(int vehicleCapacity, double percent) {
this.VEHICLE_CAPACITY = vehicleCapacity;
this.THRESHOLD = (int) (vehicleCapacity * percent);
}
@Override
public ConstraintsStatus fulfilled(JobInsertionContext iFacts, TourActivity prevAct, TourActivity newAct, TourActivity nextAct, double prevActDepTime) {
List<TourActivity> tourActivities = iFacts.getRoute().getActivities();
Job newJob = ((JobActivity) newAct).getJob();
boolean isNewJobDelivery = isJobDelivery.test(newJob);
int[] vol = getPickedVol(tourActivities, prevAct, nextAct);
if (isNewJobDelivery) {
if (vol[0] >= THRESHOLD && vol[1] >= THRESHOLD)
return ConstraintsStatus.FULFILLED;
} else {
if (vol[0] + vol[1] + newJob.getSize().get(0) <= VEHICLE_CAPACITY)
return ConstraintsStatus.FULFILLED;
}
return ConstraintsStatus.NOT_FULFILLED;
}}
// vol has size 2. vol[0] is volume picked from prevAct upto previous delivery and after Start.
// vol[1] is volume picked from nextAct upto next delivery and before End.
isJobDelivery.test is used to test whether or not the current job is delivery.
I think why constraint is not followed is due the ruin precess. Of course, whenever insertion of a TourActivity has to happen the constraint has be followed. But ruin may occur only to subroute of the VehicleRoute and may result into removal of delivery location and inserting into some other route. VehicleRoute from which the delivery location is removed may break the constraint. So in this way we also need to restrict the ruin process and not only the insertion process.
yeah I think in general this is possible (of course it depends on what your constraint is). for example, if I have a constraint that job activities A and B must be in the same route and there must be at least N job activities between them, then I suppose the ruin process could break such constraint.
Can we restrict or customize the ruin process?
out of the box I don’t think so. I think you will have to implement your own ruin strategy.
Currently I am using HardActivityConstraint. Also added softActivityConstraint constraint for the same purpose. Increased the number of iterations, and at the end, from VehicleRoutingAlgorithm.searchSolutions() choosing solution which is most suitable.
I have found that we have very less number of VehicleRoute not respecting the constraint(1 out of 40 route).
Hi,
Restricting the ruin step does not sound like a very good idea as it will go against the basic principle of Ruin and Recreate. Basically ruin step introduces randomness in search and allows the algo to search the solution space rigourously without getting stuck at local minima. If that is restricted algorithm might get stuck at local minima.
However I like your approach of tackling this using soft constraint. With proper soft constraint you can force algo to build routes with minimum constraint violation.
How have you defined the cost for softActivityConstraint?
Amount by which bike violates the constraint * MAX_COST (MAX_COST is some high fix value)
for example, if between two delivery location, picked volume is greater than bike actual capacity then difference of that * MAX_COST. In case it is less than threshold value then (picked vol - threshold)* MAX_COST.
Let me know if it can be further improved.
This looks like a reasonable softConstraint.
Hi,
There is an update.
I am also adding SolutionAcceptor which increases our control.
But it appears to accept some of the unaccepted Solutions.
Does Jsprit stores some of the solutions before it starts using SolutionAcceptor ?
Is that really true? I’m aslo facing a similar problem.
SolutionAcceptor is an interface which adds newSolution to existing collection of solutions and returns true if newSolution is accepted.
I observed that even though I am putting some criteria for solutions to be accepted with the help of SolutionAcceptor, in the end while calling VehicleRoutingAlgorithm.searchSolutions(),some of the vehicleRoutingProblemSolutions were unacceptable i.e. SolutionAcceptor should not have allowed it in the very first place.
I think this may be because, in ruin process stored solutions itself are ruined instead of their cloned version. The better way could be to make a deep copy of solutions before ruining them.