Underground vehicular ad-hoc networks are indorsing wireless networks because they can realize many goals such as improving the driving safety and monitoring the emergency alerts in underground environments (i.e., road tunnels). It is necessary for vehicular nodes to recognize their positions to achieve these goals. However, Global Positioning System (GPS) devices cannot operate in underground environments; furthermore, the signal propagation faces many effects such as attenuation, multipath and shadow fading. Traditional distance measurement techniques are inadequate to estimate vehicular node locations in underground environments because the expected measurement errors lead to poor positioning. In this paper, the network connectivity is exploited to estimate vehicular node positions instead of radio ranging methods. This work investigates one of the most important techniques that are based on the network connectivity (i.e., Monte Carlo) and proposes new heuristics that achieve an appropriate position estimation accuracy for vehicular nodes. As the underlying method is predictable, it enables these nodes to know their positions all the time inside underground environments. In addition, an efficient deployment strategy is proposed in this work to well organize reference nodes (i.e., fixed nodes that their positions are preconfigured) inside a road tunnel. The proposed scheme performance is verified by NS2 simulator and compared with the current Monte Carlo localization schemes where the simulation results indicate the superiority of the proposed scheme.