Mostrar el registro sencillo del ítem
dc.contributor.author | Landete, Mercedes![]() |
es_ES |
dc.contributor.author | Plana, Isaac![]() |
es_ES |
dc.contributor.author | Sainz-Pardo, José Luis![]() |
es_ES |
dc.contributor.author | Sanchís Llopis, José María![]() |
es_ES |
dc.date.accessioned | 2024-04-11T06:28:29Z | |
dc.date.available | 2024-04-11T06:28:29Z | |
dc.date.issued | 2023-11 | es_ES |
dc.identifier.issn | 0305-0548 | es_ES |
dc.identifier.uri | http://hdl.handle.net/10251/203287 | |
dc.description.abstract | [EN] In this paper we present a generalization of the Graphical Traveling Salesman Problem (GTSP). Given a communication graph in which not all direct connections are necessarily possible, the Graphical Traveling Salesman Problem consists of finding the shortest tour that visits each node at least once. In this work, we assume the availability of a budget that allows to upgrade, i.e. reduce their traversal cost, some of the current connections and we propose the problem of designing the minimum cost tour using this budget. We propose and study a formulation for the problem, verifying that the polyhedron associated with the set of feasible solutions of a relaxed version of the problem is a full-dimensional polytope. We present families of valid inequalities that reinforce the model and pre-processing techniques to reduce the number of variables of the formulation. To solve the problem, we propose a branch-and-cut algorithm that uses the introduced valid inequalities, as well as a heuristic to obtain good upper bounds and a tailor-made branching strategy. Comprehensive computational experiments on a new set of benchmark instances are presented to assess the performance of this exact method. | es_ES |
dc.description.sponsorship | This work was supported by Generalitat Valenciana, Spain through project CIGE/2021/161 and by grant PID2021-122344NB-I00 funded by MCIN/AEI/10.13039/501100011033 and "ERDF A way of making Europe". | es_ES |
dc.language | Inglés | es_ES |
dc.publisher | Elsevier | es_ES |
dc.relation.ispartof | Computers & Operations Research | es_ES |
dc.rights | Reconocimiento - No comercial - Sin obra derivada (by-nc-nd) | es_ES |
dc.subject | GTSP | es_ES |
dc.subject | Edge upgrading | es_ES |
dc.subject | Branch-and-cut | es_ES |
dc.subject.classification | MATEMATICA APLICADA | es_ES |
dc.title | Upgrading edges in the Graphical TSP | es_ES |
dc.type | Artículo | es_ES |
dc.identifier.doi | 10.1016/j.cor.2023.106321 | es_ES |
dc.relation.projectID | info:eu-repo/grantAgreement/AEI/Plan Estatal de Investigación Científica y Técnica y de Innovación 2021-2023/PID2021-122344NB-I00/ES/NUEVAS TENDENCIAS EN OPTIMIZACION COMBINATORIA PARA LA GESTION DE RECURSOS Y DATOS/ | es_ES |
dc.relation.projectID | info:eu-repo/grantAgreement/GVA//CIGE%2F2021%2F161/ | es_ES |
dc.relation.projectID | info:eu-repo/grantAgreement/MICINN//PID2021-122344NB-I00 //NUEVAS TENDENCIAS EN OPTIMIZACION COMBINATORIA PARA LA GESTION DE RECURSOS Y DATOS/ | es_ES |
dc.rights.accessRights | Abierto | es_ES |
dc.contributor.affiliation | Universitat Politècnica de València. Escuela Técnica Superior de Ingenieros Industriales - Escola Tècnica Superior d'Enginyers Industrials | es_ES |
dc.description.bibliographicCitation | Landete, M.; Plana, I.; Sainz-Pardo, JL.; Sanchís Llopis, JM. (2023). Upgrading edges in the Graphical TSP. Computers & Operations Research. 159:1-15. https://doi.org/10.1016/j.cor.2023.106321 | es_ES |
dc.description.accrualMethod | S | es_ES |
dc.relation.publisherversion | https://doi.org/10.1016/j.cor.2023.106321 | es_ES |
dc.description.upvformatpinicio | 1 | es_ES |
dc.description.upvformatpfin | 15 | es_ES |
dc.type.version | info:eu-repo/semantics/publishedVersion | es_ES |
dc.description.volume | 159 | es_ES |
dc.relation.pasarela | S\510583 | es_ES |
dc.contributor.funder | Generalitat Valenciana | es_ES |
dc.contributor.funder | European Regional Development Fund | es_ES |
dc.contributor.funder | Ministerio de Ciencia e Innovación | es_ES |