Pasar al contenido principal

Resultados relacionados

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

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

A Partial Allocation Local Search Matheuristic for Solving the School Bus Routing Problem with Bus Stop Selection

  • Calvete, H.I.
  • Gale, C.
  • Iranzo, J.A.
  • Toth, P.
This paper addresses the school bus routing problem with bus stop selection, which jointly handles the problems of determining the set of bus stops to visit, allocating each student to one of these bus stops and computing the routes that visit the selected bus stops, so that the total routing cost is minimized and the walking distance of the students is limited by a given value. A fast and efficient matheuristic is developed based on an innovative approach that first partially allocates the students to a set of active stops that they can reach, and computes a set of routes that minimizes the routing cost. Then, a refining process is performed to complete the allocation and to adapt the routes until a feasible solution is obtained. The algorithm is tested on a set of benchmark instances. The computational results show the efficiency of the algorithm in terms of the quality of the solutions yielded and the computing time.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Washing machine dynamic model to prevent tub collision during transient state

  • Sánchez-Tabuenca, B.
  • Galé, C.
  • Lladó, J.
  • Albero, C.
  • Latre, R.
In horizontal-axis washing machines, the front gasket as well as the damping system are crucial owing to the possible collision of the tub with the housing during the transient period. However, most dynamic models for predicting tub motion focus on the steady state and consider only the suspension system without including the gasket. We conducted an experimental study to analyze the effect of the gasket on the transient motion of the tub. The results obtained indicate the necessity of implementing the gasket in the multibody model of a washing machine to accurately predict the tub behavior during this period. The gasket model is formed by a combination of Voigt elements. Stiffness parameters are determined using a load cell, and damping factors are estimated using a process that integrates Adams/View, Matlab optimization algorithms, and displacement measurements that are taken using accelerometers. A D-optimal design used to predict the effect of the gasket parameters reveals that the tub displacement is most sensitive to the changes in linear stiffness in the transversal direction. Finally, the model of the gasket provides a better approach for predicting the tub movement during resonance that can be used in the design phase to avoid tub collision.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

On the integration of Cid''s radial intermediary

  • Abad, A.
  • Calvo, M.
  • Elipe, A.
This paper deals with the integrations of homogeneous quasi-Keplerian Hamiltonians, that is, perturbed Kepler Hamiltonians which perturbation is of the form SUM j=2 N Aj/rj with Aj constant. Although there are many applications of these Hamiltonians in Physics, Astronomy and Astrodynamics, we focus our interest on a particular case in the core of Artificial Satellite Theory, the Cid's radial intermediary. For this problem, we integrate the equations of motion in two different ways, by means of the elliptic P-Weierstrass function and by using the Krylov–Bogoliubov averaging method to integrate a perturbed harmonic oscillator. In this case, the resulting solution is given in terms of the classical Kepler's equation, with no need of introducing more complex generalized Kepler's equation.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

A decision tool based on bilevel optimization for the allocation of water resources in a hierarchical system

  • Calvete, Herminia I.
  • Galé, Carmen
  • Iranzo, José A.
  • Mateo, Pedro M.
This paper addresses the optimal allocation of water among competing stakeholders during a finite planning horizon. We focus on those water systems where there are two levels of decision making organized according to a hierarchical framework. At the upper level, a central authority allocates water to demand points having regard to environmental and sustainability issues as well as balancing water users' supply/demand. At the lower level of the hierarchy, demand point managers allocate water to users prioritizing economic strategies. On the other hand, when it comes to allocating limited resources that affect public welfare, the authority in charge can also use different political instruments such as fees to influence the decisions made at those levels of decision making that are not directly within its competence. We propose a multiobjective multifollower bilevel optimization problem that aims to fulfill the central authority goals while including the reaction of the demand point managers in terms of optimization problems as constraints. Using the well-known Karush–Kuhn–Tucker approach, we transform the bilevel model into an equivalent multiobjective mixed-integer single-level model for which we provide tight big-M values. For the purpose of showing the versatility of the model, extensive computational experiments on a set of instances have been carried out. The results show that the optimization problem can be solved to optimality in small computing times using off-the-shelf mixed-integer solvers even for complex water systems and long planning periods. In addition, they illustrate the effect of imposing fees on the achievement of the central authority's objectives.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Accurate computations with Wronskian matrices of Bessel and Laguerre polynomials

  • Mainar, E.
  • Peña, J.M.
  • Rubio, B.
This paper provides an accurate method to obtain the bidiagonal factorization of Wronskian matrices of Bessel polynomials and of Laguerre polynomials. This method can be used to compute with high relative accuracy their singular values, the inverse of these matrices, as well as the solution of some related systems of linear equations. Numerical examples illustrating the theoretical results are included. © 2022 The Authors
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Depth of almost strictly sign regular matrices

  • Alonso, Pedro
  • Jiménez, Jorge
  • Peña, Juan Manuel
  • Serrano, María Luisa
The concept of depth of an almost strictly sign regular matrix is introduced and used to simplify some algorithmic characterizations of these matrices.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Total positivity and accurate computations with Gram matrices of Bernstein bases

  • Mainar, E.
  • Peña, J. M.
  • Rubio, B.
In this paper, an accurate method to construct the bidiagonal factorization of Gram (mass) matrices of Bernstein bases of positive and negative degree is obtained and used to compute with high relative accuracy their eigenvalues, singular values and inverses. Numerical examples are included.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

On the numerical integration of an explicit solution of the homologous collapse’s radial evolution in time

  • Calvo, Manuel
  • Elipe, Antonio
  • Rández, Luis
In a recent paper, Slepian and Philcox derive an explicit solution of the homologous collapse from rest of a uniform density sphere under its self-gravity as a function of time. Their solution is given in terms of two curvilinear integrals along a suitable Jordan contour; in practice, it must be approximated by a quadrature rule. The aim of this paper is to examine how the choice of the contour and the quadrature rule affects the accuracy and the efficiency of this integral solution approximation. More precisely, after a study of the complex roots of a transcendental equation that relates time with the variable, some alternative Jordan contours that turn out to be more convenient are proposed. Then, by using as quadrature rule the composite trapezoidal rule because of its reliability and spectral convergence accuracy, some numerical experiments are presented to show that the combination of contours and quadrature rule allows us to obtain numerical results with high accuracy and low computational cost.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Accurate computations with matrices related to bases {tie¿t}

  • Mainar, E.
  • Peña, J. M.
  • Rubio, B.
The total positivity of collocation, Wronskian and Gram matrices corresponding to bases of the form (eλt,teλt,…,tneλt) is analyzed. A bidiagonal decomposition providing the accurate numerical resolution of algebraic linear problems with these matrices is derived. The numerical experimentation confirms the accuracy of the proposed methods.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Accurate and efficient computations with Wronskian matrices of Bernstein and related bases

  • Mainar, Esmeralda
  • Peña, Juan M.
  • Rubio, Beatriz
In this article, we provide a bidiagonal decomposition of the Wronskian matrices of Bernstein bases of polynomials and other related bases such as the Bernstein basis of negative degree or the negative binomial basis. The mentioned bidiagonal decompositions are used to achieve algebraic computations with high relative accuracy for these Wronskian matrices. The numerical experiments illustrate the accuracy obtained using the proposed decomposition when computing inverse matrices, eigenvalues or singular values, and the solution of some related linear systems. © 2021 John Wiley & Sons Ltd.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

The school bus routing problem with student choice: a bilevel approach and a simple and effective metaheuristic

  • Calvete, H.I.
  • Galé, C.
  • Iranzo, J.A.
  • Toth, P.
The school bus routing problem (SBRP) involves interrelated decisions such as selecting the bus stops, allocating the students to the selected bus stops, and designing the routes for transporting the students to the school taking into account the bus capacity constraint, with the objective of minimizing the cost of the routes. This paper addresses the SBRP when the reaction of students to the selection of bus stops is taken into account, that is, when students are allowed to choose the selected bus stop that best suits them. A bilevel optimization model with multiple followers is formulated, and its transformation into a single-level mixed integer linear programming (MILP) model is proposed. A simple and effective metaheuristic algorithm is also developed to solve the problem. This algorithm involves solving four MILP problems at the beginning, which can be used to obtain tight upper bounds of the optimal solution. Extensive computational experiments on SBRP benchmark instances from the literature show the effectiveness of the proposed algorithm in terms of both the quality of the solution found and the required computing time.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

On the integral solution of elliptic Kepler’s equation

  • Calvo, M.
  • Elipe, A.
  • Rández, L.
In a recent paper, Philcox, Goodman and Slepian obtain an explicit solution of the elliptic Kepler’s equation (KE) as a quotient of two contour integrals along a Jordan curve C=C(M,e) that contains the unique real solution of KE but not includes other complex zeros of KE in its interior. The aim of this paper is to study the main issues that arise in the practical implementation of this integral solution. Thus, after a study of the complex zeros of KE, several families of Jordan contours C=C(M,e) that are suitable for this integral solution are proposed. Since contours with minimal length turn out to be the more accurate for numerical purposes, several families that minimize their length are constructed. Secondly, the approximation of the contour integrals by the composite trapezoidal rule is considered. Recall that this rule is employed in the fast Fourier transform and, in spite of its lower order, displays a spectral convergence as a function of the number of nodes, which implies a very fast convergence. Finally, the results of some numerical experiments are presented to show that such a combination of appropriate contours with the composite trapezoidal rule leads to a powerful numerical method to solve KE with any desired accuracy for all values of eccentricity.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

A biobjective model for resource provisioning in multi-cloud environments with capacity constraints

  • Brotcorne, Luce
  • Ezpeleta, Joaquín
  • Galé, Carmen
Private and public clouds are good means for getting on-demand intensive computing resources. In such a context, selecting the most appropriate clouds and virtual machines (VMs) is a complex task. From the user’s point of view, the challenge consists in efficiently managing cloud resources while integrating prices and performance criteria. This paper focuses on the problem of selecting the appropriate clouds and VMs to run bags-of-tasks (BoT): big sets of identical and independent tasks. More precisely, we define new mathematical optimization models to deal with the time of use of each VMs and to jointly integrate the execution makespan and the cost into the objective function through a bi-objective problem. In order to provide trade-off solutions to the problem, we propose a lexicographic approach. In addition, we introduce, in two different ways, capacity constraints or bounds on the number of VMs available in the clouds. A global limit on the number of VMs or resource constraints at each time period can be defined. Computational experiments are performed on a synthetic dataset. Sensitivity analysis highlights the effect of the resource limits on the minimum makespan, the effect of the deadline in the total operation cost, the impact of considering instantaneous capacity constraints instead of a global limit and the trade-off between the cost and the execution makespan.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Gaussian Markov Random fields and totally positive matrices

  • Baz, Juan
  • Alonso, Pedro
  • Peña, Juan Manuel
  • Pérez-Fernández, Raúl
The present paper focuses on the study of the conditions under which the covariance matrix of a multivariate Gaussian distribution is totally positive, paying particular attention to multivariate Gaussian distributions that are Gaussian Markov Random Fields. More specifically, it is proven that, if the graph over which the Gaussian Markov Random Field is defined consists of path graphs and the covariances between adjacent variables on the graph are non-negative, then there always exists a reordering of the variables that renders the resulting covariance matrix totally positive. Moreover, this reordering is identified and some cases for which the conditions for the covariance matrix of a multivariate Gaussian distribution to be totally positive are necessary and sufficient are provided.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

An evaluation algorithm for q-Bézier triangular patches formed by convex combinations

  • Delgado, J.
  • Orera, H.
  • Peña, J.M.
An extension to triangular domains of the univariate q-Bernstein basis functions is introduced and analysed. Some recurrence relations and properties such as partition of unity and degree elevation are proved for them. It is also proved that they form a basis for the space of polynomials of total degree less than or equal to n on a triangle. In addition, it is presented a de Casteljau type evaluation algorithm whose steps are all linear convex combinations.
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)

Approaching the Pareto Front in a Biobjective Bus Route Design Problem Dealing with Routing Cost and Individuals’ Walking Distance by Using a Novel Evolutionary Algorithm

  • Calvete, Herminia I.
  • Galé, Carmen
  • Iranzo, José A.
This paper addresses a biobjective bus routing problem that pays attention to both the routing cost and the total distance walked by the individuals to reach their assigned pickup point. These two objectives are conflicting. Generally, the less the individuals walk, the more the number of visited pickup points and so the more the routing cost. In addition, the problem deals with finding the set of pickup points visited among the set of potential locations, identifying the set of individuals assigned to each visited pickup point, and designing the bus routes. Taking into account the highly combinatorial nature of the problem, an evolutionary algorithm is proposed to approach the associated Pareto front. Its main novelties are twofold. The first is the way in which the chromosomes are encoded since they only provide information about the number of routes and the visited pickup points. The second novelty lies in the procedure to construct a feasible solution from the chromosome, which involves a heuristic and several local search procedures to improve both objective functions. Computational experiments are carried out to check the performance of the algorithm in terms of the quality of the Pareto front yielded.
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.