Premium
Selective arc‐ng pricing for vehicle routing
Author(s) -
Costa Luciano,
Contardo Claudio,
Desaulniers Guy,
Pecin Diego
Publication year - 2021
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/itor.12911
Subject(s) - column generation , solver , mathematical optimization , computer science , path (computing) , relaxation (psychology) , set (abstract data type) , vehicle routing problem , routing (electronic design automation) , mathematics , psychology , social psychology , computer network , programming language
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.