Optimització del transport dels centres d'educació especial de Barcelona

El Consorci d'Educació de Barcelona proveeix als Centres d'Educació Especial d'un servei de transport escolar per ajudar a les famílies dels alumnes d'aquests centres. Actualment, la gestió d'aquest servei està descentralitzada, de manera que els centres que se'n beneficien s'encarreguen de gestionar-lo. Això fa que els centres no comparteixin vehicles, cosa que, en cas de fer-ho, podria augmentar la qualitat del servei ofert i el nombre d'estudiants beneficiats. A més, les rutes que es duen a terme actualment es creen de forma manual, aprofitant les rutes de l'any anterior, eliminant els alumnes que ja no assisteixen a l'escola, i afegint els que la comencen. El problema al qual fem front és una versió del problema d'optimització combinatori Vehicle Routing Problem (VRP), que és una generalització del conegut Problema del Viatjant de Comerç (TSP). De fet, donat que el que es transporta són persones, sovint es parla del Dial-a-Ride Problem, que és una extensió del VRP que té en compte aspectes particulars del transport de persones. En aquest cas, a més, es tracten bastants extensions del problema, com per exemple el de la flota heterogènia o restriccions sobre la compartició de vehicles entre certs alumnes. Aquesta classe de problemes són NP-Hard en les versions d'optimització, de manera que l'ús de mètodes exactes no és factible a l'hora de tractar instàncies de dimensions realistes. Per aquest motiu, en aquest Treball de Fi de Grau, realitzat en el marc d'un conveni de col·laboració amb l'inLab FIB, es realitza un estudi sobre la viabilitat d'aplicar algorismes de routing amb l'objectiu de millorar el servei proporcionat pel Consorci. Per a fer-ho, es presenta una formalització del problema, amb un model de programació lineal entera, i una metaheurística basada en Deterministic Annealing per a poder tractar instàncies realistes. A més, s'exploren diversos escenaris variant alguns dels paràmetres, tot observant com això afecta el cost i a la qualitat de la solució
The Barcelona Education Consortium provides the Special Education Centers with a school transport service to help the families of the students at these centers. Currently, the management of this service is decentralized, meaning that the centers that benefit from it are in charge of managing it. This means that the centers do not share vehicles, which, if done, could increase both the quality of the service offered and the number of students who benefit from it. In addition, the routes that are currently being carried out are created manually, taking advantage of the routes of the previous year, removing the students who no longer attend school, and adding those who start to. The problem we face is a version of the Vehicle Routing Problem (VRP), which is a generalization of the well-known Travelling Salesman Problem (TSP). In fact, since what is transported are people, we are actually facing a version of the Dial-a-Ride Problem, which is an extension of the VRP that takes into account particular aspects of transporting people. In addition, in this case we have to deal with many extensions of the problem, such as the heterogeneous fleet or restrictions on the sharing of vehicles between certain students. This kind of problems are NP-Hard in the optimization versions, so the use of exact methods is not feasible when dealing with instances of realistic dimensions. For this reason, in this Final Degree Project, carried out within the framework of a collaboration agreement with the inLab FIB, a study is carried out on the feasibility of applying routing algorithms with the aim to improve the service provided by the Consortium. To do this, a formalization of the problem, with an integer linear programming model, and a metaheuristic based on Deterministic Annealing to be able to deal with realistic instances are presented. In addition, various scenarios are explored varying some of the parameters, observing how this affects the cost and quality of the solution obtained. To