Publicación:
ACCELERATING THE MILLER-TUCKER-ZEMLIN MODEL FOR THE ASYMMETRIC TRAVELING SALESMAN PROBLEM

Vista sencilla de ítem
dc.creatorGIOVANNI FRANCISCO CAMPUZANO ARROYO
dc.creatorCARLOS ENRIQUE OBREQUE NÍÑEZ
dc.date2020
dc.date.accessioned2025-01-10T15:14:00Z
dc.date.available2025-01-10T15:14:00Z
dc.date.issued2020
dc.description.abstractIN THIS ARTICLE, WE PRESENT AN EASY TO IMPLEMENT ALGORITHMIC APPROACH THAT IMPROVES THE COMPUTATIONAL PERFORMANCE OF THE MILLER?TUCKER?ZEMLIN (MTZ) MODEL FOR THE ASYMMETRIC TRAVELING SALESMAN PROBLEM (ATSP) BY EFFICIENTLY GENERATING VALID INEQUALITIES FROM FRACTIONAL SOLUTIONS. COMPUTATIONAL EXPERIMENTS SHOW THAT THE PROPOSED APPROACH ENHANCES CONSIDERABLY THE PERFORMANCE OF MTZ-BASED FORMULATIONS REPORTED IN THE LITERATURE. BY ADDING FACET-DEFINING INEQUALITIES OF THE UNDERLINE ATSP-POLYTOPE, THE NUMBER OF NODES IN THE BRANCH-AND-BOUND TREE IS DRASTICALLY REDUCED, AND THE CONVERGENCE OF THE MTZ-TYPE FORMULATIONS IS ACCELERATED. WE ALSO EXTEND THIS IDEA TO SOLVE THE MULTIPLE ASYMMETRIC TRAVELING SALESMAN PROBLEM (MATSP). THIS APPROACH CAN HELP PRACTITIONERS TO SOLVE REAL-LIFE PROBLEMS TO NEAR OPTIMALITY USING A STANDARD OPTIMIZATION SOLVER AND MAY BE USEFUL TO SOLVE A VARIETY OF ROUTING PROBLEMS THAT USE MTZ-TYPE OF SUBTOUR ELIMINATION CONSTRAINTS.
dc.formatapplication/pdf
dc.identifier.doi10.1016/j.eswa.2020.113229
dc.identifier.issn1873-6793
dc.identifier.issn0957-4174
dc.identifier.urihttps://repositorio.ubiobio.cl/handle/123456789/11042
dc.languagespa
dc.publisherEXPERT SYSTEMS WITH APPLICATIONS
dc.relation.uri10.1016/j.eswa.2020.113229
dc.rightsPUBLICADA
dc.titleACCELERATING THE MILLER-TUCKER-ZEMLIN MODEL FOR THE ASYMMETRIC TRAVELING SALESMAN PROBLEM
dc.title.alternativeACELERACIÓN DEL MODELO MILLER-TUCKER-ZEMLIN PARA EL PROBLEMA ASIMÉTRICO DEL VENDEDOR AMBULANTE
dc.typeARTÍCULO
dspace.entity.typePublication
ubb.EstadoPUBLICADA
ubb.Otra ReparticionDEPARTAMENTO DE INGENIERIA INDUSTRIAL
ubb.SedeCONCEPCIÓN
ubb.SedeCONCEPCIÓN
Archivos
Colecciones
Artículos científicos