Optimització de l'assignació d'activitats extraescolars i del transport escolar mitjançant heurístiques

Abstract

Aquest treball aborda el problema de l’assignació d’activitats extraescolars i la gestió del transport escolar dins d’una xarxa d’escoles col·laboradores. L’objectiu principal és maximitzar el nombre d’alumnes que poden participar en activitats extraescolars i reduir la demanda no satisfeta, tot respectant les restriccions de capacitat de les activitats, la disponibilitat de les instal·lacions i les limitacions del transport entre centres. Per afrontar aquest problema, es planteja un enfocament basat en mètodes heurístics i metaheurístics, capaços de gestionar la complexitat del sistema de manera eficient. En primer lloc, es desenvolupa una heurística constructiva que permet generar una solució inicial mitjançant l’assignació progressiva dels alumnes a les activitats i la planificació dels desplaçaments, tant a peu com amb transport escolar. Posteriorment, aquesta solució es millora mitjançant una metaheurística de tipus Large Neighborhood Search (LNS), que permet explorar de manera més eficient l’espai de solucions i millorar la qualitat dels resultats obtinguts. El model considera diferents grups d’edat, activitats amb capacitats mínimes i màximes, la compatibilitat amb les instal·lacions disponibles i les restriccions operatives associades als desplaçaments. Els resultats obtinguts mostren que la combinació de l’heurística constructiva amb la metaheurística LNS permet obtenir solucions de bona qualitat en termes de demanda satisfeta i de beneficis econòmics, amb temps de càlcul molt bons. Finalment, els resultats obtinguts amb l’enfocament heurístic i metaheurístic proposat es comparen amb els resultats corresponents al mateix problema resolt mitjançant un model de programació lineal entera mixta (MILP). D’aquesta comparativa s’extreu la conclusió que l’enfocament heurístic i metaheurístic proposat obté millors resultats en termes de demanda satisfeta, mantenint alhora un menor cost computacional, en comparació amb la resolució del mateix problema mitjançant un model de programació lineal entera mixta (MILP).