I'm investigating how I can combine a construction heuristic and a local search metaheuristic to quickly solve Capacitated Split Delivery Veichle Routing Problem (CSDVRP). The construction heuristic implemented is the one suggested in this paper. First the heuristic creates feasible routes for each vehicle and then uses TSP to solve all the smaller instances individually to optimize the order of the visits for each vehicle. This works good and very fast.
In the paper, conclusion section, the authors suggest that
"the best solution from this construction heuristic could then be used as a starting solution for other methods, such as ..."
I'm wondering why/how one would use other methods if the TSP already optimizes the order (gap = 0% for each route)? What exactly do they mean?
An idea for improvement of my above method
Assume I have the locations [0,...,10] to visit where 0 is the depot and I have 3 vehicles, each with maximum capacity Q, to complete the routes and each location has a certain demand associated with it. Of course the demand at the depot is zero.
The construction heuristic constructs feasible routes and outputs a feasible solution like this:
vehicle 1 = [0,3,7,2,0]
vehicle 2 = [0,5,4,1,0]
vehicle 3 = [0,8,6,9,0]
Then, a TSP is run on each vehicle route and outputs an optimized order for each vehicle, given the starting solution above. As stated earlier, this works pretty well (low duality gap) and completes within 10 seconds even with very large problems (500+ locations). The downside is that the TSP only optimizes each vehicle route and not the whole fleet simultaneously, but what if I could find a better combination initially, outputted by the construction heuristic, and THEN run the TSP? Is there a way to perturb my initial solution and do some sort of local search that swaps locations between the vehicles without exceeding the capacity constraints?
