Abstract Resource transport in the aftermath of disasters is critical, yet in the absence of sufficient historical data or accurate forecasting approaches, the development of resource transport strategies often faces the challenge of dealing with uncertainty, especially uncertainties in demand and travel time. In this paper we investigate the vehicle routing problem with drones under uncertain demands and truck travel times. Specifically, there is a set of trucks and drones (each truck is associated with a drone) collaborating to transport relief resources to the affected areas, where a drone can be launched from its associated truck at a node, independently transporting relief resources to one or more of the affected areas, and returning to the truck at another node along the truck route. For this problem, we present a tailored robust optimization model based on the well-known budgeted uncertainty set, and develop an enhanced branch-and-price-and-cut algorithm incorporating a bounded bidirectional labelling algorithm to solve the pricing problem, which can be modelled as a robust resource-constrained vehicle and drone synthetic shortest path problem. To enhance the performance of the algorithm, we employ subset-row inequalities to tighten the lower bound and incorporate some enhancement strategies to quickly solve the pricing problem. We perform extensive numerical studies to assess the performance of the developed algorithm, discuss the benefits of considering uncertainty and robustness, and analyse the impacts of key model parameters on the optimal solution. We also evaluate the benefits of the truck–drone collaborative transport mode over the truck-only transport mode through a real case study of the 2008 earthquake in Wenchuan, China.

    Highlights A vehicle routing problem with drones under uncertain demands and truck travel times is studied. A tailored robust optimization model based on the budgeted uncertainty set is given. A branch-and-price-and-cut algorithm with some improvement strategies is devised. Experiment results show the benefits of considering uncertainty and robustness. How the model performs in the actual earthquake that occurred in China is also showed.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Robust vehicle routing with drones under uncertain demands and truck travel times in humanitarian logistics


    Contributors:
    Yin, Yunqiang (author) / Yang, Yongjian (author) / Yu, Yugang (author) / Wang, Dujuan (author) / Cheng, T.C.E. (author)


    Publication date :

    2023-06-11




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English




    Interval travel times for robust synchronization in city logistics vehicle routing

    Groß, Patrick-Oliver / Ehmke, Jan Fabian / Mattfeld, Dirk Christian | Elsevier | 2020



    A Robust Scenario Approach for the Vehicle Routing Problem with Uncertain Travel Times

    Han, J. / Lee, C. / Park, S. | British Library Online Contents | 2014



    Multidepot Vehicle Routing with Uncertain Demands: Chance Constrained Approach

    Miranda, P. A. / Garrido, R. A. / Transportation Research Board | British Library Conference Proceedings | 2004