Pasar al contenido principal

MODELOS Y METODOS DE PROGRAMACION MATEMATICA Y SUS APLICACIONES (OPTIMOS2)

MTM2009-14039-C06-02

•
Nombre agencia financiadora Ministerio de Ciencia e Innovación
Acrónimo agencia financiadora MICINN
Programa Programa Nacional de Proyectos de Investigación Fundamental
Subprograma Subprograma de Proyectos de Investigación Fundamental no Orientada
Convocatoria Proyectos I+D
Año convocatoria 2009
Plan Estatal 2008-2011 Plan Nacional de Investigación Científica, Desarrollo e Innovación Tecnológica
Unidad de gestión Subdirección General de Proyectos de Investigación
Centro beneficiario UNIVERSITAT DE VALÈNCIA
Identificador persistente http://dx.doi.org/10.13039/501100004837

Resultados relacionados

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

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

The mixed general routing polyhedron

  • Corberán, Angel
  • Romero Rozalén, Antonio
  • Sanchís Llopis, José María|||0000-0002-0039-8122
[EN] In Arc Routing Problems, ARPs, the aim is to find on a graph a minimum cost traversal satisfying some conditions related to the links of the graph. Due to restrictions to traverse some streets in a specified way, most applications of ARPs must be modeled with a mixed graph. Although several exact algorithms have been proposed, no polyhedral investigations have been done for ARPs on a mixed graph. In this paper we deal with the Mixed General Routing Problem which consists of finding a minimum cost traversal of a given link subset and a given vertex subset of a mixed graph. A formulation is given that uses only one variable for each link (edge or arc) of the graph. Some properties of the associated polyhedron and some large families of facet-inducing inequalities are described. A preliminary cutting-plane algorithm has produced very good lower bounds over a set of 100 randomly generated instances of the Mixed Rural Postman Problem. Finally, applications of this study to other known routing problems are described., The authors wish to thank the Ministerio de Innovación y Ciencia/FEDER of Spain (projects MTM2009-14039-C06-02, MTM2010-19576-C02-02 and DE2009-0057) and Junta de Andalucía/FEDER (grant number FQM-5849) for its support. They also thank two anonymous referees for their careful reading of the manuscript and for their many suggestions and comments that have helped to improve the contents and readability of the paper.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

The Team Orienteering Arc Routing Problem

  • Archetti, Claudia
  • Speranza, M. Grazia
  • Corberan, Angel
  • Sanchís Llopis, José María
  • Plana, Isaac
The team orienteering arc routing problem (TOARP) is the extension to the arc routing setting of the team orienteering problem. In the TOARP, in addition to a possible set of regular customers that have to be serviced, another set of potential customers is available. Each customer is associated with an arc of a directed graph. Each potential customer has a profit that is collected when it is serviced, that is, when the associated arc is traversed. A fleet of vehicles with a given maximum traveling time is available. The profit from a customer can be collected by one vehicle at most. The objective is to identify the customers that maximize the total profit collected while satisfying the given time limit for each vehicle. In this paper we propose a formulation for this problem and study a relaxation of its associated polyhedron. We present some families of valid and facet-inducing inequalities that we use in the implementation of a branch-and-cut algorithm for the resolution of the problem. Computational experiments are run on a large set of benchmark instances., The authors thank the reviewers for their comments that helped to provide an improved and clearer version of this paper. Angel Corberan, Isaac Plana, and Jose M. Sanchis wish to thank the Ministerio de Ciencia e Innovacion [Project MTM2009-14039-C06-02] and the Ministerio of Economia y Competitividad [Project MTM2012-36163-C06-02] of Spain for their support.
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)

A Branch-Price-and-Cut Algorithm for the Min-Max k -Vehicle Windy Rural Postman Problem

  • Benavent Lopez, Enrique
  • Corberán, Angel
  • Desaulniers, Guy
  • Lessard, François
  • Plana, Isaac
  • Sanchís Llopis, José María|||0000-0002-0039-8122
[EN] The min-max k -vehicles windy rural postman problem consists of minimizing the maximal distance traveled by a vehicle to find a set of balanced routes that jointly service all the required edges in a windy graph. This is a very difficult problem, for which a branch-and-cut algorithm has already been proposed, providing good results when the number of vehicles is small. In this article, we present a branch-price-and-cut method capable of obtaining optimal solutions for this problem when the number of vehicles is larger for the same set of required edges. Extensive computational results on instances from the literature are presented., Contract grant sponsor: Ministerio de Education y Ciencia of Spain: Contract gram number: MTM2006-14961-C05-02 Canadian Natural Sciences and Engineering Research Council; Contract grant number: 157935-07
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

The Windy Clustered Prize-Collecting Arc-Routing Problem

  • Corberan, Ángel
  • Fernandez, Elena
  • Franquesa, Carles
  • Sanchís Llopis, José María
This paper introduces the windy clustered prize-collecting arc-routing problem. It is an arc-routing problem where each demand edge is associated with a profit that is collected once if the edge is serviced, independent of the number of times the edge is traversed. It is further required that if a demand edge is serviced, then all the demand edges of its component are also serviced. A mathematical programming formulation is given and some polyhedral results including several facet-defining and valid inequalities are presented. The separation problem for the different families of inequalities is studied. Numerical results from computational experiments are analyzed. © 2011 INFORMS., The authors thank the Ministerio de Educacion y Ciencia of Spain ( Projects MTM2009-14039-C06-02 and MTM2009-14039-C06-05) for its support. They also thank the associate editor and three anonymous referees for their careful reading of the manuscript and for their many comments and suggestions that contributed significantly to improving it.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

A branch-and-cut algorithm for the maximum benefit Chinese postman problem

  • Corberán, Angel
  • Plana, Isaac
  • Rodríguez-Chía, Antonio Manuel
  • Sanchís Llopis, José María|||0000-0002-0039-8122
[EN] The Maximum Benefit Chinese Postman Problem (MBCPP) is an NP-hard problem that considers several benefits associated with each edge, one for each time the edge is traversed with a service. The objective is to find a closed walk with maximum benefit.We propose an IP formulation for the undirected MBCPP and, based on the description of its associated polyhedron, we propose a branch-and-cut algorithm and present computational results on instances with up to 1,000 vertices and 3,000 edges., The authors wish to thank the Ministerio de Innovacion y Ciencia/FEDER of Spain (projects MTM2009-14039-C06-02, MTM2010-19576-C02-02 and DE2009-0057) and Junta de Andalucia/FEDER (grant number FQM-5849) for its support. They also thank two anonymous referees for their careful reading of the manuscript and for their many suggestions and comments that have helped to improve the contents and readability of the paper.