Search results for: charging problem

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 2626

Authors: L. Bokopane, K. Kusakana, H. J. Vermaark

Abstract:

The success of renewable powered electric vehicle charging station in isolated areas depends highly on the availability and sustainability of renewable resources all year round at a selected location. The main focus of this paper is to discuss the possible charging strategies that could be implemented to find the best possible configuration of an electric Tuk-Tuk charging station at a given location within South Africa. The charging station is designed, modeled and simulated to evaluate its performances. The technoeconomic analysis of different feasible supply configurations of the charging station using renewable energies is simulated using HOMER software and the results compared in order to select the best possible charging strategies in terms of cost of energy consumed.

Keywords: Electric Tuk-Tuk, Renewable energy, Energy Storage, Hybrid systems, HOMER.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2470

Authors: A. Won-Yong Chae, B. Hyung-Nam Kim, C. Kyoung-Jun Lee, D. Hee-Je Kim

Abstract:

The renewable energy has been attracting attention as a new alternative energy due to the problem of environmental pollution and resource depletion. In particular, daylighting and PV system are regarded as the solutions. In this paper, the hybrid dimming control system supplied by solar cell and daylighting system was designed. Daylighting system is main source and PV system is spare source. PV system operates the LED lamp which supports daylighting system because daylighting system is unstable due to the variation of irradiance. In addition, PV system has a role charging batteries. Battery charging has a benefit that PV system operate LED lamp in the bad weather. However, LED lamp always can`t turn on that-s why dimming control system was designed. In particular, the solar charging robot was designed to check the interior irradiance intensity. These systems and the application of the solar charging robot are expected to contribute developing alternative energy in the near future.

Keywords: Daylighting system, PV system, LED lamp, Suntracking robot.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1767

Authors: Manan’Iarivo Rasolonjanahary, Chris Bingham, Nigel Schofield, Masoud Bazargan

Abstract:

This paper presents the research and application of model predictive scheduled charging of electric vehicles (EV) subject to limited available power resource. To focus on algorithm and operational characteristics, the EV interface to the source is modelled as a battery state equation during the charging operation. The researched methods allow for the priority scheduling of EV charging in a multi-vehicle regime and when subject to limited source power availability. Priority attribution for each connected EV is described. The validity of the developed methodology is shown through the simulation of different scenarios of charging operation of multiple connected EVs including non-scheduled and scheduled operation with various numbers of vehicles. Performance of the developed algorithms is also reported with the recommendation of the choice of suitable parameters.

Keywords: Model predictive control, non-scheduled, power limited sources, scheduled and stop-start battery charging.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 452

Authors: A.G.E. Sutjipto, Jufriadi, R. Muhida, Afzeri, E.Y. Adesta

Abstract:

Charging and discharging phenomenon on the surface of materials can be found in plasma display panel, spacecraft charging, high voltage insulator, etc. This report gives a simple explanation on this phenomenon. A scanning electron microscope was used not only as a tool to produce energetic electron beam to charge an insulator without metallic coating and to produce a surface discharging (surface breakdown/flashover) but also to observe the visible charging and discharging on the sample surface. A model of electric field distribution on the surface was developed in order to explain charging and discharging phenomena. Since charging and discharging process involves incubation time, therefore this process can be used to evaluate the insulation property of materials under electron bombardment.

Keywords: Flashover, SEM, Electron Bombardment, Electric Field.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1489

Authors: Mahmud Fotuhi-Firuzabad, Ali Abbaspour, Mohsen Mazidi, Mohamamd Rastegar

Abstract:

To tackle the air pollution issues, Plug-in Hybrid Electric Vehicles (PHEVs) are proposed as an appropriate solution. Charging a large amount of PHEV batteries, if not controlled, would have negative impacts on the distribution system. The control process of charging of these vehicles can be centralized in parking lots that may provide a chance for better coordination than the individual charging in houses. In this paper, an optimization-based approach is proposed to determine the optimum PHEV parking capacities in candidate nodes of the distribution system. In so doing, a profile for charging and discharging of PHEVs is developed in order to flatten the network load profile. Then, this profile is used in solving an optimization problem to minimize the distribution system losses. The outputs of the proposed method are the proper place for PHEV parking lots and optimum capacity for each parking. The application of the proposed method on the IEEE-34 node test feeder verifies the effectiveness of the method.

Keywords: Plug-in Hybrid Electric Vehicle (PHEV), PHEV parking lot, V2G.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2256

Authors: Priyanka Paliwal, N. P. Patidar, R. K. Nema

Abstract:

Battery storage system is emerging as an essential component of hybrid power system based on renewable energy resources such as solar and wind in order to make these sources dispatchable. Accurate modeling of battery storage system is ssential in order to ensure optimal planning of hybrid power systems incorporating battery storage. Majority of the system planning studies involving battery storage assume battery charging efficiency to be constant. However a strong correlation exists between battery charging efficiency and battery state of charge. In this work a Fuzzy logic based model has been presented for determining battery charging efficiency relative to a particular SOC. In order to demonstrate the efficacy of proposed approach, reliability evaluation studies are carried out for a hypothetical autonomous hybrid power system located in Jaisalmer, Rajasthan, India. The impact of considering battery charging efficiency as a function of state of charge is compared against the assumption of fixed battery charging efficiency for three different configurations comprising of wind-storage, solar-storage and wind-solar-storage.

Keywords: Battery Storage, Charging efficiency, Fuzzy Logic, Hybrid Power System, Reliability

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2042

Authors: Leonor Varandas, Pedro D. Gaspar, Martim L. Aguiar

Abstract:

One of the biggest concerns in the field of agriculture is around the energy efficiency of robots that will perform agriculture’s activity and their charging methods. In this paper, two different charging methods for agricultural standalone docking stations are shown that will take into account various variants as field size and its irregularities, work’s nature to which the robot will perform, deadlines that have to be respected, among others. Its features also are dependent on the orchard, season, battery type and its technical specifications and cost. First charging base method focuses on wireless charging, presenting more benefits for small field. The second charging base method relies on battery replacement being more suitable for large fields, thus avoiding the robot stop for recharge. Existing many methods to charge a battery, the CC CV was considered the most appropriate for either simplicity or effectiveness. The choice of the battery for agricultural purposes is if most importance. While the most common battery used is Li-ion battery, this study also discusses the use of graphene-based new type of batteries with 45% over capacity to the Li-ion one. A Battery Management Systems (BMS) is applied for battery balancing. All these approaches combined showed to be a promising method to improve a lot of technical agricultural work, not just in terms of plantation and harvesting but also about every technique to prevent harmful events like plagues and weeds or even to reduce crop time and cost.

Keywords: Agricultural mobile robot, charging base methods, battery replacement method, wireless charging method.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 781

Authors: Wahab Ali Shah, Junjia He

Abstract:

Transferring electrical power without any wiring has been a dream since late 19^th century. There were some advances in this area as to know more about microwave systems. However, this subject has recently become very attractive due to their practiScal systems. There are low power applications such as charging the batteries of contactless tooth brushes or implanted devices, and higher power applications such as charging the batteries of electrical automobiles or buses. In the first group of applications operating frequencies are in microwave range while the frequency is lower in high power applications. In the latter, the concept is also called inductive power transfer. The aim of the paper is to have an overview of the inductive power transfer for electrical vehicles with a special concentration on coil design and power converter simulation for static charging. Coil design is very important for an efficient and safe power transfer. Coil design is one of the most critical tasks. Power converters are used in both side of the system. The converter on the primary side is used to generate a high frequency voltage to excite the primary coil. The purpose of the converter in the secondary is to rectify the voltage transferred from the primary to charge the battery. In this paper, an inductive power transfer system is studied. Inductive power transfer is a promising technology with several possible applications. Operation principles of these systems are explained, and components of the system are described. Finally, a single phase 2 kW system was simulated and results were presented. The work presented in this paper is just an introduction to the concept. A reformed compensation network based on traditional inductor-capacitor-inductor (LCL) topology is proposed to realize robust reaction to large coupling variation that is common in dynamic wireless charging application. In the future, this type compensation should be studied. Also, comparison of different compensation topologies should be done for the same power level.

Keywords: Coil design, contactless charging, electrical automobiles, inductive power transfer, operating frequency.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 944

Authors: Sun-Ki Hong, Nam-HeeByeon, Jung-Seop Lee, Tae-Sam Kang

Abstract:

For Common R or R-L load to apply arbitrary voltage, the bridge traditional inverters don’t have any difficulties by PWM method. However for driving some piezoelectric actuator, arbitrary voltage not a pulse but a steady voltage should be applied. Piezoelectric load is considered as R-C load and its voltage does not decrease even though the applied voltage decreases. Therefore it needs some special inverter with circuit that can discharge the capacitive energy. Especially for unidirectional arbitrary voltage driving like as sine wave, it becomes more difficult problem. In this paper, a charge and discharge circuit for unidirectional arbitrary voltage driving for piezoelectric actuator is proposed. The circuit has charging and discharging switches for increasing and decreasing output voltage. With the proposed simple circuit, the load voltage can have any unidirectional level with tens of bandwidth because the load voltage can be adjusted by switching the charging and discharging switch appropriately. The appropriateness is proved from the simulation of the proposed circuit.

Keywords: DC-DC converter, analog output voltage, sinusoidal drive, piezoelectric load, discharging circuit.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2479

Authors: A. Hassoune, M. Khafallah, A. Mesbahi, T. Bouragba

Abstract:

This work presents an improved strategy of control for charging a lithium-ion battery in an electric vehicle charging station using two charger topologies i.e. single ended primary inductor converter (SEPIC) and forward converter. In terms of rapidity and accuracy, the power system consists of a topology/control diagram that would overcome the performance constraints, for instance the power instability, the battery overloading and how the energy conversion blocks would react efficiently to any kind of perturbations. Simulation results show the effectiveness of the proposed topologies operated with a power management algorithm based on voltage/peak current mode controls. In order to provide credible findings, a low power prototype is developed to test the control strategy via experimental evaluations of the converter topology and its controls.

Keywords: Battery charger, forward converter, lithium-ion, management algorithm, SEPIC.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 700

Authors: Muhammad Abdullah Arafat, Nahrin Nowrose

Abstract:

Wireless charging of electric vehicles is becoming more and more attractive as large amount of power can now be transferred to a reasonable distance using magnetic resonance coupling method. However, proper tuning of the compensation network is required to achieve maximum power transmission. Due to the variation of coil distance from the nominal value as a result of change in tire condition, change in weight or uneven road condition, the tuning of the compensation network has become challenging. In this paper, a tuning method has been described to determine the optimum values of the compensation network in order to maximize the average output power. The simulation results show that 5.2% increase in average output power is obtained for 10% variation in coupling coefficient using the optimum values without the need of additional space and electro-mechanical components. The proposed method is applicable to both static and dynamic charging of electric vehicles.

Keywords: Coupling coefficient, electric vehicles, magnetic resonance coupling, tuning capacitor, wireless power transfer.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 170

Authors: M. Saeki

Abstract:

This paper presents the results of an experimental study on the performance of a triboelectric separator of plastic mixtures used for recycling. The separator consists of four cylindrical electrodes. The principle behind the separation technique is based on the difference in the Coulomb force acting on the plastic particles after triboelectric charging. The separation of mixtures of acrylonitrile butadiene styrene (ABS) and polystyrene (PS) using this method was studied. The effects of the triboelectric charging time and applied voltage on the separation efficiency were investigated. The experimental results confirm that it is possible to obtain a high purity and recovery rate for the initial compositions considered in this study.

Keywords: Coulomb force, recycling, triboelectric separator, waste plastics.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2799

Authors: R. Mkahl, A. Nait-Sidi-Moh, M. Wack

Abstract:

Batteries of electric vehicles (BEV) are becoming more attractive with the advancement of new battery technologies and promotion of electric vehicles. BEV batteries are recharged on board vehicles using either the grid (G2V for Grid to Vehicle) or renewable energies in a stand-alone application (H2V for Home to Vehicle). This paper deals with the modeling, sizing and control of a photovoltaic stand-alone application that can charge the BEV at home. The modeling approach and developed mathematical models describing the system components are detailed. Simulation and experimental results are presented and commented.

Keywords: Electric vehicles, photovoltaic energy, lead-acid batteries, charging process, modeling, simulation, experimental tests.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 4154

Authors: Sven Borén, Lisiana Nurhadi, Henrik Ny

Abstract:

From a theoretical perspective, electric buses can be more sustainable and can be cheaper than fossil fuelled buses in city traffic. The authors have not found other studies based on actual urban public transport in Swedish winter climate. Further on, noise measurements from buses for the European market were found old. The aims of this follow-up study was therefore to test and possibly verify in a real-life environment how energy efficient and silent electric buses are, and then conclude on if electric buses are preferable to use in public transport. The Ebusco 2.0 electric bus, fitted with a 311 kWh battery pack, was used and the tests were carried out during November 2014-April 2015 in eight municipalities in the south of Sweden. Six tests took place in urban traffic and two took place in more of a rural traffic setting. The energy use for propulsion was measured via logging of the internal system in the bus and via an external charging meter. The average energy use turned out to be 8% less (0,96 kWh/km) than assumed in the earlier theoretical study. This rate allows for a 320 km range in public urban traffic. The interior of the bus was kept warm by a diesel heater (biodiesel will probably be used in a future operational traffic situation), which used 0,67 kWh/km in January. This verified that electric buses can be up to 25% cheaper when used in public transport in cities for about eight years. The noise was found to be lower, primarily during acceleration, than for buses with combustion engines in urban bus traffic. According to our surveys, most passengers and drivers appreciated the silent and comfortable ride and preferred electric buses rather than combustion engine buses. Bus operators and passenger transport executives were also positive to start using electric buses for public transport. The operators did however point out that procurement processes need to account for eventual risks regarding this new technology, along with personnel education. The study revealed that it is possible to establish a charging infrastructure for almost all studied bus lines. However, design of a charging infrastructure for each municipality requires further investigations, including electric grid capacity analysis, smart location of charging points, and tailored schedules to allow fast charging. In conclusion, electric buses proved to be a preferable alternative for all stakeholders involved in public bus transport in the studied municipalities. However, in order to electric buses to be a prominent support for sustainable development, they need to be charged either by stand-alone units or via an expansion of the electric grid, and the electricity should be made from new renewable sources.

Keywords: Sustainability, Electric, Bus, Noise, GreenCharge.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2229

Authors: Minghui Wang, Shanrui Hu

Abstract:

An inverse problem of doubly center matrices is discussed. By translating the constrained problem into unconstrained problem, two iterative methods are proposed. A numerical example illustrate our algorithms.

Keywords: doubly center matrix, electric network theory, iterative methods, least-square problem.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1436

Authors: Jakub Hospodka

Abstract:

This paper dissertates about issues which may occur after next year will be major part of civil aviation in EU included into system of Emission trading. This system should help to fight against global warming and to fulfill Kyoto Protocol commitments of European countries. Main issues mentioned in this paper are connected with problem of radiative forcing from emissions and lack of their monitoring and charging in EU legislative. There are mentioned main differences between industrial emissions and emissions form aviation with notification about possible negative impacts of neglecting these differences. Special attention is dedicated to risk of possible reverse effect of inclusion aviation in EU ETS, which may theoretically occur.

Keywords: EU ETS, radiative forcing, aviation, emissiontrading.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1367

Authors: Darwin Gouwanda, S. G. Ponnambalam

Abstract:

Set covering problem is a classical problem in computer science and complexity theory. It has many applications, such as airline crew scheduling problem, facilities location problem, vehicle routing, assignment problem, etc. In this paper, three different techniques are applied to solve set covering problem. Firstly, a mathematical model of set covering problem is introduced and solved by using optimization solver, LINGO. Secondly, the Genetic Algorithm Toolbox available in MATLAB is used to solve set covering problem. And lastly, an ant colony optimization method is programmed in MATLAB programming language. Results obtained from these methods are presented in tables. In order to assess the performance of the techniques used in this project, the benchmark problems available in open literature are used.

Keywords: Set covering problem, genetic algorithm, ant colony optimization, LINGO.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 3583

Authors: Chao Wang, Ting-Zhu Huang Chen Jia

Abstract:

In this paper, we propose a new linear complementarity problem named as bi-linear complementarity problem (BLCP) and the method for solving BLCP. In addition, the algorithm for error estimation of BLCP is also given. Numerical experiments show that the algorithm is efficient.

Keywords: Bi-linear complementarity problem, Linear complementarity problem, Extended linear complementarity problem, Error estimation, P-matrix, M-matrix.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1686

Authors: Sukhveer Singh, Sandeep Singh

Abstract:

A bi-objective fuzzy transportation problem with the objectives to minimize the total fuzzy cost and fuzzy time of transportation without according priorities to them is considered. To the best of our knowledge, there is no method in the literature to find efficient solutions of the bi-objective transportation problem under uncertainty. In this paper, a bi-objective transportation problem in an uncertain environment has been formulated. An algorithm has been proposed to find efficient solutions of the bi-objective transportation problem under uncertainty. The proposed algorithm avoids the degeneracy and gives the optimal solution faster than other existing algorithms for the given uncertain transportation problem.

Keywords: Transportation problem, efficient solution, ranking function, fuzzy transportation problem.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1311

Authors: Kenza Aida Amara, Bachir Djebbar

Abstract:

We treat the two-dimensional bin packing problem which involves packing a given set of rectangles into a minimum number of larger identical rectangles called bins. This combinatorial problem is NP-hard. We propose a pretreatment for the oriented version of the problem that allows the valorization of the lost areas in the bins and the reduction of the size problem. A heuristic method based on the strategy first-fit adapted to this problem is presented. We present an approach of resolution by bee colony optimization. Computational results express a comparison of the number of bins used with and without pretreatment.

Keywords: Bee colony optimization, bin packing, heuristic algorithm, pretreatment.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1049

Authors: Tsuyoshi Okita, Tatsuya Niwa

Abstract:

For a given specific problem an efficient algorithm has been the matter of study. However, an alternative approach orthogonal to this approach comes out, which is called a reduction. In general for a given specific problem this reduction approach studies how to convert an original problem into subproblems. This paper proposes a formal modeling language to support this reduction approach. We show three examples from the wide area of learning problems. The benefit is a fast prototyping of algorithms for a given new problem.

Keywords: Formal language, statistical inference problem, reduction.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1572

Authors: M. Ahmad, M. Gourgand, C. Caux

Abstract:

The Resource-Constrained Project Scheduling Problem (RCPSP) is concerned with single-item or small batch production where limited resources have to be allocated to dependent activities over time. Over the past few decades, a lot of work has been made with the use of optimal solution procedures for this basic problem type and its extensions. Brucker and Knust[1] discuss, how timetabling problems can be modeled as a RCPSP. Authors discuss high school timetabling and university course timetabling problem as an example. We have formulated two mathematical formulations of course timetabling problem in a new way which are the prototype of single-mode RCPSP. Our focus is to show, how course timetabling problem can be transformed into RCPSP. We solve this transformation model with genetic algorithm.

Keywords: Course Timetabling, Integer programming, Combinatorial optimizations

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1982

Authors: Nicolas Zufferey

Abstract:

The vehicle routing problem (VRP) is a famous combinatorial optimization problem. Because of its well-known difficulty, metaheuristics are the most appropriate methods to tackle large and realistic instances. The goal of this paper is to highlight the key ideas for designing VRP metaheuristics according to the following criteria: efficiency, speed, robustness, and ability to take advantage of the problem structure. Such elements can obviously be used to build solution methods for other combinatorial optimization problems, at least in the deterministic field.

Keywords: Vehicle routing problem, Metaheuristics, Combinatorial optimization.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2031

Authors: Mohammed Salem Alzahrani

Abstract:

In this paper the optimality of the solution of an existing real word assignment problem known as the seat assignment problem using Seat Assignment Method (SAM) is discussed. SAM is the newly driven method from three existing methods, Hungarian Method, Northwest Corner Method and Least Cost Method in a special way that produces the easiness & fairness among all methods that solve the seat assignment problem.

Keywords: Assignment Problem, Hungarian Method, Least Cost Method, Northwest Corner Method, Seat Assignment Method (SAM), A Real Word Assignment Problem.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 3395

Authors: Mhand Hifi, Hedi Mhalla, Mustapha Michaphy

Abstract:

In this paper, we study the multi-scenario knapsack problem, a variant of the well-known NP-Hard single knapsack problem. We investigate the use of an adaptive algorithm for solving heuristically the problem. The used method combines two complementary phases: a size reduction phase and a dynamic 2- opt procedure one. First, the reduction phase applies a polynomial reduction strategy; that is used for reducing the size problem. Second, the adaptive search procedure is applied in order to attain a feasible solution Finally, the performances of two versions of the proposed algorithm are evaluated on a set of randomly generated instances.

Keywords: combinatorial optimization, max-min optimization, knapsack, heuristics, problem reduction

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1560

Authors: Zohreh O. Akbari

Abstract:

In this paper a deterministic polynomial-time algorithm is presented for the Clique problem. The case is considered as the problem of omitting the minimum number of vertices from the input graph so that none of the zeroes on the graph-s adjacency matrix (except the main diagonal entries) would remain on the adjacency matrix of the resulting subgraph. The existence of a deterministic polynomial-time algorithm for the Clique problem, as an NP-complete problem will prove the equality of P and NP complexity classes.

Keywords: Clique problem, Deterministic Polynomial-time Algorithm, Equality of P and NP Complexity Classes.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1772

Authors: Ben Mohamed Ahemed Mohamed, Yassine Adnan

Abstract:

The problem of bin-packing in two dimensions (2BP) consists in placing a given set of rectangular items in a minimum number of rectangular and identical containers, called bins. This article treats the case of objects with a free orientation of 90Ôùª. We propose an approach of resolution combining optimization by colony of ants (ACO) and the heuristic method IMA to resolve this NP-Hard problem.

Keywords: Ant colony algorithm, bin-packing problem, heuristics methods.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1787

Authors: Maricar G. Misola, Bryan B. Navarro

Abstract:

Facility Layout Problem (FLP) is one of the essential problems of several types of manufacturing and service sector. It is an optimization problem on which the main objective is to obtain the efficient locations, arrangement and order of the facilities. In the literature, there are numerous facility layout problem research presented and have used meta-heuristic approaches to achieve optimal facility layout design. This paper presented genetic algorithm to solve facility layout problem; to minimize total cost function. The performance of the proposed approach was verified and compared using problems in the literature.

Keywords: Facility Layout Problem, Genetic Algorithm, Material Handling Cost, Meta-heuristic Approach.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 4685

Authors: Aldy Gunawan, Kien Ming Ng, Kim Leng Poh

Abstract:

This paper presents a hybrid algorithm for solving a timetabling problem, which is commonly encountered in many universities. The problem combines both teacher assignment and course scheduling problems simultaneously, and is presented as a mathematical programming model. However, this problem becomes intractable and it is unlikely that a proven optimal solution can be obtained by an integer programming approach, especially for large problem instances. A hybrid algorithm that combines an integer programming approach, a greedy heuristic and a modified simulated annealing algorithm collaboratively is proposed to solve the problem. Several randomly generated data sets of sizes comparable to that of an institution in Indonesia are solved using the proposed algorithm. Computational results indicate that the algorithm can overcome difficulties of large problem sizes encountered in previous related works.

Keywords: Timetabling problem, mathematical programming model, hybrid algorithm, simulated annealing.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 4522