Don't forget that if Perrin sent out the Asha'man to find Rand after they had a few days of rest (ie: a few days after his last POV in TGS), this would have taken place a few days after Perrin had seen Rand at a Tairen manor (ie: right before the KOD false Tuon trap) and then during the few weeks when Rand was moving almost constantly and hiding. He settled at one place and let Rhuarc know to come to him etc. a few weeks later only. It's very doubtful the Asha'man would have managed to find Rand during those weeks and before he moved to Bandar Eban. The best information they could get (from Darlin in Tear for example) would be : "he's somewhere in Arad Doman and he reaches us, not the other way around". After failing for weeks to locate Rand in AD (countryside hideouts), the Asha'man may have given up and returned to Perrin.

It's doubftul it's what happened, though. We've seen messengers Rand had sent to Tear reporting back to him (I mean, we know what they reported). Rand would have heard that Perrin has been looking for him at the Stone of Tear then.

As for "a better solution", we actually don't know what Perrin has decided to do in the end. His POVs stopped before the Asha'man were rested enough to Travel. We can tell that at that point, on the moment he was told how long it would take the two Asha'man to send all the groups of refugees home, Perrin has not considered a solution involving Rand, but we have no idea what he decided to do in the end.

There's an apparent plot hole there. In KOD Grady had taken to tie up his gateways because he was exhausted. It's conceivable that Neald and him forgot to do that during the hunt for Faile, or thought it too dangerous (ambushes/sneak attacks by Shaido etc.) not to stay in control of the gateways at all time and so ended up exhausting themselves over the 60 days or so (they alternated making a big/prolonged gateway each night to travel to the last point the scouts had spotted the Shaido trail during the day), but it's hard to explain why they don't simply use tied-up gateways for the refugees to avoid exhaustion. It's not like they need to drop each of them on their own doorsteps and make thousands of trips. They can dump all those within a few days of Cairhien at Cairhien, and those living near Maerone at Maerone and so on, and instead of leaving the gateways open and channel for very long each time, they could tied them up instead. We're speaking of a few hundred gateways to make, at most. It should take a few days, at most as the Asha'man can open a great number of human-size gateways per day. Balwer's calculations seem rather based on the maximum length of time the Asha'man can afford to leave large gateways open each day and how many refugees will be able to pass through in that time, which isn't such an issue if the gateways are tied-up

There's no doubt RJ was setting things up for Perrin's Asha'man to be exhausted (it's all over his storyline in KOD) and unable to Travel for a while, but the whole refugee vs. Travelling problem sounds like it could be an addition by Brandon. This could mean it's a "false issue", ie: something will happen soon and Perrin won't be sending out the refugees after all, it's just something Brandon came up with to have an issue to discuss in the Perrin "teaser" chapters in TGS (and while doing so, he forgot about tied-up gateways not making this as big an issue as he made Balwer make. Even Perrin knows about tied-up gateways - he toyed with the idea of asking Grady to leave one to EF open to send Faile out after her rescue and decided it was too dangerous to risk it).