I think you sort of answered your own question, you'd need to either configure things locally such that the yml file described what was on your disk, OR, automate the steps to do that as part of the Travis CI build script.
The good news is that my script only installs the Arduino IDE if it can't find it. arduino_ci/arduino_installation.rb at master · Arduino-CI/arduino_ci · GitHub
So this should be workable. Want to try this out?