GraphHopper.com | Forum | GitHub | Maps | Blog

How HardConstraint works behind the scenes


#1

Hi,

I’ve been trying to implement multiple custom HardConstraints - MaxDrivingTime, MaxJobs, MaxActivities, DisallowedVehicles (for shipments and services) and currently neither of them seem to be working. Well, I found the fault why my constraints werent working, mainly the usage of getRoute().getVehicle() instead of getNewVehicle(), thanks for the help of everyone. I will be closing this thread if I knew how :smiley: .
I’ve checked the fulfilled method through debugging and it reacts how it should to routes, yet somehow jobs that do not fulfill the constraint end up as BestSolution. What it does is only filter bad solutions to certain extent - 10% bad solutions.

As far as I know HardConstraints should eliminate every Not_Fulfilled solution.
Also that Ruin could be the problem for those constraints.
And that possible solutions could be applying the constraint twice, either by adding it to RuinListener or by adding it to customCostCalculator .

My questions are:

  • When is HardConstraint in JSprit applied? Are there any gaps other than Ruin?
  • What are the default HardConstraints?
  • What is the difference iFacts.getRoute().getVehicle() and iFacts.getNewVehicle() [iFacts being JobInsertionContext]
  • What happens if there are 2 constraints that directly oppose each other?

for example (opossing hardConstraints): route every job & limit routing to only jobs that are services

Answers:

  1. ServiceInsertionCalculator and ShipmentInsertionCalculator (jie31best)
  2. TimeWindow, Load, Skills and SwitchNotFeasible found at AlgorithmUtil.class
  3. iFacts.getRoute().getVehicle() is vehicle which already went through HardConstraints. iFacts.getNewVehicle() is the one that should be tested

#2

Hi Xuan

Im not an expert on this matter and I struggle with some of the same problems. A couple of things I’ve picked up on recently are:

I understand that hardActivityConstraints are applied as a “proposal” to insert the job into the route. If you return fulfilled, otherwise not.

Im not sure when hardRouteConstraints are applied but I suspect it is also as a proposal to insert a job.

Things like disallowed vehicles are fairly easy to implement usually. You can use a hard activity constraint, or you could use features and skills which are really hard constraints.

I dont understand why an unfulfilled condition sometimes ends up in the best solution. I have implemented a SolutionCostCalculator as an objectiveFunction call back (.setObjectiveFunction(solutionCostCalculator)) with some success, however this is behaves more like a soft constraint and does not guarantee that the final solution won’t have bad jobs.

I need to learn more about the RuinListener. Perhaps a ruin listener could target specific jobs to remove from the route - but I dont know enough about it yet and have not found a good source of info on the topic.

I’ll be watching your post to see what the gurus have to say.

regards
Grant


#3

Hi, I understand what you mean, by saying that disallowed_vehicles could be added through skills. But the way I see it, it ends up being this way, if I had 2 vehicles:
Service skill - not_vehicle_2
Vehicle_1 skill - not_vehicle_2
Vehicle_2 skill - not_vehicle_1

It looks fine, but if I have 50 vehicles it becomes very clunky and every vehicle would need to have 49 skills by default. If you meant a different solution, then could you specify it a little bit more?


#4

Ok, from my research - getNewVehicle() is the one that should be checked by hardconstraint. getRoute().getVehicle() is the old vehicle that already works.


#5

Hi

Features and skills only work (so far as I know) in the positive sense. That is to say if a job has a feature requirement of “crane” then it will only be assigned to a vehicle that has a “crane” feature.

An example we have (and use) of vehicles being “not allowed” is that some of our vehicles are not allowed into certain areas of a city. So we add a “city” feature to those vehicles that are allowed. Then when we create the jobs we check the post code of the job against a list of restricted locations and if it is restricted we add a “city” feature requirement to the job. It only requires a one time setup to authorise vehicles and then it is automagic. I dont know if this helps.

Yes I also believe that to be true.


#6

You can check the ServiceInsertionCalculator and the ShipmentInsertionCalculator, and look for the calls of “checkRouteContraints” and “fulfilled” methods for when hard route constraints and hard activity constraints are checked, respectively.