Search results for "OPTIMIZATION"
showing 10 items of 2824 documents
A computational study of several heuristics for the DRPP
1995
The problem of designing a route of minimum length for a postman that starts and finishes at his office and has to deliver the mail along a set of streets in a city is known as the Rural Postman Problem. When the postman has to obey the directions of the streets, we have the directed version of this problem. Finding an exact solution, in the general case, is intractably difficult. Hence, we have implemented three heuristic algorithms for approximately solving this problem and a procedure for obtaining a lower bound to the optimal length. Also, we present numerical experimentations based on a collection of random instances with up to 30 connected components, 240 vertices and 801 arcs. A lowe…
Bifurcations of Reachable Sets Near an Abnormal Direction and Consequences
2007
We describe precisely, under generic conditions, the contact and the bifurcations of the reachable set at time T along an abnormal direction, first for a single-input affine control system with constraint on the control, and then as an application for a sub-Riemannian system of rank 2. As a consequence we obtain in sub-Riemannian geometry a new splitting-up of the sphere near an abnormal minimizer γ into two sectors, bordered by the first Pontryagin’s cone along γ, called the L ∞-sector and the L 2-sector. Moreover we find again necessary and sufficient conditions of optimality of an abnormal trajectory for such systems, for any optimization problem.
On Automaton Recognizability of Abnormal Extremals
2002
For a generic single-input planar control system $\dot x=F(x)+ u G(x),$ $x\in\mathbb{R}^2,$ $u\in [-1,1]$, $F(0)=0$, we analyze the properties of abnormal extremals for the minimum time stabilization to the origin. We prove that abnormal extremals are finite concatenations of bang arcs with switchings occurring on the set in which the vector fields F and G are collinear. Moreover, all the generic singularities of one parametric family of extremal trajectories near to abnormal extremals are studied. In particular, we prove that all possible sequences of these singularities, and hence all generic abnormal extremals, can be classified by a set of words recognizable by an automaton.
A primal-dual algorithm for the fermat-weber problem involving mixed gauges
1987
We give a new algorithm for solving the Fermat-Weber location problem involving mixed gauges. This algorithm, which is derived from the partial inverse method developed by J.E. Spingarn, simultaneously generates two sequences globally converging to a primal and a dual solution respectively. In addition, the updating formulae are very simple; a stopping rule can be defined though the method is not dual feasible and the entire set of optimal locations can be obtained from the dual solution by making use of optimality conditions. When polyhedral gauges are used, we show that the algorithm terminates in a finite number of steps, provided that the set of optimal locations has nonepty interior an…
Stochastic frontier models using R
2020
Abstract The production function is usually assumed to specify the maximum output obtainable, from a given set of inputs, describing the boundary or frontier of the obtainable output from each feasible combination of input; it relates the production process of individual units to the efficient border of the production possibilities. The measure of the distance of each unit from the border is the most immediate way to assess its (in)efficiency. However, the production function is not generally known, but it has only a set of information on each production unit and it is therefore essential to develop techniques to estimate the production frontier. Starting from the packages already developed…
A Posteriori Methods
1998
A posteriori methods could also be called methods for generating Pareto optimal solutions. After the Pareto optimal set (or a part of it) has been generated, it is presented to the decision maker, who selects the most preferred among the alternatives. The inconveniences here are that the generation process is usually computationally expensive and sometimes in part, at least, difficult. On the other hand, it is hard for the decision maker to select from a large set of alternatives. One more important question is how to present or display the alternatives to the decision maker in an effective way. The working order in these methods is: 1) analyst, 2) decision maker.
Heuristics for the bi-objective path dissimilarity problem
2009
In this paper the path dissimilarity problem is considered. The problem has previously been studied within several contexts, the most popular of which is motivated by the need to select transportation routes for hazardous materials. The aim of this paper is to formally introduce the problem as a bi-objective optimization problem, in which a single solution consists of a set of p different paths, and two conflicting objectives arise, on one hand the average length of the paths must be kept low, and on the other hand the dissimilarity among the paths in the set should be kept high. Previous methods are reviewed and adapted to this bi-objective problem, thus we can compare the methods using th…
A Hierarchy of Twofold Resource Allocation Automata Supporting Optimal Sampling
2009
We consider the problem of allocating limited sampling resources in a "real-time" manner with the purpose of estimating multiple binomial proportions. More specifically, the user is presented with `n ' sets of data points, S 1 , S 2 , ..., S n , where the set S i has N i points drawn from two classes {*** 1 , *** 2 }. A random sample in set S i belongs to *** 1 with probability u i and to *** 2 with probability 1 *** u i , with {u i }. i = 1, 2, ...n , being the quantities to be learnt. The problem is both interesting and non-trivial because while both n and each N i are large, the number of samples that can be drawn is bounded by a constant, c . We solve the problem by first modelling it a…
Fast solution of radial distribution networks with automated compensation and reconfiguration
2000
Abstract Optimal operation of radial distribution networks with automated compensation and reconfiguration requires the solution of a combinatorial optimisation problem, since the variables are the on/off status of capacitor banks and the open/close status of tie-switches. The solution approaches recently proposed use iterative algorithms such as genetic algorithms, simulated annealing and tabu search, for which the network needs to be solved in different configurations and at different compensation levels. The aim of this evaluation is that of attributing a quality index to each solution so that all the solutions can be suitably ordered. In an automated network, any configuration can be ob…
A Maximal-Space Algorithm for the Container Loading Problem
2008
In this paper, a greedy randomized adaptive search procedure (GRASP) for the container loading problem is presented. This approach is based on a constructive block heuristic that builds upon the concept of maximal space, a nondisjoint representation of the free space in a container. This new algorithm is extensively tested over the complete set of Bischoff and Ratcliff problems [Bischoff, E. E., M. S. W. Ratcliff. 1995. Issues in the development of approaches to container loading. Omega 23 377–390], ranging from weakly heterogeneous to strongly heterogeneous cargo, and outperforms all the known nonparallel approaches that, partially or completely, have used this set of test problems. When …