Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.
Sign up to join this community
I am solving Capacitated Vehicle Routing Problem (CVRP) with Adaptive Large Neighborhood Search (ALNS) metaheuristic.
I start my algorithm with a random initial solution, but the solution I get is incomplete. There is a node that has not been visited.
Does it cause a problem, in this case, to start with an incomplete initial solution? Is there a way to fix this problem?
My program is in Java. The initial solution is generated randomly.
There is no problem in starting your ALNS with an infeasible (what you call "incomplete") solution. ALNS consists of destroying a part of the solution and then repairing it, at each iteration. Generally, destroying is done by removing a number of tours in the incumbent solution. But you can adapt the method by selecting a number of tours plus some clients which are not delivered.
Nevertheless, building an initial solution to the CVRP that is feasible ("complete") is not difficult. For example, you can use the Clarke & Wright heuristic. Many Java implementations are given on the web; you can find one here. It will considerably speed up the convergence of your ALNS.
