Partial Dominance in Branch-Price-and-Cut for the Basic Multicompartment Vehicle-Routing Problem

Publikationstyp:
Zeitschriftenaufsatz
Metadaten:
Autoren
  • Katrin Hessler
  • Stefan Irnich
Autoren-URL
https://www.webofscience.com/api/gateway?GWVersion=2&SrcApp=fis-test-1&SrcAuth=WosAPI&KeyUT=WOS:000949150900004&DestLinkType=FullRecord&DestApp=WOS_CPL
DOI
10.1287/ijoc.2022.1255
eISSN
1526-5528
Externe Identifier
  • Clarivate Analytics Document Solution ID: 9W5XJ
ISSN
1091-9856
Ausgabe der Veröffentlichung
1
Zeitschrift
INFORMS JOURNAL ON COMPUTING
Schlüsselwörter
  • vehicle routing
  • packing
  • shortest-path problem with resource constraints
  • dynamic-programming labeling
  • partial dominance
Paginierung
50 - 65
Datum der Veröffentlichung
2023
Status
Published
Titel
Partial Dominance in Branch-Price-and-Cut for the Basic Multicompartment Vehicle-Routing Problem
Sub types
  • Article
Ausgabe der Zeitschrift
35

Datenquelle: Web of Science (Lite)

Andere Metadatenquellen:
Abstract
<jats:p> We consider the exact solution of the basic version of the multiple-compartment vehicle-routing problem, which consists of clustering customers into groups, routing a vehicle for each group, and packing the demand of each visited customer into one of the vehicle’s compartments. Compartments have a fixed size, and there are no incompatibilities between the transported items or between items and compartments. The objective is to minimize the total length of all vehicle routes such that all customers are visited. We study the shortest-path subproblem that arises when solving the problem with a branch-price-and-cut algorithm exactly. For this subproblem, we compare a standard dynamic-programming labeling approach with a new one that uses a partial dominance. The algorithm with standard labeling already struggles with relatively small instances, whereas the one with partial dominance can cope with much larger instances. </jats:p><jats:p> History: Accepted by Andrea Lodi, Area Editor for Design &amp; Analysis of Algorithms—Discrete. </jats:p><jats:p> Funding: This research was supported by the Deutsche Forschungsgemeinschaft [Grant IR 122/10-1 of Project 418727865]. </jats:p><jats:p> Supplemental Material: The e-companion is available at https://doi.org/10.1287/ijoc.2022.1255 . </jats:p>
Autoren
  • Katrin Heßler
  • Stefan Irnich
DOI
10.1287/ijoc.2022.1255
eISSN
1526-5528
ISSN
1091-9856
Ausgabe der Veröffentlichung
1
Zeitschrift
INFORMS Journal on Computing
Sprache
en
Paginierung
50 - 65
Datum der Veröffentlichung
2023
Status
Published
Herausgeber
Institute for Operations Research and the Management Sciences (INFORMS)
Herausgeber URL
http://dx.doi.org/10.1287/ijoc.2022.1255
Datum der Datenerfassung
2023
Titel
Partial Dominance in Branch-Price-and-Cut for the Basic Multicompartment Vehicle-Routing Problem
Ausgabe der Zeitschrift
35

Datenquelle: Crossref

Beziehungen:
Eigentum von

Werkzeuge