Optional Nodes and ApplyLocksToAllVehicles

[sean.r...@ucd.ie]

Hi All, 

I am working on some large VRPs with a lot of constraints (Time Windows, Skill requirements, maximum travel distance, latest home time, and individual driver working hours) with approximately 1500 - 2000 nodes and 300 vehicles. 

As the constraints were added, it became harder to find a solution, whereby the solver would exit after the time limit (1 hour) with no solution found. All of the nodes were optional so this seemed like at least some sort of result should be returned, so I started using ALL_UNPERFORMED as the search strategy and this at least guaranteed that a solution would be found.

The latest part I need to implement and get working is a small number of jobs (~40) that must be be visited first by a specific driver first on their route. 

I have tried putting very large penalties on these (100 to 50000 times the penalty applied to normal jobs) but sometimes they would still not be visited.

I tried using partial routes, but any time i use ApplyLocksToAllVehicles with just these jobs the solver exits immediately with no solution.

I have also tried introducing these as an initial assignment (like in the example) but still some are left off the routes. 

Does anyone have any suggestions of how to go about helping with the situation by speeding things up or another way to encourage the solver to put those node where I need them?

If necessary I can produce an example, but it will take a little work to pull the important bits out of a larger system and put it together...

Thanks

Sean