Google Maps "Searching for GPS"

Hello,

So I not a new Android user but I am new person to this forum thingy! I am also a Android Guy from 3 to 4 year approximately. The main reason I joined this forum is because of google maps. So recently from past 1 year or 6 to 4 months I am getting an error saying "Searching for GPS" when ever I try to go to a destination. Sometimes it even shows me somewhere else even though I am not there. Everything works fine when I am on my home wifi network. Or could this just me my sim operator problem. I have enabled all location even High accuracy and I have no idea what the problem is. I did search all over google, I saw a lot of people having this problem and they have no answer for it. If someone could help me out that would be great.

Thanks