New Exact Algorithm for the Vehicle Routing Problem with Stochastic Demands

Autor(en)

Alexandre Florio, Richard Hartl, Stefan Minner

Abstrakt

This paper considers the vehicle routing problem with stochastic demands (VRPSD) under optimal restocking. We develop an exact algorithm that is effective for solving instances with many vehicles and few customers per route. In our experiments, we show that in these instances solving the stochastic problem is most relevant (i.e., the potential gains over the deterministic equivalent solution are highest). The proposed branch-price-and-cut algorithm relies on an efficient labeling procedure, exact and heuristic dominance rules, and completion bounds to price profitable columns. Instances with up to 76 nodes could be solved in less than 5 hours, and instances with up to 148 nodes could be solved in long-runs of the algorithm. The experiments also allowed new findings on the problem. Solving the stochastic problem leads to solutions up to 10% superior to the deterministic equivalent solution. When the number of routes is not fixed, the optimal solutions under detour-to-depot and optimal restocking are nearly equivalent. Opening new routes is a good strategy to reduce restocking costs, and in many cases results in solutions with less transportation costs. For the first time, scenarios where the expected demand in a route is allowed to exceed the capacity of the vehicle were also tested, and the results indicate that superior solutions with lower cost and fewer routes exist.

Organisation(en)

Institut für Business Decisions and Analytics, Institut für Rechnungswesen, Innovation und Strategie

Externe Organisation(en)

Technische Universität München

Journal

Transportation Science

Band

54

Seiten

855-1152

Anzahl der Seiten

18

ISSN

0041-1655

DOI

https://doi.org/10.1287/trsc.2020.0976

Publikationsdatum

06-2020

Peer-reviewed

Ja

ÖFOS 2012

502017 Logistik

Schlagwörter

ASJC Scopus Sachgebiete

Transportation, Civil and Structural Engineering

Link zum Portal

https://ucris.univie.ac.at/portal/de/publications/new-exact-algorithm-for-the-vehicle-routing-problem-with-stochastic-demands(23727b9c-38ec-4ea3-997a-afa7f952d557).html