共查询到20条相似文献,搜索用时 0 毫秒
1.
Luciana S. Buriol Michael J. Hirsch Panos M. Pardalos Tania Querido Mauricio G. C. Resende Marcus Ritt 《Optimization Letters》2010,4(4):619-633
One of the main goals in transportation planning is to achieve solutions for two classical problems, the traffic assignment
and toll pricing problems. The traffic assignment problem aims to minimize total travel delay among all travelers. Based on
data derived from the first problem, the toll pricing problem determines the set of tolls and corresponding tariffs that would
collectively benefit all travelers and would lead to a user equilibrium solution. Obtaining high-quality solutions for this
framework is a challenge for large networks. In this paper, we propose an approach to solve the two problems jointly, making
use of a biased random-key genetic algorithm for the optimization of transportation network performance by strategically allocating
tolls on some of the links of the road network. Since a transportation network may have thousands of intersections and hundreds
of road segments, our algorithm takes advantage of mechanisms for speeding up shortest-path algorithms. 相似文献
2.
Takeo Ojika Satoshi Watanabe Taketomo Mitsui 《Journal of Mathematical Analysis and Applications》1983,96(2):463-479
T. Ojika, S. Watanabe, and T. Mitsui (in preparation) have been developing a subroutine package NAES (Nonlinear Algebraic Equations Solver) for the numerical solutions of the system of nonlinear equations. An algorithm, in the package, termed the deflation algorithm, for determining multiple roots for a system of nonlinear equations, is presented and its effectiveness is shown by solving a numerical example. 相似文献
3.
Thiago F. Noronha Mauricio G. C. Resende Celso C. Ribeiro 《Journal of Global Optimization》2011,50(3):503-518
The problem of routing and wavelength assignment in wavelength division multiplexing optical networks consists in routing
a set of lightpaths and assigning a wavelength to each of them, such that lightpaths whose routes share a common fiber are
assigned different wavelengths. This problem was shown to be NP-hard when the objective is to minimize the total number of
wavelengths used. We propose a genetic algorithm with random keys for routing and wavelength assignment with the goal of minimizing
the number of different wavelengths used in the assignment. This algorithm extends the best heuristic in the literature by
embedding it into an evolutionary framework. Computational results show that the new heuristic improves the state-of-the-art
algorithms in the literature. 相似文献
4.
Mauricio G. C. Resende Rodrigo F. Toso José Fernando Gonçalves Ricardo M. A. Silva 《Optimization Letters》2012,6(4):605-619
We present a biased random-key genetic algorithm (BRKGA) for finding small covers of computationally difficult set covering
problems that arise in computing the 1-width of incidence matrices of Steiner triple systems. Using a parallel implementation
of the BRKGA, we compute improved covers for the two largest instances in a standard set of test problems used to evaluate
solution procedures for this problem. The new covers for instances A
405 and A
729 have sizes 335 and 617, respectively. On all other smaller instances our algorithm consistently produces covers of optimal
size. 相似文献
5.
In this paper, we investigate a resource-constrained project scheduling problem with flexible resources. This is an \(\mathcal {NP}\)-hard combinatorial optimization problem that consists of scheduling a set of activities requiring specific resource units of several skills. The goal is to minimize the makespan of the project. We propose a biased random-key genetic algorithm for computing feasible solutions for the referred problem. We study different decoding mechanisms: an already existing method in the literature, a new adapted serial scheduling generation scheme, and a combination of both. The new procedure is tested using a set of benchmark instances of the problem. The results provide strong evidence that the new heuristic is robust and yields high-quality feasible solutions. 相似文献
6.
Luciana S. Pessoa Andréa C. Santos Mauricio G. C. Resende 《Optimization Letters》2017,11(7):1371-1384
Hubs are facilities used to treat and dispatch resources in a transportation network. The objective of Hub Location Problems (HLP) is to locate a set of hubs in a network and route resources from origins to destinations such that the total cost of attending all demands is minimized. In this paper, we investigate a particular HLP, called the Tree of Hubs Location Problem in which hubs are connected by means of a tree and the overall network infrastructure relies on a spanning tree. This problem is particularly interesting when the total cost of building the hub backbone is high. We propose a biased random key genetic algorithm for solving the tree of hubs location problem. Computational results show that the proposed heuristic is robust and effective to this problem. The method was able to improve best known solutions of two benchmark instances used in the experiments. 相似文献
7.
In this paper, a class of parameter-free filled functions is proposed for solving box-constrained system of nonlinear equations. Firstly, the original problem is converted into an equivalent global optimization problem. Subsequently, a class of parameter-free filled functions is proposed for solving the problem. Some properties of the new class of filled functions are studied and discussed. Finally, an algorithm which neither computes nor explicitly approximates gradients during minimizing the filled functions is presented. The global convergence of the algorithm is also established. The implementation of the algorithm on several test problems is reported with satisfactory numerical results. 相似文献
8.
9.
Beong In Yun 《Applied mathematics and computation》2010,217(2):599-606
In this paper, to estimate a multiple root p of an equation f(x) = 0, we transform the function f(x) to a hyper tangent function combined with a simple difference formula whose value changes from −1 to 1 as x passes through the root p. Then we apply the so-called numerical integration method to the transformed equation, which may result in a specious approximate root. Furthermore, in order to enhance the accuracy of the approximation we propose a Steffensen-type iterative method, which does not require any derivatives of f(x) nor is quite affected by an initial approximation. It is shown that the convergence order of the proposed method becomes cubic by simultaneous approximation to the root and its multiplicity. Results for some numerical examples show the efficiency of the new method. 相似文献
10.
Beong In Yun 《Journal of Computational and Applied Mathematics》2011,235(5):1553-1555
For a nonlinear equation f(x)=0 having a multiple root we consider Steffensen’s transformation, T. Using the transformation, say, Fq(x)=Tqf(x) for integer q≥2, repeatedly, we develop higher order iterative methods which require neither derivatives of f(x) nor the multiplicity of the root. It is proved that the convergence order of the proposed iterative method is 1+2q−2 for any equation having a multiple root of multiplicity m≥2. The efficiency of the new method is shown by the results for some numerical examples. 相似文献
11.
Ramandeep Behl Fiza Zafar Moin-ud-Din Junjua Ali Saleh Alshomrani 《Mathematical Methods in the Applied Sciences》2020,43(5):2421-2443
In most of the earlier research for multiple zeros, in order to obtain a new iteration function from the existing scheme, the usual practice is to make no change at the first substep. In this paper, we explore the idea that what are the advantages if the flexibility of choice is also given at the first substep. Therefore, we present a new two-point sixth-order scheme for multiple roots (m>1). The main advantages of our scheme over the existing schemes are flexibility at both substeps, simple body structure, smaller residual error, smaller error difference between two consecutive iterations, and smaller asymptotic error constant. The development of the scheme is based on midpoint formula and weight functions of two variables. We compare our methods with the existing methods of the same order with real-life applications as well as standard test problems. From the numerical results, we find that our methods can be considered as better alternates for the existing methods of the same order. Finally, dynamical study of the proposed schemes is presented that confirms the theoretical results. 相似文献
12.
This paper presents a fifth-order iterative method as a new modification of Newton’s method for finding multiple roots of
nonlinear equations with unknown multiplicity m. Its convergence order is analyzed and proved. Moreover, several numerical examples demonstrate that the proposed iterative
method is superior to the existing methods. 相似文献
13.
To solve nonlinear system of equation, F(x) = 0, a continuous Newton flow x t (t) = V (x) = ?(DF(x))?1 F(x), x(0) = x 0 and its mathematical properties, such as the central field, global existence and uniqueness of real roots and the structure of the singular surface, are studied. We concisely introduce random Newton flow algorithm (NFA) for finding all roots, based on discrete Newton flow x j+1 = x j + hV (x j ) with random initial value x 0 and h ∈ (0, 1], and three computable quantities, g j , d j and K j . The numerical experiments with dimension n = 300 are provided. 相似文献
14.
Linton C. Freeman 《The Journal of mathematical sociology》2013,37(4):227-241
A new solution to the old problem of partitioning a matrix of social proximities into groups is proposed. It draws on a heuristic developed in computer science, the simple genetic algorithm. The algorithm is described and its utility is demonstrated with applications to three standard data sets. 相似文献
15.
It is well known that it is an ill-posed problem to decide whether a function has a multiple root. Even for a univariate polynomial
an arbitrary small perturbation of a polynomial coefficient may change the answer from yes to no. Let a system of nonlinear
equations be given. In this paper we describe an algorithm for computing verified and narrow error bounds with the property
that a slightly perturbed system is proved to have a double root within the computed bounds. For a univariate nonlinear function
f we give a similar method also for a multiple root. A narrow error bound for the perturbation is computed as well. Computational
results for systems with up to 1000 unknowns demonstrate the performance of the methods. 相似文献
16.
This paper concentrates on iterative methods for obtaining the multiple roots of nonlinear equations. Using the computer algebra system Mathematica, we construct an iterative scheme and discuss the conditions to obtain fourth-order methods from it. All the presented fourth-order methods require one-function and two-derivative evaluation per iteration, and are optimal higher-order iterative methods for obtaining multiple roots. We present some special methods from the iterative scheme, including some known already. Numerical examples are also given to show their performance. 相似文献
17.
Numerical Algorithms - The initiation of iterations and the encounters of all of its solutions are two of the main problems that are derived from iterative methods. These are produced within... 相似文献
18.
Fiza Zafar Alicia Cordero Juan R. Torregrosa 《Mathematical Methods in the Applied Sciences》2020,43(14):7869-7884
Newton-Raphson method has always remained as the widely used method for finding simple and multiple roots of nonlinear equations. In the past years, many new methods have been introduced for finding multiple zeros that involve the use of weight function in the second step, thereby, increasing the order of convergence and giving a flexibility to generate a family of methods satisfying some underlying conditions. However, in almost all the schemes developed over the past, the usual way is to use Newton-type method at the first step. In this paper, we present a new two-step optimal fourth-order family of methods for multiple roots (m > 1). The proposed iterative family has the flexibility of choice at both steps. The development of the scheme is based on using weight functions. The first step can not only recapture Newton's method for multiple roots as special case but is also capable of defining new choices of first step. A stability analysis of some particular cases is also given to explain the dynamical behavior of the new methods around the multiple roots and decide the best values of the free parameters involved. Finally, we compare our methods with the existing schemes of the same order with a real life application as well as standard test problems. From the numerical results, we find that our methods can be considered as a better alternative for the existing procedures of same order. 相似文献
19.
In this paper, we present a new fourth-order method for finding multiple roots of nonlinear equations. It requires one evaluation of the function and two of its first derivative per iteration. Finally, some numerical examples are given to show the performance of the presented method compared with some known third-order methods. 相似文献
20.
For an equation f(x)=0 having a multiple root of multiplicity m>1 unknown, we propose a transformation which converts the multiple root to a simple root of H(x)=0. The transformed function H(x) of f(x) with a small >0 has appropriate properties in applying a derivative free iterative method to find the root. Moreover, there is no need to choose a proper initial approximation. We show that the proposed method is superior to the existing methods by several numerical examples. 相似文献