5
$\begingroup$

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.

$\endgroup$

1 Answer 1

6
$\begingroup$

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.

$\endgroup$
2
  • 3
    $\begingroup$ "Nevertheless, building an initial solution to the CVRP that is feasible ("complete") is not difficult". If you work with a fixed fleet size, finding a feasible solution is hard as you in principle need to solve a GAP. $\endgroup$
    – Sune
    Feb 20, 2021 at 8:24
  • 1
    $\begingroup$ Of course. The remark holds for unlimited fleet size. $\endgroup$
    – Hexaly
    Feb 20, 2021 at 9:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.