New features for customer classification in the Flying Sidekick Traveling Salesman Problem

The increasing interest in the deployment of truck and drone delivery systems leads to the definition of new and complex vehicle routing problems. In this context, the flying sidekick traveling salesman problem (FS-TSP) is the first truck-and-drone routing problem defined in the literature. Several variants appeared in the last years differing in the operating conditions and the structure of the hybrid truck-and-drone delivery system. Exact and heuristic solution methods have been proposed in the literature to solve these problems effectively. However, the exact solution methods can generally solve only small-size instances due to the complexity of these problems. On the other hand, heuristic solution methods are able to find feasible solutions with an acceptable computational burden but without any guarantee of the quality of the solution. This work aims to investigate the possibility of using data science and machine learning techniques to reduce the complexity of solving an FS-TSP instance. The idea is to determine a good/optimal customer-to-vehicle assignment apriori to reduce the number of decisions involved in the FS-TSP solution. The assignment is determined through the classification of customers based on a subset of features specifically defined for the FS-TSP. This information can be exploited by existing solution approaches for the FS-TSP to improve their performance. An extensive computational campaign on benchmark instances is carried out with a twofold objective. On the one hand, we aim to evaluate the impact of the features on customer classification. On the other hand, we intend to show the relationship between classification and combinatorial optimization results by observing the effect of the customer classification on the FS-TSP solution.