Search results for: Short integer solution problem
5924 Constant Factor Approximation Algorithm for p-Median Network Design Problem with Multiple Cable Types
Authors: Chaghoub Soraya, Zhang Xiaoyan
Abstract:
This research presents the first constant approximation algorithm to the p-median network design problem with multiple cable types. This problem was addressed with a single cable type and there is a bifactor approximation algorithm for the problem. To the best of our knowledge, the algorithm proposed in this paper is the first constant approximation algorithm for the p-median network design with multiple cable types. The addressed problem is a combination of two well studied problems which are p-median problem and network design problem. The introduced algorithm is a random sampling approximation algorithm of constant factor which is conceived by using some random sampling techniques form the literature. It is based on a redistribution Lemma from the literature and a steiner tree problem as a subproblem. This algorithm is simple, and it relies on the notions of random sampling and probability. The proposed approach gives an approximation solution with one constant ratio without violating any of the constraints, in contrast to the one proposed in the literature. This paper provides a (21 + 2)-approximation algorithm for the p-median network design problem with multiple cable types using random sampling techniques.Keywords: Approximation algorithms, buy-at-bulk, combinatorial optimization, network design, p-median.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 5395923 Optimal Control of Volterra Integro-Differential Systems Based On Legendre Wavelets and Collocation Method
Authors: Khosrow Maleknejad, Asyieh Ebrahimzadeh
Abstract:
In this paper, the numerical solution of optimal control problem (OCP) for systems governed by Volterra integro-differential (VID) equation is considered. The method is developed by means of the Legendre wavelet approximation and collocation method. The properties of Legendre wavelet together with Gaussian integration method are utilized to reduce the problem to the solution of nonlinear programming one. Some numerical examples are given to confirm the accuracy and ease of implementation of the method.
Keywords: Collocation method, Legendre wavelet, optimal control, Volterra integro-differential equation.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 28535922 Using Tabu Search to Analyze the Mauritian Economic Sectors
Authors: J. Cheeneebash, V. Beeharry, A. Gopaul
Abstract:
The aim of this paper is to express the input-output matrix as a linear ordering problem which is classified as an NP-hard problem. We then use a Tabu search algorithm to find the best permutation among sectors in the input-output matrix that will give an optimal solution. This optimal permutation can be useful in designing policies and strategies for economists and government in their goal of maximizing the gross domestic product.Keywords: Input-Output matrix, linear ordering problem, Tabusearch.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 14525921 State Estimation Solution with Optimal Allocation of Phasor Measurement Units Considering Zero Injection Bus Modeling
Authors: M. Ravindra, R. Srinivasa Rao, V. Shanmukha Naga Raju
Abstract:
This paper presents state estimation with Phasor Measurement Unit (PMU) allocation to obtain complete observability of network. A matrix is designed with modeling of zero injection constraints to minimize PMU allocations. State estimation algorithm is developed with optimal allocation of PMUs to find accurate states of network. The incorporation of PMU into traditional state estimation process improves accuracy and computational performance for large power systems. The nonlinearity integrated with zero injection (ZI) constraints is remodeled to linear frame to optimize number of PMUs. The problem of optimal PMU allocation is regarded with modeling of ZI constraints, PMU loss or line outage, cost factor and redundant measurements. The proposed state estimation with optimal PMU allocation has been compared with traditional state estimation process to show its importance. MATLAB programming on IEEE 14, 30, 57, and 118 bus networks is implemented out by Binary Integer Programming (BIP) method and compared with other methods to show its effectiveness.
Keywords: Observability, phasor measurement units, synchrophasors, SCADA measurements, zero injection bus.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 7665920 Decision Maturity Framework: Introducing Maturity In Heuristic Search
Authors: Ayed Salman, Fawaz Al-Anzi, Aseel Al-Minayes
Abstract:
Heuristics-based search methodologies normally work on searching a problem space of possible solutions toward finding a “satisfactory" solution based on “hints" estimated from the problem-specific knowledge. Research communities use different types of methodologies. Unfortunately, most of the times, these hints are immature and can lead toward hindering these methodologies by a premature convergence. This is due to a decrease of diversity in search space that leads to a total implosion and ultimately fitness stagnation of the population. In this paper, a novel Decision Maturity framework (DMF) is introduced as a solution to this problem. The framework simply improves the decision on the direction of the search by materializing hints enough before using them. Ideas from this framework are injected into the particle swarm optimization methodology. Results were obtained under both static and dynamic environment. The results show that decision maturity prevents premature converges to a high degree.Keywords: Heuristic Search, hints, Particle Swarm Optimization, Decision Maturity Framework.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 13135919 Two Iterative Algorithms to Compute the Bisymmetric Solution of the Matrix Equation A1X1B1 + A2X2B2 + ... + AlXlBl = C
Authors: A.Tajaddini
Abstract:
In this paper, two matrix iterative methods are presented to solve the matrix equation A1X1B1 + A2X2B2 + ... + AlXlBl = C the minimum residual problem l i=1 AiXiBi−CF = minXi∈BRni×ni l i=1 AiXiBi−CF and the matrix nearness problem [X1, X2, ..., Xl] = min[X1,X2,...,Xl]∈SE [X1,X2, ...,Xl] − [X1, X2, ..., Xl]F , where BRni×ni is the set of bisymmetric matrices, and SE is the solution set of above matrix equation or minimum residual problem. These matrix iterative methods have faster convergence rate and higher accuracy than former methods. Paige’s algorithms are used as the frame method for deriving these matrix iterative methods. The numerical example is used to illustrate the efficiency of these new methods.
Keywords: Bisymmetric matrices, Paige’s algorithms, Least square.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 13495918 An Improved Integer Frequency Offset Estimator using the P1 Symbol for OFDM System
Authors: Yong-An Jung, Young-Hwan You
Abstract:
This paper suggests an improved integer frequency offset (IFO) estimation scheme using P1 symbol for orthogonal frequency division multiplexing (OFDM) based the second generation terrestrial digital video broadcasting (DVB-T2) system. Proposed IFO estimator is designed by a low-complexity blind IFO estimation scheme, which is implemented with complex additions. Also, we propose active carriers (ACs) selection scheme in order to prevent performance degradation in blind IFO estimation. The simulation results show that under the AWGN and TU6 channels, the proposed method has low complexity than conventional method and almost similar performance in comparison with the conventional method.Keywords: OFDM, DVB-T2, P1 symbol, ACs, IFO.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 18615917 Fuzzy Based Problem-Solution Data Structureas a Data Oriented Model for ABS Controlling
Authors: Ahmad Habibizad Navin, Mehdi Naghian Fesharaki, Mohamad Teshnelab, Ehsan Shahamatnia
Abstract:
The anti-lock braking systems installed on vehicles for safe and effective braking, are high-order nonlinear and timevariant. Using fuzzy logic controllers increase efficiency of such systems, but impose a high computational complexity as well. The main concept introduced by this paper is reducing computational complexity of fuzzy controllers by deploying problem-solution data structure. Unlike conventional methods that are based on calculations, this approach is based on data oriented modeling.Keywords: ABS, Fuzzy controller, PSDS, Time-Memory tradeoff, Data oriented modeling.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 16935916 Multimodal Reasoning in a Knowledge Engineering Framework for Product Support
Authors: Rossitza M. Setchi, Nikolaos Lagos
Abstract:
Problem solving has traditionally been one of the principal research areas for artificial intelligence. Yet, although artificial intelligence reasoning techniques have been employed in several product support systems, the benefit of integrating product support, knowledge engineering, and problem solving, is still unclear. This paper studies the synergy of these areas and proposes a knowledge engineering framework that integrates product support systems and artificial intelligence techniques. The framework includes four spaces; the data, problem, hypothesis, and solution ones. The data space incorporates the knowledge needed for structured reasoning to take place, the problem space contains representations of problems, and the hypothesis space utilizes a multimodal reasoning approach to produce appropriate solutions in the form of virtual documents. The solution space is used as the gateway between the system and the user. The proposed framework enables the development of product support systems in terms of smaller, more manageable steps while the combination of different reasoning techniques provides a way to overcome the lack of documentation resources.Keywords: Knowledge engineering framework, product support, case-based reasoning, model-based reasoning, multimodal reasoning.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 17555915 Connected Vertex Cover in 2-Connected Planar Graph with Maximum Degree 4 is NP-complete
Authors: Priyadarsini P. L. K, Hemalatha T.
Abstract:
This paper proves that the problem of finding connected vertex cover in a 2-connected planar graph ( CVC-2 ) with maximum degree 4 is NP-complete. The motivation for proving this result is to give a shorter and simpler proof of NP-Completeness of TRA-MLC (the Top Right Access point Minimum-Length Corridor) problem [1], by finding the reduction from CVC-2. TRA-MLC has many applications in laying optical fibre cables for data communication and electrical wiring in floor plans.The problem of finding connected vertex cover in any planar graph ( CVC ) with maximum degree 4 is NP-complete [2]. We first show that CVC-2 belongs to NP and then we find a polynomial reduction from CVC to CVC-2. Let a graph G0 and an integer K form an instance of CVC, where G0 is a planar graph and K is an upper bound on the size of the connected vertex cover in G0. We construct a 2-connected planar graph, say G, by identifying the blocks and cut vertices of G0, and then finding the planar representation of all the blocks of G0, leading to a plane graph G1. We replace the cut vertices with cycles in such a way that the resultant graph G is a 2-connected planar graph with maximum degree 4. We consider L = K -2t+3 t i=1 di where t is the number of cut vertices in G1 and di is the number of blocks for which ith cut vertex is common. We prove that G will have a connected vertex cover with size less than or equal to L if and only if G0 has a connected vertex cover of size less than or equal to K.Keywords: NP-complete, 2-Connected planar graph, block, cut vertex
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 19625914 Existence of Solution for Boundary Value Problems of Differential Equations with Delay
Authors: Xiguang Li
Abstract:
In this paper , by using fixed point theorem , upper and lower solution-s method and monotone iterative technique , we prove the existence of maximum and minimum solutions of differential equations with delay , which improved and generalize the result of related paper.
Keywords: Banach space, boundary value problem, differential equation, delay.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 11875913 Reducing the Number of Constraints in Non Safe Petri Net
Authors: M. Zareiee, A. Dideban
Abstract:
This paper addresses the problem of forbidden states in non safe Petri Nets. In the system, for preventing it from entering the forbidden states, some linear constraints can be assigned to them. Then these constraints can be enforced on the system using control places. But when the number of constraints in the system is large, a large number of control places must be added to the model of system. This concept complicates the model of system. There are some methods for reducing the number of constraints in safe Petri Nets. But there is no a systematic method for non safe Petri Nets. In this paper we propose a method for reducing the number of constraints in non safe Petri Nets which is based on solving an integer linear programming problem.Keywords: discrete event system, Supervisory control, Petri Net, Constraint
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 12725912 A Robust Frequency Offset Estimator for Orthogonal Frequency Division Multiplexing
Authors: Keunhong Chae, Seokho Yoon
Abstract:
We address the integer frequency offset (IFO) estimation under the influence of the timing offset (TO) in orthogonal frequency division multiplexing (OFDM) systems. Incorporating the IFO and TO into the symbol set used to represent the received OFDM symbol, we investigate the influence of the TO on the IFO, and then, propose a combining method between two consecutive OFDM correlations, reducing the influence. The proposed scheme has almost the same complexity as that of the conventional schemes, whereas it does not need the TO knowledge contrary to the conventional schemes. From numerical results it is confirmed that the proposed scheme is insensitive to the TO, consequently, yielding an improvement of the IFO estimation performance over the conventional schemes when the TO exists.
Keywords: Estimation, integer frequency offset, OFDM, timing offset.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 20695911 Entropy Based Spatial Design: A Genetic Algorithm Approach (Case Study)
Authors: Abbas Siefi, Mohammad Javad Karimifar
Abstract:
We study the spatial design of experiment and we want to select a most informative subset, having prespecified size, from a set of correlated random variables. The problem arises in many applied domains, such as meteorology, environmental statistics, and statistical geology. In these applications, observations can be collected at different locations and possibly at different times. In spatial design, when the design region and the set of interest are discrete then the covariance matrix completely describe any objective function and our goal is to choose a feasible design that minimizes the resulting uncertainty. The problem is recast as that of maximizing the determinant of the covariance matrix of the chosen subset. This problem is NP-hard. For using these designs in computer experiments, in many cases, the design space is very large and it's not possible to calculate the exact optimal solution. Heuristic optimization methods can discover efficient experiment designs in situations where traditional designs cannot be applied, exchange methods are ineffective and exact solution not possible. We developed a GA algorithm to take advantage of the exploratory power of this algorithm. The successful application of this method is demonstrated in large design space. We consider a real case of design of experiment. In our problem, design space is very large and for solving the problem, we used proposed GA algorithm.
Keywords: Spatial design of experiments, maximum entropy sampling, computer experiments, genetic algorithm.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 16015910 Load Forecasting in Microgrid Systems with R and Cortana Intelligence Suite
Authors: F. Lazzeri, I. Reiter
Abstract:
Energy production optimization has been traditionally very important for utilities in order to improve resource consumption. However, load forecasting is a challenging task, as there are a large number of relevant variables that must be considered, and several strategies have been used to deal with this complex problem. This is especially true also in microgrids where many elements have to adjust their performance depending on the future generation and consumption conditions. The goal of this paper is to present a solution for short-term load forecasting in microgrids, based on three machine learning experiments developed in R and web services built and deployed with different components of Cortana Intelligence Suite: Azure Machine Learning, a fully managed cloud service that enables to easily build, deploy, and share predictive analytics solutions; SQL database, a Microsoft database service for app developers; and PowerBI, a suite of business analytics tools to analyze data and share insights. Our results show that Boosted Decision Tree and Fast Forest Quantile regression methods can be very useful to predict hourly short-term consumption in microgrids; moreover, we found that for these types of forecasting models, weather data (temperature, wind, humidity and dew point) can play a crucial role in improving the accuracy of the forecasting solution. Data cleaning and feature engineering methods performed in R and different types of machine learning algorithms (Boosted Decision Tree, Fast Forest Quantile and ARIMA) will be presented, and results and performance metrics discussed.
Keywords: Time-series, features engineering methods for forecasting, energy demand forecasting, Azure machine learning.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 12405909 A Survey on the Requirements of University Course Timetabling
Authors: Nurul Liyana Abdul Aziz, Nur Aidya Hanum Aizam
Abstract:
Course timetabling problems occur every semester in a university which includes the allocation of resources (subjects, lecturers and students) to a number of fixed rooms and timeslots. The assignment is carried out in a way such that there are no conflicts within rooms, students and lecturers, as well as fulfilling a range of constraints. The constraints consist of rules and policies set up by the universities as well as lecturers’ and students’ preferences of courses to be allocated in specific timeslots. This paper specifically focuses on the preferences of the course timetabling problem in one of the public universities in Malaysia. The demands will be considered into our existing mathematical model to make it more generalized and can be used widely. We have distributed questionnaires to a number of lecturers and students of the university to investigate their demands and preferences for their desired course timetable. We classify the preferences thus converting them to construct one mathematical model that can produce such timetable.Keywords: University course timetabling problem, integer programming, preferences, constraints.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 17675908 Applying Genetic Algorithms for Inventory Lot-Sizing Problem with Supplier Selection under Storage Space
Authors: Vichai Rungreunganaun, Chirawat Woarawichai
Abstract:
The objective of this research is to calculate the optimal inventory lot-sizing for each supplier and minimize the total inventory cost which includes joint purchase cost of the products, transaction cost for the suppliers, and holding cost for remaining inventory. Genetic algorithms (GAs) are applied to the multi-product and multi-period inventory lot-sizing problems with supplier selection under storage space. Also a maximum storage space for the decision maker in each period is considered. The decision maker needs to determine what products to order in what quantities with which suppliers in which periods. It is assumed that demand of multiple products is known over a planning horizon. The problem is formulated as a mixed integer programming and is solved with the GAs. The detailed computation results are presented.Keywords: Genetic Algorithms, Inventory lot-sizing, Supplier selection, Storage space.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 21055907 A New Heuristic Algorithm for the Classical Symmetric Traveling Salesman Problem
Authors: S. B. Liu, K. M. Ng, H. L. Ong
Abstract:
This paper presents a new heuristic algorithm for the classical symmetric traveling salesman problem (TSP). The idea of the algorithm is to cut a TSP tour into overlapped blocks and then each block is improved separately. It is conjectured that the chance of improving a good solution by moving a node to a position far away from its original one is small. By doing intensive search in each block, it is possible to further improve a TSP tour that cannot be improved by other local search methods. To test the performance of the proposed algorithm, computational experiments are carried out based on benchmark problem instances. The computational results show that algorithm proposed in this paper is efficient for solving the TSPs.Keywords: Local search, overlapped neighborhood, travelingsalesman problem.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 21705906 Evolutionary Computation Technique for Solving Riccati Differential Equation of Arbitrary Order
Authors: Raja Muhammad Asif Zahoor, Junaid Ali Khan, I. M. Qureshi
Abstract:
In this article an evolutionary technique has been used for the solution of nonlinear Riccati differential equations of fractional order. In this method, genetic algorithm is used as a tool for the competent global search method hybridized with active-set algorithm for efficient local search. The proposed method has been successfully applied to solve the different forms of Riccati differential equations. The strength of proposed method has in its equal applicability for the integer order case, as well as, fractional order case. Comparison of the method has been made with standard numerical techniques as well as the analytic solutions. It is found that the designed method can provide the solution to the equation with better accuracy than its counterpart deterministic approaches. Another advantage of the given approach is to provide results on entire finite continuous domain unlike other numerical methods which provide solutions only on discrete grid of points.Keywords: Riccati Equation, Non linear ODE, Fractional differential equation, Genetic algorithm.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 18985905 Solution of Nonlinear Second-Order Pantograph Equations via Differential Transformation Method
Authors: Nemat Abazari, Reza Abazari
Abstract:
In this work, we successfully extended one-dimensional differential transform method (DTM), by presenting and proving some theorems, to solving nonlinear high-order multi-pantograph equations. This technique provides a sequence of functions which converges to the exact solution of the problem. Some examples are given to demonstrate the validity and applicability of the present method and a comparison is made with existing results.
Keywords: Nonlinear multi-pantograph equation, delay differential equation, differential transformation method, proportional delay conditions, closed form solution.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 25085904 Cross-Industry Innovations–Systematic Identification of Ideas for Radical Problem Solving
Authors: Niklas Echterhoff, Benjamin Amshoff, Jürgen Gausemeier
Abstract:
Creativity is often based on an unorthodox recombination of knowledge; in fact: 80% of all innovations use given knowledge and put it into a new combination. Cross-industry innovations follow this way of thinking and bring together problems and solution ideas from different industries. Therefore analogies and search strategies have to be developed. Taking this path, the questions where to search, what to search and how to search have to be answered. Afterwards, the gathered information can be used within a planned search process. Identified solution ideas have to be assessed and analyzed in detail for the success promising adaption planning.Keywords: analogy building, cross-industry innovations, knowledge transfer, solution adaption.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 20185903 On the Solution of the Towers of Hanoi Problem
Authors: Hayedeh Ahrabian, Comfar Badamchi, Abbass Nowzari-Dalini
Abstract:
In this paper, two versions of an iterative loopless algorithm for the classical towers of Hanoi problem with O(1) storage complexity and O(2n) time complexity are presented. Based on this algorithm the number of different moves in each of pegs with its direction is formulated.Keywords: Loopless algorithm, Binary tree, Towers of Hanoi.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 47915902 Intelligent Neural Network Based STLF
Authors: H. Shayeghi, H. A. Shayanfar, G. Azimi
Abstract:
Short-Term Load Forecasting (STLF) plays an important role for the economic and secure operation of power systems. In this paper, Continuous Genetic Algorithm (CGA) is employed to evolve the optimum large neural networks structure and connecting weights for one-day ahead electric load forecasting problem. This study describes the process of developing three layer feed-forward large neural networks for load forecasting and then presents a heuristic search algorithm for performing an important task of this process, i.e. optimal networks structure design. The proposed method is applied to STLF of the local utility. Data are clustered due to the differences in their characteristics. Special days are extracted from the normal training sets and handled separately. In this way, a solution is provided for all load types, including working days and weekends and special days. We find good performance for the large neural networks. The proposed methodology gives lower percent errors all the time. Thus, it can be applied to automatically design an optimal load forecaster based on historical data.
Keywords: Feed-forward Large Neural Network, Short-TermLoad Forecasting, Continuous Genetic Algorithm.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 17885901 The Algorithm to Solve the Extend General Malfatti’s Problem in a Convex Circular Triangle
Authors: Ching-Shoei Chiang
Abstract:
The Malfatti’s problem solves the problem of fitting three circles into a right triangle such that these three circles are tangent to each other, and each circle is also tangent to a pair of the triangle’s sides. This problem has been extended to any triangle (called general Malfatti’s problem). Furthermore, the problem has been extended to have 1 + 2 + … + n circles inside the triangle with special tangency properties among circles and triangle sides; it is called the extended general Malfatti’s problem. In the extended general Malfatti’s problem, call it Tri(Tn), where Tn is the triangle number, there are closed-form solutions for the Tri(T₁) (inscribed circle) problem and Tri(T₂) (3 Malfatti’s circles) problem. These problems become more complex when n is greater than 2. In solving the Tri(Tn) problem, n > 2, algorithms have been proposed to solve these problems numerically. With a similar idea, this paper proposed an algorithm to find the radii of circles with the same tangency properties. Instead of the boundary of the triangle being a straight line, we use a convex circular arc as the boundary and try to find Tn circles inside this convex circular triangle with the same tangency properties among circles and boundary as in Tri(Tn) problems. We call these problems the Carc(Tn) problems. The algorithm is a mO(Tn) algorithm, where m is the number of iterations in the loop. It takes less than 1000 iterations and less than 1 second for the Carc(T16) problem, which finds 136 circles inside a convex circular triangle with specified tangency properties. This algorithm gives a solution for circle packing problem inside convex circular triangle with arbitrarily-sized circles. Many applications concerning circle packing may come from the result of the algorithm, such as logo design, architecture design, etc.
Keywords: Circle packing, computer-aided geometric design, geometric constraint solver, Malfatti’s problem.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 515900 A Hybrid Search Algorithm for Solving Constraint Satisfaction Problems
Authors: Abdel-Reza Hatamlou, Mohammad Reza Meybodi
Abstract:
In this paper we present a hybrid search algorithm for solving constraint satisfaction and optimization problems. This algorithm combines ideas of two basic approaches: complete and incomplete algorithms which also known as systematic search and local search algorithms. Different characteristics of systematic search and local search methods are complementary. Therefore we have tried to get the advantages of both approaches in the presented algorithm. The major advantage of presented algorithm is finding partial sound solution for complicated problems which their complete solution could not be found in a reasonable time. This algorithm results are compared with other algorithms using the well known n-queens problem.Keywords: Constraint Satisfaction Problem, Hybrid SearchAlgorithm.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 13235899 An Asymptotic Formula for Pricing an American Exchange Option
Authors: Hsuan-Ku Liu
Abstract:
In this paper, the American exchange option (AEO) valuation problem is modelled as a free boundary problem. The critical stock price for an AEO is satisfied an integral equation implicitly. When the remaining time is large enough, an asymptotic formula is provided for pricing an AEO. The numerical results reveal that our asymptotic pricing formula is robust and accurate for the long-term AEO.
Keywords: Integral equation, asymptotic solution, free boundary problem, American exchange option.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 15745898 Vehicle Routing Problem with Mixed Fleet of Conventional and Heterogenous Electric Vehicles and Time Dependent Charging Costs
Authors: Ons Sassi, Wahiba Ramdane Cherif-Khettaf, Ammar Oulamara
Abstract:
In this paper, we consider the vehicle routing problem with mixed fleet of conventional and heterogenous electric vehicles and time dependent charging costs, denoted VRP-HFCC, in which a set of geographically scattered customers have to be served by a mixed fleet of vehicles composed of a heterogenous fleet of Electric Vehicles (EVs), having different battery capacities and operating costs, and Conventional Vehicles (CVs). We include the possibility of charging EVs in the available charging stations during the routes in order to serve all customers. Each charging station offers charging service with a known technology of chargers and time dependent charging costs. Charging stations are also subject to operating time windows constraints. EVs are not necessarily compatible with all available charging technologies and a partial charging is allowed. Intermittent charging at the depot is also allowed provided that constraints related to the electricity grid are satisfied. The objective is to minimize the number of employed vehicles and then minimize the total travel and charging costs. In this study, we present a Mixed Integer Programming Model and develop a Charging Routing Heuristic and a Local Search Heuristic based on the Inject-Eject routine with different insertion methods. All heuristics are tested on real data instances.
Keywords: charging problem, electric vehicle, heuristics, local search, optimization, routing problem.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 26235897 Truck Routing Problem Considering Platooning and Drivers’ Breaks
Authors: Xiaoyuan Yan, Min Xu
Abstract:
Truck platooning refers to a convoy of digitally connected automated trucks traveling safely with a small inter-vehicle gap. It has been identified as one of the most promising and applicable technologies towards automated and sustainable freight transportation. Although truck platooning delivers significant energy-saving benefits, it cannot be realized without good coordination of drivers’ shifts to lead the platoons subject to their mandatory breaks. Therefore, this study aims to route a fleet of trucks to their destinations using the least amount of fuel by maximizing platoon opportunities under the regulations of drivers’ mandatory breaks. We formulate this platoon coordination problem as a mixed-integer linear programming problem and solve it by CPLEX. Numerical experiments are conducted to demonstrate the effectiveness and efficiency of our proposed model. In addition, we also explore the impacts of drivers’ compulsory breaks on the fuel-savings performance. The results show a slight increase in the total fuel costs in the presence of drivers’ compulsory breaks, thanks to driving-while-resting benefit provided for the trailing trucks. This study may serve as a guide for the operators of automated freight transportation.
Keywords: Truck platooning, route optimization, compulsory breaks, energy saving.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 5195896 Modeling and Numerical Simulation of Sound Radiation by the Boundary Element Method
Authors: Costa, E.S., Borges, E.N.M., Afonso, M.M.
Abstract:
The modeling of sound radiation is of fundamental importance for understanding the propagation of acoustic waves and, consequently, develop mechanisms for reducing acoustic noise. The propagation of acoustic waves, are involved in various phenomena such as radiation, absorption, transmission and reflection. The radiation is studied through the linear equation of the acoustic wave that is obtained through the equation for the Conservation of Momentum, equation of State and Continuity. From these equations, is the Helmholtz differential equation that describes the problem of acoustic radiation. In this paper we obtained the solution of the Helmholtz differential equation for an infinite cylinder in a pulsating through free and homogeneous. The analytical solution is implemented and the results are compared with the literature. A numerical formulation for this problem is obtained using the Boundary Element Method (BEM). This method has great power for solving certain acoustical problems in open field, compared to differential methods. BEM reduces the size of the problem, thereby simplifying the input data to be worked and reducing the computational time used.
Keywords: Acoustic radiation, boundary element
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 14275895 Research of a Multistep Method Applied to Numerical Solution of Volterra Integro-Differential Equation
Authors: M.Imanova, G.Mehdiyeva, V.Ibrahimov
Abstract:
Solution of some practical problems is reduced to the solution of the integro-differential equations. But for the numerical solution of such equations basically quadrature methods or its combination with multistep or one-step methods are used. The quadrature methods basically is applied to calculation of the integral participating in right hand side of integro-differential equations. As this integral is of Volterra type, it is obvious that at replacement with its integrated sum the upper limit of the sum depends on a current point in which values of the integral are defined. Thus we receive the integrated sum with variable boundary, to work with is hardly. Therefore multistep method with the constant coefficients, which is free from noted lack and gives the way for finding it-s coefficients is present.Keywords: Volterra integro-differential equations, multistepmethods, finite-difference methods, initial value problem
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1437