Los sensores de tráfico son vitales para el desarrollo y operación de Sistemas de Transporte Inteligente, proporcionando datos esenciales para el monitoreo del tráfico, la gestión y la planificación de la infraestructura de transporte. Sin embargo, optimizar la ubicación de estos sensores, particularmente en grandes y complejas redes de carreteras estatales, sigue siendo una tarea desafiante. En esta investigación, presentamos un nuevo algoritmo de búsqueda diseñado para abordar este desafío aprovechando los gradientes de información de los K vecinos más cercanos dentro de un espacio de incrustación. Nuestro método permitió una colocación de sensores más informada y estratégica bajo restricciones de presupuesto y recursos, mejorando la cobertura general de la red y la calidad de los datos. Además, incorporamos un análisis de kriging espacial, aprovechando las correlaciones espaciales de los sensores existentes para refinar y reducir el espacio de búsqueda. Nuestro enfoque propuesto fue probado contra el ampliamente utilizado Algoritmo Genético, demostrando una eficiencia superior en términos de tiempo de convergencia y produciendo soluciones más efectivas con una reducción de la pérdida de información.