Otimização de roteamento de veículos com coleta de prêmios utilizando a meta-heurística ant colony optimization

Abstract

In the present day, we live in a society where the internet is deeply embedded in people’s daily lives, making them increasingly dependent on technologies that benefit from this tool. Due to its importance, the internet has become the catalyst for various services, notably electronic commerce (e-commerce), radically transforming the way products and services are bought and sold. This shift has led to a rapid increase in demand for deliveries, requiring companies to implement efficient and scalable logistics solutions. An efficient delivery system brings several benefits, such as cost reduction, increased productivity, and customer satisfaction. In this context, an algorithm based on meta-heuristics was developed to solve the vehicle routing problem, exploring the feasibility region to find optimal solutions for the delivery system. To achieve this, the meta-heuristic Ant Colony Optimization was implemented with the primary objective of finding a Hamiltonian path over a subset of vertices, starting at the initial vertex and ending at the final vertex, in order to minimize the total travel costs. The results obtained revealed that the Ant Colony Optimization algorithm performs well in routing problems with prize collecting, finding low-cost solutions within reasonable time. Moreover, the algorithm is particularly effective in problems with fewer vertices but also demonstrates capability in handling more complex problems, with a moderate increase in execution time.