Search

This paper aims at proposing a Constraint-based Learning Estimation of Distribution Algorithm (EDA) to solve the Multi-Mode Resource Constrained Project Scheduling Problem (MMRCPSP). This problem is considered a combinatorial optimization problem and consists of a set of tasks to be carried out in an ordered way, limited availability of resources, and an execution mode for each task. Generally, traditional EDAs handle the constraints of the problem using strategies such as penalty, Pareto dominance, or others, without taking into account these constraints during the learning process. These traditional approaches usually cause the generation of infeasible solutions in each iteration. In this paper, an approach based on the constraints handling during the learning process of the probabilistic model is proposed. To validate the performance of the algorithms, the new approach in two scenarios is compared. First, in the solution of a set of classical optimization problems, where different EDAs are compared in terms of efficiency and efficacy. The second group of experiments is performed on a set of instances of the PSPLIB database. In this case, the proposed algorithm is compared with a traditional EDA and with other results reported in the bibliography. The experimental results demonstrate that the proposal outperforms both the results of traditional EDA and other EDA reported in the literature. [ABSTRACT FROM AUTHOR]

Introduction This paper presents a proposal to apply the meta-heuristic Optimization Based on Variable Meshes (VMO) to the discreet problem of the Traveler Seller (TSP); This model explores the search space to Objective from a population of solutions called mesh that expands and contracts in order to find good quality solutions. In this context, the expansion operator is modified in such a way that it is applicable in a discrete domain, making combinations among the solutions in order to obtain new nodes. Another element that is modified is the clearing operator, which is responsible for maintaining the diversity of the mesh in each interaction. Methodology. A study of VMO model parameters is summarized in this paper, using a set of TSP instances with different characteristics; In addition, it can be observed that the proposal of this work obtains competitive results when compared with other international reference algorithms mentioned in the state of the art. The work is structured as follows: Section 1 describes the fundamental aspects of the TSP study problem. Then, in the second, the general functioning of VMO is explained, in the third one, each of the expansion and contraction operators is defined for the study problem. Later in the fourth section a study of the parameters of the proposal and an experimental comparative analysis with the results obtained with other algorithms mentioned in the state of the art is made. Conclusions Other operators of generation of new nodes were applied in the expansion process, where a combination of solutions is made in order to comply with the restrictions imposed by the problem. [ABSTRACT FROM AUTHOR]

Vehicle Routing Problem with Simultaneous Pickup and Delivery (VRPSPD) is defined as follows: given a set of customers with pickup and delivery demands, a set of vehicles and a depot, the goal is to design least - cost routes originating and terminating at the depot such that all customers are served in single visits and subject to vehicle capacity constraints. The critical feature of the problem is the fluctuating load on the vehicle, thus a route may be not feasible even if the total delivery and the total pickup loads are both below the vehicle's maximum capacity. In this paper, a penalization related to the overload in the routes is included in the objective function and a set of GRASP based methods are proposed. At each iteration, local search is performed using Variable Neighborhood Descent, Random Variable Neighborhood Descent and Simulated Annealing. All strategies were tested using Dethloff benchmark. It was obtained competitive results, it has reached 18 best solutions over 40 intances, in the remaining cases the average gap was arround 0.5 percent. [ABSTRACT FROM AUTHOR]

This paper presents an alternative procedure to solve the Capacitated Vehicle Routing Problem (CVRP) with homogeneous fleet. The paper proposes a two-phase metaheuristic algorithm: routes design and fleet scheduling. The first phase is based on heuristics and metaheuristics procedures in order to build an initial solution that is then improved using tabu search to obtain non-dominated solutions in polynomial computational time. For the second phase, corresponding to fleet scheduling, the problem is approached using an analogy with the identical parallel machine scheduling problem. This procedure looks for the minimization of the fixed cost of using installed capacity as the objective function. The proposed procedure was tested using both a random-generated instance and real data, giving competitive results in comparison with other heuristics tested. [ABSTRACT FROM AUTHOR]

This paper presents algorithms for solving Constraint Satisfaction Problems (CSPs) capable of measure the performance of their process through relevant indicators to enable adaptations (self-adjust). The adaptation options are related to the change of Enumeration Strategy, used when bad performance is detected. Done in this way, to find quickly solutions to different problems, solving one of the limitations on the Enumeration Strategy: "for a given problem, there is a particular strategy that works very well, but limited in the efficient resolution of other problems." The proposal outlined is based on existing approaches, that have been designed with other orientation, such as Adaptive Constraint Satisfaction (ACS), where given a sequence of algorithms to use, bad ones are detected and replaced by the next candidate. However, this paper is not intended to change a complete algorithm, but for the same algorithm, modify the strategy that guides it based on the observation of the set of indicators obtained from the analysis of the search process that is playing. [ABSTRACT FROM AUTHOR]

The flexibility of spectrum usage required by emerging paradigms, radio spectrum demand driven by new wireless technologies, new applications and government policies oriented to massive use of Internet require spectrum management authorities to have smarter tools to do their work in an efficient way. This paper presents the design and implementation of a web application to support spectrum management activities using constraints programming. The design includes a mathematical model for allocation constraints, a mathematical model for interference constraints, a relational database of the National Allocation Table considering bands, channels and services associated with geopolitical division of Colombia, and an operator allocation database. These tools allow creating and to parameterize different levels of restrictions establishing different costs and weights. The interference analysis module takes into account the geographical location and technical characteristics of transmitting stations. The tool developed in this work can be used, among others, in allocation optimization studies, assessing policies of spectrum reallocation, allocation analysis to maximize specific criteria, reducing technology costs of implementing specific technologies and help identifying objective variables for spectrum price estimation. To facilitate the understanding and exploitation of the application several didactic examples are included. [ABSTRACT FROM AUTHOR]

Introduction: The goal of this paper is to illustrate how science can aid and have a positive impact on industrial decision-making problems. The combinatorial optimization problem consists of finding a partition of the set of basic units into territories so as to maximize a unique compactness objective function. The solution must also satisfy several constraints or requirements such as, balancing the different node activity measures among territories and territory contiguity. Method: We present a metaheuristic solution method, called GRASP, to a commercial territory design problem motivated by a real-world application in a beverage distribution firm. The heuristic integrates both construction and local search methods that attempt to intelligently exploit the mathematical structure of the problem. Results: The algorithm has been tested in several data sets. The results show the effectiveness of the proposed approach. GRASP obtained solutions of much better quality (in terms of both its dispersion measure and its feasibility with respect to the balancing constraints) than those found by the firm method in relatively fast computation times. Previous to this work, the company was struggling in obtaining design plans with less than 20% imbalance. The proposed method can always obtain design plans with less than 5% imbalance. Conclusion: It has been illustrated how Operations Research models and techniques can aid decision-making problems, resulting in territory plans of better quality. [ABSTRACT FROM AUTHOR]

To solve the problem of secondary distribution systems planning, this paper proposes a methodology using a tabu search algorithm as a solution technique. The problem is formulated as a nonlinear mixed-integer model, which takes into account the location and capacity of new elements (distribution transformers and primary-secondary distribution networks), relocation of existing distribution transformers, increasing the capacity of existing elements, secondary network reconfiguration, and phase balance. It also considers the costs associated with connections between primary and secondary networks and energy losses in distribution transformers. The methodology is applied to two test cases: in the first, a comparative analysis with the Chu-Beasley genetic algorithm is made to verify the efficiency of the proposed methodology; and in the second, the results are analyzed in a Colombian distribution system. In both cases, the results are of high quality, supporting the proposed methodology. [ABSTRACT FROM AUTHOR]

In this paper the necessary equations for considering existing network reconfiguration in the disjunctive linear model used to solve the problem transmission expansion planning. In the traditional methods used for solving this problem new transmission lines and two-winding transformers are commonly used as expansion candidates. However, reconfiguration of existing network has not been considered as a valid solution in the classical models. The Garver test system and a Colombian system are used to show that considering network reconfiguration can reduce investment costs of the transmission expansion planning problem. This work shows that an optimization model that includes conventional candidates and reconfiguration produces better expansion signals in the transmission lines of electric power systems. [ABSTRACT FROM AUTHOR]

The Vehicle Routing Problem (VRP) involves a major mathematical complexity to solve it. This impedes its use in small and medium size organizations, because an investment in specialized software and trained personnel is required. The methods used to find an optimal solution to the VRP start with an improving workable solution. This initial solution can be generated randomly, calculated by some other method, or even a solution provided by the user can also be used. In this paper, we present an algorithm to obtain a feasible solution to the problem of VRP called Mass Center Method (MCM). The method is easy to perform and its performance differs little from the final solutions generated by commercial algorithms, therefore, it could be used as an approximation to the solution of the problem. This can help to extend the application of the VRP. [ABSTRACT FROM AUTHOR]

This paper presents a methodology to reduce energy losses in primary distribution networks, considering a combined algorithm which involves the optimal reconfiguration of the system and phase balance. The mathematical model is nonlinear mixed integer, which takes into account the investment and operating costs of the network, subject to a set of technical constraints imposed by the system. To solve the problem of reconfiguration and phase balance algorithms are used Simulated Annealing and Ant Colony, respectively. The algorithm is tested on IEEE 37 node feeder. [ABSTRACT FROM AUTHOR]

In this paper a method to solve the state estimation problem in electric systems applying combinatorial optimization is presented. Its objective is the study of measures with difficult detection errors, which affect the performance and quality of the results when a classic state estimator is used. Due to the mathematical complexity, sensibility indicators are deduced from the theory of leverage points used in the Chu-Beasley optimization algorithm with the purpose of reducing the computational effort and enhance the quality of the results. The proposed method is validated in a 30-node IEEE system. [ABSTRACT FROM AUTHOR]

A key objective of any distributor or producer / distributor either a traditional or ebussines.com company is to achieve efficient distribution. Understood like efficient, to serve to customer with: the required quality, at the appointed time and at the lowest differentiation, which allows companies to stay in the competition. This last feature reveals the character multicriterio of distribution: on the one hand are the interests of the producer / distributor and the other the interests of clients, these criteria are usually in conflict. In the present paper shows the solution of Vehicle Routing Problem with multi-criteria approach using different methods in multicriteria discrete spaces in order to compare the results obtained by each of them and determine if there are significant differences between these, considering various factors such as talkative preference, evaluation of alternatives for each criterion depending on the method, facilities for implementation, among others. [ABSTRACT FROM AUTHOR]

This paper presents a methodology to solve the problem of distribution system planning, using a multi-objective optimization technique. In the proposed model the location and design of new elements and the upgrading of existing elements are considered. In the problem approach, investment and operation costs and network reliability are included in the objective function. This research topic is relevant to the electricity distribution companies, as it allows for new tools that bring the problem to real situations, such as considering multiple objectives, which has a positive impact on the finances and on operation of the system. In the model solution, an elitist non-dominated sorting algorithm (NSGA-II) is used, and to verify its efficiency a case of specialized literature is used, which corresponds to a distribution network of an electrical system. [ABSTRACT FROM AUTHOR]

This paper studied the permutation flowshop with sequence dependent setup times and makespan minimization. An ant colony algorithm which turns the original problem into an asymmetric TSP (Traveling Salesman Problem) structure is presented, and applied to problems proposed in the literature and is compared with an adaptation of the NEH heuristic. Subsequently a neighborhood search was applied to the solution obtained by the ACO algorithm and the NEH heuristic. [ABSTRACT FROM AUTHOR]

This paper presents an innovating Monte Carlo method for exploring n-dimensional non-linear functions defined in a compact domain which is transformed to the hypercube [0;1]n. This approach uses the beta distribution for generating random samples. Te distribution parameters, named alpha and beta, are dynamically adjusted so that, in the first iterations, the beta distribution looks like the uniform distribution. ; in the last iterations, the beta distribution is centered in the known minimum and the variance is near zero, so that only the neighborhood around the optimum is sampled. The method proposed is tested through four well known benchmark functions. [ABSTRACT FROM AUTHOR]

This paper shows the comparison made between the particle swarm optimization (PSO) algorithm and the interval analysis optimization method for solving nonlinear-function optimization with equality and/or inequality constraints. The interval analysis optimization method (IAO) was based on the one initially proposed by Ichida (1996). It was used to find the global optimum of a multimodal function with up to three variables, which is subject to equality and inequality constraints. It was found that the PSO algorithm was significantly faster for all functions, although its precision was limited. On the other hand, the IAO method was accurate in all cases, but took a considerably longer computational time. [ABSTRACT FROM AUTHOR]

This paper solves the optimization problem of communication networks by cable using a multi objective algorithm. The mathematical model is solved using a methodology based on the Non-dominated Sorting Algorithm (NSGAII). The mathematical model uses two objective functions, one is the investment costs and the other is an indicator related to the network operation. The problem solution is a Pareto front that consider information about the network design, showing a set of network configuration with minimum cost and minimum requirements of signal levels in the costumer connection nodes. For that, a real life test system is used. [ABSTRACT FROM AUTHOR]

This paper presents a novel method to solve instances of the TSP. This method is comparable in effectiveness and efficiency with "nearest neighbour", "cheapest insertion", "two-way exchange improvement" and "branch and bound". The first section provides a literature review of the combinatorial optimization, the second provides a reference frame, the third the methodology used and the fourth contains, inter alia, system thinking, A×B factorial design and management tool CAP-DO. The fourth section presents the design "new" method called systemic tetraheuristic, followed by ANOVA and Duncan ranges for each factor: method and number of cities; this section concludes with an analysis of the proportion of "failures" of the proposed algorithm with increasing complexity of the TSP. As a result of this study a method is presented for solving the TSP. This method consists of: 1. "nearest neighbour", 2. "short-term sacrifice" 3. "LIFO transfer" and a support heuristic "right search 4P4 ". For the design of the "sacrifice short-term" procedure, it was necessary to analyze the "nearest neighbour" heuristic from a systems perspective. This heuristic is related to the "quick solutions that fail" archetype, which can be applied to day-to-day. The proposed method has proved to be more efficient than others, in what concerns quality of the solution and the computation time, especially when the complexity of the TSP increases. [ABSTRACT FROM AUTHOR]

ACO is a metaheuristic inspired in the behavior of natural ant colonies to solve combinatorial optimization problems, based on simple agents that work cooperatively communicating by artificial pheromone trails. In this paper a model to solve the municipal waste collection problem by containers is presented, which applies a concept of partial collection sequences that must be joined to minimize the total collection distance. The problem to join the partial collection sequences is represented as a TSP, which is solved by an ACO algorithm. Based on the literature, algorithm parameters are experimentally calibrated and range of variations that represents good average solutions are recommended. The model is applied to a waste collection sector of the San Pedro de la Paz commune in Chile, obtaining recollection routes with less total distance with respect to the actual route utilized and to the solution obtained by a previously developed approach. [ABSTRACT FROM AUTHOR]

This paper presents a mathematical model of the problem of the planning of systems of electrical distribution which considers the location and sizing of new feeders and substations, and the reconductorazing of existing feeders. The mathematical model used is of the type Lineal Mixed Integer Programming (LMIP) and to solve it, an algorithm of Branch and Bound is used. In order to test the proposed algorithm, the electrical system of the city of Pereira is used. [ABSTRACT FROM AUTHOR]

This paper introduces a variant of the metaheuristic simulated annealing, oriented to solve multiobjective optimization problems. This technique is called MultiObjective Simulated Annealing with Random Trajectory Search (MOSARTS). This technique incorporates short and long term memory concepts to Simulated Annealing in order to balance the search effort among all the objectives involved in the problem. The algorithm was tested against three different techniques on a real life parallel machine scheduling problem, composed of 24 jobs and two identical machines. This problem represents a real life case study of the local sawmill industry. The results showed that MOSARTS behaved much better than the other methods utilized, because it found better solutions in terms of dominance and frontier dispersion. [ABSTRACT FROM AUTHOR]

this paper uses the Petri networks and genetic algorithms strengths for modelling and solving manufacturing systems and combinatorial problems, respectively. This article generates active schedules for flexible manufacturing systems that minimize weighted tardiness. The algorithm works for problems involving aspects such as: setups dependent on the operations sequences, stations with non identical parallel machines and stations buffers with finite capacity. Some of the obtained computational results make as believe it could be considered as a promise field for future works. [ABSTRACT FROM AUTHOR]

In this paper a method is proposed to complete and improve the edges defined for range images with planar surfaces. The method begins with an initial map of thickness edges, fragmented and with edge pixels bad located, obtained from the location of depth and orientation discontinuities between the surfaces of the image. This initial edge map is improved by a genetic algorithm, whose task is to add and to eliminate edge pixels in order to find a better delimitation of the surfaces. [ABSTRACT FROM AUTHOR]

In this paper, an analysis of evolutionary algorithms for multi objective optimization, Non-dominated Sorting Genetic Algorithm (NSGA-II) and Strength Pareto Evolutionary Algorithm (SPEA-II) is presented. For this analysis, is taken as reference an optimization problem in a multicast data network, which has as objective functions the hop count and transmission delay. The algorithms performance is compared in tree different networks. Moreover, the model for two of this topologies using GAMS tool is resolved and results are compared with the NSGA-II and SPEA-II algorithms proposed. Problem results show the algorithms performance in their solution. [ABSTRACT FROM AUTHOR]