Battery swap station location-routing problem with capacitated electric vehicles

In this paper, we present an electric vehicles battery swap stations location routing problem (BSS–EV–LRP), which aims to determine the location strategy of battery swap stations (BSSs) and the routing plan of a fleet of electric vehicles (EVs) simultaneously under battery driving range limitation. The problem is formulated as an integer programming model under the basic and extended scenarios. A four-phase heuristic called SIGALNS and a two-phase Tabu Search-modified Clarke and Wright Savings heuristic (TS-MCWS) are proposed to solve the problem. In the proposed SIGALNS, the BSSs location stage and the vehicle routing stage are alternated iteratively, which considers the information from the routing plan while improving the location strategy. In the first phase, an initial routing plan is generated with a modified sweep algorithm, leading to the BSSs location subproblem, which is then solved by using an iterated greedy heuristic. In the third phase, the vehicle routes resulting from the location subproblem are determined by applying an adaptive large neighborhood search heuristic with several new neighborhood structures. At the end of SIGALNS, the solution is further improved by a split procedure. Compared with the MIP solver of CPLEX and TS-MCWS over three sets of instances, SIGALNS searches the solution space more efficiently, thus producing good solutions without excessive computation on the medium and large instances. Furthermore, we systematically conduct economic and environmental analysis including the comparison between basic and extended scenarios, sensitivity analysis on battery driving range and efficiency analysis about the vehicle emissions reduction when EVs are used in the logistics practice.     

A population dynamics model to describe gene frequencies in evolutionary algorithms

The performance of evolutionary algorithms (EAs) may heavily depend severely on a suitable choice of parameters such as mutation and crossover rates. Several methods to adjust those parameters have been developed in order to enhance EA performance. For this purpose, it is important to understand the EA dynamics, i.e., to appreciate the behavior of the population. Hence, this paper presents a new model of population dynamics to describe and predict the diversity in any particular generation. The formulation is based on selecting the probability density function of each individual. The population dynamics proposed is modeled for a generational population. The model was tested in several case studies of different population sizes. The results suggest that the prediction error decreases as the population size increases.     

Parameter estimation for crop growth model using evolutionary and bio-inspired algorithms

All dynamic crop models for growth and development have several parameters whose values are usually determined by using measurements coming from the real system. The parameter estimation problem is raised as an optimization problem and optimization algorithms are used to solve it. However, because the model generally is nonlinear the optimization problem likely is multimodal and therefore classical local search methods fail in locating the global minimum and as a consequence the model parameters could be inaccurate estimated. This paper presents a comparison of several evolutionary (EAs) and bio-inspired (BIAs) algorithms, considered as global optimization methods, such as Differential Evolution (DE), Covariance Matrix Adaptation Evolution Strategy (CMA-ES), Particle Swarm Optimization (PSO) and Artificial Bee Colony (ABC) on parameter estimation of crop growth SUCROS (a Simple and Universal CROp Growth Simulator) model. Subsequently, the SUCROS model for potential growth was applied to a husk tomato crop (Physalis ixocarpa Brot. ex Horm.) using data coming from an experiment carried out in Chapingo, Mexico. The objective was to determine which algorithm generates parameter values that give the best prediction of the model. An analysis of variance (ANOVA) was carried out to statistically evaluate the efficiency and effectiveness of the studied algorithms. Algorithm's efficiency was evaluated by counting the number of times the objective function was required to approximate an optimum. On the other hand, the effectiveness was evaluated by counting the number of times that the algorithm converged to an optimum. Simulation results showed that standard DE/rand/1/bin got the best result.     

Optimal driving during electric vehicle acceleration using evolutionary algorithms

Due to the limited amount of stored battery energy it is necessary to optimally accelerate electric vehicles (EVs), especially in urban driving cycles. Moreover, a quick speed change is also important to minimize the trip time. Conversely, for comfortable driving, the jerk experienced during speed changing must be minimum. This study focuses on finding a comfortable driving strategy for EVs during speed changes by solving a multi-objective optimization problem (MOOP) with various conflicting objectives. Variants of two different competing evolutionary algorithms (EAs), NSGA-II (a non-dominated sorting multi-objective genetic algorithm) and SPEA 2 (strength Pareto evolutionary algorithm), are adopted to solve the problem. The design parameters include the acceleration value(s) with the associated duration(s) and the controller gains. The Pareto-optimal front is obtained by solving the corresponding MOOP. Suitable multi-criterion decision-making techniques are employed to select a preferred solution for practical implementation. After an extensive analysis of EA performance and keeping online implementation in mind, it was observed that NSGA-II with the crowding distance approach was the most suitable. A recently proposed innovization procedure was used to reveal salient properties associated with the obtained trade-off solutions. These solutions were analyzed to study the effectiveness of various parameters influencing comfortable driving.     

Observations in using parallel and sequential evolutionary algorithms for automatic software testing

In this paper we analyze the application of parallel and sequential evolutionary algorithms (EAs) to the automatic test data generation problem. The problem consists of automatically creating a set of input data to test a program. This is a fundamental step in software development and a time consuming task in existing software companies. Canonical sequential EAs have been used in the past for this task. We explore here the use of parallel EAs. Evidence of greater efficiency, larger diversity maintenance, additional availability of memory/CPU, and multi-solution capabilities of the parallel approach, reinforce the importance of the advances in research with these algorithms. We describe in this work how canonical genetic algorithms (GAs) and evolutionary strategies (ESs) can help in software testing, and what the advantages are (if any) of using decentralized populations in these techniques. In addition, we study the influence of some parameters of the proposed test data generator in the results. For the experiments we use a large benchmark composed of twelve programs that includes fundamental algorithms in computer science.     

Combined state of charge estimator for electric vehicle battery pack

Ah counting is not a satisfactory method for the estimation of the state of charge (SOC) of a battery, as the initial SOC and coulomb efficiency are difficult to measure. To address this issue, an equivalent coulomb efficiency is defined and a new SOC estimation method, denoted as “KalmanAh”, is proposed. This method uses the Kalman filtering method to correct for the initial value used in the Ah counting method. A Ni/MH battery test, consisting of 8.08 continuous federal urban driving schedule (FUDS) cycles, is carried out to verify the method. The SOC estimation error is 2.5% when compared with the real SOC obtained from a discharge test. This compares favorably with an estimation error of 11.4% when using Ah counting.     

A new hybrid method using evolutionary algorithms to train Fuzzy Cognitive Maps

A novel hybrid method based on evolutionary computation techniques is presented in this paper for training Fuzzy Cognitive Maps. Fuzzy Cognitive Maps is a soft computing technique for modeling complex systems, which combines the synergistic theories of neural networks and fuzzy logic. The methodology of developing Fuzzy Cognitive Maps relies on human expert experience and knowledge, but still exhibits weaknesses in utilization of learning methods and algorithmic background. For this purpose, we investigate a coupling of differential evolution algorithm and unsupervised Hebbian learning algorithm, using both the global search capabilities of Evolutionary strategies and the effectiveness of the nonlinear Hebbian learning rule. The use of differential evolution algorithm is related to the concept of evolution of a number of individuals from generation to generation and that of nonlinear Hebbian rule to the concept of adaptation to the environment by learning. The hybrid algorithm is introduced, presented and applied successfully in real-world problems, from chemical industry and medicine. Experimental results suggest that the hybrid strategy is capable to train FCM effectively leading the system to desired states and determining an appropriate weight matrix for each specific problem.     

A survey of genetic algorithms for solving multi depot vehicle routing problem

This article presents a survey of genetic algorithms that are designed for solving multi depot vehicle routing problem. In this context, most of the articles focus on different genetic approaches, methods and operators, commonly used in practical applications to solve this well-known and researched problem. Besides providing an up-to-date overview of the research in the field, the results of a thorough experiment are presented and discussed, which evaluated the efficiency of different existing genetic methods on standard benchmark problems in detail. In this manner, the insights into strengths and weaknesses of specific methods, operators and settings are presented, which should help researchers and practitioners to optimize their solutions in further studies done with the similar type of the problem in mind. Finally, genetic algorithm based solutions are compared with other existing approaches, both exact and heuristic, for solving this same problem.     

Parameter estimation for five- and seven-parameter photovoltaic electrical models using evolutionary algorithms

Equivalent electric circuit modeling of PV devices is widely used to predict PV electrical performance. The first task in using the model to calculate the electrical characteristics of a PV device is to find the model parameters which represent the PV device. In the present work, parameter estimation for the model parameter using various evolutionary algorithms is presented and compared. The constraint set on the estimation process is that only the data directly available in module datasheets can be used for estimating the parameters. The electrical model accuracy using the estimated parameters is then compared to several electrical models reported in literature for various PV cell technologies.     

A flexible distributed framework for realising electric and plug-in hybrid vehicle charging policies

Motivated by the problems of charging a number of electric vehicles via limited capacity infrastructure, this article considers the problem of individual load adjustment under a total capacity constraint. For reasons of scalability and simplified communications, distributed solutions to this problem are sought. Borrowing from communication networks (AIMD algorithms) and distributed convex optimisation, we describe a number of distributed algorithms for achieving relative average fairness whilst maximising utilisation. We present analysis and simulation results to show the performance of these algorithms. In the scenarios examined, the algorithm's performance is typically within 5% of that achievable in the ideal centralised case, but with greatly enhanced scalability and reduced communication requirements.     

A case study on using evolutionary algorithms to optimize bakery production planning

The production of bakery goods is strictly time sensitive due to the complex biochemical processes during dough fermentation, which leads to special requirements for production planning and scheduling. Instead of mathematical methods scheduling is often completely based on the practical experience of the responsible employees in bakeries. This sometimes inconsiderate scheduling approach often leads to sub-optimal performance of companies. This paper presents the modeling of the production in bakeries as a kind of no-wait hybrid flow-shop following the definitions in Scheduling Theory, concerning the constraints and frame conditions given by the employed processes properties. Particle Swarm Optimization and Ant Colony Optimization, two widely used evolutionary algorithms for solving scheduling problems, were adapted and used to analyse and optimize the production planning of an example bakery. In combination with the created model both algorithms proved capable to provide optimized results for the scheduling operation within a predefined runtime of 15 min.     

Time Complexity of Evolutionary Algorithms for Combinatorial Optimization： A Decade of Results

Computational time complexity analyzes of evolutionary algorithms (EAs) have been performed since the mid-nineties. The first results were related to very simple algorithms,such as the (1 1)-EA,on toy problems.These efforts produced a deeper understanding of how EAs perform on different kinds of fitness landscapes and general mathematical tools that may be extended to the analysis of more complicated EAs on more realistic problems.In fact,in recent years,it has been possible to analyze the (1 1)-EA on combinatorial optimization problems with practical applications and more realistic population-baeed EAs on structured toy problems. This paper presents a survey of the results obtained in the last decade along these two research lines.The most common mathematical techniques are introduced,the basic ideas behind them are discussed and their elective applications are highlighted.Solved problems that were still open are enumerated as are those still awaiting for a solution.New questions and problems arisen in the meantime are also considered.     

A distributed charging strategy based on day ahead price model for PV-powered electric vehicle charging station

This paper studies a distributed charging model based on day-ahead optimal internal price for PV-powered Electric Vehicle (EV) Charging Station (PVCS). Considering the feed-in-tariff of PV energy, the price of utility grid and the forecast model of PV based on back-propagation neural network (BPNN), a system operation model of PVCS is introduced, which consists of the profit model of PVCS operator (PO) and the cost model of EV users. The model proposed in this paper can be designed as a Stackelberg game model, where the PO acts as the leader and all EV users participated are regarded as the followers. An optimization strategy based on heuristic algorithm and nonlinear constrained programming are adopted by the PO and each EV user, respectively. Moreover, a real-time billing strategy is proposed to deal with the errors from the forecasted PV energy and the expected charging arrangements. Finally, through a practical case, the validity of the model is verified in terms of increasing operation profit and reducing charging cost.     

A bit-masking oriented data structure for evolutionary operators implementation in genetic algorithms

 In the present paper a special bit-masking oriented data structure for an improved implementation of crossover and mutation operators in genetic algorithms is shown. The developed data structure performs evolutionary operators in two separate steps: crossover and mutation mask fill and a special boolean based function application. Both phases are optimized to reach a more efficient, fast and flexible genetic reproduction than standard implementations. The method has been powered adding a multi-layered, bit-masking oriented data structure and a boolean operation based control mixer, allowing special blended crossover operators obtained by superposition of the standard ones. Several examples of crossover schemes produced by these extended controls are presented. In addition, a special purpose crossover scheme, capable to process at the same time two distinct groups of design variables with separate crossover schemes is shown, in order to improve efficiency and convergence speed of some discrete/continuous optimization problems. Finally, to highlight further capabilities of the bit-masking approach, a special single-step version of an evolutionary direction operator is also illustrated.     

A general framework for statistical performance comparison of evolutionary computation algorithms

This paper proposes a statistical methodology for comparing the performance of evolutionary computation algorithms. A twofold sampling scheme for collecting performance data is introduced, and these data are analyzed using bootstrap-based multiple hypothesis testing procedures. The proposed method is sufficiently flexible to allow the researcher to choose how performance is measured, does not rely upon distributional assumptions, and can be extended to analyze many other randomized numeric optimization routines. As a result, this approach offers a convenient, flexible, and reliable technique for comparing algorithms in a wide variety of applications.     

A pareto-based evolutionary algorithm using decomposition and truncation for dynamic multi-objective optimization

Maintaining a balance between convergence and diversity of the population in the objective space has been widely recognized as the main challenge when solving problems with two or more conflicting objectives. This is added by another difficulty of tracking the Pareto optimal solutions set (POS) and/or the Pareto optimal front (POF) in dynamic scenarios. Confronting these two issues, this paper proposes a Pareto-based evolutionary algorithm using decomposition and truncation to address such dynamic multi-objective optimization problems (DMOPs). The proposed algorithm includes three contributions: a novel mating selection strategy, an efficient environmental selection technique and an effective dynamic response mechanism. The mating selection considers the decomposition-based method to select two promising mating parents with good diversity and convergence. The environmental selection presents a modified truncation method to preserve good diversity. The dynamic response mechanism is evoked to produce some solutions with good diversity and convergence whenever an environmental change is detected. In the experimental studies, a range of dynamic multi-objective benchmark problems with different characteristics were carried out to evaluate the performance of the proposed method. The experimental results demonstrate that the method is very competitive in terms of convergence and diversity, as well as in response speed to the changes, when compared with six other state-of-the-art methods.     

A robust model for finding optimal evolutionary trees

Constructing evolutionary trees for species sets is a fundamental problem in computational biology. One of the standard models assumes the ability to compute distances between every pair of species, and seeks to find an edge-weighted treeT in which the distanced _ij ^T in the tree between the leaves ofT corresponding to the speciesi andj exactly equals the observed distance,d _ij . When such a tree exists, this is expressed in the biological literature by saying that the distance function or matrix isadditive, and trees can be constructed from additive distance matrices in0(n ²) time. Real distance data is hardly ever additive, and we therefore need ways of modeling the problem of finding the best-fit tree as an optimization problem.In this paper we present several natural and realistic ways of modeling the inaccuracies in the distance data. In one model we assume that we have upper and lower bounds for the distances between pairs of species and try to find an additive distance matrix between these bounds. In a second model we are given a partial matrix and asked to find if we can fill in the unspecified entries in order to make the entire matrix additive. For both of these models we also consider a more restrictive problem of finding a matrix that fits a tree which is not only additive but alsoultrametric. Ultrametric matrices correspond to trees which can be rooted so that the distance from the root to any leaf is the same. Ultrametric matrices are desirable in biology since the edge weights then indicate evolutionary time. We give polynomial-time algorithms for some of the problems while showing others to be NP-complete. We also consider various ways of fitting a given distance matrix (or a pair of upper- and lower-bound matrices) to a tree in order to minimize various criteria of error in the fit. For most criteria this optimization problem turns out to be NP-hard, while we do get polynomial-time algorithms for some.Supported by DIMACS under NSF Contract STC-88-09648.Supported by NSF Grant CCR-9108969.This work was begun while this author was visiting DIMACS in July and August 1992, and was supported in part by the U.S. Department of Energy under Contract DE-AC04-76DP00789.     

An indirect elicitation method for the parameters of the ELECTRE TRI-nB model using genetic algorithms

Indirect approaches for eliciting preference model parameters for multiple criteria decision aiding are of growing interest because they imply relatively less cognitive effort from the decision-maker (DM). Direct approaches are particularly hard in the case of the new ELECTRE TRI-nB method, because the task involves eliciting a number of limiting profiles for each category boundary. However, in ELECTRE methods, the simultaneous inference of the whole set of parameters needs the construction and resolution of a non-linear non-convex programming problem, which is typically very hard to solve. Therefore, an evolutionary-based method to infer the parameters of the ELECTRE TRI-nB model is proposed in this paper. The quality of the solutions is tested by measuring the capacity to restore the assignment examples and the capacity to make consistent assignments of new actions. In extensive computer experiments, using the pseudo-conjunctive assignment procedure, some main conclusions arise: (i) the capacity of the method to restore the training examples reaches high values, mainly with three and five limiting profiles per category; and (ii) the capacity to make appropriate assignments of new actions (not belonging to the training information) can be greatly improved by increasing the number of limiting profiles.     

A technique for dynamic battery model identification in automotive applications using linear parameter varying structures

In this paper, a rapid calibration procedure for identifying the parameters of a dynamic model of batteries for use in automotive applications is described. The dynamic model is a phenomenological model based on an equivalent circuit model with varying parameters that are linear spline functions of the state of charge (SoC). The model identification process is done in a layered fashion: a two step optimization process using a genetic algorithm (GA) is used to optimize the parameters of the model over an experimental data set that encompasses the operating conditions of interest for the batteries. The level of accuracy obtained with this procedure is comparable to other black/gray box techniques, while requiring very little calibration effort. The process has been applied to both lithium ion and NiMH chemistries with good results. An extension of this technique to identify a model with both SoC and temperature dependence is discussed.