Heuristics speed-up

[jcoupey]

Solving time spent during the heuristic process is usually quite low compared to overall solving time. It can nonetheless become very long when solving huge problem instances, especially with few constraints.

For a given vehicle/route construction in progress, what we do is loop through all unassigned jobs to evaluate insertion cost (actually a mix of actual cost and regret ponderation) at all possible route ranks, then pick the lowest cost. Looping through the existing route for all unassigned jobs means the process does not scale very well with very long vehicle routes (e.g. ~500 jobs per route and thousands of jobs).

I think we could come up with ways to maintain some data per route and unassigned job that would yield an easy lower bound of the insertion cost. This way whenever we have existing valid insertion candidates with low enough insertion cost, we could cut out the at all possible route ranks part for many unassigned candidates.