On the stochastic vehicle routing problem with time windows, correlated travel times, and time dependency

Simple item page
dc.contributor.authorBomboi, Federica
dc.contributor.authorBuchheim, Christoph
dc.contributor.authorPruente, Jonas
dc.date.accessioned2022-03-11T12:40:04Z
dc.date.available2022-03-11T12:40:04Z
dc.date.issued2021-03-12
dc.description.abstractMost state-of-the-art algorithms for the Vehicle Routing Problem, such as Branch-and-Price algorithms or meta heuristics, rely on a fast feasibility test for a given route. We devise the first approach to approximately check feasibility in the Stochastic Vehicle Routing Problem with time windows, where travel times are correlated and depend on the time of the day. Assuming jointly normally distributed travel times, we use a chance constraint approach to model feasibility, where two different application scenarios are considered, depending on whether missing a customer makes the rest of the route infeasible or not. The former case may arise, e.g., in drayage applications or in the pickup-and-delivery VRP. In addition, we present an adaptive sampling algorithm that is tailored for our setting and is much faster than standard sampling techniques. We use a case study for both scenarios, based on instances with realistic travel times, to illustrate that taking correlations and time dependencies into account significantly improves the quality of the solutions, i.e., the precision of the feasibility decision. In particular, the nonconsideration of correlations often leads to solutions containing infeasible routes.en
dc.identifier.urihttp://hdl.handle.net/2003/40783
dc.identifier.urihttp://dx.doi.org/10.17877/DE290R-22640
dc.language.isoende
dc.relation.ispartofseries4OR;Vol 19. 2021, Art. No 476
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/
dc.subjectStochastic VRPen
dc.subjectTime windowsen
dc.subjectCorrelated travel timesen
dc.subjectDynamic travel times Chance constraintsen
dc.subjectChance constraintsen
dc.subject.ddc520
dc.titleOn the stochastic vehicle routing problem with time windows, correlated travel times, and time dependencyen
dc.typeTextde
dc.type.publicationtypearticlede
dcterms.accessRightsopen access
eldorado.secondarypublicationtruede
eldorado.secondarypublication.primarycitation4OR. Vol 19. 2021, Art. No 476de
eldorado.secondarypublication.primaryidentifierhttps://doi.org/10.1007/s10288-021-00476-zde

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Bomboi2021_Article_OnTheStochasticVehicleRoutingP.pdf
Size:
387.88 KB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
4.85 KB
Format:
Item-specific license agreed upon to submission
Description:
Download

Collections

Fakultät für Mathematik