Document Open Access Logo

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

Authors Marco Silva, João Pedro Pedroso, Ana Viana, Xenia Klimentova

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2021.12.pdf
  • Filesize: 0.59 MB
  • 20 pages

Document Identifiers

Author Details

Marco Silva
  • INESC TEC, Porto, Portugal
João Pedro Pedroso
  • INESC TEC, Porto, Portugal
  • University of Porto, Portugal
Ana Viana
  • INESC TEC, Porto, Portugal
  • Politechnic of Porto, Portugal
Xenia Klimentova
  • INESC TEC, Porto, Portugal

Funding

The authors are funded by the ERDF – European Regional Development Fund through the COMPETE Programme (operational programme for competitiveness) and by National Funds through the Fundação para a Ciência e a Tecnologia (Portuguese Foundation for Science and Technology) within project "POCI-01-0145-FEDER-028611".

Cite As Get BibTex

Marco Silva, João Pedro Pedroso, Ana Viana, and Xenia Klimentova. A Branch-Price-And-Cut Algorithm for Stochastic Crowd Shipping Last-Mile Delivery with Correlated Marginals. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 12:1-12:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/OASIcs.ATMOS.2021.12

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.

Subject Classification

ACM Subject Classification
  • Applied computing → Transportation
  • Mathematics of computing → Mathematical optimization
Keywords
  • Last-mile delivery
  • Stochastic Vehicle Routing Problem
  • Crowd shipping
  • Distributionally Robust Optimization
  • Data-driven Optimization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Shipra Agrawal, Yichuan Ding, Amin Saberi, and Yinyu Ye. Price of correlations in stochastic optimization. Operations Research, 60(1):150-162, 2012. Google Scholar
  2. Mohamed Abdellahi Amar, Walid Khaznaji, and Monia Bellalouna. An exact resolution for the probabilistic traveling salesman problem under the a priori strategy. Procedia Computer Science, 108:1414-1423, 2017. International Conference on Computational Science, ICCS 2017, 12-14 June 2017, Zurich, Switzerland. Google Scholar
  3. Mohamed Abdellahi Amar, Walid Khaznaji, and Monia Bellalouna. A parallel branch and bound algorithm for the probabilistic tsp. In Jaideep Vaidya and Jin Li, editors, Algorithms and Architectures for Parallel Processing, pages 437-448, Cham, 2018. Springer International Publishing. Google Scholar
  4. Claudia Archetti, Martin W. P. Savelsbergh, and M. Grazia Speranza. The vehicle routing problem with occasional drivers. European Journal of Operational Research, 254(2):472-480, 2016. Google Scholar
  5. Alp M. Arslan, Niels Agatz, Leo Kroon, and Rob Zuidwijk. Crowdsourced delivery—a dynamic pickup and delivery problem with ad hoc drivers. Transportation Science, 53(1):222-235, 2019. Google Scholar
  6. Dimitris J. Bertsimas. A vehicle routing problem with stochastic demand. Operations Research, 40(3):574-585, 1992. Google Scholar
  7. Xin Chen, Melvyn Sim, and Peng Sun. A robust optimization perspective on stochastic programming. Operations Research, 55(6):1058-1071, 2007. Google Scholar
  8. Lars Dahle, Henrik Andersson, and Marielle Christiansen. The vehicle routing problem with dynamic occasional drivers. In Tolga Bektaş, Stefano Coniglio, Antonio Martinez-Sykora, and Stefan Voß, editors, Computational Logistics, pages 49-63, Cham, 2017. Springer International Publishing. Google Scholar
  9. Lars Dahle, Henrik Andersson, Marielle Christiansen, and M. Grazia Speranza. The pickup and delivery problem with time windows and occasional drivers. Computers & OR, 109:122-133, 2019. Google Scholar
  10. Iman Dayarian and Martin Savelsbergh. Crowdshipping and same-day delivery: Employing in-store customers to deliver online orders. available in Optimization Online, 2017. Google Scholar
  11. Erick Delage and Yinyu Ye. Distributionally robust optimization under moment uncertainty with application to data-driven problems. Operations Research, 58(3):595-612, 2010. Google Scholar
  12. Thai Dinh, Ricardo Fukasawa, and James Luedtke. Exact algorithms for the chance-constrained vehicle routing problem. Mathematical Programming, 172(1):105-138, November 2018. Google Scholar
  13. Katarzyna Gdowska, Ana Viana, and João Pedro Pedroso. Stochastic last-mile delivery with crowdshipping. Transportation Research Procedia, 30:90-100, 2018. Google Scholar
  14. Michel Gendreau, Gilbert Laporte, and René Séguin. An exact algorithm for the vehicle routing problem with stochastic demands and customers. Transportation Science, 29(2):143-155, 1995. Google Scholar
  15. Sudipta Kumar Ghosal and W. Wiesemann. The distributionally robust chance constrained vehicle routing problem. available at http://www.optimization-online.org/DB_FILE/2018/08/6759.pdf, 2018.
  16. Joel Goh and Melvyn Sim. Distributionally robust optimization and its tractable approximations. Operations Research, 58(4-part-1):902-917, 2010. Google Scholar
  17. Patrick Jaillet. A priori solution of a traveling salesman problem in which a random subset of the customers are visited. Operations Research, 36:929-936, December 1988. Google Scholar
  18. Felipe Lagos, Mathias Klapp, and Alejandro Toriello. Branch-and-price for probabilistic vehicle routing. available at http://www.optimization-online.org/DB_HTML/2017/12/6364.html, December 2017.
  19. Gilbert Laporte, François V. Louveaux, and Hélène Mercure. A priori optimization of the probabilistic traveling salesman problem. Operations Research, 42(3):543-549, 1994. Google Scholar
  20. Miles Lubin and Iain Dunning. Computing in Operations Research using Julia. CoRR, abs 1312.1431, 2013. Google Scholar
  21. Peyman Mohajerin Esfahani and Daniel Kuhn. Data-driven distributionally robust optimization using the Wasserstein metric: performance guarantees and tractable reformulations. Mathematical Programming, 171(1):115-166, September 2018. Google Scholar
  22. Alberto Santini, Ana Viana, Xenia Klimentova, and João Pedro Pedroso. Exact, heuristic and machine learning approaches to the probabilistic travelling salesman problem with crowdsourcing. available at https://santini.in/files/papers/santini-viana-klimentova-pedroso-2020.pdf, 2020.
  23. Herbert Scarf. A Min-Max Solution of an Inventory Problem, pages 201-209. Stanford University Press, 1958. Google Scholar
  24. Bart P. G. Van Parys, Paul J. Goulart, and Manfred Morari. Distributionally robust expectation inequalities for structured distributions. Mathematical Programming, December 2017. URL: https://doi.org/10.1007/s10107-017-1220-x.
  25. Christoph Weiler, Benjamin Biesinger, Bin Hu, and Günther R. Raidl. Heuristic approaches for the probabilistic traveling salesman problem. In Roberto Moreno-Díaz, Franz Pichler, and Alexis Quesada-Arencibia, editors, Computer Aided Systems Theory - EUROCAST 2015, pages 342-349, Cham, 2015. Springer International Publishing. Google Scholar
  26. Bo Zeng and Long Zhao. Solving two-stage robust optimization problems using a column-and-constraint generation method. Operations Research Letters, 41(5):457-461, 2013. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact