计及需求响应不确定性的综合能源系统多目标优化调度管理

需求响应作为电力系统的重要调节手段,可显著提升系统灵活性和经济性。利用价格弹性构建了包含价格与激励措施的需求响应模型,并在此基础上考虑需求响应的不确定性,以综合能源系统经济性和环保性为优化目标,构建了综合能源系统多目标优化调度模型。利用E约束法将多目标优化模型转化为单目标优化模型,得到Pareto最优解集,运用模糊决策法从中选取最优方案。基于实际案例进行测算,结果表明价格型与激励型需求响应手段的结合能够实现削峰填谷,有效降低系统的运行成本和碳排放量。     

A discrete model for optimal operation of fossil-fuel generators of electricity

This paper presents a new discrete approach to the price-based dynamic economic dispatch (PBDED) problem of fossil-fuel generators of electricity. The objective is to find a sequence of generator temperatures that maximizes profit over a fixed-length time horizon. The generic optimization model presented in this paper can be applied to automatic operation of fossil-fuel generators or to prepare market bids, and it works with various price forecasts. The model’s practical applications are demonstrated by the results of simulation experiments involving 2009 NYISO electricity market data, branch-and-bound, and tabu-search optimization techniques.     

Two-settlement electricity markets with price caps and Cournot generation firms

We compare two alternative mechanisms for capping prices in two-settlement electricity markets. With sufficient lead time, forward market prices are implicitly capped by competitive pressure of potential entry that will occur when forward prices rise above some backstop price. Another more direct approach is to cap spot prices through a regulatory intervention. In this paper we explore the implications of these two alternative mechanisms in a two-settlement Cournot equilibrium framework. We formulate the market equilibrium as a stochastic equilibrium problem with equilibrium constraints (EPEC) capturing congestion effects, probabilistic contingencies and horizontal market power. As an illustrative test case, we use the 53-bus Belgian electricity network with representative generator costs but hypothetical demand and ownership structure. Compared to a price-uncapped two-settlement system, a forward cap increases firms’ incentives for forward contracting, whereas a spot cap reduces such incentives. Moreover, in both cases, more forward contracts are committed as the generation resource ownership structure becomes more diversified.     

Evaluation of the multiobjective ant colony algorithm performances on biobjective quadratic assignment problems

The difficulty of resolving the multiobjective combinatorial optimization problems with traditional methods has directed researchers to investigate new approaches which perform better. In recent years some algorithms based on ant colony optimization (ACO) metaheuristic have been suggested to solve these multiobjective problems. In this study these algorithms have been reported and programmed both to solve the biobjective quadratic assignment problem (BiQAP) instances and to evaluate the performances of these algorithms. The robust parameter sets for each 12 multiobjective ant colony optimization (MOACO) algorithms have been calculated and BiQAP instances in the literature have been solved within these parameter sets. The performances of the algorithms have been evaluated by comparing the Pareto fronts obtained from these algorithms. In the evaluation step, a multi significance test is used in a non hierarchical structure, and a performance metric (P metric) essential for this test is introduced. Through this study, decision makers will be able to put in the biobjective algorithms in an order according to the priority values calculated from the algorithms’ Pareto fronts. Moreover, this is the first time that MOACO algorithms have been compared by solving BiQAPs.     

Scheduling electric power production at a wind farm

We present a model for scheduling power generation at a wind farm, and introduce a particle swarm optimization algorithm with a small world network structure to solve the model. The solution generated by the algorithm defines the operational status of wind turbines for a scheduling horizon selected by a decision maker. Different operational scenarios are constructed based on time series data of electricity price, grid demand, and wind speed. The computational results provide insights into management of a wind farm.     

Semi-Lagrangean approach for price discovery in markets with non-convexities

From standard economic theory, the market clearing price for a commodity is set where the demand and supply curves intersect. Convexity is a property that economic models require for a competitive equilibrium, which is efficient and well-behaved and provides equilibrium prices. However, some markets present non-convexities due to their cost structure or due to some operational constraints that need to be addressed. This is the case for electricity markets where the electricity producers incur costs for shutting down a generating unit and then bringing it back on. Non-convex cost structures can be a challenge for the price discovery process, since the supply and demand curves may not intersect, or if they intersect, the price found may not be high enough to cover the total cost of production. We apply a Semi-Lagrangean approach to find a price that can be applied in the electricity pool markets where a central system operator decides who produces and how much they should produce. By applying the model to an example from the literature, we found prices that are high enough to cover the producer’s total costs, and follows the optimal solution for achieving mining cost in production. The prices are an alternative solution to the price discovery problem in non-convexities economies; in addition, they provide nonnegative profits to all the generators without the use of side-payments or up-lifts, and closes the integrality gap.     

A branch-and-price algorithm to solve the integrated berth allocation and yard assignment problem in bulk ports

In this research, two crucial optimization problems of berth allocation and yard assignment in the context of bulk ports are studied. We discuss how these problems are interrelated and can be combined and solved as a single large scale optimization problem. More importantly we highlight the differences in operations between bulk ports and container terminals which highlights the need to devise specific solutions for bulk ports. The objective is to minimize the total service time of vessels berthing at the port. We propose an exact solution algorithm based on a branch and price framework to solve the integrated problem. In the proposed model, the master problem is formulated as a set-partitioning problem, and subproblems to identify columns with negative reduced costs are solved using mixed integer programming. To obtain sub-optimal solutions quickly, a metaheuristic approach based on critical-shaking neighborhood search is presented. The proposed algorithms are tested and validated through numerical experiments based on instances inspired from real bulk port data. The results indicate that the algorithms can be successfully used to solve instances containing up to 40 vessels within reasonable computational time.     

Multiobjective GRASP with Path Relinking

In this paper we review and propose different adaptations of the GRASP metaheuristic to solve multiobjective combinatorial optimization problems. In particular, we describe several alternatives to specialize the construction and improvement components of GRASP when two or more objectives are considered. GRASP has been successfully coupled with Path Relinking for single-objective optimization. Moreover, we propose different hybridizations of GRASP and Path Relinking for multiobjective optimization. We apply the proposed GRASP with Path Relinking variants to two combinatorial optimization problems, the biobjective orienteering problem and the biobjective path dissimilarity problem. We report on empirical tests with 70 instances and 30 algorithms, that show that the proposed heuristics are competitive with the state-of-the-art methods for these problems.     

Solving 0–1 semidefinite programs for distributionally robust allocation of surgery blocks

We allocate surgery blocks to operating rooms (ORs) under random surgery durations. Given unknown distribution of the duration of each block, we investigate distributionally robust (DR) variants of two types of stochastic programming models using a moment-based ambiguous set. We minimize the total cost of opening ORs and allocating surgery blocks, while constraining OR overtime via chance constraints and via an expected penalty cost in the objective function, respectively in the two types of models. Following conic duality, we build equivalent 0–1 semidefinite programming (SDP) reformulations of the DR models and solve them using cutting-plane algorithms. For the DR chance-constrained model, we also derive a 0–1 second-order conic programming approximation to obtain less conservative solutions. We compare different models and solution methods by testing randomly generated instances. Our results show that the DR chance-constrained model better controls average and worst-case OR overtime, as compared to the stochastic programming and DR expected-penalty-based models. Our cutting-plane algorithms also outperform standard optimization solvers and efficiently solve 0–1 SDP formulations.     

Well-tuned algorithms for the Team Orienteering Problem with Time Windows

The Team Orienteering Problem with Time Windows (TOPTW) is the extension of the Orienteering Problem (OP) where each node is limited by a predefined time window during which the service has to start. The objective of the TOPTW is to maximize the total collected score by visiting a set of nodes with a limited number of paths. We propose two algorithms, Iterated Local Search and a hybridization of Simulated Annealing and Iterated Local Search (SAILS), to solve the TOPTW. As indicated in multiple research works on algorithms for the OP and its variants, determining appropriate parameter values in a statistical way remains a challenge. We apply Design of Experiments, namely factorial experimental design, to screen and rank all the parameters thereby allowing us to focus on the parameter search space of the important parameters. The proposed algorithms are tested on benchmark TOPTW instances. We demonstrate that well-tuned ILS and SAILS lead to improvements in terms of the quality of the solutions. More precisely, we are able to improve 50 best known solution values on the available benchmark instances.     

带有风能的智能电网多周期买电策略研究

本文研究带有风能随机供给的智能电网中传统能源的多周期买电问题,假设存在一个能源运营商集中负责智能电网传统能源的购买和消费。通过构建并求解动态规划模型,找到能源运营商在风能供给不确定性下的传统能源最优多周期买电策略。在最优买电策略下,能源运营商只有在当期电价足够小时才购买传统能源,其买电量与风能分布、价格信息和时间信息有关。在实际数据的基础之上,提供详实的数值实验对比研究了本文的最优买电策略和其他两种策略(实践中只考虑风能估计的策略和放弃利用风能的策略)在最小化总成本方面的效果,并验证了本文的最优买电策略在真实风能数据中的鲁棒性。     

A comparative study of decomposition algorithms for stochastic combinatorial optimization

This paper presents comparative computational results using three decomposition algorithms on a battery of instances drawn from two different applications. In order to preserve the commonalities among the algorithms in our experiments, we have designed a testbed which is used to study instances arising in server location under uncertainty and strategic supply chain planning under uncertainty. Insights related to alternative implementation issues leading to more efficient implementations, benchmarks for serial processing, and scalability of the methods are also presented. The computational experience demonstrates the promising potential of the disjunctive decomposition (D ²) approach towards solving several large-scale problem instances from the two application areas. Furthermore, the study shows that convergence of the D ² methods for stochastic combinatorial optimization (SCO) is in fact attainable since the methods scale well with the number of scenarios.     

Technology selection and capacity investment under uncertainty

We analyze the problem of technology selection and capacity investment for electricity generation in a competitive environment under uncertainty. Adopting a Nash-Cournot competition model, we consider the marginal cost as the uncertain parameter, although the results can be easily generalized to other sources of uncertainty such as a load curve. In the model, firms make three different decisions: (i) the portfolio of technologies, (ii) each technology’s capacity and (iii) the technology’s production level for every scenario. The decisions related to the portfolio and capacity are ex-ante and the production level is ex-post to the realization of uncertainty. We discuss open and closed-loop models, with the aim to understand the relationship between different technologies’ cost structures and the portfolio of generation technologies adopted by firms in equilibrium. For a competitive setting, to the best of our knowledge, this paper is the first not only to explicitly discuss the relation between costs and generation portfolio but also to allow firms to choose a portfolio of technologies. We show that portfolio diversification arises even with risk-neutral firms and technologies with different cost expectations. We also investigate conditions on the probability and cost under which different equilibria of the game arise.     

Launching new products through exclusive sales channels

When launching a new product, a manufacturer usually sells it through competing retailers under non-exclusive arrangements. Recently, many new products (cellphones, electronics, toys, etc.) are sold through a single sales channel via an exclusive arrangement. In this paper we present two separate models that examine these two arrangements. Each model is based on a Stackelberg game in which the manufacturer acts as the leader by setting the wholesale price and the retailers act as the followers by choosing their retail prices. For each model, we solve the Stackelberg game by determining the manufacturer’s optimal wholesale price and each retailer’s optimal retail price in equilibrium. Then we examine the conditions under which the manufacturer should sell the new product through an exclusive retailer. In addition, we examine the impact of postponing the wholesale price decision and the impact of demand uncertainty on the manufacturer’s optimal profit under both arrangements.     

Estimation of Electricity Market Distribution Functions

In an electricity pool market the market distribution function gives the probability that a generator offering a certain quantity of power at a certain price will not be dispatched all of this quantity by the pool. It represents the uncertainty in a pool market associated with the offers of the other agents as well as demand. We present a general Bayesian update scheme for market distribution functions. To illustrate the approach a particular form of this procedure is applied to real data obtained from a New Zealand electricity generator.     

Divide to conquer: decomposition methods for energy optimization

Modern electricity systems provide a plethora of challenging issues in optimization. The increasing penetration of low carbon renewable sources of energy introduces uncertainty in problems traditionally modeled in a deterministic setting. The liberalization of the electricity sector brought the need of designing sound markets, ensuring capacity investments while properly reflecting strategic interactions. In all these problems, hedging risk, possibly in a dynamic manner, is also a concern. The fact of representing uncertainty and/or competition of different companies in a multi-settlement power market considerably increases the number of variables and constraints. For this reason, usually a trade-off needs to be found between modeling and numerical tractability: the more details are brought into the model, the harder becomes the optimization problem. For structured optimization and generalized equilibrium problems, we explore some variants of solution methods based on Lagrangian relaxation and on Benders decomposition. Throughout we keep as a leading thread the actual practical value of such techniques in terms of their efficiency to solve energy related problems.     

Average shadow price and equilibrium price: A case study of tradable pollution permit markets

Shadow prices indicate implicit values of limited resources at the margin and provide important information in decision making for resource management. In continuous economic models, shadow prices associated with demand-supply balance constraints represent consumers’ willingness to pay and producers’ marginal cost, hence they correspond to market equilibrium prices. As well known, however, marginal analysis fails in the case of discrete optimization, such as mixed integer programming. An alternative concept has been introduced in the literature to measure the value of an extra unit of a limited resource in such cases. This concept is based on average rather than marginal values, thus called the average shadow price, and interpreted in the same way as conventional shadow prices. Whether average shadow prices in a discrete economic model can serve as market equilibrium prices has not been addressed in the related literature. The present paper addresses this issue in an empirical setting. Using a tradable pollution permit market as an example, where firms’ YES/NO type technology adoption decisions are represented by binary variables, we show that the average shadow price of tradable permits can be interpreted as the equilibrium price only when certain conditions related to the cost structure and emission levels hold. On the other hand, we show that an iterative procedure based on individual firms’ cost minimizing behavior presents a better approach for finding a price that can eliminate or reduce the gap between demand and supply of permits in the market.     

Two-stage based ensemble optimization framework for large-scale global optimization

Large-scale global optimization (LSGO) is a very important and challenging task in optimization domain, which is embedded in many scientific and engineering applications. In order to strengthen both effectiveness and efficiency of LSGO algorithm, this paper designs a two-stage based ensemble optimization evolutionary algorithm (EOEA) framework, which serially implements two sub-optimizers. These two sub-optimizers mainly focus on exploration and exploitation separately. The EOEA framework can be easily generated, flexibly altered and modified, according to different implementation conditions. In order to analyze the effects of EOEA’s components, we compare its performance on diverse kinds of problems with its two sub-optimizers and three variants. To show its superiorities over the previous LSGO algorithms, we compare its performance with six classical LSGO algorithms on the LSGO test functions of IEEE Congress of Evolutionary Computation (CEC 2008). The performance of EOEA is further evaluated by experimental comparison with four state-of-the-art LSGO algorithms on the test functions of CEC 2010 LSGO competition. To benchmark the practical applicability of EOEA, we adopt EOEA to the parameter calibration problem of water pipeline system. Based on the experimental results on diverse scales of systems, EOEA performs steadily and robustly.