Examinando por Autor "Laguna, Manuel"

Mostrando 1 - 4 de 4

A solution method for the shared resource-constrained multi-shortest path problem
(Elsevier, 2021-11-15) García-Heredia, David; Molina, Elisenda; Laguna, Manuel; Alonso-Ayuso, Antonio
We tackle the problem of finding, for each network within a collection, the shortest path between two given nodes, while not exceeding the limits of a set of shared resources. We present an integer programming (IP) formulation of this problem and propose a parallelizable matheuristic consisting of three phases: (1) generation of feasible solutions, (2) combination of solutions, and (3) solution improvement. We show that the shortest paths found with our procedure correspond to the solution of some type of scheduling problems such as the Air Traffic Flow Management (ATFM) problem. Our computational results include finding optimal solutions to small and medium-size ATFM instances by applying Gurobi to the IP formulation. We use those solutions to assess the quality of the output produced by our proposed matheuristic. For the largest instances, which correspond to actual flight plans in ATFM, exact methods fail and we assess the quality of our solutions by means of Lagrangian bounds. Computational results suggest that the proposed procedure is an effective approach to the family of shortest path problems that we discuss here.
Changeover minimization in the production of metal parts for car seats
(Elsevier, 2024-10-16) Colmenar, J. Manuel; Laguna, Manuel; Martín-Santamaría, Raúl
We tackle a capacitated lot-sizing and scheduling problem (CLSP) with the main objective of minimizing changeover time in the production of metal parts for car seats. Changeovers occur when a machine (or production line) is reconfigured to produce a different product or part, leading to production downtime and loss of efficiency. In this study, we first provide a mixed-integer programming (MIP) formulation of the problem. We test the limits of solving the problem with commercial mathematical programming software. We also propose two approaches to tackle instances found in practice for which the mathematical programming model is not a viable solution method. Both approaches are based on partitioning the entire production of a part into production runs (or work slots). In the first approach, the work slots are assigned to machines and sequenced by a metaheuristic that follows the search principles of the GRASP (greedy randomized adaptive procedure) and VNS (variable neighborhood search) methodologies. In the second approach, we develop a Hexaly Optimizer (formerly known as LocalSolver) model to assign and sequence work slots. The study provides insights into how to minimize changeovers and improve production efficiency in metal parts manufacturing for car seats. The findings of this study have practical implications for the auto-part manufacturing industry, where efficient and cost-effective production is critical to meet the demands of the market
Multistart Search for the Cyclic Cutwidth Minimization Problem
(Computers & Operations Research (Elsevier), 2021) Cavero, Sergio; Pardo, Eduardo G.; Laguna, Manuel; Duarte, Abraham
English: The Cyclic Cutwidth Minimization Problem (CCMP) is a Graph Layout Problem that consists of finding an embedding of the vertices of a candidate graph in a host graph, in order to minimize the maximum cut of a host edge. In this case, the host graph is restricted to be a cycle. In this paper, we identify a new lower bound for the problem, and also a property which allows search procedures to drastically reduce the neighborhood size during the search. Additionally, we propose the use of an alternative objective function for min–max optimization problems, never used before in the context of the CCMP. These strategies have been combined within a multistart search procedure for this problem. The obtained method is compared with the state of the art for the CCMP using sets of problem instances previously published. Statistical tests indicate the merit of our proposal. Español: El problema de minimización del ancho de corte cíclico (CCMP) es un problema de grados que consiste en encontrar un embebido de los vértices de un grafo candidato en un grafo huésped, con el fin de minimizar el máximo corte de una arista del grafo huésped. En este caso, el grafo huésped se restringe a ser un ciclo. En este artículo, identificamos una nueva cota inferior para el problema, y también una propiedad que permite a los procedimientos de búsqueda reducir drásticamente el tamaño del vecindario durante la búsqueda. Además, proponemos el uso de una función objetivo alternativa para los problemas de optimización min-max, nunca utilizada antes en el contexto del CCMP. Estas estrategias se han combinado dentro de un procedimiento de búsqueda multistart para este problema. El método obtenido se compara con el estado del arte para el CCMP utilizando conjuntos de instancias de problemas publicados anteriormente. Las pruebas estadísticas indican el mérito de nuestra propuesta.
Solving a short sea inventory routing problem in the oil industry
(Elsevier, 2024-03) Cavero, Sergio; Laguna, Manuel; Pardo, Eduardo G.
We address an optimization problem related to the minimization of the distribution costs associated with product delivery in the oil industry. Particularly, the problem consists of determining a schedule of shipments from production ports to satisfy demand and desired inventory limits at consumptions ports. Products are transported in vessels, which can be viewed as a set of shared resources. The complexity of the problem derives from the problem structure and the number of decisions that need to be made throughout a planning horizon. The context that we studied belongs to the family of short sea inventory routing problems for which the ports are in the same geographical area. We formulate a mixed-integer programming model that captures the most relevant features of the real system. The main decisions include the selection of the vessels that will be used, the paths that each vessel will follow, and the quantities of each product loaded and unloaded at each port visited during the planning horizon. We test the limits of our mathematical programming formulation and develop a heuristic approach for tackling problem sizes that exceed the capabilities of a commercial solver