Citas bibligráficas
Ruiz, F., (2023). 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 [Universidad de Lima]. https://hdl.handle.net/20.500.12724/19749
Ruiz, F., 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 []. PE: Universidad de Lima; 2023. https://hdl.handle.net/20.500.12724/19749
@misc{renati/1435428,
title = "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",
author = "Ruiz Landers, Franco Mauricio",
publisher = "Universidad de Lima",
year = "2023"
}
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.
Este ítem está sujeto a una licencia Creative Commons Licencia Creative Commons