Bridge optimization is a significant challenge, given the huge number of possible configurations of the problem. Embodied energy and cost were taken as objective functions for a box-girder steel–concrete optimization problem considering both as single-objective. Embodied energy was chosen as a sustainable criterion to compare the results with cost. The stochastic global search TAMO algorithm, the swarm intelligence cuckoo search (CS), and sine cosine algorithms (SCA) were used to achieve this goal. To allow the SCA and SC techniques to solve the discrete bridge optimization problem, the discretization technique applying the k-means clustering technique was used. As a result, SC was found to produce objective energy function values comparable to TAMO while reducing the computation time by 25.79%. In addition, the cost optimization and embodied energy analysis revealed that each euro saved using metaheuristic methodologies decreased the energy consumption for this optimization problem by 0.584 kW·h. Additionally, by including cells in the upper and lower parts of the webs, the behavior of the section was improved, as were the optimization outcomes for the two optimization objectives. This study concludes that double composite action design on supports makes the continuous longitudinal stiffeners in the bottom flange unnecessary.