dc.contributor |
Universitat Politècnica de Catalunya. Departament d'Estadística i Investigació Operativa |
dc.contributor |
Fernández Aréizaga, Elena |
dc.contributor.author |
Garcia Bosch, Jordi |
dc.date |
2009-11 |
dc.identifier.uri |
http://hdl.handle.net/2099.1/9294 |
dc.language.iso |
cat |
dc.publisher |
Universitat Politècnica de Catalunya |
dc.rights |
Attribution-NonCommercial-ShareAlike 3.0 Spain |
dc.rights |
info:eu-repo/semantics/openAccess |
dc.rights |
http://creativecommons.org/licenses/by-nc-sa/3.0/es/ |
dc.subject |
Àrees temàtiques de la UPC::Matemàtiques i estadística::Investigació operativa::Programació matemàtica |
dc.subject |
Traveling-salesman problem |
dc.subject |
ATSP |
dc.subject |
TSP |
dc.subject |
Asymmetric Traveling Salesman |
dc.subject |
Programació matemàtica |
dc.subject |
Problema del viatjant de comerç |
dc.subject |
Classificació AMS::90 Operations research, mathematical programming |
dc.title |
ATSP EDU. Una eina de visualització, per la resolució de problemes de rutes |
dc.type |
info:eu-repo/semantics/bachelorThesis |
dc.description.abstract |
Aquest projecte és una eina pedagògica per explicar conceptes de programació matemàtica des d'una vessant pràctica. Partim del problema del viatjant de comerç asimètric, del qual hem descrit i comentat diverses formulacions. Hem escollit la formulació de C. E. Miller, A. W. Tuker, i R. A. Zemlin, posteriorment millorada per M. Desrochers, i G. Laporte (DL). L'hem resolt mitjançant el mètode subgradient aplicat a la relaxació Lagrangiana de les constriccions proposades per DL. Hem expressat el problema com la suma de dos subproblemes independents més una constant. Un dels subproblemes l'hem resolt de forma directa i l'altre hem utilitzat el mètode del Simplex.
Hem implementat l'ATSP EDU amb el llenguatge de programació Java i ens hem ajudat de la llibreria de funcions GLPK per implementar parts de la formulació i la resolució. Degut a la complexitat de l'algoritme hem desenvolupat un prototipus de la formulació i el mètode de resolució utilitzant el llenguatge modelització matemàtica AMPL i el resolutor CPLEX. Per determinar les característiques de l'aplicació hem fet un disseny previ. Hem fet servir jocs de dades de diferents dimensions per testar l'aplicació i el prototipus. Per acabar, hem fet una descripció del funcionament de l'aplicació a nivell d'usuari, un anàlisi dels resultats que genera ATSP EDU, i una relació de possibles ampliacions futures. |