Changing the tires is not impossible, you can certainly do it if you are so inclined, but it is not the most efficient way of doing things. The best method of ensuring you can go on all terrains is to buy a stroller wagon which is suitable for this in the first place.