Selective arc-ng pricing for vehicle routing
| Autor: | Luciano Costa, Claudio Contardo, Diego Pecin, Guy Desaulniers |
|---|---|
| Přispěvatelé: | Econometrics |
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
Mathematical optimization
021103 operations research Computer science Strategy and Management Existential quantification 0211 other engineering and technologies 02 engineering and technology Management Science and Operations Research Column (database) Computer Science Applications Set (abstract data type) Management of Technology and Innovation Vehicle routing problem Path (graph theory) 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Column generation Relaxation (approximation) Business and International Management Reduced cost |
| Zdroj: | International Transactions in Operational Research, 28(5), 2633-2690. Blackwell Publishing |
| ISSN: | 1475-3995 0969-6016 |
| DOI: | 10.1111/itor.12911 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|