It doesn’t have to be your searches, it could have just been the fact that your phone recognized you were on a road trip and that people in your ad cohort tend to want to buy shoes while on road trips.
Are you f'ing kiddig me? You really going to go with that excuse? Somehow by driving from one city to another city on the freeway that tells Google that I want to buy shoes? Come on, that stretches credulity.
Also, sure is weird that that has never happened to me on any of the other times I also drove the same route over the years.