Pasar al contenido principal

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

MTM2012-36163-C06-02

•
Nombre agencia financiadora Ministerio de Economía y Competitividad
Acrónimo agencia financiadora MINECO
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 2012
Plan Estatal 2008-2011 Plan Nacional de Investigación Científica, Desarrollo e Innovación Tecnológica
Unidad de gestión Secretaría de Estado de Investigación, Desarrollo e Innovación
Centro beneficiario UNIVERSITAT DE VALÈNCIA
Identificador persistente http://dx.doi.org/10.13039/501100003329

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)

A New Branch-and-Cut Algorithm for the Generalized Directed Rural Postman Problem

  • Ávila, Thais
  • Corberán, Ángel
  • Plana, Isaac
  • Sanchís Llopis, José María
The generalized directed rural postman problem, also known as the close-enough arc routing problem, is an arc routing problem with some interesting real-life applications, such as routing for meter reading. In this article we introduce two new formulations for this problem as well as various families of new valid inequalities that are used to design and implement a branch-and-cut algorithm. The computational results obtained on test bed instances from the literature show that this algorithm outperforms the existing exact methods, The authors wish to thank Minh Hoang Ha, Nathalie Bostel, Andre Langevin, and Louis-Martin Rousseau for providing their instances. The authors also thank the Spanish Ministerio de Economia y Competitividad [project MTM2012-36163-C06-02] and the Generalitat Valenciana [project GVPROMETEO2013-049] for their support.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Formulations and exact algorithms for the distance-constrained generalized directed rural postman problem

  • Ávila, Thais
  • Corberán, Angel
  • Plana, Isaac
  • Sanchís Llopis, José María|||0000-0002-0039-8122
[EN] The generalized directed rural postman problem is an arc routing problem with many interesting real-life applications, such as routing for meter reading. In this application, a vehicle with a receiver travels through a series of neighborhoods. If the vehicle gets closer than a certain distance to a meter, the receiver is able to record the gas, water, or electricity consumption. Therefore, the vehicle does not need to traverse every street, but only a few, to get close enough to each meter. We study an extension of this problem in which a fleet of vehicles is available. Given the characteristics of the mentioned application, the vehicles have no capacities but there is a maximum distance (or time) constraint all of them have to satisfy.We introduce four formulations for this problem, propose some families of valid inequalities, and present four branch-and-cut algorithms for its solution. The formulations and the algorithms are compared on a large set of instances., The authors thank the Spanish Ministerio de Economia y Competitividad (project MTM2012-36163-C06-02) and the Generalitat Valenciana (project GVPROMETEO2013-049) for their support.
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 branch-and-cut algorithm for the Profitable Windy Rural Postman Problem

  • Ávila, T.
  • Corberán, A.
  • Plana, I.
  • Sanchís Llopis, José María|||0000-0002-0039-8122
[EN] In this paper we study the profitable windy rural postman problem. This is an arc routing problem with profits defined on a windy graph in which there is a profit associated with some of the edges of the graph, consisting of finding a route maximizing the difference between the total profit collected and the total cost. This problem generalizes the rural postman problem and other well-known arc routing problems and has real-life applications, mainly in snow removal operations. We propose here a formulation for the problem and study its associated polyhedron. Several families of facet-inducing inequalities are described and used in the design of a branch-and-cut procedure. The algorithm has been tested on a large set of benchmark instances and compared with other existing algorithms. The results obtained show that the branch-and-cut algorithm is able to solve large-sized instances optimally in reasonable computing times., Authors thank Elisa Schaeffer for providing us with the instances and solutions of sets of instances Set1-Set4 and two anonymous referees for their comments and suggestions that have helped to improve the paper. Authors also wish to thank the Ministerio de Economia y Competitividad of Spain (MTM2012-36163-C06-02) and the Generalitat Valenciana (Project GVPROMETEO2013-049) for its support.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

The stacker crane problem and the directed general routing problem

  • Ávila, Thais
  • Corberán, Angel
  • Plana, Isaac
  • Sanchís Llopis, José María|||0000-0002-0039-8122
[EN] This article deals with the polyhedral description and the resolution of the directed general routing problem (DGRP) and the stacker crane problem (SCP). The DGRP contains a large number of important arc and node routing problems as special cases, including the SCP. Large families of facet-defining inequalities for the DGRP are described and a branch-and-cut algorithm for these problems is presented. Extensive computational experiments over different sets of DGRP and SCP instances are included., Contract grant sponsor: Ministerio de Economía y Competitividad (project MTM2012-36163-C06-02) of Spain Contract grant sponsor: Generalitat Valenciana (project GVPROMETEO2013-049)
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 Orienteering Arc Routing Problem

  • Archetti, C.
  • Corberán, A.
  • Plana, I.
  • Speranza, M.G.
  • Sanchís Llopis, José María|||0000-0002-0039-8122
[EN] In arc routing problems, customers are located on arcs, and routes of minimum cost have to be identified. In the Orienteering Arc Routing Problem (OARP),in addition to a set of regular customers that have to be serviced, a set of potential customers is available. From this latter set, customers have to be chosen on the basis of an associated profit. The objective is to find a route servicing the customers which maximize the total profit collected while satisfying a given time limit on the route.In this paper, we describe large families of facet-inducing inequalities for the OARP and present a branch-and-cut algorithm for its solution. The exact algorithm embeds a procedure which builds a heuristic solution to the OARP on the basis of the information provided by the solution of the linear relaxation. Extensive computational experiments over different sets of OARP instances show that the exact algorithm is capable of solving to optimality large instances, with up to 2000 vertices and 14,000 arcs, within 1 h and often within a few minutes., Authors want to thank two anonymous referees for their careful reading of the original paper and their many valuable comments and suggestions that have helped to improve the paper. Angel Corberan, Isaac Plana and Jose M. Sanchis wish to thank the Ministerio de Economia y Competitividad of Spain (MTM2012-36163-006-02) and the Generalitat Valenciana (project GVPR-OMETE02013-049) for its support.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

A matheuristic for the Team Orienteering Arc Routing Problem

  • Archetti, Claudia
  • Corberan, Angel
  • Plana, Isaac
  • Sanchís Llopis, José María
  • Speranza, M. G.
In the Team OrienteeringArc Routing Problem (TOARP) the potential customers are located on the arcs of a directed graph and are to be chosen on the basis of an associated profit. A limited fleet of vehicles is available to serve the chosen customers. Each vehicle has to satisfy a maximum route duration constraint. The goal is to maximize the profit of the served customers. We propose a matheuristic for the TOARP and test it on a set of benchmark instances for which the optimal solution or an upper bound is known. The matheuristic finds the optimal solutions on all, except one, instances of one of the four classes of tested instances (with up to 27 vertices and 296 arcs). The average error on all instances fo rwhich the optimal solution is available is 0.67 percent., Angel Corberan, Isaac Plana and Jose M. Sanchis wish to thank the Ministerio de Economia y Competitividad (project MTM2012-36163-C06-02) of Spain and the Generalitat Valenciana (project GVPROMETEO2013-049) for their support.
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