Hola:
La forma más acordada para distinguir el fin de una ruta es representar explícitamente la vuelta al depósito incluyendo el identificador del depósito.
Sobre lo segundo, es como les parezca. Intenten hacer una evaluación inteligente para verificar la eficacia de su algoritmo en las diferentes casuísticas.
Saludos,
Santiago.