Thời gian: 9h00 đến 11h00 sáng thứ 4 ngày 21/9/2022
Tóm tắt: In this talk, we study a new variant of the parallel drone scheduling traveling salesman problem that allows multiple drones to combine in the form of a collective drone (c-drone) capable of transporting heavier, larger items. This innovative concept is expected to add further flexibility in vehicle assignment decisions. An especially difficult challenge to address is the collaboration among drones, since it requires temporal synchronization between their delivery tours. To better model the reality, we also consider drone power consumption as a nonlinear function of both speed and parcel weight. We first develop a two-index mixed integer linear programming (MILP) formulation from which a simple branch-and-cut is developed to solve small-size instances to optimality. To efficiently handle larger problem instances, we propose a Ruin-and-Recreate metaheuristic with problem-tailored removal and insertion operators, in which an efficient move evaluation procedure based on the topological sort is designed to deal with the complexity of the synchronization constraints. Computational experiments demonstrate the validity of the developed MILP model and the performance of the proposed metaheuristic. Sensitivity analyses based on the Classification and Regression Tree are performed to investigate the benefits of using c-drones and the important factors affecting the efficiency of the new transportation system.
