Helena Ramalhinho, professora del Departament d’Economia i Empresa de la UPF, es troba entre els autors del treball “An ILS-based algorithm to solve a large-scale real heterogeneous fleet VRP with multi-trips and docking constraints”, publicat recentment a la revista European Journal of Operational Research, una revista líder d'aquesta àrea, en el qual es proposa un mètode per facilitar la presa de decisions i optimitzar la planificació de la distribució de mercaderies d’una empresa de grans dimensions.

L'estudi que ha portat a terme Helena Ramalhinho , investigadora del Grup de Recerca BARG (Business, Analytics Research Group) de la UPF, conjuntament amb altres investigadors de les Universitats Federals d’Ouro Preto i Fluminense de Brasil, i d’EADA Business School de Barcelona, es basa en un cas real d’una empresa catalana, que compta amb més de 400 punts de lliurament de mercaderies, dispersos geogràficament.

La resolució d’aquest problema de ruteig de vehicles (Vehicle Routing Problems, VRP, en anglès) és extremadament complex, ja que considera una flota de vehicles heterogènia (amb diferents capacitats i costos), la possibilitat de diverses rutes per a un mateix vehicle, així com problemes de càrrega o de restriccions de connexió, entre d’altres variables.

L’objectiu d’aquest mètode és minimitzar el cost total del procés de distribució per part de l’empresa, compost per un cost fix per a l’ús de cada vehicle i per cada client visitat, i un cost variable per vehicle, en funció de la distància recorreguda. També es pretén optimitzar el nombre total de rutes utilitzades, la distància total recorreguda i la capacitat productiva no utilitzada de la flota de vehicles.

Un algoritme que permet l’estalvi de diners i les millors opcions de ruta

Per incorporar i processar tot aquest conjunt de paràmetres, la recerca utilitza un mètode heurístic basat en algoritmes matemàtics, anomenat GILS-VND, que inclou la combinació de tres procediments diferents, entre els quals una de les tècniques més punteres existents per a fer aquests càlculs, l’Iterated Local Search (ILS).

Per provar el rendiment de l’algoritme, els autors de la recerca van experimentar amb un conjunt de casos reals proporcionats per l’empresa, corresponent a totes les demandes fetes pels clients durant quinze dies hàbils. Els resultats van aconseguir una reducció del cost significatiu per a l’empresa (amb una estimació d’estalvi anual al voltant de 70.000 euros) i millors indicadors, tant pel que fa al nombre de rutes utilitzades, la distància total recorreguda i la capacitat productiva no utilitzada dels vehicles.

A més de minimitzar notablement els costos, una altra avantatge de l’algoritme és la seva velocitat i fiabilitat, ja que va ser capaç de trobar bones solucions en un temps reduït. Aquest fet és important, si es té en compte que les decisions de rutatge de la flota de vehicles de l’empresa s’han de fer diàriament, després de rebre totes les demandes dels clients, en menys de 30 minuts.

Aquesta recerca, que considera la possibilitat de contemplar en un futur períodes de temps en què no sigui possible fer els lliuraments de les mercaderies (degut a aspectes com ara les restriccions de trànsit, per exemple), ha estat parcialment finançada pel Conselho Nacional de Desenvolvimiento Científico e Tecnológico (CNPq) i el Coordenação de Aperfeiçoamento de Pessoal de Nivel Superio (CAPES), ambdós organismes del Brasil, pels programes Ciencia Sin Fronteras i Programa Iberoamericano de Ciencia, Tecnología y Desarrollo i pel Ministeri d’Economia i Competitivitat d’Espanya.

Treball de referència: V.N. Coelho, A. Grasas, H. Ramalhinho, I.M. Coelho, M.J.F. Souza i R.C. Cruz. An ILS-based algorithm to solve a large-scale real heterogeneous fleet VRP with multi-trips and docking constraints. European Journal of Operational Research, doi:10.1016/j.ejor.2015.09.047, setembre 2015.