El artículo presenta la aplicación de tres técnicas de optimización heurística de una estructura tipo bóveda de hormigón armado empleada para la construcción de pasos de carretera: la búsqueda exhaustiva de máximo gradiente, la cristalización simulada y la aceptación por umbrales. La bóveda se define mediante 21 variables de decisión, siendo la función objetivo el coste económico. Todos los métodos se han aplicado a una bóveda de 4,25 m de diámetro y 1,40 m de altura en hastiales, con un relleno de tierras de 7,00 m. Se proponen dos movimientos específicos de búsqueda por entornos y un algoritmo para la calibración automática de la cristalización simulada y la aceptación por umbrales. Se comprueba la eficiencia de estas dos técnicas para el diseño automático y económico de las bóvedas de hormigón estructural, si bien la búsqueda exhaustiva reduce a la quinceava parte el tiempo de cálculo necesario. Las estructuras óptimas presentan una esbeltez importante en la bóveda, con relaciones canto/luz de 1/20. Se han encontrado ahorros cercanos al 8% respecto a estructuras calculadas de forma tradicional.