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.
A Feature Based Solution Approach for the Flying Sidekick Traveling Salesman Problem / Boccia, M.; Mancuso, A.; Masone, A.; Sterle, C.. - 1476:(2021), pp. 131-146. (Intervento presentato al convegno 20th International Conference on Mathematical Optimization Theory and Operations Research , MOTOR 2021 nel 2021) [10.1007/978-3-030-86433-0_9].
A Feature Based Solution Approach for the Flying Sidekick Traveling Salesman Problem
Boccia M.;Mancuso A.;Masone A.
;Sterle C.
2021
Abstract
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.