View in EDS

Subset‐Row Inequalities and Unreachability in Path‐Based Formulations for Vehicle Routing and Scheduling Problems.

Saved in:
Bibliographic Details
Title: Subset‐Row Inequalities and Unreachability in Path‐Based Formulations for Vehicle Routing and Scheduling Problems.
Authors: Faldum, Stefan1 (AUTHOR), Gschwind, Timo2 (AUTHOR), Irnich, Stefan1 (AUTHOR) irnich@uni-mainz.de
Source: Networks. Mar2026, Vol. 87 Issue 2, p111-130. 20p.
Subjects: Vehicle routing problem, Mathematical inequalities, Constraint programming, Scheduling, Mathematical optimization, Algorithms
Abstract: This work considers branch‐price‐and‐cut algorithms for variants of the vehicle‐routing problem in which subset‐row inequalities (SRIs) are used to strengthen the linear relaxation. SRIs often help to substantially reduce the size of the branch‐and‐bound search tree. However, their use is computationally costly because SRIs modify the structure of the respective column‐generation subproblem, which is a shortest‐path problem with resource constraints (SPPRC). Each active SRI requires the addition of a resource to the labeling algorithm that is invoked for solving the SPPRC in every iteration. In the context of time‐window constraints, the concept of unreachable customers has been used for preprocessing (time‐window reduction, arc elimination, precedence identification) as well as for improving the dominance between labels in the elementary SPPRC and its relaxations. We show that the identification of unreachable customers can also help to improve the dominance due to a modified comparison of SRI‐related resources. Computational experiments with a fully fledged branch‐price‐and‐cut algorithm for the (standard and electric) vehicle‐routing problem with time windows demonstrate the effectiveness of the approach: Overall computation times decrease; for some difficult instances, they may even be cut in half, while the required modifications of a computer implementation for combining SRIs with unreachable customers are minor. [ABSTRACT FROM AUTHOR]
Copyright of Networks is the property of Wiley-Blackwell and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
Description
Abstract:This work considers branch‐price‐and‐cut algorithms for variants of the vehicle‐routing problem in which subset‐row inequalities (SRIs) are used to strengthen the linear relaxation. SRIs often help to substantially reduce the size of the branch‐and‐bound search tree. However, their use is computationally costly because SRIs modify the structure of the respective column‐generation subproblem, which is a shortest‐path problem with resource constraints (SPPRC). Each active SRI requires the addition of a resource to the labeling algorithm that is invoked for solving the SPPRC in every iteration. In the context of time‐window constraints, the concept of unreachable customers has been used for preprocessing (time‐window reduction, arc elimination, precedence identification) as well as for improving the dominance between labels in the elementary SPPRC and its relaxations. We show that the identification of unreachable customers can also help to improve the dominance due to a modified comparison of SRI‐related resources. Computational experiments with a fully fledged branch‐price‐and‐cut algorithm for the (standard and electric) vehicle‐routing problem with time windows demonstrate the effectiveness of the approach: Overall computation times decrease; for some difficult instances, they may even be cut in half, while the required modifications of a computer implementation for combining SRIs with unreachable customers are minor. [ABSTRACT FROM AUTHOR]
ISSN:00283045
DOI:10.1002/net.70014