Resource-robust valid inequalities for set covering and set partitioning models
2021
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.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
23
References
0
Citations
NaN
KQI