This paper addresses the broadcasting storm problem by proposing an optimized relay vehicle selection methodology in the vehicular ad-hoc networks (VANETs). A crucial effect observed in the broadcasting storm is the network congestion that is caused by multiple retransmissions generated by the relay vehicles to achieve the desired network coverage. In order to address this problem, we propose an optimized relay selection methodology based on multi-objective genetic algorithm (MOGA) consisting of a novel analytical fitness function. In this paper, we present a detailed study of previous research work and identify the gaps to achieve the optimum performance in terms of network coverage time. We introduce a component-based analytical model containing the proposed MOGA to reduce these performance gaps. A dedicated solver was designed using Python to implement the proposed model in both urban and highway environments. The numerical results obtained by the proposed MOGA are compared with the existing techniques. It is shown that the proposed method performs better in terms of number of retransmissions and network coverage time.