Algoritmo mejorado basado en Kruskal y Prim que resuelve el problema del repartidor orientado a tiendas con almacén centralizado usando datos del Api Directions de Google

Abstract

La presente investigación tiene como principal objetivo resolver un tipo de problema de enrutamiento de vehículos. El problema se enfoca en couriers que realicen entregas a varios destinos. Se busca aplicar la teoría de grafos, tomando los destinos de las entregas como los nodos y el tiempo o la distancia como los vértices. Para resolverlo, se debe aplicar una forma de convertir ese grafo en un Árbol de Expansión Mínima. Por lo tanto, se realiza una comparación entre el algoritmo de Prim y una modificación del algoritmo de Kruskal ya que ambos permiten generar un Árbol de Expansión Mínima, el cual nos permite reducir el costo total de los vértices. La implementación de la solución consiste en una aplicación Node.js en la que se ingresar direcciones en coordenadas como muestras a un motor que permite crear la matriz de costos de un grafo, en el cual, los nodos equivalen a los destinos y el peso de los vértices, a la distancia entre cada destino. Dentro de este procesamiento se hace uso del recurso abierto en línea ‘Directions’ de Google, orientado al cálculo de rutas entre dos direcciones, del cual se registran las variables distancia y duración de los resultados. De esta manera, se continúa ingresando la matriz de costos como variable de entrada a cada algoritmo. Finalmente, se genera la lista de destinos donde el courier debe entregar pedidos en el orden óptimo. Para entender el impacto, se compara el costo total del orden óptimo generado por Kruskal y el orden en el que fue entregado originalmente. En cuatro de cada cinco muestras se encontró una mejora de 11% en promedio de los pesos totales del grafo que representa la matriz de costos, lo que nos indica que los distribuidores sí pueden reducir los costos de entrega.

The main objective of this research is solving a variant of VRP (Vehicle Routing Problem) focused on couriers that delivery to many places at once. Following graph theory, nodes and vertices are now destinations and time/distance. In order to solve this, we must apply a way to turn the graph into a Minimum Spanning Tree. Hence the comparison between algorithm of Prim and a modification of Kruskal’s due to both achieve to generate Minimum Spanning Tree, which lets us reduce total costs of vertices. Implementation of solution consists in a HTML web application programmed using Javascript, which works calculating total time and distance cost of a list of destinations in order to generate graph’s cost matrix in which nodes represent destinations as coordinates and vertices the route from point A to B. Within computation, Google’s online free resource ‘Directions’ is used to calculate time and distance between each par destination as input. Finally, it outputs an optimal order destination list for the courier. To address impact, there’s a comparison between total time and distance cost of optimal order created by Kruskal or original order taken by courier. On four out of five samples, there was found an improvement of 11% on average, which means that distributors can reduce costs of delivery.