  We study the Flying Sidekick Traveling Salesman Problem with Multiple Drops
(FSTSP-MD), a multi-modal last-mile delivery model where a single truck and a
single drone cooperatively deliver customer packages. In the FSTSP-MD, the
drone can be launched from the truck to deliver multiple packages before it
returns to the truck for a new delivery operation. The objective is to find the
synchronized truck and drone delivery routes that minimize the completion time
of the delivery process. We develop a simple and effective heuristic to solve
the FSTSP-MD based on an order-first, split-second scheme. This heuristic
combines standard local search and diversification techniques with a novel
shortest-path problem that finds FSTSP-MD solutions in polynomial time. We show
that our heuristic consistently outperforms state-of-the-art heuristics
developed for the FSTSP-MD and the FSTSP (i.e., the single-drop case) through
extensive numerical experiments. Based on both stylized and real-world
instances, we also show that the FSTSP-MD substantially reduces completion
times compared to traditional truck-only delivery systems. We provide extensive
managerial insights into the impacts of drone capabilities and customer
distribution on delivery efficiency. Our discussion compares the benefits of
drones with greater payload capacity and those with greater speed. We highlight
which service area characteristics increase savings but also require enhanced
drone capabilities.
