I recommend no cleats, just regular shoes. One less thing to bring on the tour. Once, while pedaling through nasty wet weather in northern Australia, I tried pedaling in Teva sandals. It worked just fine.