Qual é a melhor maneira de armazenar coordenadas geográficas relacionadas à rota planejada?

Isso pode ser um problema NP-Complete, http://en.wikipedia.org/wiki/NP-complete Compare com o problema do caixeiro viajante, http://en.wikipedia.org/wiki/Travelling_salesman_problem Não tenho certeza se for NP-Complete, pois meus textos da faculdade estão armazenados e já faz um tempo desde minhas aulas de complexidade.

Não quer dizer que não podemos simplesmente fazer algumas "matemáticas de desvio" simplistas usando tipos de dados espaciais do SQL Server começando com a abordagem de tabela sugerida por @kenwilsondba.

Uma abordagem mais completa (se não NP-Complete) procuraria onde a rota real voltou aos trilhos entre outras coisas.

No entanto, poderíamos fazer o seguinte utilizando os tipos de dados espaciais do SQL Server se tudo o que precisamos for um cálculo simplista de desvio, onde poderíamos simplesmente descartar destinos extras se a rota real for ultrapassada ou repetir o último ponto final real se a rota real for abaixo , e desconsidere todos os segmentos em que a rota voltou ao caminho certo e suponha que os IDs de parada sejam realmente sequenciais.

Observe que essa abordagem de cálculo também penaliza as rotas reais que se desviam apenas no início e nunca se desviam no restante da rota, e recompensa aqueles que permanecem na pista até os pontos finais.

Outra ressalva é que os campos no design da tabela abaixo são redundantes.

Os cálculos de distância são em metros por padrão.

CREATE TABLE a_planned_point (
    route_id            INT, 
    stop_id             INT,
    lat                 DECIMAL(10,7), 
    long                DECIMAL(10,7), 
    pointspatialdata    GEOGRAPHY,    
    city                VARCHAR(20),
    state               CHAR(2) )

CREATE TABLE b_actual_point (
    route_id            INT, 
    stop_id             INT,
    lat                 DECIMAL(10,7), 
    long                DECIMAL(10,7), 
    pointspatialdata    GEOGRAPHY,    
    city                VARCHAR(20),
    state               CHAR(2) )

CREATE TABLE c_planned_segment (
    route_id            INT, 
    start_id            INT,
    stop_id             INT,
    lat_planned_stop    DECIMAL(10,7), 
    long_planned_stop   DECIMAL(10,7), 
    city_planned        VARCHAR(20),
    state_planned       CHAR(2), 
    segmentspatialdata  GEOGRAPHY)

CREATE TABLE d_actual_segment (
    route_id            INT, 
    start_id            INT,
    stop_id             INT,
    lat_actual_stop     DECIMAL(10,7), 
    long_actual_stop    DECIMAL(10,7), 
    city_actual         VARCHAR(20),
    state_actual        CHAR(2), 
    segmentspatialdata  GEOGRAPHY)

CREATE TABLE e_drift_segment (
    route_id            INT, 
    planned_stop_id     INT,
    actual_stop_id      INT,
    lat_planned_stop    DECIMAL(10,7), 
    long_planned_stop   DECIMAL(10,7), 
    city_planned        VARCHAR(20),
    state_planned       CHAR(2), 
    lat_actual_stop     DECIMAL(10,7), 
    long_actual_stop    DECIMAL(10,7), 
    city_actual         VARCHAR(20),
    state_actual        CHAR(2), 
    distance_drift      FLOAT,
    segmentspatialdata  GEOGRAPHY)

INSERT INTO a_planned_point (route_id, stop_id, lat, long, pointspatialdata, city, state) VALUES
    (1, 0, 33.93, -118.40, CAST('POINT(-118.40 33.93)' AS GEOGRAPHY), 'Los Angeles', 'CA'), 
    (1, 1, 33.43, -112.02, CAST('POINT(-112.02 33.43)' AS GEOGRAPHY), 'Phoenix', 'AZ'),
    (1, 2, 39.75, -104.87, CAST('POINT(-104.87 39.75)' AS GEOGRAPHY), 'Denver', 'CO'), 
    (1, 3, 25.82, -80.28,  CAST('POINT(-80.28 25.82)' AS GEOGRAPHY),  'Miami Intl', 'FL'), 
    (1, 4, 40.77, -73.98,  CAST('POINT(-73.98 40.77)' AS GEOGRAPHY),  'New York', 'NY'), 
    (1, 5, 42.37, -71.03,  CAST('POINT(-71.03 42.37)' AS GEOGRAPHY),  'Boston', 'MA')

INSERT INTO b_actual_point (route_id, stop_id, lat, long, pointspatialdata, city, state) VALUES
    (1, 0, 33.93, -118.40, CAST('POINT(-118.40 33.93)' AS GEOGRAPHY), 'Los Angeles', 'CA'), 
    (1, 1, 39.75, -104.87, CAST('POINT(-104.87 39.75)' AS GEOGRAPHY), 'Denver', 'CO'), 
    (1, 2, 33.43, -112.02, CAST('POINT(-112.02 33.43)' AS GEOGRAPHY), 'Phoenix', 'AZ'),
    (1, 3, 25.82, -80.28,  CAST('POINT(-80.28 25.82)' AS GEOGRAPHY),  'Miami Intl', 'FL'), 
    (1, 4, 40.77, -73.98,  CAST('POINT(-73.98 40.77)' AS GEOGRAPHY),  'New York', 'NY')



INSERT INTO c_planned_segment (
    route_id,
    start_id, 
    stop_id,
    lat_planned_stop,
    long_planned_stop,
    city_planned,  
    state_planned,
    segmentspatialdata
    )
    SELECT 
        x.route_id, 
        x.stop_id, 
        y.stop_id, 
        y.lat, 
        y.long, 
        y.city, 
        y.state, 
        CAST('LINESTRING(' + CAST(x.long AS VARCHAR) +' '+ CAST(x.lat AS VARCHAR) +', '+ 
            CAST(y.long AS VARCHAR) +' '+ CAST(y.lat AS VARCHAR) + ')' AS GEOGRAPHY) AS segmentspatialdata
    FROM 
        a_planned_point x
    LEFT OUTER JOIN 
        a_planned_point y
    ON     
        y.stop_id = x.stop_id + 1 
    WHERE 
        y.stop_id IS NOT NULL   
        and 
        x.route_id = 1
    ORDER BY x.stop_id

INSERT INTO d_actual_segment (
    route_id, 
    start_id, 
    stop_id, 
    lat_actual_stop,
    long_actual_stop,  
    city_actual, 
    state_actual,
    segmentspatialdata 
    )
    SELECT 
        x.route_id, 
        x.stop_id, 
        y.stop_id, 
        y.lat, 
        y.long, 
        y.city, 
        y.state, 
        CAST('LINESTRING(' + CAST(x.long AS VARCHAR) +' '+ CAST(x.lat AS VARCHAR) +', '+ 
            CAST(y.long AS VARCHAR) +' '+ CAST(y.lat AS VARCHAR) + ')' AS GEOGRAPHY) AS segmentspatialdata
    FROM 
        b_actual_point x
    LEFT OUTER JOIN 
        b_actual_point y
    ON     
        y.stop_id = x.stop_id + 1 
    WHERE 
        y.stop_id IS NOT NULL   
        and 
        x.route_id = 1
    ORDER BY x.stop_id



INSERT INTO e_drift_segment (
    route_id, 
    planned_stop_id, 
    actual_stop_id, 
    lat_planned_stop, 
    long_planned_stop, 
    city_planned, 
    state_planned,
    lat_actual_stop,
    long_actual_stop,
    city_actual,
    state_actual,
    distance_drift,
    segmentspatialdata 
    )
    SELECT 
        x.route_id, 
        x.stop_id, 
        y.stop_id, 
        x.lat,
        x.long, 
        x.city, 
        x.state,
        y.lat, 
        y.long, 
        y.city, 
        y.state,
        x.pointspatialdata.STDistance(y.pointspatialdata), 
        CAST('LINESTRING(' + CAST(x.long AS VARCHAR) +' '+ CAST(x.lat AS VARCHAR) +', '+ 
            CAST(y.long + 0.0000001 AS VARCHAR) +' '+ CAST(y.lat AS VARCHAR) + ')' AS GEOGRAPHY) AS segmentspatialdata
    FROM 
        a_planned_point x
    LEFT OUTER JOIN 
        b_actual_point y
    ON     
        y.stop_id = x.stop_id 
    WHERE 
        x.stop_id IS NOT NULL   
        and 
        y.stop_id IS NOT NULL   
        and
        x.route_id = 1
    ORDER BY x.stop_id

Para encontrar a quantidade total de desvio em metros:

select sum(distance_drift) from e_drift_segment where route_id = 1

Para mostrar os segmentos de rota planejada, real e de desvio de uma só vez na guia "Resultados Espaciais" do SQL Server:

select segmentspatialdata from c_planned_segment where route_id = 1
union all
select segmentspatialdata from d_actual_segment where route_id = 1
union all
select segmentspatialdata from e_drift_segment where route_id = 1

Recomendo o uso de duas tabelas. Tabela A para a rota planejada e Tabela B para a rota real. Depois de preencher ambas as tabelas, você pode unir as duas tabelas em algum tipo de identificador e usar o método STDistance para determinar os desvios. Existem também muitos outros métodos que acho que seriam úteis nessa situação.

Consulte http://technet.microsoft.com/en-us/library/cc280766.aspx