Pasar al contenido principal

ANALISIS Y RESOLUCION DE PROBLEMAS DE RUTAS DE VEHICULOS Y LOCALIZACION DE SERVICIOS

PRE2019-087383

•
Nombre agencia financiadora Agencia Estatal de Investigación
Acrónimo agencia financiadora AEI
Programa Programa Estatal de Promoción del Talento y su Empleabilidad en I+D+i
Subprograma Subprograma Estatal de Formación
Convocatoria Contratos Predoctorales
Año convocatoria 2019
Plan Estatal 2017-2020 Plan Estatal de Investigación Científica y Técnica y de Innovación
Centro beneficiario UNIVERSITAT POLITÈCNICA DE VALÈNCIA

Resultados relacionados

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

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

Solving the length constrained K-drones rural postman problem

  • Campbell, James F.
  • Corberán, Ángel
  • Plana, Isaac
  • Segura-Martínez, Paula
  • Sanchís Llopis, José María|||0000-0002-0039-8122
[EN] In this paper we address the Length Constrained K-Drones Rural Postman Problem (LC K-DRPP). This is a continuous optimization problem where a fleet of homogeneous drones have to jointly service (traverse) a set of (curved or straight) lines of a network. Unlike the vehicles in classical arc routing problems, a drone can enter a line through any of its points, service a portion of that line, exit through another of its points, then travel directly to any point on another line, and so on. Moreover, since the range of the drones is restricted, the length of each route is limited by a maximum distance. Some applications for drone arc routing problems include inspection of pipelines, railway or power transmission lines and traffic monitoring. To deal with this problem, LC K-DRPP instances are digitized by approximating each line by a polygonal chain with a finite number of points and allowing drones to enter and exit each line only at these points. In this way we obtain an instance of the Length Constrained K-vehicles Rural Postman Problem (LC K-RPP). If the number of points used to discretize the lines is large, the LC K-RPP instance can be extremely large and, hence, very difficult to solve optimally. Even heuristic algorithms can fail in providing feasible solutions in reasonable computing times. An alternative is to generate smaller LC K-RPP instances by approximating each line with few but "significant" segments. We present a formulation and some valid inequalities for the LC K-RPP. Based on this, we have designed and implemented a branch-and-cut algorithm for its solution. Moreover, in order to be capable of providing good solutions for large LC K-RPP instances, we propose a matheuristic algorithm that begins by finding good solutions for the LC K-RPP instance obtained by approximating each line by a single segment. Then, to find better solutions, some promising intermediate points are sequentially incorporated. Extensive computational experiments to assess the performance of both algorithms are performed on several sets of instances from the literature., The work by Angel Corberan, Isaac Plana, JoseM. Sanchis, and Paula Segura was supported by the Spanish Ministerio de Ciencia, Innovacion y Universidades (MICIU) and Fondo Social Europeo (FSE) through project PGC2018-099428-B-I00
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Polyhedral analysis and a new algorithm for the length constrained K-drones rural postman problem

  • Campbell, James
  • Corberán, Ángel
  • Plana, Isaac
  • Segura-Martínez, Paula
  • Sanchís Llopis, José María|||0000-0002-0039-8122
[EN] The Length Constrained K¿Drones Rural Postman Problem (LC K¿DRPP) is a continuous optimization problem where a set of curved or straight lines of a network have to be traversed, in order to be serviced, by a fleet of homogeneous drones, with total minimum cost. Since the range and endurance of drones is limited, we consider here that the length of each route is constrained to a given limit L. Drones are not restricted to travel on the network, and they can enter and exit a line through any of its points, servicing only a portion of that line. Therefore, shorter solutions are obtained with ¿aerial¿ drones than with ¿ground¿ vehicles that are restricted to the network. If a LC K¿DRPP instance is digitized by approximating each line with a polygonal chain, and it is assumed that drones can only enter and exit a line through the points of the chain, an instance of the Length Constrained K¿vehicles Rural Postman Problem (LC K¿RPP) is obtained. This is a discrete arc routing problem, and therefore can be solved with combinatorial optimization techniques. However, when the number of points in each polygonal chain is very large, the LC K¿RPP instance can be so large that it is very difficult to solve, even for heuristic algorithms. Therefore, it is necessary to implement a procedure that generates smaller LC K¿ RPP instances by approximating each line by a few but ¿significant¿ points and segments. In this paper, we present a new formulation for the LC K¿RPP with two binary variables for each edge and each drone representing the first and second traversals of the edge, respectively. We make a polyhedral study of the set of solutions of a relaxed formulation and prove that several families of inequalities induce facets of the polyhedron. We design and implement a branch¿and¿cut algorithm for the LC K¿RPP that incorporates the separation of these inequalities. This B &C is the main routine of an iterative algorithm that, by solving a LC K¿RPP instance at each step, finds good solutions for the original LC K¿DRPP. The computational results show that the proposed method is effective in finding good solutions for LC K¿DRPP, and that the branch¿and¿cut algorithm for the LC K¿RPP outperforms the only published exact method for this problem., The work by Ángel Corberán, Isaac Plana, José M. Sanchis, and Paula Segura was supported by the Spanish Ministerio de Ciencia, Innovación y Universidades (MICIU) and Fondo Social Europeo (FSE) through project PGC2018-099428-B-I00.