A Feature Based Solution Approach for the Flying Sidekick Traveling Salesman Problem

The integration of new distribution technologies in the delivery systems, specifically drones, has been investigated by several companies to reduce the last mile logistic costs. The most promising delivery system, in terms of emissions and completion time reduction, consists of a truck and a drone operating in tandem for the parcel delivery to the customers. This has led to the definition of new and complex routing problems that have received great attention by the operations research community. Several contributions have appeared in the last years providing ILP and MILP formulation for these kinds of problems. Nevertheless, due to complexity, their solutions is impracticable even on small instances. In particular, the synchronization and the coordination of the two vehicles represent critical issues. In this work, we investigate the possibility of using customer characterizing features which allow to determine a priori promising customer-to-vehicle assignments. This information can be used to perform several variable fixings in the FSTSP formulation, so reducing the size and the complexity of the instances to be solved. Thus, the final aim is to determine optimal or sub-optimal solutions using state-of-the-art solver on a reduced FSTSP. To this aim, we provide a computational study proving the quality of the chosen features and their effectiveness in the solution of new and literature instances.