IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v292y2021i1p311-326.html
   My bibliography  Save this article

A vehicle routing problem with distribution uncertainty in deadlines

Author

Listed:
  • Zhang, Dali
  • Li, Dong
  • Sun, Hailin
  • Hou, Liwen

Abstract

This article considers a stochastic vehicle routing problem with probability constraints. The probability that customers are served before their (uncertain) deadlines must be higher than a pre-specified target. It is unrealistic to expect that the perfect knowledge on the probability distributions of deadlines is always available. To this end, we propose a distributionally robust optimisation framework to study worst bounds of the problem, which exploits the moment information of the historical observations. This framework includes two steps. We first use Conditional Value-at-Risk (CVaR) as a risk approximation to the probability of missing customer deadlines. The resulting nonlinear model is then transformed into a semi-infinite mixed integer program, using the dual form of the CVaR approximation. A sample approximation approach is then used to address the computational challenges. As the standard CVaR approximation to probability constraints is rather conservative, we suggest a relaxation to the approximation and develop an iterative algorithm to find the right value of the parameter that is introduced to the relaxed CVaR constraints. The extensive numerical experiments show that the routing policies developed by the proposed solution framework are robust and able to achieve the required target, regardless of deadline distributions.

Suggested Citation

  • Zhang, Dali & Li, Dong & Sun, Hailin & Hou, Liwen, 2021. "A vehicle routing problem with distribution uncertainty in deadlines," European Journal of Operational Research, Elsevier, vol. 292(1), pages 311-326.
  • Handle: RePEc:eee:ejores:v:292:y:2021:i:1:p:311-326
    DOI: 10.1016/j.ejor.2020.10.026
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221720309024
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.ejor.2020.10.026?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Li, Siqiao & Zhu, Xiaoning & Shang, Pan & Li, Tianqi & Liu, Wenqian, 2023. "Optimizing a shared freight and passenger high-speed railway system: A multi-commodity flow formulation with Benders decomposition solution approach," Transportation Research Part B: Methodological, Elsevier, vol. 172(C), pages 1-31.
    2. Kenneth Stoop & Mario Pickavet & Didier Colle & Pieter Audenaert, 2024. "Selective Backhauls in Truck Transport with Risk Mitigation: Large Belgian Retailer Case Study," Networks and Spatial Economics, Springer, vol. 24(1), pages 99-130, March.
    3. Alvo, Matías & Angulo, Gustavo & Klapp, Mathias A., 2021. "An exact solution approach for an electric bus dispatch problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 156(C).
    4. Sluijk, Natasja & Florio, Alexandre M. & Kinable, Joris & Dellaert, Nico & Van Woensel, Tom, 2023. "Two-echelon vehicle routing problems: A literature review," European Journal of Operational Research, Elsevier, vol. 304(3), pages 865-886.
    5. Wang, Haibo & Alidaee, Bahram, 2023. "White-glove service delivery: A quantitative analysis," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 175(C).
    6. Sebastián Dávila & Miguel Alfaro & Guillermo Fuertes & Manuel Vargas & Mauricio Camargo, 2021. "Vehicle Routing Problem with Deadline and Stochastic Service Times: Case of the Ice Cream Industry in Santiago City of Chile," Mathematics, MDPI, vol. 9(21), pages 1-18, October.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:292:y:2021:i:1:p:311-326. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.