[SJR: 0.292] [H-I: 8] [0 followers] Follow
Open Access journal
ISSN (Print) 0101-7438
Published by SciELO [727 journals]
- QUANTUM INSPIRED PARTICLE SWARM COMBINED WITH LIN-KERNIGHAN-HELSGAUN
METHOD TO THE TRAVELING SALESMAN PROBLEM
Abstract: ABSTRACT The Traveling Salesman Problem (TSP) is one of the most well-known and studied problems of Operations Research field, more specifically, in the Combinatorial Optimization field. As the TSP is a NP (Non-Deterministic Polynomial time)-hard problem, there are several heuristic methods which have been proposed for the past decades in the attempt to solve it the best possible way. The aim of this work is to introduce and to evaluate the performance of some approaches for achieving optimal solution considering some symmetrical and asymmetrical TSP instances, which were taken from the Traveling Salesman Problem Library (TSPLIB). The analyzed approaches were divided into three methods: (i) Lin-Kernighan-Helsgaun (LKH) algorithm; (ii) LKH with initial tour based on uniform distribution; and (iii) an hybrid proposal combining Particle Swarm Optimization (PSO) with quantum inspired behavior and LKH for local search procedure. The tested algorithms presented promising results in terms of computational cost and solution quality.
- LAGRANGE MULTIPLIERS IN THE PROBABILITY DISTRIBUTIONS ELICITATION PROBLEM:
AN APPLICATION TO THE 2013 FIFA CONFEDERATIONS CUP
Abstract: ABSTRACT Contributions from the sensitivity analysis of the parameters of the linear programming model for the elicitation of experts' beliefs are presented. The process allows for the calibration of the family of probability distributions obtained in the elicitation process. An experiment to obtain the probability distribution of a future event (Brazil vs. Spain soccer game in the 2013 FIFA Confederations Cup final game) was conducted. The proposed sensitivity analysis step may help to reduce the vagueness of the information given by the expert.
- AN APPROACH TO FINANCIAL RISK IN A PORTFOLIO FOR PLANNING THE INDUSTRIAL
PRODUCTION OF PRODUCTS DERIVED FROM SUGARCANE
Abstract: ABSTRACT Brazil's location and tropical weather conditions are favourable cultivating sugarcane, which has led to Brazil being one of the world's largest producers of sugarcane. The influence of the sugarcane industry on its economy stands out among the indicators of Brazilian economic growth and because the diversified investment when planning the production of products derived from this sector is encouraged. The decision on which derivative (for example, crystal sugar, anhydrous ethanol, or hydrous ethanol) to produce from raw sugarcane can be modelled as an investment decision in a portfolio decision problem whenever a combination of these products is considered. As to the future price of these commodities, raw sugarcane is considered to be capital that should be invested. Thus, this paper puts forward a decision model which uses concepts from Decision Analysis and Bayesian Risk Analysis that may well assist the process of managing assets in the Brazilian sugarcane industry by considering the financial aspect when compiling a portfolio for planning production.
- MULTI-VEHICLE COVERING TOUR PROBLEM: BUILDING ROUTES FOR URBAN PATROLLING
Abstract: ABSTRACT In this paper we study a particular aspect of the urban community policing: routine patrol route planning. We seek routes that guarantee visibility, as this has a sizable impact on the community perceived safety, allowing quick emergency responses and providing surveillance of selected sites (e.g., hospitals, schools). The planning is restricted to the availability of vehicles and strives to achieve balanced routes. We study an adaptation of the model for the multi-vehicle covering tour problem, in which a set of locations must be visited, whereas another subset must be close enough to the planned routes. It constitutes an NP-complete integer programming problem. Suboptimal solutions are obtained with several heuristics, some adapted from the literature and others developed by us. We solve some adapted instances from TSPLIB and an instance with real data, the former being compared with results from literature, and latter being compared with empirical data.
- A DISTRIBUTION FOR THE SERVICE MODEL
Abstract: ABSTRACT In this paper, we propose a distribution that describes a specific system. The system has a heavy traffic, a fast service and the service rate depends on state of the system. This distribution we call the Maximum-Conway-Maxwell-Poisson-exponential distribution, denoted by MAXCOMPE distribution. The MAXCOMPE distribution is obtained by compound distributions in which we use the zero truncated Conway-Maxwell-Poisson distribution and the exponential distribution. This distribution has adjustment mechanism in order to re-establish the equilibrium of the system when the traffic flow increases and that is described by variations of the pressure parameter. Because of this, the MAXCOMPE distribution contains sub-models, such as, the Maximum-geometric-exponential distribution, the Maximum-Poisson-exponential distribution and the Maximum-Bernoulli-exponential distribution. The properties of the proposed distribution are discussed, including formal proof of its density function and explicit algebraic formulas for their reliability function and moments. The parameter estimation is based on the usual maximum likelihood method. Simulated and real data are shown to illustrate the applicability of the model.
- SIMULATION-BASED METHODOLOGY FOR PREDICTING FOOTBALL MATCH OUTCOMES
Abstract: ABSTRACT In this paper we propose a simulation-based method for predicting the 2010 and 2014Football World Cup. Adopting a bayesian perspective, we modeled the number of goals of two opposing teams as a Poisson distribution whose mean is proportional to the relative technical level of opponents. FIFA ratings were taken as the measure of technical level of teams and experts' opinions about scores of matches were taken to construct prior distribution of parameters. Just before each round, tournament simulations were performed in order to estimate probabilities of events of main interest for audience and bettors such as qualifying to the knockout stage, reaching semi-finals, reaching the final match, winningthe tournament, among others.
- METAHEURISTICS EVALUATION: A PROPOSAL FOR A MULTICRITERIA METHODOLOGY
Abstract: ABSTRACT In this work we propose a multicriteria evaluation scheme for heuristic algorithms based on the classic Condorcet ranking technique. Weights are associated to the ranking of an algorithm among a set being object of comparison. We used five criteria and a function on the set of natural numbers to create a ranking. The discussed comparison involves three well-known problems of combinatorial optimization - Traveling Salesperson Problem (TSP), Capacitated Vehicle Routing Problem (CVRP) and Quadratic Assignment Problem (QAP). The tested instances came from public libraries. Each algorithm was used with essentially the same structure, the same local search was applied and the initial solutions were similarly built. It is important to note that the work does not make proposals involving algorithms: the results for the three problems are shown only to illustrate the operation of the evaluation technique. Four metaheuristics - GRASP, Tabu Search, ILS and VNS - are therefore only used for the comparisons.
- A NEW MATHEMATICAL MODEL FOR THE CUTTING STOCK/LEFTOVER PROBLEM
Abstract: ABSTRACT This paper addresses the cutting stock/leftover problem (CSLP), which differs from the ordinary cutting stock problem (CSP) by retaining stock leftovers that can be cut in the future to meet new demands. Therefore, leftovers are not considered waste in the current period. A new mathematical model for the CSLP is presented to capture a well-used strategy in the practice of cutting, which consists of partially cutting the objects in stock, and keeping the leftovers to be cut in the next periods. Computational experiments were made for the one-dimensional case, although other dimensions can be considered straightforward.
- THE MULTIPLE CHOICE PROBLEM WITH INTERACTIONS BETWEEN CRITERIA
Abstract: ABSTRACT An important problem in Multi-Criteria Decision Analysis arises when one must select at least two alternatives at the same time. This can be denoted as a multiple choice problem. In other words, instead of evaluating each of the alternatives separately, they must be combined into groups of n alternatives, where n = 2. When the multiple choice problem must be solved under multiple criteria, the result is a multi-criteria, multiple choice problem. In this paper, it is shown through examples how this problemcan be tackled on a bipolar scale. The Choquet integral is used in this paper to take care of interactions between criteria. A numerical application example is conducted using data from SEBRAE-RJ, a non-profit private organization that has the mission of promoting competitiveness, sustainable developmentand entrepreneurship in the state of Rio de Janeiro, Brazil. The paper closes with suggestions for future research.
- INDUSTRIAL INSIGHTS INTO LOT SIZING AND SCHEDULING MODELING
Abstract: ABSTRACT Lot sizing and scheduling by mixed integer programming has been a hot research topic in the last 20 years. Researchers have been trying to develop stronger formulations, as well as to incorporate real-world requirements from different applications. This paper illustrates some of these requirements and demonstrates how small- and big-bucket models have been adapted and extended. Motivation comes from different industries, especially from process and fast-moving consumer goods industries.