En transport, el camí més ràpid és el camí més curt?

Si volem anar de casa al supermercat, pensarem gairebé de forma automàtica per on passarem per anar-hi. Si és un recorregut habitual, és possible que ja hàgim provat diverses alternatives i coneguem quina ruta és la més ràpida. És possible que el camí més ràpid (entès com el camí en què menys temps triguem) sigui el camí més curt (entès com el camí en què es recorre una distància total més baixa), però no sempre serà així. Els amants de la muntanya saben bé que hi ha camins ben curts, però amb una dificultat tan alta que a la pràctica no resulten ser els més ràpids. Així doncs, el camí més ràpid no només depèn de la distància sinó d’altres factors que caracteritzen la ruta.

Aquest acte que fem de forma quasi inconscient és una de les principals decisions operatives que han de prendre les empreses de transport quan han d’anar a recollir o a entregar paquets a diferents punts del territori. Si bé aquesta tasca pot semblar senzilla quan hi ha pocs llocs a visitar i es coneix el terreny, es torna un veritable mal de cap quan els punts a visitar són múltiples, les condicions orogràfiques són limitants i es té el compromís de fer acte de presència (per recollir o entregar) en una certa hora.

És per això que ja fa més de 60 anys que es van desenvolupar models matemàtics per automatitzar la cerca de la ruta més eficient. L’any 1959, George Dantzig i John Ramser (article) van ser els primers a plantejar-se el problema d’optimitzar les rutes per repartir combustible.

La recerca de modelitzacions i mètodes per resoldre aquest problema és molt abundant i actual, però de moment no s’ha aconseguit poder resoldre aquest problema de forma exacta per a problemes grans en un temps adequat. És per això que es desenvolupen solucions heurístiques que puguin trobar rutes de qualitat en el temps disponible.

El problema de l'assignació de rutes dels vehicles (o Vehicle Routing Problem, en anglès) consisteix a planificar les rutes òptimes d’una flota de vehicles per tal de servir la demanda a un conjunt de clients. Se suposa que els vehicles tenen una capacitat limitada per transportar la demanda i surten des d’un únic punt, que representa el magatzem, i és el mateix al qual han de tornar. Per identificar la millor solució, es defineix el criteri sobre el qual es valoraran diverses propostes de rutes. El criteri més habitual és minimitzar el cost total del transport expressat com la distància total recorreguda pels vehicles. Altres criteris poden ser la minimització del temps utilitzat o bé la minimització de les emissions generades.

Posem, per exemple, que avui hem d’entregar un paquet a set clients. Aquests estan localitzats com en el mapa de la següent figura, en una ciutat de traçat ortogonal. Disposem de dues furgonetes que poden transportar fins a quatre paquets cadascuna. Quina és la millor manera de repartir-se la feina? Suposem que volem fer el recorregut més curt i que en aquest exemple podem calcular fàcilment la distància rectilínia entre dos punts, també coneguda com a distància Manhattan. Bàsicament hem de comptar quantes illes s’han de recórrer per viatjar entre dos punts. Per exemple, la distància entre el magatzem i el client 1 és de 6 unitats, 4 illes en vertical i dues illes en horitzontal.

Una solució senzilla seria servir els clients 1-2-3-4 amb un vehicle i els clients 5-6-7 amb l’altre vehicle. Aquesta solució representaria una distància de 40 unitats (recordeu que la ruta té sortida i arribada al magatzem). Una solució millorada la podríem trobar utilitzant una heurística del veí més proper, on es busqui visitar sempre el client que queda més proper del punt que visitem. Així doncs, una ruta seria servir els clients 4, 6, 7 i 1 i l’altra ruta seria servir els clients 3, 2 i 5. Aquesta nova proposta recorre una distància total de 36 unitats, una rebaixa del 10%. El repte és, doncs, saber si hi ha alguna altra solució que millori aquest resultat. Ho voleu provar? Al final de l’escrit us en donarem la resposta!

Si en lloc d’optimitzar respecte a la distància, volguéssim tenir en compte el temps utilitzat per recórrer les rutes, és molt possible que la solució no fos la mateixa, ja que el temps depèn del tipus de via per la qual se circula, la velocitat permesa, el moment del dia o altres afectacions puntuals que puguin tenir les vies (obres, congestió, situació meteorològica, etc.).

L’optimització de rutes és un camp ric d’opcions a tenir en compte que, ben plantejat, pot proporcionar un avantatge a les empreses que tenen una part important del seu negoci basada en el transport. Un exemple és l’observació que rutes amb molts girs a l’esquerra acostumen a ser molt més lentes tot i ser més curtes que altres rutes que “fan més tomb” però que arriben abans. Així doncs, l’optimització de les rutes complint amb aquest criteri pot permetre entregar més productes, reduir l’ús de combustible i fins i tot reduir les emissions de CO₂ (notícia).

La planificació de rutes es pot aplicar en diversos àmbits, com per exemple: el repartiment de paquets a domicili, la recollida de les escombraries, les rutes d’autobusos, visites comercials a clients o per fer la planificació de vols de supervisió de diverses zones mitjançant drons.

L’optimització del problema de l'assignació de rutes de vehicles és una aplicació que pot suposar importants estalvis per a l’empresa. A escala europea, el transport representa un 5% del producte interior brut (font), fet que implica que petites millores en aquest aspecte tinguin un gran impacte tant econòmic com mediambiental. 

PS: Una planificació encara millor són les rutes 3-4-5-6 i 1-7-2 amb una distància total de 34 unitats. I no és l'única solució!