Pasar al contenido principal

METODOLOGIAS PARA LA BUSQUEDA DE SOLUCIONES EN PROBLEMAS CON CRITERIOS ECONOMICOS, SOCIALES Y MEDIOAMBIENTALES. HACIA UNA ECONOMIA CIRCULAR

PID2022-139543OB-C43

•
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 2022
Plan Estatal 2021-2023 Plan Estatal de Investigación Científica y Técnica y de Innovación
Centro beneficiario UNIVERSIDAD DE ZARAGOZA

Resultados relacionados

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

Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Balancing the cardinality of clusters with a distance constraint: a fast algorithm

  • Calvete, Herminia I.
  • Galé, Carmen
  • Iranzo, José A.
Logistics companies partition the customers they serve into delivery zones as a tactical decision and manage the customers assigned to each zone as a cluster for the purpose of routing, workload allocation, etc. Frequently, this partition is made in accordance with customers’ geographical location, which can result in very unbalanced clusters in terms of the number of customers they include. In addition, in the day-to-day operations, not necessarily all customers need to be served every day so, even if the clusters originally created are balanced, daily needs may lead to unbalanced clusters. Given an a priori assignment of customers to clusters, improving the balance between clusters in advance of workload management is therefore a key issue. This paper addresses the problem of balancing clusters, when there is a distance constraint that prevents reassigning customers to clusters far away from their original pre-assignment. This problem is formulated as a lexicographic biobjective optimization model. The highest priority objective function minimizes the variance of the number of customers in the clusters. The second ranked objective function minimizes the total distance resulting from all reassignments. A fast and effective heuristic algorithm is developed, based on exploring customer reassignments, either by comparing clusters two by two or by extending the search to allow for sequential customer swaps among clusters. Both the quality of the solution and the computational time required encourage the use of this algorithm by logistics companies to balance clusters in real scenarios.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

A Bilevel Approach to the Facility Location Problem with Customer Preferences Under a Mill Pricing Policy

  • Calvete, Herminia I.
  • Galé, Carmen
  • Hernández, Aitor
  • Iranzo, José A.
This paper addresses the facility location problem under a mill pricing policy, integrating customers’ behavior through the concept of preferences. The problem is modeled as a bilevel optimization problem, where the existence of ties in customers’ preferences can lead to an ill-posed bilevel problem due to the possible existence of multiple optima to the lower-level problem. As the commonly employed optimistic and pessimistic strategies are inadequate for this problem, a specific approach is proposed bearing in mind the customers’ rational behavior. In this work, we propose a novel formulation of the problem as a bilevel model in which each customer faces a lexicographic biobjective problem in which the preference is maximized and the total cost of accessing the selected facility is minimized. This allows for a more accurate representation of customer preferences and the resulting decisions regarding facility location and pricing. To address the complexities of this model, we apply duality theory to the lower-level problems and, ultimately, reformulate the bilevel problem as a single-level mixed-integer optimization problem. This reformulation incorporates big-M constants, for which we provide valid bounds to ensure computational tractability and solution quality. The computational study conducted allows us to assess, on the one hand, the effectiveness of the proposed reformulation to address the bilevel model and, on the other hand, the impact of the length of the customer preference lists and fixed opening cost for facilities on the computational time and the optimal solution.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

An iterated greedy‐based metaheuristic with local search for the rank pricing problem

  • Calvete, Herminia I.
  • Galé, Carmen
  • Hernández, Aitor
  • Iranzo, José A.
The rank pricing problem involves determining optimal prices for a set of products while accounting for customers' budgets and preferences. This study develops an iterated greedy‐based metaheuristic to efficiently solve this problem. The core idea is to generate a sequence of solutions by iteratively applying destruction and reconstruction phases. In this process, some components of a solution are removed, yielding partial solutions from which complete solutions are reconstructed. A local search method with three neighborhood exploration strategies is then applied. Computational experiments demonstrate the effectiveness of the proposed algorithm by comparing its performance with exact and heuristic methods from the literature. It consistently finds optimal or near‐optimal solutions for instances with known optima. For most cases where the optimal solution is unknown, the algorithm matches or outperforms the best‐known solutions. Moreover, it achieves these results with significantly lower computational times, reinforcing its suitability for solving the rank pricing problem.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

A novel approach to pessimistic bilevel problems. An application to the rank pricing problem with ties

  • Calvete, Herminia I.
  • Galé, Carmen
  • Hernández, Aitor
  • Iranzo, José A.
This paper introduces a novel method to address the pessimistic approach to the bilevel problem. It consists of considering a lexicographic biobjective optimization problem at the lower level. To emphasize the significance of this approach, we implement it in the context of the Rank Pricing Problem with Ties. This problem can be formulated as a bilevel problem that inherently demands the use of the pessimistic approach. Considering the properties of the lexicographic biobjective problem involved, we formulate this problem as a single level mixed integer optimization problem, deriving also valid values for the big-Ms involved and valid inequalities for this formulation. The computational experiment carried out confirms the relevance of the proposed method.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Generalized Capacitated Vertex Separator Problem: Models and Algorithms

  • Anglada, Sergio
  • Galé, Carmen
  • Salazar-González, Juan José
Given an undirected graph and two numbers q and b, the Capacitated Vertex Separation Problem (CVSP) looks for a vertex subset of minimum cardinality such that the connected components in the subgraph generated after the vertex removal can be packed into no more than q bins of cardinality at most b. This problem has been studied in graph theory, and most of the success in solving it is due to the hypothesis that the objective function minimizes the number of deleted vertices, that is, each node removal contributes identically to the objective function. In our work, this hypothesis is relaxed so each vertex has a cost and a weight, and the problem aims to minimize the total cost of the removed vertices while the total vertex weight in each bin is within the given capacity b, still limiting the number of bins to at most q. We introduce several mathematical formulations for the new problem, called the Generalized Capacitated Vertex Separator Problem (GCVSP), and analyze the performance of algorithms based on such formulations.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

An exact and computationally efficient algorithm for balanced customer clustering under relocation constraints

  • Calvete, Herminia I.
  • Galé, Carmen
  • Iranzo, José A.
In logistics, customer clusters are often predefined based on geographic locations to optimize resource management and workload distribution. However, this approach frequently leads to significant cluster imbalance, particularly when not all customers require daily service or when operational constraints restrict the possibility of reallocating customers across clusters. These imbalances may affect workload equity, routing efficiency, and overall service performance. This paper addresses the problem of balancing customer clusters under relocation constraints by introducing two alternative criteria for measuring imbalance and enforcing them within a constrained reassignment framework. Our goal is to redistribute the set of customers so as to construct new clusters whose cardinalities are as balanced as possible while fully respecting the reassignment limitations. After formulating both nonlinear optimization models, we propose an exact algorithm that systematically reallocates customers through sequences of feasible moves, thereby ensuring progress toward a balanced configuration. We provide formal proofs showing that the algorithm always converges to an optimal solution for both imbalance criteria after a finite number of iterations. From these results, it follows that both models yield the same optimal solution. In addition, computational experiments demonstrate the efficiency of the method, showing that optimal solutions are obtained with very low running times for large-scale instances.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

A high-performance hybrid metaheuristic for the survivable one-fault-tolerant ring star problem

  • Calvete, Herminia I.
  • Galé, Carmen
  • Hernández, Aitor
  • Iranzo, José A.
The Ring Star Problem (RSP) arises in the design of communication and distribution networks that combine a ring connecting a subset of nodes, called hubs, that includes the depot, with star-shaped assignments of the remaining nodes, called terminals, to the hubs. To address survivability issues in such networks, the 1-Survivable Ring Star Problem (1-S-RSP) extends the classical RSP by enforcing survivability against the failure of at most one node, which means preserving the ring–star structure via the inclusion of additional edges and arcs. The resulting problem is computationally challenging due to the strong interdependence among ring construction, node assignments, and survivability requirements. In this paper, a hybrid metaheuristic based on evolutionary algorithms is proposed to efficiently solve the 1-S-RSP. The algorithm relies on a compact chromosome representation that encodes only hub-related information, while complete feasible solutions are constructed through dedicated procedures that determine the ring structure, backup edges, and terminal-to-hub assignments. The method is further enhanced by problem-specific local search mechanisms, including 2-opt and 3-opt backup procedures that explicitly account for survivability considerations. An extensive computational study is conducted on benchmark instances. After tuning the main design parameters of the algorithm, the proposed approach is evaluated against the best feasible solutions reported in the literature. The results show that the hybrid metaheuristic consistently produces solutions of comparable or superior quality, while requiring significantly shorter computing times. These outcomes demonstrate the effectiveness of the proposed method for addressing large-scale instances of the 1-S-RSP and highlight its potential for practical applications in survivable network design.