A logic-based Benders decomposition method for the multi-trip traveling repairman problem with drones

摘要

This paper considers the problem of delivering a certain number of packages to a set of customers using multiple drones dispatched from a single truck. Once a drone delivers a package, it returns to the truck to pick up another package while the truck waits at the launch location. The aim is to determine the truck route and the sequence of drone trips from the truck such that all the customer demands are served, either by the truck or drones, to minimize the sum of customer waiting times. We propose a new formulation of this problem based on an extended graph network representation. A new logic-based Benders decomposition method enhanced with relaxations is also developed and evaluated on several benchmark instances. The numerical results show that the proposed exact method obtains optimal solutions to the majority of the problem instances within the time limit of one hour.