Google map android sdk оптимальный маршрут между многими точками

Думаю чтобы проложить оптимальный маршрут с n точками нужно построить попарно маршрут между ними. Что бы построить маршрут между двумя точками на карте тебе нужно вызвать api метод google для построения маршрута между двумя точками.

"https://maps.googleapis.com/maps/api/directions/json?" + parameters;

Где parameters это строка которая формируется вот так

String str_origin = "origin=" + origin.latitude + "," + origin.longitude;
String str_dest = "destination=" + dest.latitude + "," + dest.longitude;
String parameters = str_origin + "&" + str_dest + "&sensor=false;

В ответе ты получишь массив точек. Эти точки ты просто соединяешь межу собой в googleMaps при помощи метода карты

map.addPolyline(...)

Просто отобразить точки на карте, в целом не сложно https://developers.google.com/maps/documentation/android-sdk/polygon-tutorial

ОДнако прокладка маршрутов, пошаговая навигация - это коммерческое API https://cloud.google.com/maps-platform/routes/

ВОзможно вот это вам поможет https://stackoverflow.com/questions/24531391/is-it-possible-to-create-turn-by-turn-gps-navigation-app-on-android-using-google