License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2021.12
URN: urn:nbn:de:0030-drops-148811
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14881/
Silva, Marco ;
Pedroso, João Pedro ;
Viana, Ana ;
Klimentova, Xenia
A Branch-Price-And-Cut Algorithm for Stochastic Crowd Shipping Last-Mile Delivery with Correlated Marginals
Abstract
We study last-mile delivery with the option of crowd shipping, where a company makes use of occasional drivers to complement its vehicle’s fleet in the activity of delivering products to its customers. We model it as a data-driven distributionally robust optimization approach to the capacitated vehicle routing problem. We assume the marginals of the defined uncertainty vector are known, but the joint distribution is difficult to estimate. The presence of customers and available occasional drivers can be random. We adopt a strategic planning perspective, where an optimal a priori solution is calculated before the uncertainty is revealed. Therefore, without the need for online resolution performance, we can experiment with exact solutions. Solving the problem defined above is challenging: not only the first-stage problem is already NP-Hard, but also the uncertainty and potentially the second-stage decisions are binary of high dimension, leading to non-convex optimization formulations that are complex to solve. We propose a branch-price-and-cut algorithm taking into consideration measures that exploit the intrinsic characteristics of our problem and reduce the complexity to solve it.
BibTeX - Entry
@InProceedings{silva_et_al:OASIcs.ATMOS.2021.12,
author = {Silva, Marco and Pedroso, Jo\~{a}o Pedro and Viana, Ana and Klimentova, Xenia},
title = {{A Branch-Price-And-Cut Algorithm for Stochastic Crowd Shipping Last-Mile Delivery with Correlated Marginals}},
booktitle = {21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
pages = {12:1--12:20},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-213-6},
ISSN = {2190-6807},
year = {2021},
volume = {96},
editor = {M\"{u}ller-Hannemann, Matthias and Perea, Federico},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14881},
URN = {urn:nbn:de:0030-drops-148811},
doi = {10.4230/OASIcs.ATMOS.2021.12},
annote = {Keywords: Last-mile delivery, Stochastic Vehicle Routing Problem, Crowd shipping, Distributionally Robust Optimization, Data-driven Optimization}
}
|
Keywords: |
|
Last-mile delivery, Stochastic Vehicle Routing Problem, Crowd shipping, Distributionally Robust Optimization, Data-driven Optimization |
|
Collection: |
|
21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
27.09.2021 |
