Selective arc‐ng pricing for vehicle routing. (5th December 2020)

• Record Type: Journal Article
• Authors: Costa, Luciano; Contardo, Claudio; Desaulniers, Guy; Pecin, Diego
• Is Part Of: International transactions in operational research. Volume 28:Number 5(2021)
• Page Start: 2633
• Page End: 2690
• Publication Date: 2020-12-05
• Subjects: column generation -- shortest path problem with resource constraints -- selective pricing -- vehicle routing; Operations research -- Periodicals; 003
• DOI: 10.1111/itor.12911
• Languages: English
• ISSNs: 0969-6016

Abstract

Abstract: Column generation algorithms for solving vehicle routing problems often rely on a relaxed pricing subproblem where routes may be nonelementary and which is solved by a labeling algorithm. This pricing algorithm is said to be selective if it can discard nonelementary paths that may be Pareto‐optimal but guarantees finding at least one (not necessarily elementary) path of negative reduced cost when there exists at least one elementary path of negative reduced cost. In this paper, we propose a selective pricing mechanism for a recently introduced variant of the ng ‐route relaxation, in which the neighborhoods are associated with arcs instead of nodes. We extend a state‐of‐the‐art set‐based dominance criterion for this problem and show, by means of an exhaustive computational campaign, that the resulting mechanism is effective at reducing the number of nondominated labels as compared to the original pricing algorithm for the same problem. As a result, typically shorter computing times are required to compute similar lower bounds when the proposed mechanism is embedded within a column generation solver.