Interactive balance space approach for solving multi-level multi-objective programming problems

This paper studies a multi-level multi-objective decision-making (ML-MODM) problems with linear or non-linear constraints. The objective functions at each level are non-linear functions, which are to be maximized or minimized.This paper presents a three-level multi-objective decision-making (TL-MODM) model and an interactive algorithm for solving such a model. The algorithm simplifies three-level multi-objective decision-making problems by transforming them into separate multi-objective decision making problems at each level, thereby avoiding the difficulty associated with non-convex mathematical programming. Our algorithm is an extension of the work of Shi and Xia [X. Shi, H. Xia, Interactive bi-level multi-objective decision making, Journal of the Operational Research Society 48 (1997) 943-949], which dealt with interactive bi-level multi-objective decision-making problems, with some modifications in assigning satisfactoriness to each objective function in all the levels of the TL-MODM problem. Also, we solve each separate multi-objective decision making problem of the TL-MODM problem by the balance space approach.A new formula is introduced to interconnect the satisfactoriness and the proportions of deviation needed to reflect the relative importance of each objective function. Thus, we have the proportions of deviation including satisfactoriness.In addition, we present new definitions for the satisfactoriness and the preferred solution in view of singular-level multi-objective decision making problems that corresponds to the η-optimal solution of the balance space approach. Also, new definitions for the feasible solution and the preferred solution (η-optimal point) of the TL-MODM problem are presented. An illustrative numerical example is given to demonstrate the algorithm.     

Integrating the logistics network design with order quantity determination under uncertain customer demands

This paper aims to design an optimal logistics network including suppliers and retailers by taking into account the order quantity of products under uncertain consumer demand pattern. This research proposes a mixed-integer bi-level programming model and employs the iterative-optimization method. In the bi-level programming, the upper model is the logistics network design (LND) problem, which is designed for suppliers and consists of the hub locations, wholesale price of the products as well as the transportation flow of the commodity. The lower model is the order quantity determination (OQD) problem for retailers. It processes a special case of inventory problem in which the customer demand is stochastic and follows a series of assumed probability distributions. By applying the proposed methodology in a computational experiment, this research shows that if there were a large number of suppliers in the logistics system, retailers could order the product with relatively low price and the largest profit belongs to the retailer who could sell the commodity at the highest price.     

知识化制造环境下航空发动机装配车间自进化

针对产品动态到达的航空发动机装配车间, 对知识化制造系统的自进化问题进行研究. 将自进化的思想应用于该装配车间, 提出了知识化制造环境下该装配车间自进化问题的求解算法. 根据双层规划理论, 建立了系统在每个决策时刻静态决策问题的一般数学模型, 并设计了一种基于可行域搜索的双层遗传算法(FR-BiGA) 对模型进行求解. 仿真结果验证了该模型与算法的有效性和可行性, 且实验数据表明, 自进化的系统具有相对较优的生产性能.

     

Modelling demand response in organized wholesale energy markets

We propose a bi-level optimization model for demand response in organized wholesale energy markets. In this model, the lower level performs the economic dispatch of energy and generates the price and the upper level minimizes the total amount of demand response subject to a net benefit requirement. In an economic sense, demand response is a trade of ‘consuming rights’ instead of a sale of energy. Therefore it must be traded separately from the energy market. Although a bi-level optimization model is very hard to solve in general, we demonstrate that realistic power networks have characteristics that can be exploited to reduce the effective size of the problem instance. In particular, we transform the nonconvex net benefit test constraint to an equivalent linear form, and reformulate the nonconvex complementarity conditions of doubly bounded variables using SOS2 constraints. For realistic instances of the MPEC, we employ a three-phase approach that exploits the fast local solution from a nonlinear programming solver as well as LP-based bound strengthening within a mixed integer/SOS2 formulation. The model is tested against various data cases and settings, and generates useful insight for demand response dispatch operations in practice.     

The combination of continuous network design and route guidance

In this study, a traffic management measure is presented by combining the route guidance of Advanced Traveler Information System (ATIS) and the continuous network design (CNDP) to alleviate increasing traffic congestion. The route guidance recommends the travelers to choose the shortest path based on marginal travel cost and user constraints. The problem is formulated into a bi-level programming problem. The most distinct property of this problem formulation is that the feasible path set of its lower-level problem is determined by the decision variable of upper-level problem, while in conventional transportation network design problems the feasible path set for lower-level traffic assignment problem is fixed to be all the viable paths between each specific origin-destination pair. The simulated annealing algorithm is improved to solve this bi-level problem. A path-based traffic algorithm is developed to calculate the lower-level traffic assignment problem under the route guidance. Compared to the results of conventional CNDP, the measure presented in this study can better improve the transportation network performance.     

考虑多种运输方式的整车物流服务供应链订单分配问题

针对整车物流服务供应链的订单分配问题，提出了考虑多种运输方式的双层订单分配模型。首先，考虑到运输方式会影响运输成本、客户的准时送达要求等因素，建立以准时送达和最小化物流采购成本为目标的双层规划模型；其次，设计启发式算法（HA）确定各运输方式的任务量；然后，借助混合蛙跳算法（SFLA）求解各功能物流服务提供商间各运输方式的任务量分配；最后，通过不同规模的算例与遗传算法（GA）、粒子群算法（PSO）、蚁群算法（ACO）等进行求解对比。算例结果表明，与原有的成本438万元相比，所提模型得到显著优化的421万元，说明所构建模型的订单分配方案能够更有效解决整车物流的订单分配问题。实验对比表明，较传统智能算法（GA、PSO、ACO）的求解结果，两阶段的HA-SFLA算法能更快得出显著优化的结果，说明HA-SFLA算法能更好地求解考虑运输方式的双层订单分配规划模型。在满足客户送达时间要求的同时，考虑运输方式的双层订单分配模型及算法显著降低物流成本，促进物流集成商为获取更多利益而在订单分配阶段考虑运输方式。     

云制造环境下基于双层规划的资源优化配置模型

为了解决云制造环境下制造资源的优化配置问题,综合考虑需求与服务双方以及云平台运营方的利益,提出了一种基于双层规划的资源优化配置模型。该模型以前景理论结合多约束多属性评价体系求解出的供需双方满意度作为上层规划的优化目标;以云平台资源利用率最大化为下层规划的优化目标;通过双层规划并采用改进的i-NSGA-II-JG算法对多目标制造资源配置问题进行求解。最后,通过算例仿真实验证明了该模型的可行性和优越性。     

Modeling and optimization of two-stage procurement in dual-channel supply chain

An online marketing platform should be designed to fairly take the benefits of buyers and suppliers into consideration based on their risk preferences and business strategies. In this paper, the dual-channel supply chain models are developed to implement the risk-averse strategy for buyers and risk-neutral strategy for suppliers, respectively. The buyers under the consideration are the manufacturers who acquire raw materials, parts, or components to make their final products. The major factors in the developed models include the risk preferences of buyers and suppliers, random price fluctuations of goods, and varying demands of final products. To reflect the purchasing practice of a manufacturer, (1) a supply chain is considered to have two supply channels, i.e., contract-based purchase with a lead-time before the goods are used and a direct purchase from online spot markets when the goods are used; (2) the time factor on decision making is specially taken into account, and the procurements are divided into the contract stage of purchase and online stage of purchase. Gaming analysis is conducted to develop the supply chain models for manufactures and suppliers to implement their purchasing or pricing strategies. The simulation is conducted and the result has shown that two-stage purchases in a dual-channel supply chain have improved the performances of suppliers and manufacturers in terms of the profits they can make, their supply–demand relations, and their adjustability to uncertainties in globalized and segmented markets. The proposed model has its significance for manufacturers to better control the price risk of goods and the demand risk of final products; on the other hand, suppliers can benefit from adjusting dynamic sales using online spot markets.     

Price-Based Residential Demand Response Management in Smart Grids: A Reinforcement Learning-Based Approach

This paper studies price-based residential demand response management (PB-RDRM) in smart grids, in which non-dispatchable and dispatchable loads (including general loads and plug-in electric vehicles (PEVs)) are both involved. The PB-RDRM is composed of a bi-level optimization problem, in which the upper-level dynamic retail pricing problem aims to maximize the profit of a utility company (UC) by selecting optimal retail prices (RPs), while the lower-level demand response (DR) problem expects to minimize the comprehensive cost of loads by coordinating their energy consumption behavior. The challenges here are mainly two-fold: 1) the uncertainty of energy consumption and RPs; 2) the flexible PEVs’ temporally coupled constraints, which make it impossible to directly develop a model-based optimization algorithm to solve the PB-RDRM. To address these challenges, we first model the dynamic retail pricing problem as a Markovian decision process (MDP), and then employ a model-free reinforcement learning (RL) algorithm to learn the optimal dynamic RPs of UC according to the loads’ responses. Our proposed RL-based DR algorithm is benchmarked against two model-based optimization approaches (i.e., distributed dual decomposition-based (DDB) method and distributed primal-dual interior (PDI)-based method), which require exact load and electricity price models. The comparison results show that, compared with the benchmark solutions, our proposed algorithm can not only adaptively decide the RPs through on-line learning processes, but also achieve larger social welfare within an unknown electricity market environment.      

Models and algorithms for competitive facility location problems with different customer behavior

Competitive facility location problems arise in the context of two non-cooperating companies, a leader and a follower, competing for market share from a given set of customers. We assume that the firms place a given number of facilities on locations taken from a discrete set of possible points. For this bi-level optimization problem we consider six different customer behavior scenarios from the literature: binary, proportional and partially binary, each combined with essential and unessential demand. The decision making for the leader and the follower depends on these scenarios. In this work we present mixed integer linear programming models for the follower problem of each scenario and use them in combination with an evolutionary algorithm to optimize the location selection for the leader. A complete solution archive is used to detect already visited candidate solutions and convert them efficiently into similar, not yet considered ones. We present numerical results of our algorithm and compare them to so far state-of-the-art approaches from the literature. Our method shows good performance in all customer behavior scenarios and is able to outperform previous solution procedures on many occasions.     

Pricing for seasonal deteriorating products with price- and ramp-type time-dependent demand

A production–inventory problem for a seasonal deteriorating product is considered. It is assumed that the demand is price- and ramp-type time-dependent. The selling season for the deteriorating product is fixed. The decision maker needs to set up the price and the production schedule at the beginning of the season. Although the profit function is not concave in general, the optimal price can be determined efficiently through a simple algorithm.     

An interactive approach based on a discrete differential evolution algorithm for a class of integer bilevel programming problems

This paper presents an interactive approach based on a discrete differential evolution algorithm to solve a class of integer bilevel programming problems, in which integer decision variables are controlled by an upper-level decision maker and real-value or continuous decision variables are controlled by a lower-level decision maker. Using the Karush--Kuhn–Tucker optimality conditions in the lower-level programming, the original discrete bilevel formulation can be converted into a discrete single-level nonlinear programming problem with the complementarity constraints, and then the smoothing technique is applied to deal with the complementarity constraints. Finally, a discrete single-level nonlinear programming problem is obtained, and solved by an interactive approach. In each iteration, for each given upper-level discrete variable, a system of nonlinear equations including the lower-level variables and Lagrange multipliers is solved first, and then a discrete nonlinear programming problem only with inequality constraints is handled by using a discrete differential evolution algorithm. Simulation results show the effectiveness of the proposed approach.     

Distributed dynamic pricing based on demand-supply balance and voltage phase difference in power grid

This paper discusses a distributed decision procedure for determining the electricity price for a real-time electricity market in an energy management system. The price decision algorithm proposed in this paper derives the optimal electricity price while considering the constraints of a linearized AC power grid model. The algorithm is based on the power demand-supply balance and voltage phase differences in a power grid. In order to determine the optimal price that maximizes the social welfare distributively and to improve the convergence speed of the algorithm, the proposed algorithm updates the price through the alternating decision making of market participants. In this paper, we show the convergence of the price derived from our proposed algorithm. Furthermore, numerical simulation results show that the proposed dynamic pricing methodology is effective and that there is an improvement in the convergence speed, as compared with the conventional method.     

Bi-level programming modeling and hierarchical hybrid algorithm for antimissile dynamic firepower allocation problem with uncertain environment

Aiming at the shortcomings of antimissile dynamic firepower allocation (ADFA) researches under uncertain environment, the fuzzy chance-constrained bi-level programming model with complex constraints is proposed by introducing the uncertain programming theory. Firstly, maximization cost-effectiveness ratio and earliest interception time as the upper and the lower objective functions of the model, respectively, are used. In order to close to the battlefield environment, the model constraint includes interception time window, effective damage lower bound and intercept strategy, etc. Secondly, a particle coding scheme and repairing scheme are given with hierarchical structure for multi-constrained bi-level ADFA problem. Furthermore, the improved variable neighborhood PSO algorithm with convergence criterions and the PSO algorithm with doubt and repulsion factor (PSO-DR) are effectively combined. On these bases, the hierarchical hybrid fuzzy particle swarm optimization algorithm is presented with fuzzy simulation technique. Finally, the results of comparison show the proposed algorithm has stronger global searching ability and faster convergence speed, which can effectively solve large-scale ADFA problem and adapt to the requirements of real-time decision.     

Look-ahead heuristics for the dynamic traveling purchaser problem

Given a set of products each with positive discrete demand, and a set of markets selling products at given prices, the traveling purchaser problem (TPP) looks for a tour visiting a subset of markets such that products demand is satisfied at minimum purchasing and traveling costs. In this paper we analyze a dynamic variant of the problem, where quantities may decrease as time goes on. Complete information is assumed on current state of the world, i.e. decision maker knows quantities available for each product in each market at present time and is informed about any consumption event when it occurs. Nevertheless, planner does not have any information on future events. Two groups of heuristics are described and compared. The first group consists of simplified approaches deciding which market to visit next on the basis of some greedy criteria considering only one of the two objective costs. The second one includes heuristics based on a look-ahead approach taking into account both traveling and purchasing costs and inserting some future prediction. Heuristics behavior has been tested on a large set of randomly generated instances under different levels of dynamism.     

供应链网络双渠道均衡

研究了制造商通过分销商实体链和电子商务直销渠道,将其产品经由零售商销售给具有随机需求的消费市场的供应链网络双渠道均衡问题.利用有限维变分不等式理论,分别刻画了存在生产能力限制的供应市场、分销市场、零售市场以及存在限定性价格上限的消费市场的均衡,建立了整个供应链网络双渠道均衡模型,并且设计了供应链网络双渠道均衡的投影收缩算法.数值算例结果表明:当政府对竞争市场实行限制性价格上限时,将造成消费市场中的商品短缺,并导致制造商、分销商以及零售商的总利润减少,当存在产能约束时情况更为严重.     

Cooperative capacity planning and resource allocation by mutual outsourcing using ant algorithm in a decentralized supply chain

Lumpy demand forces capacity planners to maximize the profit of individual factories as well as simultaneously take advantage of outsourcing from its supply chain and even competitors. This study examines a business model of capacity planning and resource allocation in which consists of two profit-centered factories. We propose an ant algorithm for solving a set of non-linear mixed integer programming models of the addressed problem with different economic objectives and constraints of negotiating parties. An individual factory applies a specific resource planning policy to improve its objective while borrowing resource capacity from its peer factory or lending extra capacity of resources to the other. The proposed method allows a mutually acceptable capacity plan of resources for a set of customer tasks to be allocated by two negotiating parties, each with private information regarding company objectives, cost and price. Experiment results reveal that near optimal solutions for both of isolated (a single factory) and negotiation-based (between the two factories) environments are obtained.     

Stochastic Programming For Order Allocation And Production Planning

Stochastic demand is an important factor that heavily affects production planning. It influences activities such as purchasing, manufacturing, and selling, and quick adaption is required. In production planning, for reasons such as reducing costs and obtaining supplier discounts, many decisions must be made in the initial stage when demand has not been realized. The effects of non-optimal decisions will propagate to later stages, which can lead to losses due to overstocks or out-of-stocks. To find the optimal solutions for the initial and later stage regarding demand realization, this study proposes a stochastic two-stage linear programming model for a multi-supplier, multi-material, and multi-product purchasing and production planning process. The objective function is the expected total cost after two stages, and the results include detailed plans for purchasing and production in each demand scenario. Small-scale problems are solved through a deterministic equivalent transformation technique. To solve the problems in the large scale, an algorithm combining metaheuristic and sample average approximation is suggested. This algorithm can be implemented in parallel to utilize the power of the solver. The algorithm based on the observation that if the remaining quantity of materials and number of units of products at the end of the initial stage are given, then the problems of the first and second stages can be decomposed.     

Fuzzy two-stage material procurement planning problem

Material procurement planning (MPP) deals with the problem that purchasing the right quantity of material from the right supplier at the right time, a purchaser can reduce the material procurement costs via a reasonable MPP model. In order to handle the MPP problem in a fuzzy environment, this paper presents a new class of two-stage fuzzy MPP models, in which the material demand, the spot market material unit price and the spot market material supply quantity are assumed to be fuzzy variables with known possibility distributions. In addition, the procurement decisions are divided into two groups. Some procurement decisions, called first-stage decisions, must be taken before knowing the the particular values taken by the fuzzy variables; while some other decisions, called second-stage decisions, can be taken after the realizations of the fuzzy variables are known. The objective of the proposed fuzzy MPP model is to minimize the expected material procurement costs over the two stages. On other hand, since the fuzzy material demand, the fuzzy spot market material unit price and the fuzzy spot market material supply quantity are usually continuous fuzzy variables with infinite supports, the proposed MPP model belongs to an infinite-dimensional optimization problem whose objective function cannot be computed exactly. To avoid this difficulty, we suggest an approximation approach (AA) to evaluating the objective function, and turn the original MPP model into an approximating finite-dimensional one. To show the credibility of the AA, the convergence about the objective function of the approximating MPP model to that of the original MPP one is discussed. Since the exact analytical expression for the objective function in the approximating fuzzy MPP model is unavailable, and the approximating MPP model is a mixed-integer program that is neither linear nor convex, the traditional optimization algorithms cannot be used to solve it. Therefore, we design an AA-based particle swarm optimization to solve the approximating two-stage fuzzy MPP model. Finally, we apply the two-stage MPP model to an actual fuel procurement problem, and demonstrate the effectiveness of the designed algorithm via numerical experiments.     

基于二层规划的供应链定价决策研究

针对一个单一制造商与多个零售商构成的分布控制型供应链,其中制造商作为主导者确定批发价,零售商确定各自的零售价,市场需求量由零售价格决定的问题,利用二层规划模型研究了具有S tacke lberg博弈特征的定价决策,并给出了混沌搜索求解算法,同时给出供应链成员合作的条件.研究结论表明,分布控制型供应链虽然不能保证系统最优,但却能实现成员利益最大化,因而均衡状态下的价格是稳定的.最后通过实例验证了给出的结论.