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
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 191298659
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Subset‐Row Inequalities and Unreachability in Path‐Based Formulations for Vehicle Routing and Scheduling Problems.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Faldum%2C+Stefan%22">Faldum, Stefan</searchLink><relatesTo>1</relatesTo> (AUTHOR)<br /><searchLink fieldCode="AR" term="%22Gschwind%2C+Timo%22">Gschwind, Timo</searchLink><relatesTo>2</relatesTo> (AUTHOR)<br /><searchLink fieldCode="AR" term="%22Irnich%2C+Stefan%22">Irnich, Stefan</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> irnich@uni-mainz.de</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Networks%22">Networks</searchLink>. Mar2026, Vol. 87 Issue 2, p111-130. 20p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Vehicle+routing+problem%22">Vehicle routing problem</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+inequalities%22">Mathematical inequalities</searchLink><br /><searchLink fieldCode="DE" term="%22Constraint+programming%22">Constraint programming</searchLink><br /><searchLink fieldCode="DE" term="%22Scheduling%22">Scheduling</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+optimization%22">Mathematical optimization</searchLink><br /><searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: 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]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>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.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=191298659
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1002/net.70014
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 20
        StartPage: 111
    Subjects:
      – SubjectFull: Vehicle routing problem
        Type: general
      – SubjectFull: Mathematical inequalities
        Type: general
      – SubjectFull: Constraint programming
        Type: general
      – SubjectFull: Scheduling
        Type: general
      – SubjectFull: Mathematical optimization
        Type: general
      – SubjectFull: Algorithms
        Type: general
    Titles:
      – TitleFull: Subset‐Row Inequalities and Unreachability in Path‐Based Formulations for Vehicle Routing and Scheduling Problems.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Faldum, Stefan
      – PersonEntity:
          Name:
            NameFull: Gschwind, Timo
      – PersonEntity:
          Name:
            NameFull: Irnich, Stefan
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 03
              Text: Mar2026
              Type: published
              Y: 2026
          Identifiers:
            – Type: issn-print
              Value: 00283045
          Numbering:
            – Type: volume
              Value: 87
            – Type: issue
              Value: 2
          Titles:
            – TitleFull: Networks
              Type: main
ResultId 1