Joint UAV and Truck Routing Under Uncertain Disruptions: Measuring the Value of Information


We consider a joint UAV and truck routing problem in which the operation of the UAV is subject to uncertain disruptions. The planner initially does not know in which locations a disruption will occur but can refine his/her knowledge by spending additional resources to probe locations for additional information, removing the uncertainty for the probed locations. In order to determine the best planning approach, the planner requires measuring how valuable is the information that is gathered by the probes. To this end, we present a framework that computes the value of information based on a two-stage stochastic optimization problem in which the uncertainty is partially revealed depending on the decisions of the first stage, that is, in the first stage the planner selects the locations to probe and in the second stage the planner selects the route based on the results of the probes. Our approach is able to find optimal probing plans for the case in which the disruptions are statistically independent. We reformulate the two-stage stochastic problem as a bilevel optimization problem with multiple followers, in which the lower-level problem is a challenging joint UAV and truck routing problem. We propose two formulations for the routing problem, one based on subtour elimination constraints, and another based on decision diagrams. We also develop two exact approaches to solve the resulting bilevel problem, one based on a value function reformulation and another based on scenario decomposition. Our extensive computational experiments show that the proposed approaches are able to solve bilevel problems with up to $30$ nodes to optimality and that probing, even if it is only on a small subset of locations, can yield significant gains in solution quality compared to not probing any locations.



View Joint UAV and Truck Routing Under Uncertain Disruptions: Measuring the Value of Information