El problema del viatjant a l'era moderna

Formulat per primera vegada al segle XIX, l'estudi del problema del viatjant (TSP, per les sigles en anglès) va avançar notablement gràcies al matemàtic nord-americà Merrill M. Flood als anys trenta, quan es va proposar resoldre un problema de rutes d'autobusos escolars. El TSP és un problema matemàtic en què cal trobar la ruta més curta possible que passi per un conjunt de punts (en aquest cas, parades d'autobús). La ruta definida ha de passar per cada punt una sola vegada abans de tornar al punt de partida.

En general, l'ordre en què es visita cada parada o punt no és un factor principal, sempre que el viatjant passi per tots una vegada. Malgrat l'extraordinària senzillesa de la seva formulació, el TSP és un problema NP-difícil d'optimització combinatòria i es pot utilitzar com a model per provar tècniques d'optimització aplicades a problemes molt diversos, inclòs el despatx dinàmic de vehicles compartits.

En un pla més abstracte, el TSP es pot descriure mitjançant la teoria de grafs com una xarxa ponderada no dirigida, els nodes de la qual representen ciutats i els enllaços de la qual tenen pesos que indiquen les distàncies entre elles. En aquest context, trobar la solució òptima del TSP significa trobar el camí més curt que connecti tots els nodes de la xarxa. A la literatura existeixen diversos algorismes que analitzen les propietats estructurals d'una xarxa buscant-ne els camins més curts, i són el nucli de la teoria de grafs tradicional. L'aplicació d'aquests algorismes a xarxes complexes es dona en camps consolidats com les matemàtiques, la biologia i les ciències socials.

Resulta sorprenent que, encara que aquests algorismes es basen en un problema relativament senzill i es van desenvolupar per resoldre'l, avui la seva capacitat predictiva també s'aprofita per facilitar operacions industrials complexes. Sectors d'enorme importància a la nostra vida diària, com el repartiment de mercaderies a escala local, nacional i internacional, el sector marítim, les xarxes aeroportuàries o les xarxes de transport públic de les grans àrees metropolitanes, són només alguns exemples que utilitzen variants dels algorismes del TSP per fer-nos la vida més fàcil.

El camí més curt en una variant del TSP es pot trobar calculant totes les combinacions de rutes possibles. Aquest enfocament de força bruta funciona quan N és prou petit, però és pràcticament inviable per a valors grans de N. En aquest últim cas, els algorismes de cerca heurística ofereixen excel·lents solucions aproximades. El seu principal avantatge és la seva capacitat d'obtenir solucions de la variant del TSP que, encara que no siguin exactes, són molt més pràctiques i, sobretot, s'obtenen ràpidament i amb un baix cost computacional. Això fa que els algorismes de cerca heurística siguin populars i adequats per a serveis de programari en què els recursos de computació són limitats i la resposta en temps real és crucial, sobretot quan la demanda creix.

La tecnologia de Shotl utilitza mètodes científics moderns que permeten aprofitar la recerca passada i actual sobre xarxes complexes i algorismes d'optimització. El servei, recolzat per un disseny d'enginyeria àgil, es construeix al voltant d'un sòlid nucli algorítmic que troba solucions òptimes en una variant del TSP formulada segons les restriccions de cada situació concreta.

La nostra solució algorítmica agrupa diversos passatgers que van en la mateixa direcció en un vehicle en moviment, minimitzant les distàncies recorregudes i els temps d'espera, i ofereix així un millor servei i una millor experiència de transport.