Template-Type: ReDIF-Paper 1.0
Author-Name: Hoogendoorn, Y.N.
Author-Name-Last: Hoogendoorn
Author-Name-First: Ymro
Author-Name: Dalmeijer, K.
Author-Name-Last: Dalmeijer
Author-Name-First: Kevin
Title: Resource-robust valid inequalities for set covering and set partitioning models
Abstract: For a variety of routing and scheduling problems in aviation, shipping, rail, and
 road transportation, the state-of-the-art solution approach is to model the prob-
 lem as a set covering type problem and to use a branch-price-and-cut algorithm to
 solve it. The pricing problem typically takes the form of a Shortest Path Problem
 with Resource Constraints (SPPRC). In this context, valid inequalities are known
 to be `robust' if adding them does not complicate the pricing problem, and `non-
 robust' otherwise. In this paper, we introduce `resource-robust' as a new category
 of valid inequalities between robust and non-robust that can still be incorporated
 without changing the structure of the pricing problem, but only if the SPPRC
 includes specic resources. Elementarity-robust and ng-robust are introduced as
 widely applicable special cases that rely on the resources that ensure elementary
 routes and ng-routes, respectively, and practical considerations are discussed. The
 use of resource-robust valid inequalities is demonstrated with an application to the
 Capacitated Vehicle Routing Problem. Computational experiments show that re-
 placing robust valid inequalities by ng-robust valid inequalities may result in better
 lower bounds, a reduction in the number of nodes in the search tree, and a decrease
 in solution time.
Length: 54
Creation-Date: 2021-01-12
File-URL: https://repub.eur.nl/pub/134553/EI2020-08-herziene-versie.pdf
File-Format: application/pdf
Series: RePEc:ems:eureir
Number: EI 2020-08
Keywords: Resource-Robust, Valid Inequalities, Branch-Price-and-Cut.
Handle: RePEc:ems:eureir:134553