Tosefta for Pesachim 11:22

One who departs with a caravan or sets sail on a ship more than thirty days [before Passover] does not need to search [for chametz], [but one who departs or sets sail] within thirty days searches, and removes them (i.e., the pieces of chametz), and [then] goes on his way.