Càlcul de rutes: una aproximació a l'actualitat

Quina és la ruta més ràpida de Barcelona a Sevilla? Demà, a les 9:00h del matí, seguirà sent la mateixa?  I si hi vaig amb un vehicle de gran tonatge? D’es d’on soc ara, fins a on puc arribar en 30 minuts? He de visitar aquesta llista de clients, quina ruta he de seguir per fer-ho el més ràpidament possible? D'una llista de vehicles que es troben en unes posicions determinades, quin és el que trigarà menys a arribar a aquest client ? 

Aquestes i altres preguntes similars són les que és capaç de respondre la llibreria de càlcul de rutes de Nexus Geographics. Internament l'anomenem NGRouteNet5.

La primera versió va aparèixer al voltant de l’any 2003. Fins aquell moment utilitzàvem una llibreria comercial.  El número de trams de la xarxa de carreteres havia augmentat molt (si mal no recordo, uns 150.000 trams) i aleshores trigava més de 45 segons per calcular una ruta de punta a punta d’Espanya. Amb la nova llibreria vam aconseguir reduir-ho a uns segons… les màquines d’aquell moment estaven força limitades en quan a memòria i rendiment.

Al llarg dels anys, el número de trams a la xarxa no ha parat de créixer, o bé perquè ha anat augmentant la cobertura dins dels països, o bé perquè n’hem afegit de nous. Les característiques de les màquines han anat millorant molt però ha calgut anar modificant els algorismes per aprofitar-ne el rendiment.

Actualment arribem a tractar xarxes amb més de 100 milions de trams.

D’altra banda, el nombre de peticions de càlcul per minut dels nostres clients no ha parat de créixer i ha calgut estudiar solucions per calcular-les en paral·lel, dins d’una mateixa màquina (multi thread) i a fora, utilitzant-ne d’altres.

La llibreria ha anat incorporant cada vegada més funcionalitats: matrius de costos entre molts orígens i destins; rutes  amb restriccions per camions i vehicles especials; rutes amb restriccions temporals; isòcrones, rutes en funció del trànsit previst a certa data i hora o rutes calculades tenint en compte l’estat del trànsit actual.

La majoria de característiques anteriors requereixen que es pugui modificar dinàmicament els costs del trams. Aquesta flexibilitat limita l’elecció dels algorismes que es poden aplicar per optimitzar el càlcul de rutes. Per exemple, en el món open source s’utilitza habitualment Contraction Hierarchies que dona uns temps de càlcul immillorables. Però per aplicar aquest algorisme cal executar abans un procés de preparació en que es necessita saber el cost final per travessar els trams. Aquesta preparació pot arribar a trigar més de 24 hores en xarxes de 100 milions de tramsi si es modifica el cost d’un sol tram cal tornar a executar la preparació.  En el nostre cas, apliquem altres tipus d’optimitzacions més enfocades cap a la topologia de la xarxa que no pas al cost específic dels trams, serà pel nostre ADN GIS?

Amb aquest tipus d’algoritme un canvi de cost en un tram no implica haver de tornar a precalcular tota la xarxa. 

Donat que cada cop hi ha més interès per l’optimització de flotes en temps real preveiem que el volum de peticions anirà creixent. Sobretot el de càlcul de matrius. És aquí on destinem el nostres esforços per optimitzar-ho encara més.

Albert Rovira. Cap de producte de Cercalia.