El diseño de rutas eficientes para vehículos comerciales es de
vital importancia en los sectores de transporte y logística. El ruteo de vehículos
pertenece a la familia de problemas NP-Difícil, lo que obliga al diseño
de algoritmos heurísticos para su solución. El presente estudio introduce
una novedosa versión de la búsqueda tabú que hace uso de una lista
tridimensional y aplica penalizaciones con incremento lineal a soluciones
no viables durante la búsqueda. El algoritmo fue evaluado utilizando un
reconocido conjunto de casos, y presentó buenos resultados.
The design of efficient routes for commercial vehicles is critical
in the logistics and transportation sectors. The Vehicle Routing Problem is
NP-Hard. Consequently, approximation algorithms are required to solve
real-life size problem instances. This work introduces a tabu search algorithm
that uses a tridimensional tabu list and a linear increasing penalty
for handling infeasible solutions. The algorithm was tested using a well
known set of problem instances, showing strong and encouraging results.