Optimizing the Hub-and-Spoke Network with Drone-Based Traveling Salesman Problem

Abstract

The hub-and-spoke network (HSN) design generally assumes direct transportation between a spoke node and its assigned hub, while the spoke’s demand may be far less than a truckload. Therefore, the total number of trucks on the network increases unnecessarily. We form a drone-based traveling salesman problem (TSP-D) for the cluster of spokes assigned to a hub. A truck starts from the hub, visiting each spoke node of the hub in turn and finally returning to the hub. We propose a three-stage decomposition model to solve the HSN with TSPD (HSNTSP-D). The corresponding three-stage decomposition algorithm is developed, including cooperation among variable neighborhood search (VNA) heuristics and nearest neighbor algorithm (NNA), and then the spoke-to-hub assignment algorithm through the reassignment strategy (RA) method. The performance of the three-stage decomposition algorithm is tested and compared on standard datasets (CAB, AP, and TR). The numerical analysis of the scenarios shows that whether it is trunk hub-level transportation or drone spoke-level transportation, it integrates resources to form a scale effect, which can reduce transport devices significantly, as well as decreasing the investment and operating costs.

Keywords

• hub and spoke network
• traveling salesman problem
• drone routing problem
• variable neighborhood search
• nearest neighbor algorithm