Planificación de rutas.

Un procedimiento para determinar una ruta para un vehículo (6),

comprendiendo el procedimiento:

medir, mediante un aparato de medición (20), la posición del vehículo (6);

proporcionar, para su utilización por uno o varios procesadores (22), una especificación de un área (12) a la que se tiene que desplazar el vehículo (6); y

utilizando las mediciones y la especificación del área (12), llevar a cabo, mediante dichos uno o varios procesadores (22), un proceso de determinación de ruta para determinar la ruta para el vehículo (6), en el que el proceso de determinación de ruta comprende:

construir un grafo (34) dentro de un espacio de estados (X) del vehículo (6), comprendiendo el grafo (34) una serie de vértices y uno o varios bordes que conectan dichos vértices;

identificar, dentro del grafo construido (34), un trayecto desde un primer vértice del grafo (34) hasta un segundo vértice del grafo (34), correspondiendo el primer vértice a una posición medida del vehículo (6), y correspondiendo el segundo vértice al vehículo (6) estando ubicado, por lo menos parcialmente, dentro del área (34);

utilizando el trayecto identificado, llevar a cabo un algoritmo de acortamiento de trayectos para proporcionar un trayecto acortado; y

determinar la ruta del vehículo especificada por el trayecto acortado, proporcionando de ese modo la ruta para el vehículo (6); y

el algoritmo de acortamiento de trayectos comprende:

definir el trayecto identificado como el trayecto actual; y

llevar a cabo una o varias etapas i a vi, para producir el trayecto acortado; donde la etapa i comprende seleccionar un vértice a lo largo del trayecto actual para proporcionar un primer vértice del trayecto;

la etapa ii comprende seleccionar otro vértice a lo largo del trayecto actual para proporcionar un segundo vértice del trayecto, estando el segundo vértice del trayecto conectado al primer vértice del trayecto mediante por lo menos dos bordes;

la etapa iii comprende determinar un primer valor de coste, siendo el primer valor de coste indicativo de un coste asociado con un trayecto dentro del trayecto actual desde el primer vértice del trayecto hasta el segundo vértice del trayecto;

la etapa iv comprende proporcionar un borde adicional, teniendo el borde adicional como su vértice inicial el primer vértice del trayecto y como su vértice final el segundo vértice del trayecto;

la etapa v comprende determinar un segundo valor de coste, siendo el segundo valor de coste indicativo de un coste asociado con un trayecto desde el primer vértice del trayecto hasta el segundo vértice del trayecto a lo largo del borde adicional; y

la etapa vi, en función del primer y el segundo valores de coste:

deshecha el borde adicional y mantiene el trayecto actual; o bien

modifica el trayecto actual eliminando del trayecto actual los bordes y vértices en el trayecto actual mediante los que están conectados el primer vértice del trayecto y el segundo vértice del trayecto, e incluye el borde adicional en el trayecto actual.