  There are emerging transportation problems known as the Traveling Salesman
Problem with Drone (TSPD) and the Flying Sidekick Traveling Salesman Problem
(FSTSP) that involve the use of a drone in conjunction with a truck for package
delivery. This study represents a hybrid genetic algorithm for solving TSPD and
FSTSP by combining local search methods and dynamic programming. Similar
algorithms exist in the literature. Our algorithm, however, considers more
sophisticated chromosomes and simpler dynamic programming to enable broader
exploration by the genetic algorithm and efficient exploitation through dynamic
programming and local searches. The key contribution of this paper is the
discovery of how decision-making processes should be divided among the layers
of genetic algorithm, dynamic programming, and local search. In particular, our
genetic algorithm generates the truck and the drone sequences separately and
encodes them in a type-aware chromosome, wherein each customer is assigned to
either the truck or the drone. We apply local searches to each chromosome,
which is decoded by dynamic programming for fitness evaluation. Our dynamic
programming algorithm merges the two sequences by determining optimal launch
and landing locations for the drone to construct a TSPD solution represented by
the chromosome. We propose novel type-aware order crossover operations and
effective local search methods. A strategy to escape from local optima is
proposed. Our new algorithm is shown to outperform existing algorithms on most
benchmark instances in both quality and time. Our algorithms found the new best
solutions for 538 TSPD instances out of 920 and 93 FSTSP instances out of 132.
