@roganjosh pointed me to this paper. Thanks, @roganjosh, for this. I find it very interesting and like to implement and test the proposed strategies. This topic here is to discuss interesting thoughts and findings.
references that might be of interests:
I guess I thought you’d already seen it 
I gave that response because I’d read a few articles that day and academia seems determined to get to best-known solutions. It started to irk me 
I don’t think vehicle routing is used so much these days for that; some companies might want absolute efficiency in planning their fleet movement but actually, for on-demand services, it’s used more as a tool to answer “can I accommodate this job?” and, if so, “when?”. I don’t think new companies are so determined to know that they have the most efficient calculated route (conjecture!). It would be nice if academia and industry could be better aligned on this, but the industry is moving very fast and in divergent ways in the services they provide.
I’ve found jsprit to be pretty efficient in what it seems to want to be; a general purpose routing algorithm that covers a lot of scenarios (this is a good thing). The paper I linked didn’t have too many constraints. It really depends on how much work you think it would be to implement a new ruin/recreate strategy. The observations about the proportion of jobs ruined on each iteration might be easy enough to implement, I’m not so sure on the ease of the insertion strategy or whether I agree with it in a more constrained problem.
Their ruin strategies (string and split-string) are different to what is already available in jsprit and I think it is definitely worth a trial. I dont think that this is difficult to implement. I just need to understand the details which does not seem to be difficult as well (just flew over yesterday).
The ruin part of the above paper is now available in the master, thus one can play with it by increasing the probability of Strategy.STRING_BEST and Strategy.STRING_REGRET. It can be configured by setting K_MIN, K_MAX (no of routes to be ruined) and L_MIN, L_MAX (string length to be ruined). It is not yet exactly what is described in the paper since the insertion part is still inclomplete. I just used the insertion strategies available, i.e. Best- and RegretInsertion. One can nicely visualize this with AlgorithmEventRecorder/Viewer. It helps to understand how this strategy works. I really like it.
2 Likes