Collaborative Truck-Drone Routing with Multi-visit via Surrogate-Assisted Bi-level Optimization

The development of drone techniques has extensive applications to fields like last-mile parcel delivery. For economic and efficiency advantages, collaborative truck-drone systems have attracted great attention and formulated as truck-drone routing problems. In this paper, a multi-visit traveling salesman problem with drones is investigated. We decompose it into a two-layer structure and formulate it as a new bi-level model (Bi-MTSPD). The major advantage of the bi-level model is its ability to represent the complex interactions between truck and drone routes by dispatching the drones under the premise of truck routes. To solve the bi-level model, we propose a novel surrogate-assisted bi-level optimization method. The upper-level subproblem can be treated as a traveling salesman problem with customer assignment, and high-quality truck routes are identified by the K-nearest neighbor-based surrogate model with newly proposed features in order to allocate more computational resources to promising upper-level solutions. For the lower-level drone location routing problem (DLR), a customized memetic algorithm is developed to optimize the drone routes for the corresponding truck route. Comprehensive experimental results show that the proposed algorithm significantly outperforms the existing state-of-the-art algorithms across most benchmark instances. Further analysis verifies the congruence of the bi-level optimization for MTSP-D and the effectiveness of upper-level and lower-level solvers.