ALGORITHMS FOR DRONE-ASSISTED PARCEL DELIVERY PROBLEM
A delivery modality that is being considered by big companies like Amazon and DHL is the package delivery using a truck with a drone as assistant. Many researchers are proposing variations of optimization problems that model this type of delivery, and solving it with heuristics and exact methods.
This work propose two algorithms that find solutions for instances of one of the variation of this problem, named Flying Sidekick Travelling Salesman Problem (FSTSP). The Advantageous Triples algorithm uses a quadratic programming model to find possible combination of sub-routes with drones that solve the problem. Also, we developer an heuristic, called Expansion Heuristic, that uses some of the problem properties to try to improve FSTSP instances solutions.
By the analyzes made, the Advantageous Triples algorithm could find, in ave- rage, solutions that are better than the solutions found by the FSTSP author algorithm. The Expansion Heuristic got small improvements in the solution with low computational complexity.