Pasar al contenido principal

NUEVAS TENDENCIAS EN OPTIMIZACION COMBINATORIA PARA LA GESTION DE RECURSOS Y DATOS

PID2021-122344NB-I00

•
Nombre agencia financiadora Agencia Estatal de Investigación
Acrónimo agencia financiadora AEI
Programa Programa Estatal para Impulsar la Investigación Científico-Técnica y su Transferencia
Subprograma Subprograma Estatal de Generación de Conocimiento
Convocatoria Proyectos de I+D+i (Generación de Conocimiento y Retos Investigación)
Año convocatoria 2021
Plan Estatal 2021-2023 Plan Estatal de Investigación Científica y Técnica y de Innovación
Centro beneficiario UNIVERSIDAD MIGUEL HERNANDEZ DE ELCHE

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)

Upgrading edges in the Graphical TSP

  • Landete, Mercedes
  • Plana, Isaac
  • Sainz-Pardo, José Luis
  • Sanchís Llopis, José María|||0000-0002-0039-8122
[EN] In this paper we present a generalization of the Graphical Traveling Salesman Problem (GTSP). Given a communication graph in which not all direct connections are necessarily possible, the Graphical Traveling Salesman Problem consists of finding the shortest tour that visits each node at least once. In this work, we assume the availability of a budget that allows to upgrade, i.e. reduce their traversal cost, some of the current connections and we propose the problem of designing the minimum cost tour using this budget. We propose and study a formulation for the problem, verifying that the polyhedron associated with the set of feasible solutions of a relaxed version of the problem is a full-dimensional polytope. We present families of valid inequalities that reinforce the model and pre-processing techniques to reduce the number of variables of the formulation. To solve the problem, we propose a branch-and-cut algorithm that uses the introduced valid inequalities, as well as a heuristic to obtain good upper bounds and a tailor-made branching strategy. Comprehensive computational experiments on a new set of benchmark instances are presented to assess the performance of this exact method., This work was supported by Generalitat Valenciana, Spain through project CIGE/2021/161 and by grant PID2021-122344NB-I00 funded by MCIN/AEI/10.13039/501100011033 and "ERDF A way of making Europe".
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

A modified single-objective genetic algorithm for solving the rural postman problem with load-dependent costs

  • De Santis, David
  • Landete, Mercedes
  • Cabezas, Xavier
  • Peiró, Juanjo
  • Sanchís Llopis, José María|||0000-0002-0039-8122
[EN] This study addresses the rural postman problem with load-dependent costs, a variant of the arc routing problem where the traversal cost of an edge depends on its length and the vehicle's load. The objective is to find a minimum-cost tour that services all required edges, a problem of particular importance when the demand weight is significant compared to the vehicle's curb weight. We present an integer linear programming model for the problem and propose a heuristic algorithm based on bio-inspired methodologies to efficiently obtain near-optimal solutions within short computing times. The effectiveness of the approach is demonstrated through computational experiments on benchmark instances, and the results highlight the practicality of the proposed methods., This work was supported by Gobierno de Espana through Ministerio Ciencia, Innovacion y Ministerio de Universidades and Fondo Europeo de Desarrollo Regional (FEDER) , Spain under projects PID2021-122344NB-I00, and RED2018-102363-T, by Generalitat Valenciana, Spain under projects PROMETEO/2021/063 and CIGE/2022/57. The authors would like to thank the anonymous reviewers for their comments and suggestions, which have contributed to improving 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)

The multidepot drone general routing problem with duration and capacity constraints

  • Corberán, Teresa
  • Plana, Isaac
  • Sanchis, José M.
  • Segura-Martínez, Paula
[EN] This paper studies the multidepot drone general routing problem with duration and capacity constraints (MDdGRP), an extension of the classical general routing problem with several depots. A fleet of drones with limited flight time and payload, each one located in a different depot, must jointly perform the service. In this continuous optimization problem, a set of lines of a network has to be serviced and a set of nodes has to be visited to deliver a given commodity. The aim is to find a set of drone routes performing the complete service with the shortest total duration. Aerial drones can enter a line at any point, service a portion of that line, and exit through another point, without following the lines of the network. While this flexibility allows for potentially better solutions, it also adds complexity to the problem. To deal with this, we digitize the MDdGRP instances by approximating each line with a polygonal chain containing a finite number of points that can be used to enter and exit each line. Thus, an instance of a discrete multidepot general routing problem (MDGRP) is obtained. This paper proposes an integer formulation for the MDGRP, some families of valid inequalities, and a branch-and-cut algorithm based on the strengthened formulation. Two matheuristic algorithms are presented, focused on sequentially selecting (and adding) some promising intermediate points to enter and exit a line. Instances involving up to six depots, 22 delivery points, and 88 original lines have been generated to test the performance of the methods proposed., This work was supported by grant PID2021-122344NB-I00 funded by MCIN/AEI/10.13039/501100011033 and "ERDF A way of making Europe."
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)

The min max multi-trip drone location arc routing problem

  • Corberán Fabra, Teresa
  • Plana, Isaac
  • Sanchís Llopis, José María|||0000-0002-0039-8122
[EN] This paper studies the Min Max Multi-Trip drone Location Arc Routing Problem (MM-MT-dLARP), an arc routing problem that combines trucks and drones. We have a set of lines (usually curved) that have to be flown over by drones to perform a service (inspection, for example). There is a depot from which the trucks leave, each one carrying a drone, and a set of potential launching points where the truck can launch and pickup the drone. Drones have limited autonomy, but they can make several flights. We consider a min-max objective, in which the makespan, or time necessary to complete the service, must be minimized. Using aerial drones instead of ground vehicles allows to travel off the network: drones can enter a line through any of its points, service only a portion of that line and then exit through another of its points, without following the lines of the network. This allows for finding better solutions but also increases the difficulty of the problem. This issue can be addressed by digitizing the MM-MT-dLARP instances, approximating each line by a polygonal chain with a finite number of intermediate points, and requiring that drones can only enter and exit aline through those intermediate points. Thus, an instance of a discrete Min Max Multi-Trip Location Arc Routing Problem (MM-MT-LARP) is obtained. Here, an integer formulation for the MM-MT-LARP is proposed, some families of valid inequalities are proved to be facet-inducing of a relaxed polyhedron, and a branch-and-cut algorithm based on the strengthened formulation is developed. This algorithm has only been applied to small instances without intermediate points on the lines. In addition, we have developed a matheuristic algorithm for the MM-MT-dLARP that combines a construction phase, four local search procedures integrated into a Variable Neighborhood Descent (VND) algorithm, and a set of rules for selecting intermediate points to improve the solutions. We present the results obtained on a set of randomly generated instances involving up to 6 launching points and 88 original lines., This work was supported by grant PID2021-122344NB-I00 funded by MCIN/AEI, Spain/10.13039/501100011033 and "ERDF A way of making Europe".
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Theoretical and computational analysis of a new formulation for the Rural Postman Problem and the General Routing Problem

  • Corberán, Ángel
  • Plana, Isaac
  • Segura-Martínez, Paula
  • Sanchís Llopis, José María|||0000-0002-0039-8122
[EN] The Rural Postman Problem (RPP) is one of the most well-known problems in arc routing. Given an undirected graph, the RPP consists of finding a closed walk traversing and servicing a given subset of edges with minimum total cost. In the General Routing Problem (GRP), there is also a subset of vertices that must be visited. Both problems were introduced by Orloff and proved to be NP-hard. In this paper, we propose a new formulation for the RPP and the GRP using two sets of binary variables representing the first and second traversal, respectively, of each edge. We present several families of valid inequalities that induce facets of the polyhedron of solutions under mild conditions. Using this formulation and these families of inequalities, we propose a branch-and-cut algorithm, test it on a large set of benchmark instances, and compare its performance against the exact procedure that, as far as we know, produced the best results. The results obtained show that the proposed formulation is useful for solving undirected RPP and GRP instances of very large size., The work by Isaac Plana, Jose M. Sanchis, and Paula Segura was supported by grant PID2021-122344NB-I00 funded by MCIN/AEI/10.13039/501100011033 and "ERDF A way of making Europe".
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

An extension of an interior-point method to include risk aversion in large-scale multistage stochastic optimization

  • Castro Pérez, Jordi|||0000-0003-3573-4568
  • Escudero Bueno, Laureano F.
  • Monge Ivars, Juan Francisco
In the earlier paper “On solving large-scale multistage stochastic optimization problems with a new specialized interior-point approach, (Castro et al., 2023)” the authors presented a novel approach based on a specialized interior-point method (IPM) for solving (risk neutral) large-scale multistage stochastic optimization problems. The method computed the Newton direction by combining Cholesky factorizations with preconditioned conjugate gradients (PCG). This work extends that approach to the risk averse setting by incorporating coherent risk measures, namely expected conditional value-at-risk and second-order expected conditional stochastic dominance. Introducing risk aversion makes the optimization problems substantially more challenging and, for very large instances, can even exhaust the available memory resources. The contributions of this work are twofold. First, we propose a reformulation of risk averse stochastic optimization models based on a novel variable splitting scheme, which proves highly effective for general-purpose IPM solvers. Second, we show that the reformulated problem remains fully compatible with the specialized IPM. In particular, the new risk averse constraints extend the PCG preconditioner with an additional diagonal matrix, thereby preserving the efficiency of the solution process. Extensive computational experiments are reported for large-scale risk averse multistage stochastic revenue management problems with up to 278 million variables and 99 million constraints. The results show that the proposed splitting formulation significantly outperforms the classical compact formulation when using state-of-the-art solvers, and that the specialized IPM achieves superior performance on most of the largest problem instances., Peer Reviewed