С 11 июня 2018 года Google начал принудительно использовать ключи API. Использование без ключа приведет к ухудшению работы или к ошибке типа OVER_DAILY_LIMIT и OVER_QUERY_LIMIT.
Источник: Важные обновления с Google Maps Platform
Вставка ключа API в URL, как это, является хорошим решением:
String url = "https://maps.googleapis.com/maps/api/directions/"+output+"?"+parameters + "&key=" + MY_API_KEY
Но будьте уверены, что ваши ключевые ограничения хорошо настроены. Если вы ограничиваете ключ для своего приложения, он может не работать, потому что запрос, сделанный через HTTP, связан с вашим IP-адресом. Это означает, что даже если вы правильно настроили приложение Android и манифест, это может привести к ACCESS_DENIED. Это можно проверить, изменив ограничение.
Пример отсутствия ограничений для целей тестирования:
Подробнее о ключе API и ограничениях: Краткое руководство по получению ключа