It appears that only the radiant quests handed out by Mags Black, Nisha and Mason count for this achievement. Fritsch's Amoral Combat for instance, as well as other minor Nuka-World quests, seem to be considered invalid.
Given that the gang leaders' tasks invariably send the Sole Survivor to the Commonwealth and only three of them can be active in parallel (one per gang), at least four trips are required to unlock the achievement. This mechanic poses a particular nuisance for anyone playing the game in Survival mode due to the sheer amount of lengthy travels involved for very little gain. It is therefore recommended to tackle this achievement while playing on a basic difficulty level.