Pasar al contenido principal

MODELOS Y ALGORITMOS PARA PROBLEMAS DE RUTAS DE VEHICULOS Y DE LOCALIZACION DE SERVICIOS

MTM2015-68097-P

•
Nombre agencia financiadora Ministerio de Economía y Competitividad
Acrónimo agencia financiadora MINECO
Programa Programa Estatal de Fomento de la Investigación Científica y Técnica de Excelencia
Subprograma Subprograma Estatal de Generación de Conocimiento
Convocatoria Proyectos de I+D (Excelencia / Generación de Conocimiento)
Año convocatoria 2015
Plan Estatal 2013-2016 Plan Estatal de Investigación Científica y Técnica y de Innovación
Unidad de gestión Secretaría de Estado de Educación, Formación Profesional y Universidades
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)

The Chinese Postman Problem with Load-Dependent Costs

  • Corberán, Ángel
  • Erdogan, Gunes
  • Laporte, Gilbert
  • Plana, Isaac
  • Sanchís Llopis, José María
[EN] We introduce an interesting variant of the well-known Chinese postman problem (CPP). While in the CPP the cost of traversing an edge is a constant (equal to its length), in the variant we present here the cost of traversing an edge depends on its length and on the weight of the vehicle at the moment it is traversed. This problem is inspired by the perspective of minimizing pollution in transportation, since the amount of pollution emitted by a vehicle not only depends on the travel distance but also on its load, among other factors. We define the problem, study its computational complexity, provide two mathematical programming formulations, and propose two metaheuristics for its solution. Extensive computational experiments reveal the extraordinary difficulty of this problem., The work by Angel Corberan, Isaac Plana, and Jose M. Sanchis was supported by the Spanish Ministerio de Economia y Competitividad and Fondo Europeo de Desarrollo Regional (FEDER) through [project MTM2015-68097-P] (MINECO/FEDER) and by the Generalitat Valenciana [project GVPROMETEO2013-049]. Gilbert Laporte was supported by the Canadian Natural Sciences and Engineering Research Council under [Grant 2015-06189].
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Drone arc routing problems

  • Campbell, James F.
  • Corberán, Angel
  • Plana, Isaac
  • Sanchís Llopis, José María|||0000-0002-0039-8122
[EN] In this article, we present some drone arc routing problems (Drone ARPs) and study their relation with well-known postman ARPs. Applications for Drone ARPs include traffic monitoring by flying over roadways, infrastructure inspection such as by flying along power transmission lines, pipelines or fences, and surveillance along linear features such as coastlines or territorial borders. Unlike the postmen in traditional ARPs, drones can travel directly between any two points in the plane without following the edges of the network. As a consequence, a drone route may service only part of an edge, with multiple routes being used to cover the entire edge. Thus the Drone ARPs are continuous optimization problems with an infinite number of feasible solutions. In order to solve them as a discrete optimization problem,we approximate each curve in the plane by a polygonal chain, thus allowing the vehicle to enter and leave each curve only at the points of the polygonal chain. If the capacity of the vehicles is unlimited, the resulting problem is a rural postman problem (RPP). We propose an algorithm that iteratively solves RPP instances with an increasing number of points of the polygonal chain and present results on several sets of instances.We also briefly discuss the case in which the drones have limited capacity and several drones are needed., This research was supported by the Ministerio de Economia y Competitividad and FEDER - European Regional Development Fund, MTM2015-68097-P.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

The directed profitable rural postman problem with incompatibility constraints

  • Colombi, Marco
  • Corberan, Angel
  • Mansini, Renata
  • Plana, Isaac
  • Sanchís Llopis, José María|||0000-0002-0039-8122
[EN] In this paper, we study a variant of the directed rural postman problem (RPP) where profits are asso- ciated with arcs to be served, and incompatibility constraints may exist between nodes and profitable arcs leaving them. If convenient, some of the incompatibilities can be removed provided that penalties are paid. The problem looks for a tour starting and ending at the depot that maximizes the difference between collected profits and total cost as sum of traveling costs and paid penalties, while satisfying remaining incompatibilities. The problem finds application in the domain of road transportation service, and in particular in the context of horizontal collaboration among carriers and shippers. We call this problem the directed profitable rural postman problem with incompatibility constraints. We propose two problem formulations and introduce a matheuristic procedure exploiting the presence of a variant of the generalized independent set problem (GISP) and of the directed rural postman problem (DRPP) as sub- problems. Computational results show how the matheuristic is effective outperforming in many cases the result obtained in one hour computing time by a straightforward branch-and-cut approach implemented with IBM CPLEX 12.6.2 on instances with up to 500 nodes, 1535 arcs, 1132 profitable arcs, and 10,743 incompatibilities., The work by Angel Corberan, Isaac Plana, and Jose M. Sanchis was supported by the Spanish Ministerio de Economia y Competitividad and Fondo Europeo de Desarrollo Regional (FEDER) through project MTM2015-68097-P (MINECO/FEDER) and by the Generalitat Valenciana (project GVPROMETE02013-049).
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

The Hierarchical Mixed Rural Postman Problem

  • Colombi, Marco
  • Corberán, Ángel
  • Mansini, Renata
  • Plana, Isaac
  • Sanchís Llopis, José María|||0000-0002-0039-8122
[DE] In this paper, we study a generalization of the Hierarchical Chinese Postman Problem on a mixed graph where only a subset of arcs and edges require a service to be accomplished following a hierarchical order. The problem, called the Hierarchical Mixed Rural Postman Problem, also generalizes the Rural Postman Problem and thus is NP-hard. We propose a new mathematical formulation, and introduce two effective solution algorithms. The first procedure is a matheuristic that is based on the exact solution of a variant of the Mixed Rural Postman Problem for each hierarchy. The second approach is a tabu search algorithm based on different improvement and diversification strategies. Computational results on an extended set of instances show how the proposed solution methods are quite effective and efficient when compared to the solutions of a branch-and-cut algorithm stopped after one hour of computation., The work by Angel Corberan, Isaac Plana, and Jose M. Sanchis was supported by the Spanish Ministerio de Economia y Competitividad and Fondo Europeo de Desarrollo Regional (FEDER) through [project MTM2015-68097-P] (MINECO/FEDER) and by the Generalitat Valenciana [project GVPROMETEO2013-049].
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Aesthetic considerations for the min-max K-Windy Rural Postman Problem

  • Corberán, A.
  • Golden, Bruce
  • Lum, Oliver
  • PLANA, ISAAC
  • Sanchís Llopis, José María|||0000-0002-0039-8122
[EN] The aesthetic quality of routes is a feature of route planning that is of practical importance, but receives relatively little attention in the literature. Several practitioners have pointed out that the visual appeal of a proposed set of routes can have a strong influence on the willingness of a client to accept or reject a specific routing plan. While some work has analyzed algorithmic performance relative to traditional min-sum or min-max objective functions and aesthetic objective functions, we are not aware of any work that has considered a multi-objective approach. This work considers a multi-objective variant of the Min-Max K-Vehicles Windy Rural Postman Problem, discusses several formulations of the problem, and presents computational experiments with a heuristic algorithm. After exploring several formulations, we choose to study the problem with a bi-objective function that includes contributions from the route overlap index and average task distance aesthetic measures. The heuristic extends the cluster-first procedure presented in Lum et al. (Networks 69 (2017), 290-303) by incorporating the new objective function into the improvement phase and adding a perturbation routine. (c) 2017 Wiley Periodicals, Inc., Contract grant sponsor: Spanish Ministerio de Economia y Competitividad and Fondo Europeo de Desarrollo Regional (FEDER); Contract grant number: project MTM2015-68097-P (MINECO/FEDER). Contract grant sponsor: Generalitat Valenciana; Contract grant number: project GVPROMETEO2013-049
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

The Hierarchical Mixed Rural Postman Problem: Polyhedral analysis and a branch-and-cut algorithm

  • Colombi, Marco
  • Corberán, Angel
  • Mansini, Renata
  • Plana, Isaac
  • Sanchís Llopis, José María|||0000-0002-0039-8122
[EN] The Hierarchical Mixed Rural Postman Problem is defined on a mixed graph where arcs and edges that require a service are divided into clusters' that have to be serviced in a hierarchical order. The problem generalizes the Mixed Rural Postman Problem and thus is NP-hard. In this paper, we provide a polyhedral analysis of the problem and propose a branch-and-cut algorithm for its solution based on the introduced classes of valid inequalities. Extensive computational experiments are reported on benchmark instances. The exact approach allows to find the optimal solutions in less than 1 hour for instances with up to 999 vertices, 2678 links, and five clusters., The work by Angel Corberan, Isaac Plana, and Jose M. Sanchis was supported by the Spanish Ministerio de Economia y Competitividad and Fondo Europeo de Desarrollo Regional (FEDER) through project MTM2015-68097-P (MINECO/FEDER) and by the Generalitat Valenciana (project GVPROMETEO2013-049).
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

A matheuristic for the Distance-Constrained Close-Enough Arc Routing Problem

  • Corberán, A.
  • PLANA, ISAAC
  • Reula, Miguel
  • Sanchís Llopis, José María|||0000-0002-0039-8122
[EN] The Close-Enough Arc Routing Problem, also called Generalized Directed Rural Postman Problem, is an arc routing problem with 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 within a certain distance of 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, in order to be close enough to each meter. In this paper we deal with an extension of this problem, the Distance-Constrained Generalized Directed Rural Postman Problem or Distance-Constrained Close Enough Arc Routing Problem, in which a fleet of vehicles is available. The vehicles have to leave from and return to a common vertex, the depot, and the length of their routes must not exceed a maximum distance (or time). For solving this problem we propose a matheuristic that incorporates an effective exact procedure to optimize the routes obtained. Extensive computational experiments have been performed on a set of benchmark instances and the results are compared with those obtained with an exact procedure proposed in the literature., This work was supported by the Spanish Ministerio de Economia y Competitividad and Fondo Europeo de Desarrollo Regional (FEDER) through Project MTM2015-68097-P (MINECO/FEDER). Authors want to thank two anonymous referees for their suggestions and comments that have contributed to improve the paper.
Docta Complutense
Publicación Artículo científico (JournalArticle)

The Probabilistic Pickup-and-Delivery Travelling Salesman Problem

  • Benavent, Enrique
  • Landete, Mercedes
  • Salazar González, Juan José
  • Tirado Domínguez, Gregorio
Transportation problems are essential in commercial logistics and have been widely studied in the litera- ture during the last decades. Many of them consist in designing routes for vehicles to move commodities between locations. This article approaches a pickup-and-delivery single-vehicle routing problem where there is susceptibility to uncertainty in customer requests. The probability distributions of the requests are assumed to be known, and the objective is to design an a priori route with minimum expected length. The problem has already been approached in the literature, but through a heuristic method. This article proposes the first exact approach to the problem. Two mathematical formulations are proposed: one is a compact model (i.e. defined by a polynomial number of variables and constraints); the other one contains an exponential number of inequalities and is solved within a branch-and-cut framework. Computational results show the upsides as well as the breakdowns of both formulations.