Optimization of a truck-drone in tandem delivery network using k-means and genetic algorithm

Abstract

Purpose: 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.