{"id":26890,"date":"2023-11-01T12:09:42","date_gmt":"2023-11-01T11:09:42","guid":{"rendered":"https:\/\/cio.umh.es\/?p=26890"},"modified":"2024-02-20T12:10:37","modified_gmt":"2024-02-20T11:10:37","slug":"mercedes-landete-isaac-plana-jose-luis-sainz-pardo-jose-maria-sanchis-2023-upgrading-edges-in-the-graphical-tsp-computers-operations-research-159-106321","status":"publish","type":"post","link":"https:\/\/cio.umh.es\/en\/2023\/11\/01\/mercedes-landete-isaac-plana-jose-luis-sainz-pardo-jose-maria-sanchis-2023-upgrading-edges-in-the-graphical-tsp-computers-operations-research-159-106321\/","title":{"rendered":"Mercedes Landete, Isaac Plana, Jos\u00e9 Luis Sainz-Pardo, &amp; Jos\u00e9 Mar\u00eda Sanchis (2023). Upgrading edges in the Graphical TSP. Computers &amp; Operations Research, 159, 106321."},"content":{"rendered":"<p><strong>Mercedes Landete (Departamento de Estad\u00edstica, Matem\u00e1ticas e Inform\u00e1tica, Universidad Miguel Hern\u00e1ndez), Isaac Plana (Departamento de Matem\u00e1ticas para la Econom\u00eda y la Empresa, Universidad de Valencia), Jos\u00e9 Luis Sainz-Pardo (Departamento de Estad\u00edstica, Matem\u00e1ticas e Inform\u00e1tica, Universidad Miguel Hern\u00e1ndez) and Jos\u00e9 Mar\u00eda Sanchis (Departamento de Matem\u00e1tica Aplicada, Universidad Polit\u00e9cnica de Valencia)<\/strong><\/p>\n<p><strong>Abstract:<\/strong><\/p>\n<p>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.<\/p>","protected":false},"excerpt":{"rendered":"<p>Mercedes Landete (Departamento de Estad\u00edstica, Matem\u00e1ticas e Inform\u00e1tica, Universidad Miguel Hern\u00e1ndez), Isaac Plana (Departamento de Matem\u00e1ticas para la Econom\u00eda y la Empresa, Universidad de Valencia), Jos\u00e9 Luis Sainz-Pardo (Departamento de Estad\u00edstica, Matem\u00e1ticas e Inform\u00e1tica, Universidad Miguel Hern\u00e1ndez) and Jos\u00e9 Mar\u00eda Sanchis (Departamento de Matem\u00e1tica Aplicada, Universidad Polit\u00e9cnica de Valencia)<br \/>\nAbstract:<br \/>\nIn this paper we present a generalization [&#8230;]<\/p>","protected":false},"author":11048,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_links_to":"","_links_to_target":""},"categories":[369888,75,7834],"tags":[378950,384832],"_links":{"self":[{"href":"https:\/\/cio.umh.es\/en\/wp-json\/wp\/v2\/posts\/26890"}],"collection":[{"href":"https:\/\/cio.umh.es\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/cio.umh.es\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/cio.umh.es\/en\/wp-json\/wp\/v2\/users\/11048"}],"replies":[{"embeddable":true,"href":"https:\/\/cio.umh.es\/en\/wp-json\/wp\/v2\/comments?post=26890"}],"version-history":[{"count":0,"href":"https:\/\/cio.umh.es\/en\/wp-json\/wp\/v2\/posts\/26890\/revisions"}],"wp:attachment":[{"href":"https:\/\/cio.umh.es\/en\/wp-json\/wp\/v2\/media?parent=26890"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/cio.umh.es\/en\/wp-json\/wp\/v2\/categories?post=26890"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/cio.umh.es\/en\/wp-json\/wp\/v2\/tags?post=26890"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}