EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

980. Flowty’s Resource Constrained Shortest Path Algorithm

Invited abstract in session WB-64: Vehicle Routing Problems With Time Windows, stream VeRoLog - Vehicle Routing and Logistics.

Wednesday, 10:30-12:00
Room: S16 (building: 101)

Authors (first author is the speaker)

1. Bjørn Petersen
Flowty
2. Simon Spoorendonk
Flowty

Abstract

Flowty is a network optimization solver that exploits the network structure in a column generation algorithm. This talk is about the resource constrained shortest path (RCSPP) algorithm at the core of this algorithm.

The RCSPP algorithm is a bidirectional labeling algorithm parallelized on a bucket level, that is pulling (as opposed to pushing) labels into buckets. The size of the buckets is small enough to avoid cycles within the bucket.

Pulling into buckets is done in parallel for independent buckets. The dependency graph between buckets is handled implicitly, and the bidirectional midpoint/stopping criteria is dynamic, meaning that buckets are extended until the opposite direction is encountered.

As is always the case for pull-based labeling algorithms; carefully choosing the order of which labels are created, it is possible to guarantee that only labels not dominated are ever stored. This not only limits the memory footprint, it also allows labels to be stored as immutable ‘object of arrays’ (as opposed to ‘array of objects’) thereby enabling the use of vectorized instructions for dominance checks and thus exploiting a second level of parallelization.

The Vehicle Routing Problem with Time Windows (VPRTW) is used as an illustrative case.

Keywords

Status: accepted

Back to the list of papers