Solve TSP if one vehicle is enough?

[tcokyasar44]

I am definitely not an expert in the VRP area, but my very little recent experience showed that solving a VRP solution of which suggests one vehicle use is taking more time than solving the same problem with Gurobi's tsp.py.

If it is possible to see if one vehicle is enough to do the whole delivery/routing prior to starting to solve the VRP, I would suggest the following procedure (and I am pretty sure you can develop it further): 1) solve the problem with a local search/simulated annealing (or any other alternative), 2) feed this solution into Gurobi's tsp.py as a start. Note that Gurobi code should be tweaked a bit to allow asymmetric feature.

[Kuifje02]

Thanks @tcokyasar44 . I have actually been thinking about this lately. You are absolutely right, in case only one vehicle is required, we may need a dedicated strategy. The additional complexity is that although there is a unique vehicle, one may want to satisfy all the other constraints (time windows, capacity, etc), and in this case Gurobi's tsp will not work (as is). But thanks for pointing out this specific case which definitely needs to be adressed in the next versions. I posted a question regarding this issue a while ago on or.stackexchange.

[tcokyasar44]

I don't know how the solution method is constructed, but you may also think of solving TSPs for each vehicle when a feasible (but not optimal) VRP solution is obtained. This simply ensures, for each vehicle we have the optimal TSP solution. Then, swapping (across vehicle sets) algorithms could be used to improve the VRP solution.