Pasar al contenido principal

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

PGC2018-099428-B-I00

•
Nombre agencia financiadora Agencia Estatal de Investigación
Acrónimo agencia financiadora AEI
Programa Programa Estatal de Generación de Conocimiento y Fortalecimiento Científico y Tecnológico del Sistema de I+D+i
Subprograma Subprograma Estatal de Generación de Conocimiento
Convocatoria Proyectos de I+D (Excelencia / Generación de Conocimiento)
Año convocatoria 2018
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): 7
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 Profitable Close-Enough Arc Routing Problem

  • Bianchessi, Nicola
  • Corberán, Ángel
  • Plana, Isaac
  • Reula, Miguel
  • Sanchís Llopis, José María|||0000-0002-0039-8122
[EN] In this article, we deal with the Profitable Close-Enough Arc Routing Problem (PCEARP), which is an extension of the Close-Enough ARP (CEARP). The CEARP models the situation in which customers are not necessarily nodes of a network and the associated serviced can be performed from any traversed edge that is close enough to the customer. It consists of finding a minimum cost tour that services all the customers. In the PCEARP, a profit is associated with each customer and it is collected (only once) when the customer is serviced. The goal is to find a tour maximizing the difference between the total profit collected and the travel distance. A formulation for this new problem and some valid inequalities are presented, and a polyhedral study of its feasible solutions is conducted. We propose a heuristic and a branch-and-cut procedure for solving the PCEARP, and their performance has been tested on several sets of instances with different characteristics., The work by Angel Corberan, Isaac Plana, Miguel Reula, and Jose M. Sanchis was supported by the Spanish Ministerio de Ciencia, Innovacion, Universidades (MICIU) and Fondo Social Europeo (FSE), Spain through project PGC2018-099428-B-I00. The authors want to thank the comments and suggestions done by two anonymous reviewers that have contributed to improve the content and readability of the article.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

On the Distance-Constrained Close Enough Arc Routing Problem

  • Corberán, Ángel
  • Plana, Isaac
  • Reula, Miguel
  • Sanchís Llopis, José María|||0000-0002-0039-8122
[EN] Arc routing problems consist basically of finding one or several routes traversing a given set of arcs and/or edges that must be serviced. The Close-Enough Arc Routing Problem, or Generalized Directed Rural Postman Problem, does not assume that customers are located at specific arcs, but can be serviced by traversing any arc of a given subset. Real-life applications include routing for meter reading, in which a vehicle equipped with a receiver travels a street network. If the vehicle gets within a certain distance of a meter, the receiver collects its data. Therefore, only a few streets which are close enough to the meters need to be traversed. In this paper we study the generalization of this problem to the case in which a fleet of vehicles is available. This problem, the Distance-Constrained Close Enough Arc Routing Problem, consists of finding a set of routes with minimum total cost such that their length does not exceed a maximum distance. In this article, we propose a new formulation for the Distance-Constrained Close Enough Arc Routing Problem and present some families of valid inequalities that we use in a branch-and-cut algorithm for its solution. Extensive computational experiments have been performed on a set of benchmark instances and the results are compared with those obtained with other heuristic and exact methods., This work was supported by the Spanish Ministerio de Ciencia, Innovacion y Universidades (MICIU) and Fondo Social Europeo (FSE) through project PGC2018-099428-B-I00. The authors want to thank the comments and suggestions done by two anonymous referees that have contributed to improve the content and readability of the article.
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.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

The multi-purpose K-drones general routing problem

  • Campbell, James
  • Corberán, Ángel
  • Plana, Isaac
  • Segura-Martínez, Paula
  • Sanchís Llopis, José María|||0000-0002-0039-8122
[EN] In this article, we present and solve the multi-pur pose K-drones general routing problem (MP K-DGRP). In this optimization problem, a fleet of multi-pur pose drones, aerial vehicles that can both make deliveries and conduct sensing activities (e.g., imaging), have to jointly visit a set of nodes to make deliveries and map one or more continuous areas. This problem is motivated by global healthcare applica-tions that deploy multipurpose drones that combine delivery trips with collection of aerial imaging data for use in emergency preparedness and resilience planning. The continuous areas that have to be mapped may correspond to terrain surfaces (e.g., flooded areas or regions with a disease outbreak) or to infrastructure networks to be inspected. The continuous areas can be modeled as a set of lines so that each area is completely serviced if all the lines covering it are traversed. Thus, given a set of nodes and a set of lines, the problem is to design drone routes of shortest total duration traversing the lines and visiting the nodes, while not exceeding the range limit (flight time) and capacity (loading) of the drones. Unlike ground vehicles in classical routing problems, drones can enter a line through any of its points, service only a part of that line and then exit through another of its points. The possibility of flying directly between any two points of the network offered by drones can lead to reduced costs, but it increases the difficulty of the problem. To deal with this problem, the lines are discretized, allowing drones to enter and exit each line only at a finite set of points, thus obtaining an instance of the K-vehicles general routing problem (K-GRP). We present in this article an integer programming formulation for the K-GRP and propose a matheuristic algorithm and a branch-and-cut proce-dure for its solution. Results are provided for problems with up to 20 deliveries and up to 28 continuous areas., Fondo Social Europeo (FSE), Grant/Award Number: PGC2018-099428-B-I00; European Regional Development Fund, Grant/Award Number: PID2021-122344NB-I00; European Social Fund; Ministerio de Ciencia e Innovacion; Ministerio de Ciencia, Innovacion y Universidades.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Arc routing problems: A review of the past, present, and future

  • Corberán, Ángel
  • Eglese, Richard
  • Hasle, Geir
  • Plana, Isaac
  • Sanchís Llopis, José María|||0000-0002-0039-8122
[EN] Arc routing problems (ARPs) are defined and introduced. Following a brief history of developments in this area of research, different types of ARPs are described that are currently relevant for study. In addition, particular features of ARPs that are important from a theoretical or practical point of view are discussed. A section on applications describes some of the changes that have occurred from early applications of ARP models to the present day and points the way to emerging topics for study. A final section provides information on libraries and instance repositories for ARPs. The review concludes with some perspectives on future research developments and opportunities for emerging applications, This research was supported by the Ministerio de Economia y Competitividad and Fondo Europeo de Desarrollo Regional, Grant/Award Number: PGC2018-099428-B-I00. The Research Council of Norway, Grant/Award Numbers: 246825/O70 (DynamITe), 263031/O70 (AXIOM).
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

The min-max close-enough arc routing problem

  • Bianchessi, Nicola
  • Corberán, Ángel
  • Plana, Isaac
  • Reula, Miguel
  • Sanchís Llopis, José María|||0000-0002-0039-8122
[EN] Here we introduce the Min-Max Close-Enough Arc Routing Problem, where a fleet of vehicles must serve a set of customers while trying to balance the length of the routes. The vehicles do not need to visit the customers, since they can serve them from a distance by traversing arcs that are ¿close enough¿to the customers. We present two formulations of the problem and propose a branch-and-cut and a branch-and- price algorithm based on the respective formulations. A heuristic algorithm used to provide good upper bounds to the exact procedures is also presented. Extensive computational experiments to compare the performance of the algorithms are carried out., The work by Angel Corberan, Isaac Plana, Miguel Reula, and Jose M. Sanchis was supported by the Spanish Ministerio de Ciencia, Innovacion y Universidades (MICIU) and Fondo Social Europeo (FSE) through project PGC2018-099428-B-I00. The authors want to thank the comments and suggestions done by three anonymous reviewers that have contributed to improve the content and readability of the article.