This paper addresses the Traveling Salesman Problem with Drone (TSP-D), in
which a truck and drone are used to deliver parcels to customers. The objective
of this problem is to either minimize the total operational cost (min-cost
TSP-D) or minimize the completion time for the truck and drone (min-time
TSP-D). This problem has gained a lot of attention in the last few years since
it is matched with the recent trends in a new delivery method among logistics
companies. To solve the TSP-D, we propose a hybrid genetic search with dynamic
population management and adaptive diversity control based on a split
algorithm, problem-tailored crossover and local search operators, a new restore
method to advance the convergence and an adaptive penalization mechanism to
dynamically balance the search between feasible/infeasible solutions. The
computational results show that the proposed algorithm outperforms existing
methods in terms of solution quality and improves best known solutions found in
the literature. Moreover, various analyses on the impacts of crossover choice
and heuristic components have been conducted to analysis further their
sensitivity to the performance of our method.

Source link