A rollout algorithm for the resource constrained elementary shortest path problem. (3rd September 2019)

• Record Type: Journal Article
• Authors: Guerriero, Francesca; Di Puglia Pugliese, Luigi; Macrina, Giusy
• Is Part Of: Optimization methods and software. Volume 34:Number 5(2019)
• Page Start: 1056
• Page End: 1074
• Publication Date: 2019-09-03
• Subjects: Rollout metaheuristic -- constrained shortest paths -- local search methods -- hybrid approach; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2018.1551391
• Languages: English
• ISSNs: 1055-6788

Abstract

ABSTRACT: This paper presents a metaheuristic approach for the resource constrained elementary shortest path problem ( R C E S P P ). R C E S P P 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.