Resource-robust valid inequalities for set covering and set partitioning models
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.
|Resource-Robust, Valid Inequalities, Branch-Price-and-Cut.|
|Econometric Institute Research Papers|
|This document is a preliminary version of the paper that includes computational results for the Capacitated Vehicle Routing Problem. We are currently applying the ideas in this paper to other valid inequalities and other problems, and we are performing additional numerical experiments to better showcase the potential of resource-robust valid inequalities|
|Organisation||Department of Econometrics|
Hoogendoorn, Y.N, & Dalmeijer, K. (2021, January 12). Resource-robust valid inequalities for set covering and set partitioning models. Econometric Institute Research Papers. Retrieved from http://hdl.handle.net/1765/134553