Polarimetric dehazing is an effective way to enhance the quality of images captured in foggy weather. However, images of essential polarization parameters are vulnerable to noise, and the brightness of dehazed images is usually unstable due to different environmental illuminations. These two weaknesses reveal that current polarimetric dehazing algorithms are not robust enough to deal with different scenarios. This paper proposes a novel, to our knowledge, and robust polarimetric dehazing algorithm to enhance the quality of hazy images, where a low-rank approximation method is used to obtain low-noise polarization parameter images. Besides, in order to improve the brightness stability of the dehazed image and thus keep the image have more details within the standard dynamic range, this study proposes a multiple virtual-exposure fusion (MVEF) scheme to process the dehazed image (usually having a high dynamic range) obtained through polarimetric dehazing. Comparative experiments show that the proposed dehazing algorithm is robust and effective, which can significantly improve overall quality of hazy images captured under different environments.