Ese tipo de cosas las suelo hacer en After Effects, pero se me ocurre: Dibuja la ruta o sendero con su canal alfa (en Photoshop) y le pones encima una máscara que se mueva, descubriendo la trayectoria en la línea de tiempo, todo esto lo colocas sobre el mapa y listo.
En After Effects se dibuja una línea vectorial sobre el mapa con la forma del sendero y luego se anima el filtro render>stroke y está listo en un por favor.
Intenta lo que te digo y si te trabas en alguna etapa del proceso lo publicas para echarte un cable. Suerte.