This paper presents a metaheuristic approach for the resource constrained elementary shortest path problem (RCESPP). RCESPP 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

Guerriero, Francesca;Di Puglia Pugliese, Luigi;Macrina, Giusy
2019

Abstract

This paper presents a metaheuristic approach for the resource constrained elementary shortest path problem (RCESPP). RCESPP 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.
constrained shortest paths; hybrid approach; local search methods; Rollout metaheuristic; Software; Control and Optimization; Applied Mathematics
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.11770/289877
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 4
social impact