To access the full text documents, please follow this link: http://hdl.handle.net/2099.1/9294

ATSP EDU. Una eina de visualització, per la resolució de problemes de rutes
Garcia Bosch, Jordi
Universitat Politècnica de Catalunya. Departament d’Estadística i Investigació Operativa; Fernández Aréizaga, Elena
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.
Àrees temàtiques de la UPC::Matemàtiques i estadística::Investigació operativa::Programació matemàtica
Traveling-salesman problem
ATSP
TSP
Asymmetric Traveling Salesman
Programació matemàtica
Problema del viatjant de comerç
Classificació AMS::90 Operations research, mathematical programming
Attribution-NonCommercial-ShareAlike 3.0 Spain
http://creativecommons.org/licenses/by-nc-sa/3.0/es/
info:eu-repo/semantics/bachelorThesis
Universitat Politècnica de Catalunya
         

Show full item record

 

Coordination

 

Supporters