Societat de la Informació i el Coneixement

Randomized Algorithms for Rich Vehicle Routing Problems: From a Specialized Approach to a Generic Methodology

Doctorat de Societat de la Informació i el Coneixement
22/11/2013

Autor: José de Jesús Cáceres Cruz
Programa: Doctorat de Societat de la Informació i el Coneixement
Idioma: anglès
Director: Dr. Ángel Alejandro Juan Pérez
Departament / Institut: Internet Interdisciplinary Institute (IN3), Departament d'Informàtica, Multimèdia i Telecomunicació
Matèries: Informàtica, Anàlisi, Teoria general de l'anàlisi combinatòria, Teoria de grafs, Enginyeria, Tecnologia, Enginyeria del transport terrestre, Enginyeria dels vehicles de transport
Paraules clau: Problemes enriquits de rutes de vehicles, Heurístiques aleatòries i esbiaixades, Metaheurístiques, Aplicacions reals, Optimització, Logística
Àrea de coneixement: Ciència de la Computació i Intel·ligència Artificial

+ Enllaç al projecte

Resum

El problema de rutes de vehicles (VRP) i les seves diferents variants bàsiques són un domini àmpliament estudiat en la comunitat científica d'optimització. Alguns estudis han usat combinacions específiques de restriccions trobades a la vida real per a definir els emergents VRP enriquits. Aquest treball aborda la integració d'heurístiques, probabilitat esbiaixada, simulació, tècniques de computació distribuïda i paral·lela, i programació amb restriccions. Els enfocaments proposats han solucionat algunes variants del VRP: en primer lloc, les famílies deterministes, com VRP amb flotes heterogènies (HVRP), VRP amb flotes heterogènies i cost variable (HVRP-V), VRP amb flota heterogènia i múltiples viatges (HVRPM), VRP amb matriu de cost asimètrica (AVRP), VRP amb flota heterogènia i matriu de cost asimètrica (HAVRP), VRP amb finestres de temps (VRPTW) i VRP amb distància limitada (DCVRP); en segon lloc, les famílies de naturalesa estocàstica, com VRP amb demandes estocàstiques (VRPSD), i problemes d'inventari i rutes de vehicles amb demandes estocàstiques (IRPSD). D'altra banda, s'ha dut a terme una extensa revisió bibliogràfica per a cadascuna d'aquestes variants. Un primer enfocament proposa la combinació d'una aleatorització esbiaixada amb heurístiques clàssiques per a solucionar problemes deterministes. Un segon enfocament centra l'atenció en la combinació d'heurístiques aleatòries amb simulació (simheuristics) per a aplicar-ho en els problemes estocàstics comentats. Finalment, es proposa un tercer enfocament basat en el treball conjunt d'heurístiques aleatòries amb programació de restriccions per a resoldre diferents tipus de problemes de rutes. Els algorismes heurístics desenvolupats s'han aplicat en diferents casos de referència –entre els quals hi ha dos estudis de casos reals de distribució a Espanya– i els resultats obtinguts són, en general, prometedors i útils per als decisors.