dc.contributor |
Universitat Politècnica de Catalunya. Departament d'Organització d'Empreses |
dc.contributor |
Coves Moreno, Anna Maria |
dc.contributor.author |
Bellés Roca, Andreu |
dc.date |
2012-04 |
dc.identifier.uri |
http://hdl.handle.net/2099.1/15388 |
dc.language.iso |
cat |
dc.publisher |
Universitat Politècnica de Catalunya |
dc.rights |
info:eu-repo/semantics/openAccess |
dc.title |
Disseny d'algorismes heurístics per a la programació de la producció i la distribució de formigó |
dc.type |
info:eu-repo/semantics/bachelorThesis |
dc.description.abstract |
L’objectiu d’aquest projecte és el de dissenyar algorismes heurístics per a programar la
producció i la distribució del formigó i que siguin eficaços per a casos reals. S’han dissenyat
algorismes heurístics per resoldre eficaçment la programació diària de les producció i la
distribució de formigó des de les plantes on es fabrica fins a les obres on es lliura. Degut a
que el problema és NP-Hard [1] convé dissenyar algorismes heurístics pel cas en què el
temps de resolució per altres mètodes exactes siguin excessius. Els algorismes dissenyats
estan basats en MS (Multi-Start) i VNS (Variable Neighborhood Search) i s'han validat amb
exemplars aleatoris basats en les comandes diàries facilitades per una empresa del sector.
L’algorisme basat en MS (anomenat MS_SIM) ha donat molt bons resultats mentre que el
basat en VNS (VNS_SIM) no ha estat tan satisfactori aplicat de forma independent. S’han
dissenyat altres algorismes que són una barreja dels dos anteriors en diferents proporcions
de temps dedicat a cadascun d‘ells, com per exemple l’algorisme anomenat MIX_SIM_1.
Aquest algorisme dedica la primera meitat del temps d’execució al MS i la segona meitat del
temps al VNS. De tots aquests algorismes mixtes el millor ha estat el MIX_SIM_2, que
destina un 80% del temps a MS i un 20% a VNS. Finalment s’ha optat per integrar el VNS
dins del MS de manera que el VNS realitza una optimització local de cada solució obtinguda
amb el MS donant lloc així a un algorisme híbrid anomenat HÍBRID_SIM. El resultat d’aquest
últim ha estat semblant al del MIX_SIM_2. El temps d’execució dels algorismes dissenyats
ha estat satisfactori per als exemplars creats en base a dades reals.
S’ha comprovat l’eficàcia dels algorismes amb altres exemplars semblants resolts amb altres
mètodes com ara el proposat per Fenoy [2] basat en propagació de restriccions (CLP,
Constraint Logic Programming). S’ha realitzat una comparativa dels resultats obtinguts per a
exemplars idèntics. Els resultats de la comparativa han estat molt satisfactoris |