Except that there are Android applications (like ABRP - https://abetterrouteplanner.com/ ) that do planning _better_ than the built-in navigation software in Tesla.

> Maybe a separate map app that ran inside carplay to provide the required featureset?

Yup. It's a pretty straightforward feature. Heck, I'd write it myself once I get an EV with Android Auto.