Hello. I’m trying to develop more efficient strategies for the ruin/recreate processes regarding the pickup and delivery problem. We have various ideas, and would like to hear any feedback or comments before choosing some to implement. I will describe the strategies in light detail below:
-
Recreate. When a delivery route is chosen, it should be chosen via nearest neighbor (or whatever algorithm is used), but only considering choices that would make it valid – as in, the delivery would be fulfilled by the same vehicle who picked up the package, and that the delivery must be after the pickup. Enforcing this during insertion would speed up the process by reducing the number of invalid solution attempts.
-
Ruin. When a pickup or delivery is ruined, it should also find the corresponding delivery or pickup (respectively) and ruin both connections to that correspondent node as well. Otherwise, during recreation, the ruined nodes will not be able to switch vehicles. Radial ruin works with VRP because the radial circle selects all nearby nodes – which, in the case of VRP, are all the relevant nodes. However, in Pickup and Delivery, relevant nodes include not just nearby nodes but also the corresponding delivery or pickup node.
Has anyone tried any of these approaches? Or does anyone have any feedback on how well you think this would work?
Another item of interest is Tabu search. I worked with Optaplanner earlier to tackle the same pickup and delivery problem, and tabu search greatly outperformed all the other algorithms. Has anyone tried implementing Tabu search in the local/recreate phase of Jsprit?
Much Thanks,
Raymond