Pasar al contenido principal

Resultados relacionados

Resultados totales (Incluyendo duplicados): 6
Encontrada(s) 1 página(s)

RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Min-Max K-vehicles Windy Rural Postman Problem

  • Benavent López, Enrique
  • Corberan, Angel
  • Plana, Isaac
  • Sanchís Llopis, José María|||0000-0002-0039-8122
[EN] In this article the Min-Max version of the windy rural postman problem with several vehicles is introduced. For this problem, in which the objective is to minimize the length of the longest tour in order to find a set of balanced tours for the vehicles, we present here an ILP formulation and study its associated polyhedron. Based on its partial description, a branch-and-cut algorithm has been implemented and computational results on a large set of instances are finally presented. (C) 2009 Wiley Periodicals, Inc. NETWORKS, Vol. 54(4),216-226 2009, Contract grant sponsor: Ministerio de Education y Ciencia of Spain: Contract gram number: MTM2006-14961-C05-02
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

A metaheuristic for the min-max Windy Rural Postman Problem with K vehicles

  • Benavent, Enrique
  • Corberán, Angel
  • Sanchís Llopis, José María
[EN] In this paper we deal with the min¿max version of the windy rural postman problem with K vehicles. For this problem, in which the objective is to minimize the length of the longest tour in order to find a set of balanced tours for the vehicles, we present here a metaheuristic that produces very good feasible solutions in reasonable computing times. It is based on the combination of a multi-start procedure with an Iterated Local Search. Extensive computational results on a large set of instances with up to 50 vertices, 184 edges and 5 vehicles are presented. The results are very good, the average gaps with respect to a known lower bound are less than 0.40% for instances with 2 or 3 vehicles and up to 1.60% when 4 or 5 vehicles are considered., Authors wish to thank the Ministerio de Educación y Ciencia of Spain (projects MTM2006-14961-C05-02 and MTM2009-14039-C06-02) for its support.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

New results on the Windy Postman Problem

  • Corberán, Angel
  • Oswald, Marcus
  • Plana, Isaac
  • Reinelt, Gerhard
  • Sanchís Llopis, José María|||0000-0002-0039-8122
[EN] In this paper, we study the Windy Postman Problem (WPP). This is a well-known Arc Routing Problem that contains the Mixed Chinese Postman Problem (MCPP) as a special case. We extend to arbitrary dimension some new inequalities that complete the description of the polyhedron associated with the Windy Postman Problem over graphs with up to four vertices and ten edges. We introduce two new families of facet-inducing inequalities and prove that these inequalities, along with the already known odd zigzag inequalities, are Chvátal-Gomory inequalities of rank at most 2. Moreover, a branch-and-cut algorithm that incorporates two new separation algorithms for all the previously mentioned inequalities and a new heuristic procedure to obtain upper bounds are presented. Finally, the performance of a branch-and-cut algorithm over several sets of large WPP and MCPP instances, with up to 3,000 nodes and 9,000 edges (and arcs in the MCPP case), shows that, to our knowledge, this is the best algorithm to date for the exact resolution of the WPP and the MCPP. © 2010 Springer and Mathematical Optimization Society., The authors want to thank the three referees for their careful reading of the manuscript and for their many comments and suggestions that have contributed to improve the paper content and readability. In particular, several remarks regarding the discussion of C-G and mod-k inequalities were pointed out by one of the referees. A. Corberan, I. Plana and J.M. Sanchis wish to thank the Ministerio de Educacion y Ciencia of Spain (projects MTM2006-14961-C05-02 and MTM2009-14039-C06-02) for its support.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

New Facets and an Enhanced Branch-and-Cut for the Min-Max K-Windy Rural Postman Problem

  • Benavent López, Enrique
  • Corberán, Angel
  • Plana, Isaac
  • Sanchís Llopis, José María|||0000-0002-0039-8122
[EN] The min-max windy rural postman problem is a multiple vehicle version of the windy rural postman problem, WRPP, which consists of minimizing the length of the longest route to find a set of balanced routes for the vehicles. In a previous paper, an ILP formulation and a partial polyhedral study were presented, and a preliminary branch-and-cut algorithm that produced some promising computational results was implemented. In this article, we present further results for this problem. We describe several new facet-inducing inequalities obtained from the WRPP, as well as some inequalities that have to be satisfied by any optimal solution. We present an enhanced branch-and-cut algorithm that takes advantage of both these new inequalities and high quality min-max K-WRPP feasible solutions obtained by a metaheuristic. Computational results on a large set of instances are also reported. © 2011 Wiley Periodicals, Inc., Contract grant sponsor: Ministerio de Ciencia e Innovacion of Spain; Contract grant numbers: MTM2006-14961-C05-02, MTM2009-14039-C06-02
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

The effects of age and emotional valence on recognition memory: An ex-Gaussian components analysis

  • Moret-Tatay, Carmen
  • Moreno-Cid, Amparo
  • Iracema de Lima Argimon, Irani
  • Irigaray, Tatiana Quarty
  • Szczerbinski, Marcin
  • Murphy, Mike
  • Vázquez-Martínez, Andrea
  • Vazquez Molina, J.
  • Navarro Pardo, Esperanza
  • Saiz Mauleón, María Begoña|||0000-0002-8650-0916
  • Fernández de Córdoba, Pedro|||0000-0002-0347-7280
[EN] The aim of this work was to study the effects of valence and age on visual image recognition memory. The International Affective Picture System (IAPS) battery was used, and response time data were analyzed using analysis of variance, as well as an ex-Gaussian fit method. Older participants were slower and more variable in their reaction times. Response times were longer for negative valence pictures, however this was statistically significant only for young participants. This suggests that negative emotional valence has a strong effect on recognition memory in young but not in old participants. The tau parameter, often related to attention in the literature, was smaller for young than old participants in an ex-Gaussian fit. Differences on the tau parameter might suggest poorer attentional performance in old participants., This work was supported by the Ministerio de Educación y Ciencia of Spain (project MTM2006-14961-C05-02)
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

The Windy General Routing Polyhedron: A global view of many known Arc Routing Polyhedra

  • Corberán, Angel
  • Plana, Isaac
  • Sanchís Llopis, José María|||0000-0002-0039-8122
[EN] The windy postman problem consists of finding a minimum cost traversal of all of the edges of an undirected graph with two costs associated with each edge, representing the costs of traversing it in each direction. In this paper we deal with the windy general routing problem (WGRP), in which only a subset of edges must be traversed and a subset of vertices must be visited. This is also an NP-hard problem that generalizes many important arc routing problems (ARPs) and has some interesting real-life applications. Here we study the description of the WGRP polyhedron, for which some general properties and some large families of facet-inducing inequalities are presented. Moreover, since the WGRP contains many well-known routing problems as special cases, this paper also provides a global view of their associated polyhedra. Finally, for the first time, some polyhedral results for several ARPs defined on mixed graphs formulated by using two variables per edge are presented., This work was supported by the Ministerio de Educación y Ciencia of Spain (project MTM2006-14961-C05-02).