Optimizing Truck-Drone Delivery Routes: A Sub-Circuit Construction Algorithm

Truck-drone combined logistics has received increasing attention, and the multi-drops flying sidekick traveling salesman problem (mFSTSP) is one of the classic models. For the mFSTSP, we establishes an integer programming model based on drone range constraint, and designs a sub-circuit construction algorithm according to the modeling idea. Based on the range of the drone, the obtained TSP route is segmented and the optimal sub-circuit are constructed in sequence. Further optimization through dynamic adjustment augmented service mechanism, and three discussions are conducted on the starting position of the segmentation. Considering different operational scenarios, a set of numerical experiments are conducted. Compared with several advanced heuristic algorithms, the proposed sub-circuit construction algorithm shows remarkable advantages in solving large-scale problems, with a maximum solution scale exceeding 700 nodes.