Modelado del VRPD y codificación de las soluciones para la optimización con algoritmos genéticos

Abstract

En los últimos años, la distribución de última milla ha experimentado un notable incremento, impulsado fundamentalmente por el aumento del comercio electrónico. Se estima que en cada ruta de distribución es necesario entregar entre 50 y 150 productos por día. Empresas de renombre internacional ya han incorporado el uso de drones para la entrega de sus productos. En los últimos años, se ha comenzado a estudiar el problema de ruteo de vehículos con drones (VRPD), el cual corresponde a una extensión del clásico problema de ruteo de vehículos (VRP). El VRPD plantea que tanto camiones como drones operen de manera simultánea para llevar a cabo la entrega de los productos. Este estudio aborda el modelado matemático y el uso de un algoritmo genético para su resolución. La función objetivo del modelo considera los tiempos de viaje tanto de los camiones como de los drones, y debe ser minimizada para lograr un punto óptimo de operación. Se llevaron a cabo experimentos con instancias pequeñas generadas aleatoriamente en un entorno urbano, y los resultados demostraron que la codificación de las soluciones, así como una correcta parametrización, son factores claves para desarrollar un algoritmo eficiente.

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.