Nested Vehicle Routing Problem: Optimizing Drone-Truck Surveillance Operations
Abstract: Unmanned aerial vehicles or drones are becoming increasingly popular due to their low cost and high mobility. In this presentation, I will discuss 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. My collaborators and I refer to this as the Nested-Vehicle Routing Problem (Nested-VRP) and have develop a Mixed Integer Programming (MIP) formulation with critical operational constraints, including drone battery capacity and synchronization of both vehicles during scheduled rendezvous. Given the NP-hard nature of the Nested-VRP, we propose an efficient neighborhood search (NS) heuristic where we generate and improve on a good initial solution (i.e., where the optimality gap is on average less than 10% in large instances) by iteratively solving the Nested-VRP on a local scale. We provide comparisons of both the MIP and NS heuristic methods with a relaxation lower bound in the cases of small and large problem sizes, present the results of a computational study to show the effectiveness of the MIP model and 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.
Bio: John-Paul Clarke is a Professor of Aerospace Engineering and Engineering Mechanics at the University of Texas at Austin, where he holds the Ernest Cockrell Jr Memorial Chair in Engineering. Prof. Clarke develops and uses stochastic models and optimization algorithms to improve the efficiency and robustness of complex systems, with a particular focus on aviation. For example, his work has led to the development of: (a) the world’s first fully autopilot-coupled continuous descent arrival procedure in daily operations, i.e., the RIIVR Arrival that has significantly reduced the noise impact, fuel burn, and emissions around Los Angeles International Airport (LAX); (b) airline schedules that are “robust” to poor weather and/or aircraft failures, i.e., have minimal flight and passenger itinerary disruption; (c) state-of-the art algorithm to maximize the likelihood of success for a portfolio of research and development projects or financial assets with uncertain future performance and schedule. Prior to UT Austin, he was a College of Engineering Dean’s Professor at the Georgia Institute of Technology – where he held appointments in the Daniel Guggenheim School of Aerospace Engineering and the H. Milton Stewart School of Industrial and Systems Engineering – and a Professor at the Massachusetts Institute of Technology – where he received his SB (1991), SM (1992) and ScD (1997) degrees in Aeronautics and Astronautics. Between November 2018 and April 2020, while on leave from Georgia Tech, he was the Vice President of Strategic Technologies at United Technologies Corporation (now Raytheon) where he led technology strategy, technology acceleration, partnerships, and global technology education throughout the company, and developed and deployed a novel framework to create enterprise-wide technology roadmaps. Earlier in his career, he was a researcher at Boeing and the NASA Jet Propulsion Lab. Professor Clarke is a co-founder of Universal Hydrogen – a company dedicated to the decarbonization of aviation via a novel low capital expenditure hydrogen supply and distribution system.
|
