In spite of their relatively high lattice thermal conductivity κ, the XNiSn (X=Ti, Zr, or Hf) half-Heusler compounds are good thermoelectric materials. Previous studies have shown that κcan be reduced by sublattice alloying on the X site. To cast light on how the alloy composition affects κ, we study this system using the phonon Boltzmann-transport equation within the relaxation time approximation in conjunction with density functional theory. The effect of alloying through mass-disorder scattering is explored using the virtual crystal approximation to screen the entire ternary TixZryHf1-x-yNiSn phase diagram. The lowest lattice thermal conductivity is found for the TixHf1-xNiSn compositions; in particular, there is a shallow minimum centered at Ti0.5Hf0.5NiSn with κtaking values between 3.2 and 4.1 W/mK when the Ti content varies between 20% and 80%. Interestingly, the overall behavior of mass-disorder scattering in this system can only be understood from a combination of the nature of the phonon modes and the magnitude of the mass variance. Mass-disorder scattering is not effective at scattering acoustic phonons of low energy. By using a simple model of grain boundary scattering, we find that nanostructuring these compounds can scatter such phonons effectively and thus further reduce the lattice thermal conductivity; for instance, Ti0.5Hf0.5NiSn with a grain size of L=100 nm experiences a 42% reduction of κcompared to that of the single crystal.