This paper presents a metaheuristic approach for the resource constrained elementary shortest path problem (). arises as pricing problem, when the vehicle routing problem is solved by branch-and-price algorithms. The availability of efficient metaheuristic and optimal solution approaches has contributed to the success of solution procedures based on column-generation. We focus on rollout strategies integrated with local search strategies. The scientific literature considers metaheuristics based on a tabu search procedure in order to price out columns. A comparative analysis between the proposed rollout approaches and the tabu search is conduced and the effectiveness of our proposed algorithms is tested. A comparison with exact solution approaches is also carried out in order to assess the behaviour of the implemented solution strategies in terms of both efficiency and solution quality.
A rollout algorithm for the resource constrained elementary shortest path problem
Di Puglia Pugliese, Luigi;
2019
Abstract
This paper presents a metaheuristic approach for the resource constrained elementary shortest path problem (). arises as pricing problem, when the vehicle routing problem is solved by branch-and-price algorithms. The availability of efficient metaheuristic and optimal solution approaches has contributed to the success of solution procedures based on column-generation. We focus on rollout strategies integrated with local search strategies. The scientific literature considers metaheuristics based on a tabu search procedure in order to price out columns. A comparative analysis between the proposed rollout approaches and the tabu search is conduced and the effectiveness of our proposed algorithms is tested. A comparison with exact solution approaches is also carried out in order to assess the behaviour of the implemented solution strategies in terms of both efficiency and solution quality.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
