Joshua T. Margolis

In the multi‐vehicle covering tour problem with speed optimization, we aim to construct a set of maximal coverage routes for a fleet of vehicles that serve (observe) a set of secondary sites, given a fixed time schedule and coverage requirements. We develop an exact solution approach using a branch‐and‐price framework with a label‐correcting algorithm and a set of innovative dominance rules to solve the resulting pricing problem. We also develop a two‐stage heuristic capable of finding effective initial solutions. In addition, we consider practical extensions to the model by incorporating risk thresholds, energy capacities, and time windows. To validate our proposed solution approaches, we perform an extensive set of numerical experiments. Numerical results show the computational advantage of our proposed solution approaches compared with a state‐of‐the‐art commercial solver.

The multi-vehicle covering tour problem with time windows (MCTPTW) aims to construct a set of maximal coverage routes for a fleet of vehicles that serve (observe) a secondary set of sites given a fixed time schedule, coverage requirements, and energy restrictions. The problem is formulated as a mixed-integer second-order cone programming (MISOCP) model and is an extension of both the multi-covering tour problem and the vehicle routing problem with time windows under energy constraints. Further, we study a special case of the proposed model and develop a labeling algorithm to solve its Lagrangian relaxation problem, which exploits the combinatorial structure exhibited by an optimal solution to the Lagrangian relaxation.