Branch-and-cut for the split delivery vehicle routing problem with time windows

Publication type:
Journal article
Metadata:
Autoren
  • Nicola Bianchessi
  • Stefan Irnich
Sammlungen
  • metadata
ISSN
1526-5447
Ausgabe der Veröffentlichung
2
Zeitschrift
Transportation science
Schlüsselwörter
  • 330 Wirtschaft
  • 330 Economics
Sprache
eng
Paginierung
Seiten: 442 - 462
Datum der Veröffentlichung
2019
Herausgeber
INFORMS
Herausgeber URL
http://dx.doi.org/10.1287/trsc.2018.0825
Datum der Datenerfassung
2020
Datum, an dem der Datensatz öffentlich gemacht wurde
2020
Zugang
Public
Titel
Branch-and-cut for the split delivery vehicle routing problem with time windows
Ausgabe der Zeitschrift
53

Data source: METADATA.UB

Other metadata sources:
Autoren
  • Nicola Bianchessi
  • Stefan Irnich
Autoren-URL
https://www.webofscience.com/api/gateway?GWVersion=2&SrcApp=fis-test-1&SrcAuth=WosAPI&KeyUT=WOS:000465151000007&DestLinkType=FullRecord&DestApp=WOS_CPL
DOI
10.1287/trsc.2018.0825
Externe Identifier
  • Clarivate Analytics Document Solution ID: HU3DE
ISSN
0041-1655
Ausgabe der Veröffentlichung
2
Zeitschrift
TRANSPORTATION SCIENCE
Schlüsselwörter
  • vehicle routing problem
  • split delivery
  • time windows
  • valid inequalities
Paginierung
442 - 462
Datum der Veröffentlichung
2019
Status
Published
Titel
Branch-and-Cut for the Split Delivery Vehicle Routing Problem with Time windows
Sub types
  • Article
Ausgabe der Zeitschrift
53

Data source: Web of Science (Lite)

Abstract
<jats:p> The split delivery vehicle routing problem with time windows (SDVRPTW) is a notoriously hard combinatorial optimization problem. First, it is hard to find a useful compact mixed-integer programming (MIP) formulation for the SDVRPTW. Standard modeling approaches either suffer from inherent symmetries (mixed-integer programs with a vehicle index) or cannot exactly capture all aspects of feasibility. Because of the possibility to visit customers more than once, the standard mechanisms to propagate load and time along the routes fail. Second, the lack of useful formulations has rendered any direct MIP-based approach impossible. Up to now, the most effective exact algorithms for the SDVRPTW have been branch-and-price-and-cut approaches using path-based formulations. In this paper, we propose a new and tailored branch-and-cut algorithm to solve the SDVRPTW. It is based on a new, relaxed compact model, in which some integer solutions are infeasible for the SDVRPTW. We use known and introduce some new classes of valid inequalities to cut off such infeasible solutions. One new class is path-matching constraints that generalize infeasible-path constraints. However, even with the valid inequalities, some integer solutions to the new compact formulation remain to be tested for feasibility. For a given integer solution, we build a generally sparse subnetwork of the original instance. On this subnetwork, all time-window-feasible routes can be enumerated, and a path-based residual problem then solved to decide on the selection of routes, the delivery quantities, and thereby the overall feasibility. All infeasible solutions need to be cut off. For this reason, we derive some strengthened feasibility cuts exploiting the fact that solutions often decompose into clusters. Computational experiments show that the new approach is able to prove optimality for several previously unsolved instances from the literature. </jats:p><jats:p> The e-companion is available at https://doi.org/10.1287/trsc.2018.0825 . </jats:p>
Autoren
  • Nicola Bianchessi
  • Stefan Irnich
DOI
10.1287/trsc.2018.0825
eISSN
1526-5447
ISSN
0041-1655
Ausgabe der Veröffentlichung
2
Zeitschrift
Transportation Science
Sprache
en
Paginierung
442 - 462
Datum der Veröffentlichung
2019
Status
Published
Herausgeber
Institute for Operations Research and the Management Sciences (INFORMS)
Herausgeber URL
http://dx.doi.org/10.1287/trsc.2018.0825
Datum der Datenerfassung
2023
Titel
Branch-and-Cut for the Split Delivery Vehicle Routing Problem with Time Windows
Ausgabe der Zeitschrift
53

Data source: Crossref

Autoren
  • Nicola Bianchessi
  • Stefan Irnich
DOI
10.1287/trsc.2018.0825
Zeitschrift
Transp. Sci.
Artikelnummer
2
Paginierung
442 - 462
Datum der Veröffentlichung
2019
Titel
Branch-and-Cut for the Split Delivery Vehicle Routing Problem with Time Windows.
Ausgabe der Zeitschrift
53

Data source: DBLP

Beziehungen:
Property of

Tools