Collaborative Truck-Drone Routing with Multivisit via Surrogate-Assisted Bi-Level Optimization

The development of drone techniques has extensive applications to fields such as last-mile parcel delivery. For economic and efficiency advantages, collaborative truck-drone systems have attracted great attention and formulated as truck-drone routing problems (TDRPs). In this article, a multivisit traveling salesman problem with drones (MTSP-D) 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 (SaBO) 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 (KNN)-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 (DLR) problem, 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.