I need to constrain a truck to pickup from no more than X sites during a route. I have written a hard constraint but it does not work. I can’t figure out what Im doing wrong.
Any help would be appreciated.
Here is the constraint code:
// ensure that no more than MAX_PICKUP_SITES are added to the route.
public class HC_MaxPickupSitesPerRoute implements HardActivityConstraint {
private final int MAX_PICKUP_SITES = 3;
private Set depotList = new HashSet();
HC_MaxPickupSitesPerRoute(){
} @Override
public ConstraintsStatus fulfilled(JobInsertionContext iFacts, TourActivity prevAct, TourActivity newAct, TourActivity nextAct, double prevActDepTime) {
List activities = iFacts.getRoute().getActivities();
for(TourActivity act: activities){
if(act instanceof PickupShipment){
if(!depotList.contains(act.getLocation().getId())){
depotList.add(act.getLocation().getId());
}
}
}
if(depotList.size() < MAX_PICKUP_SITES || depotList.contains((String) newAct.getLocation().getId())){
return ConstraintsStatus.FULFILLED;
}
if(depotList.size() >= MAX_PICKUP_SITES){
Utils.LOGGER.log(Level.INFO, “Too many pickup locations. Cant add this one” );
return ConstraintsStatus.NOT_FULFILLED;
}
return ConstraintsStatus.FULFILLED; // we have to return something so this is a fall through but should not get here.
}
after you added the pickup, the next activity that you will check if you can add it, it will be the shipment, so you cannot add it because you have MAX_PICKUP_SITES pickup locations…
fulfilled called, but it does not mean that the job will be inserted…
public class HC_MaxPickupSitesPerRoute implements HardActivityConstraint, IterationEndsListener, JobInsertedListener {
private final Set pickupLocations = new HashSet<>();
private final int MAX_PICKUP_SITES = 3;
@Override
public void informIterationEnds(int i, VehicleRoutingProblem vehicleRoutingProblem, Collection<VehicleRoutingProblemSolution> collection) {
pickupLocations.clear();
}
@Override
public void informJobInserted(Job job, VehicleRoute vehicleRoute, double v, double v1) {
if (job instanceof Shipment)
pickupLocations.add(((Shipment) job).getPickupLocation().getId());
}
@Override
public ConstraintsStatus fulfilled(JobInsertionContext jobInsertionContext, TourActivity tourActivity, TourActivity newAct, TourActivity tourActivity2, double v) {
if (newAct instanceof PickupShipment && pickupLocations.size() == MAX_PICKUP_SITES && !pickupLocations.contains(newAct.getLocation().getId()))
return ConstraintsStatus.NOT_FULFILLED;
return ConstraintsStatus.FULFILLED;
}
Thankyou kandelirina for your input. I may not have been precise enough in that what I need is for the maximum number of pickup locations per route to be limited - not per problem.
However your comments made me realise I had made a fundamental error in not constraining the test overall to pickups. I have fixed that and the code below works correctly.
However I have found it is not thread safe. If I run a single thread it works fine, but with multiple threads I end up with routes with more than the limit of pickup locations. I think I need to use a state manager to make it thread safe. Would you agree ?
I’m not experienced in building a state manager and although I’ve browsed some examples found Im not getting the basic structure of how to work them.
Could you, or someone, pls give some guidance on how to build a state manager for this problem ?
many thanks
Grant
public class HC_MaxPickupSitesPerRoute implements HardActivityConstraint {
private int maxPickupSites;
private Set<String> depotList = new HashSet<String>();
HC_MaxPickupSitesPerRoute(int a ){
Utils.LOGGER.log(Level.INFO, " Max Pickup locations per route: " + a);
this.maxPickupSites = a;
}
@Override
public ConstraintsStatus fulfilled(JobInsertionContext iFacts, TourActivity prevAct, TourActivity newAct, TourActivity nextAct, double prevActDepTime) {
if(newAct instanceof PickupShipment){
List<TourActivity> activities = iFacts.getRoute().getActivities();
// build a list of unique delivery sites for this vehicle in this route.
depotList.clear();
for(TourActivity act: activities){
if(act instanceof PickupShipment){
if(!depotList.contains(act.getLocation().getId())){
depotList.add(act.getLocation().getId());
}
}
}
// if we already have that site listed then it is ok.
if(depotList.contains((String) newAct.getLocation().getId())){
return ConstraintsStatus.FULFILLED;
}
// if there is no room then we say no.
if(depotList.size() >= maxPickupSites ){
return ConstraintsStatus.NOT_FULFILLED;
}
}
return ConstraintsStatus.FULFILLED; // we have to return something so this is a fall through for deliveries.
}
}
just move the depotList to be function local variable… so in HC_MaxPickupSitesPerRoute class only one local variable, maxPickupSites.
but take in account that fulfilled function have to be very fast, because of amounts of calls to it…
public ConstraintsStatus fulfilled(JobInsertionContext iFacts, TourActivity prevAct, TourActivity newAct, TourActivity nextAct, double prevActDepTime) {
if(newAct instanceof PickupShipment){
List activities = iFacts.getRoute().getActivities();
// build a list of unique delivery sites for this vehicle in this route.
final var depotList = new HashSet<>();
for(TourActivity act: activities)
if(act instanceof PickupShipment)
depotList.add(act.getLocation().getId());
// if we already have that site listed then it is ok.
if(depotList.contains((String) newAct.getLocation().getId())){
return ConstraintsStatus.FULFILLED;
}
// if there is no room then we say no.
if(depotList.size() >= maxPickupSites ){
return ConstraintsStatus.NOT_FULFILLED;
}
}
return ConstraintsStatus.FULFILLED; // we have to return something so this is a fall through for deliveries.
}
Thanks again - great input. I must admit I did not realise that Set.add(item) already did the check to see if the item existed. It is now running great and I appreciate your help.
I have another issue (unrelated) but I’ll post it separately so that this can be marked as resolved.
It seems your problem has already been resolved, but I’ll put in my two cents here anyways.
Perhaps you’d better use a route constraint instead of an activity constraint in your case, because the constraint has nothing to do with which position in the route the activity is inserted at, and it would be more efficient;
In general, we would try to avoid looping over the activities in the route in a constraint (esp. in an activity constraint), because it would be very inefficient;
State updater is the way to go. With them, you can calculate and store states that you would like to use later in constraints in order to avoid unnecessary repeated calculations.
For example, in your case, you would want a state updater to record the depotList for each route. It would be like this:
(1) It implements ActivityVisitor and StateUpdater;
(2) In begin(), you have
depotList = new HashSet<>();
(3) In visit(), you add pickup locations to the set;
(4) In finish(), you record the route state by
stateManager.putRouteState(route, **some state id**, depotList);
(5) Then in the constraint, when you need the depotList for a particular route, you call
depotList = stateManager.getRouteState(route, **the same state id**, Set.class);
