Application of “Travelling Salesman Problem” in Dynamic Programming for Efficient and Cost Effective Route Design for Distribution
Case of Chifles Distribution of ORFI Company, Ecuador
Keywords:
Symmetric Travelling Salesman Problem, Dynamic Programming, Deductive analysis, Distribution, Symmetric distance matrices.Abstract
Purpose: The present study is designed to optimize a route for the distribution of chifles of the ORFI Company in school bars within the Río Verde parish of the Santo Domingo City, Republic of Ecuador.
Methodology: Time and distance data were collected regarding the route of the vendors, then distance matrices were developed between distribution points, and a graph was designed to find the best route using the Bellman-Hell-Karp algorithm.
Results: The sector graph had 46 nodes and the optimal route was found by applying dynamic programming with the Held-Karp mathematical algorithm, the optimal route for the ORFI company chifles distribution is: 1-2-3-4-5-8-7-6-10-9-12-11-13-14-15-16-18-17-19-20-21-22-23-24-25-26-31-27-28-29-30-32-33-34-38-35-36-37-39-40-41-42-43-44-45-46-1, with 23089 meters of distance, optimizing in travel time 15% and travel distance 11%.
Implications: The application of the findings is expected to reduce the cost and time of distribution expended by the OFRI Company. Similar approaches also can be applied by other companies operating in the city.
