Hybrid algorithms for solving routing problems

• Autores: Daniel Guimarans Serrano
• Directores de la Tesis: Juan José Ramos González (dir. tes.) , Daniel Riera i Terrén (dir. tes.)
• Lectura: En la Universitat Autònoma de Barcelona ( España ) en 2012
• Idioma: inglés
• Tribunal Calificador de la Tesis: Miquel Àngel Piera i Eroles (presid.) , Marco Gavanelli (secret.) , Patrick Hirsch (voc.)
• Enlaces
  • Tesis en acceso abierto en:  TDX  DDD  TESEO 
• Resumen

  • Un component important de molts sistemes de distribució és el càlcul de les rutes dels vehicles per servir els clients. El Vehicle Routing Problem (VRP) proporciona el marc teòric per tractar aquest tipus de problemes logístics relacionats amb la distribució física de béns. Per la seva complexitat i aplicabilitat, aquest tipus de problemes logístics es troba entre les línies de recerca més populars en optimització combinatòria. Aquesta tesi de doctorat té com a objectiu la introducció de tres metodologies diferents per resoldre el VRP. Aquestes metodologies han estat especialment dissenyades per ser flexibles, en el sentit que poden ser utilitzades, amb adaptacions menors, per resoldre diferents variants del VRP presents en casos d’aplicació industrial. En les tres metodologies descrites en aquest treball s’utilitzen diferents tècniques per aconseguir la flexibilitat, l’eficiència i la robustesa desitjades. Constraint Programming (CP) ha estat escollit com a paradigma de modelat per descriure les principals restriccions presents en el VRP. CP proporciona la flexibilitat desitjada per les tres metodologies, atès que afegir restriccions addicionals presents en molts casos d’aplicació real només afecta al modelat del problema, però no a la definició dels algorismes de cerca. En les dues primeres metodologies descrites, el model de CP només s’utilitza per comprovar la factibilitat de les solucions durant la cerca. La tercera metodologia presenta un model més ric del VRP que permet tractar diferents variants del problema. En aquest cas, la cerca es realitza i es controla fent servir els mecanismes que CP proporciona. La Relaxació Lagrangiana (LR) i una versió probabilística de l’heurística Clarke and Wright Savings (RCWS) s’utilitzen amb una finalitat molt específica dins de les metodologies. LR s’utilitza per minimitzar la distància total recorreguda pels vehicles, mentre que la RCWS es fa servir per calcular una solució inicial de bona qualitat. Ambdós mètodes proporcionen una aproximació eficient als problemes respectius. A més, la utilització de LR permet reduir la complexitat computacional dels processos de cerca local i, d’aquesta manera, redueix el temps computacional necessari per resoldre el VRP. Totes les metodologies es basen en la metaheurística coneguda com Variable Neighborhood Search (VNS). El VNS està format per una família d’algorismes que aprofiten sistemàticament la idea de canviar el veïnat explorat al voltant d’una solució, tant en el procés de cerca per trobar un mínim local com en el procés de pertorbació, per escapar de la vall corresponent. Malgrat que és un mètode bastant estès, hi ha pocs exemples d’aplicació en el VRP. En tot cas, fins i tot els mètodes VNS més simples han aconseguit bons resultats quan han estat aplicats en aquest problema. Aquesta tesi té com a objectiu contribuir en la recerca de l’aplicació de la metaheurística VNS en el VRP. Aquesta ha estat escollida com a marc en el que integrar les tècniques mencionades. Així, la metaheurística s’utilitza per guiar la cerca, mentre que l’eficiència desitjada s’aconsegueix mitjançant els mètodes que s’hi integren. D’altra banda, utilitzar CP com a paradigma de modelat proporciona la flexibilitat requerida. Aquesta característica és especialment rellevant en el cas de la darrera metodologia descrita. En aquest cas, la cerca de CP es guia mitjançant una combinació de les metaheurístiques VNS i Large Neighborhood Search (LNS). Aquesta metodologia representa una primera aproximació a la resolució eficient de problemes VRP més complexos, similars a casos d’aplicació real.