A Branch-Price-And-Cut Algorithm for Stochastic Crowd Shipping Last-Mile Delivery with Correlated Marginals

• Tipo: Artigo em Livro de Atas de Conferência Internacional
• Data: 2021

Autores

Silva, M (Autor) Outra; Joao Pedro Pedroso (Autor) FCUP; Viana, A (Autor) Outra; Klimentova, X (Autor) Outra

Ata de Conferência Internacional

Título: 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2021, September 9-10, 2021, Lisbon, Portugal (Virtual Conference).

Página Inicial: 12:1

Indexação

Scopus - 2 Citações

Outras Informações

ID Authenticus: P-00V-FQG

DOI: 10.4230/oasics.atmos.2021.12

Abstract (EN): 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.

Idioma: Inglês

Tipo (Avaliação Docente): Científica