Abstract Unmanned aerial vehicles or drones are becoming increasingly popular due to their low cost and high mobility. In this paper we address the routing and coordination of a drone-truck pairing where the drone travels to multiple locations to perform specified observation tasks and rendezvous periodically with the truck to swap its batteries. We refer to this as the Nested-Vehicle Routing Problem (Nested-VRP) and develop a Mixed Integer Quadratically Constrained Programming (MIQCP) formulation with critical operational constraints, including drone battery capacity and synchronization of both vehicles during scheduled rendezvous. An enhancement of the MIQCP model for the Nested-VRP is achieved by deriving the equivalent Mixed Integer Linear Programming (MILP) formulation as well as leveraging lifting and Reformulation-Linearization techniques to strengthen the subtour elimination constraints of the drone. Given the NP-hard nature of the Nested-VRP, we further propose an efficient neighborhood search (NS) heuristic where we generate and improve on a good initial solution by iteratively solving the Nested-VRP on a local scale. We provide comparisons of both the exact approaches based on MIQCP or its enhanced formulations and NS heuristic methods with a relaxation lower bound in the cases of small and large problem sizes, and present the results of a computational study to show the effectiveness of the MIQCP model and its variants as well as the efficiency of the NS heuristic, including for a real-life instance with 631 locations. We envision that this framework will facilitate the planning and operations of combined drone-truck missions.

    Highlights We propose a novel mathematical model for enabling truck-drone combined routings. The model tackles operational constraint due to the drone’s limited flight endurance. The battery swap and routing decisions are optimized to minimize mission makespan. We propose a heuristic, and its efficiency and effectiveness are well examined. The results will benefit the planning of truck-drone coordinated mission.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Nested vehicle routing problem: Optimizing drone-truck surveillance operations


    Contributors:


    Publication date :

    2022-03-08




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English




    Nested Vehicle Routing Problem: Combined Operations of UAV and Ground Vehicle

    Zeng, Fanruiqi / Chen, Zaiwei / Nikoue, Harold et al. | AIAA | 2020


    NESTED VEHICLE ROUTING PROBLEM: COMBINED OPERATIONS OF UAV AND GROUND VEHICLE

    Zeng, Fanruiqi / Chen, Zaiwei / Nikoue, Harold et al. | TIBKAT | 2020


    Truck–drone hybrid routing problem with time-dependent road travel time

    Wang, Yong / Wang, Zheng / Hu, Xiangpei et al. | Elsevier | 2022


    En route truck–drone parcel delivery for optimal vehicle routing strategies

    Marinelli, Mario / Caggiani, Leonardo / Ottomanelli, Michele et al. | IET | 2018

    Free access

    En route truck–drone parcel delivery for optimal vehicle routing strategies

    Marinelli, Mario / Caggiani, Leonardo / Ottomanelli, Michele et al. | Wiley | 2018

    Free access