Diari de recerca | Tecnologia i enginyeria

La Investigació Operativa és una branca de les matemàtiques relativament recent. Pertany al que anomenem “matemàtica aplicada” i es dedica a resoldre problemes d’optimització, és a dir, problemes on s’ha d’extreure el màxim rendiment a uns recursos limitats.
Al missatge d’avui ens acompanya en Francesc López que està realitzant un doctorat al departament d’Estadística i Investigació Operativa de la UPC. Allà desenvolupa un nou algorisme per al disseny de xarxes de transport més eficients.
Com ell mateix ens explica, es tracta d’un problema complex que no sempre es treballa com un tot. Així, el més habitual és seguir l’esquema de 4 passos que van proposar de Ceder i Wilson el 1986:

1. Dissenyar primer el traçat de les línies de metro, tramvia i bus i ubicar les parades.
2. Després, decidir la freqüència de pas que tindrà cada línia.
3. A continuació, assignar els vehicles disponibles  (amb diferents capacitats i característiques) a cada línia.
4. Finalment, assignar el personal necessari a cada vehicle.

Cadascun d’aquests problemes té una naturalesa diferent. Així, en el primer cas s’ha d’assegurar que tothom tingui transport públic prop de casa i que ningú no faci massa volta per anar d’un lloc a un altre. En el segon cas, importen més els fluxos de persones que ha de moure el sistema (sabem per on passarà la gent i ens hem d’assegurar de que no es creïn embussos. El tercer pas consisteix en assignar uns recursos limitats (els vehicles) de la manera més eficient possible, mentre que en el darrer pas el problema rau en distribuir operaris complint la normativa amb el menor cost possible (fent les aturades de seguretat pertinents, assignant els operaris més qualificats a les tasques més difícils, reduint el nombre de desplaçaments innecessaris i les hores extra que fa cada empleat…).

Paquets de Software com AINSUM ha fet servir aquests models per facilitat la planificació urbana de ciutats com Saragossa o Barcelona.
Malgrat que cada problema s’acostuma a resoldre per separat i que són de tipus molt diferents (cadascun d’ells tracta d’optimitzar un factor diferent) la veritat és que les 4 fases estan molt interrelacionades i l’ideal seria comptar amb un model únic que les tingui en compte a totes. Malauradament un model matemàtic com aquest es torna totalment impracticable fins i tot per la ciutat més petita.
Un primer pas cap al model total
La investigació d’en Francesc està centrada en integrar la resolució dels dos primers problemes en un únic model i fer servir algorismes propis de la investigació operativa per resoldre’l.
Així, el nou model tindrà en compte no només els possibles traçats i les possibles parades que pot tenir cada línia sinó també la freqüència de pas i el flux de persones que es desplacen sobre elles. Amb el nou model és possible que es puguin descobrir noves solucions que abans quedaven eliminades en el primer pas. Així, potser abans es feia servir una línia de metro on era més adient fer servir dos d’autobusos o potser serà millor bifurcar una línia de tramvia a mig recorregut que tenir-ne dos.
Però no tot són avantatges per al nou model, detectar aquestes solucions alternatives més eficients té un cost addicional: el model és més complex i té en compte més factors, així que no es pot aplicar als mateixos casos que abans sense trobar algorismes més eficients de resolució. Sobre aquests algorismes i la seva relació amb l’àlgebra lineal parlarem el proper dia amb en Francesc.
MMACA, Museu de Matemàtiques de Catalunya