Apple TV can't always be detected by Mac & iPhone I have both a Mac and iPhone: the AirPlay icon to stream video and music to AppleTV randomly appears and disappears on both of them. 

I think it is a network issue, but I don't know how to solve it, since it might work perfectly one day and the next no device can find the AppleTV.
I had the exact same problem. My Mac, iPhone, or iPad wouldn't connect because the icon disappears at random intervals.

You can try plugging in an Ethernet cable, however this doesn't seem to permanently fix the problem.

What I did was get a new router that supports dual band (2.4 GHz and 5 GHz). The iPhone uses 2.4 GHz and my Mac and AppleTV use 5 GHz. There was less traffic that way (because of splitting the bands over different devices) through the router and the AppleTV is always detected. This forced the AirPlay option to always appear on my devices. 

You can check my question and other possible answers here AirPlay option disappeared?