Solución al problema de generación de planes de trabajo basado en el problema del agente viajero utilizando el algoritmo genético Chu-Beasley

Abstract

This article introduces a methodology to address logistics management by generating work plans based on the Multiple Traveling Salesman Problem (MTSP). The primary objective is cost minimization, which can manifest in two forms: distance or the time required for executing work plans. Two methods are used to measure distance: the first calculates spherical distances using the Haversine formula, and the second leverages Google Maps data to obtain traffic-related travel time information. One of the goals of this methodology is to validate the benefits of carrying out optimizations on multiple routes affected by traffic variables, resulting in travel times, within a modern, modular, and rapidly implementable software architecture. To solve the mathematical model, the Chu-Beasley genetic algorithm is used with enhancements through the Or-Opt operator, aiming to obtain high-quality solutions with reasonable times in daily logistics planning. In the results analysis stage, tests were conducted using instances obtained from real company locations whose operations are affected by logistics performance. The study's results were compared to those of an expert in the field using the nearest neighbor algorithm as a reference, focusing on the distance variable, which demonstrated significant improvements and confirmed the benefits of using logistics planning with optimization algorithms considering traffic variables.