Optimization of a truck-drone in tandem delivery network using k-means and genetic algorithm
Abstract: The purpose of this
paper is to investigate the effectiveness of implementing unmanned aerial
delivery vehicles in delivery networks. We investigate the notion of the
reduced overall delivery time, energy, and costs for a truck-drone network by
comparing the in-tandem system with a stand-alone delivery effort. The
objectives are (1) to investigate the time, energy, and costs associated to a
truck-drone delivery network compared to standalone truck or drone, (2) to
propose an optimization algorithm that determines the optimal number of launch
sites and locations given delivery requirements, and drones per truck, (3) to
develop mathematical formulations for closed form estimations for the optimal
number of launch locations, optimal total time, as well as the associated cost
for the system.
Design/methodology/approach: The design of the algorithm herein computes
the minimal time of delivery utilizing K-means clustering to find launch
locations, as well as a genetic algorithm to solve the truck route as a
traveling salesmen problem (TSP). The optimal solution is determined by finding
the minimum cost associated to the parabolic convex cost function. The optimal
min-cost is determined by finding the most efficient launch locations using
K-means algorithms to determine launch locations and a genetic algorithm to
determine truck route between those launch locations.
Findings: Results show improvements with in-tandem delivery efforts as
opposed to standalone systems. Further, multiple drones per truck are more
optimal and contribute to savings in both energy and time. For this, we sampled
various initialization variables to derive closed form mathematical solutions
for the problem.
Originality/value: Ultimately, this provides the necessary analysis of an
integrated truck-drone delivery system which could be implemented by a company
in order to maximize deliveries while minimizing time and energy. Closed-form
mathematical solutions can be used as close estimators for final costs and
time.
Author: Sergio Mourelo
Ferrandez, Timothy Harbison, Troy Weber, Robert Sturges, Robert Rich
Journal Code: jptindustrigg160038
