Modeling the VRPD and solution encoding for optimization using genetic algorithms

Abstract

In recent years, last-mile delivery has experienced significant growth, mainly driven by the rise of e-commerce. It is estimated that between 50 and 150 products need to be delivered per route each day. Internationally renowned companies have already incorporated the use of drones for product delivery. Recently, the vehicle routing problem with Drones (VRPD) has begun to be studied, this is an extension of the classic vehicle routing problem (VRP). The VRPD proposes that both trucks and drones operate simultaneously to carry out product deliveries. This study addresses the mathematical modeling and the use of a genetic algorithm to solve the problem. The model's objective function considers the travel times of both trucks and drones, which must be minimized to achieve an optimal operating point. Experiments were conducted using small randomly generated instances in an urban environment, and the results showed that solution encoding, as well as proper parameter tuning, are key factors in developing an efficient algorithm.