二层随机规划逼近解的收敛性

对二层随机规划的逼近解的收敛性作了探讨,证明了当随机向量序列{ζ(k)(w)}依分布收敛于ζ(w)时,相应于ζ(k)(w)的二层随机规划问题的任何最优解序列将收敛到原问题的最优解.     

Natural gas bilevel cash-out problem: Convergence of a penalty function method

This paper studies a special bi-level programming problem that arises from the dealings of a Natural Gas Shipping Company and the Pipeline Operator, with facilities of the latter used by the former. Because of the business relationships between these two actors, the timing and objectives of their decision-making process are different and sometimes even opposed. In order to model that, bi-level programming was traditionally used in previous works. Later, the problem was expanded and theoretically studied to facilitate its solution; this included extension of the upper level objective function, linear reformulation, heuristic approaches, and branch-and-bound techniques. In this paper, we present a linear programming reformulation of the latest version of the model, which is significantly faster to solve when implemented computationally. More importantly, this new formulation makes it easier to analyze the problem theoretically, allowing us to draw some conclusions about the nature of the solution of the modified problem. Numerical results concerning the running time, convergence, and optimal values, are presented and compared to previous reports, showing a significant improvement in speed without actual sacrifice of the solution’s quality.     

Two phased hybrid local search for the periodic capacitated arc routing problem

The periodic capacitated arc routing problem (PCARP) is a challenging general model with important applications. The PCARP has two hierarchical optimization objectives: a primary objective of minimizing the number of vehicles (F_v) and a secondary objective of minimizing the total cost (F_c). In this paper, we propose an effective two phased hybrid local search (HLS) algorithm for the PCARP. The first phase makes a particular effort to optimize the primary objective while the second phase seeks to further optimize both objectives by using the resulting number of vehicles of the first phase as an upper bound to prune the search space. For both phases, combined local search heuristics are devised to ensure an effective exploration of the search space. Experimental results on 63 benchmark instances demonstrate that HLS performs remarkably well both in terms of computational efficiency and solution quality. In particular, HLS discovers 44 improved best known values (new upper bounds) for the total cost objective F_c while attaining all the known optimal values regarding the objective of the number of vehicles F_v. To our knowledge, this is the first PCARP algorithm reaching such a performance. Key components of HLS are analyzed to better understand their contributions to the overall performance.     

TOPSIS for bi-level MODM problems

TOPSIS (technique for order preference by similarity to ideal solution) is a multiple criteria method to identify solutions from a finite set of alternatives based upon simultaneous minimization of distance from an ideal point and maximization of distance from a nadir point. This paper proposes a fuzzy TOPSIS algorithm to solve bi-level multi-objective decision-making (BL-MODM) problems, and in which the objective function at each level are non-linear functions which are to be maximized. The proposed model for getting the satisfactory solution of the BL-MODM problems includes the membership functions for the upper level decision variables vector with possible tolerances, the membership function of the distance function from the positive ideal solution (PIS) and the membership function of the distance function from the negative ideal solution (NIS). A numerical illustrative example is given to clarify the proposed TOPSIS approach of this paper.     

A fuzzy shortest path with the highest reliability

This paper concentrates on a shortest path problem on a network where arc lengths (costs) are not deterministic numbers, but imprecise ones. Here, costs of the shortest path problem are fuzzy intervals with increasing membership functions, whereas the membership function of the total cost of the shortest path is a fuzzy interval with a decreasing linear membership function. By the max–min criterion suggested in [R.E. Bellman, L.A. Zade, Decision-making in a fuzzy environment, Management Science 17B (1970) 141–164], the fuzzy shortest path problem can be treated as a mixed integer nonlinear programming problem. We show that this problem can be simplified into a bi-level programming problem that is very solvable. Here, we propose an efficient algorithm, based on the parametric shortest path problem for solving the bi-level programming problem. An illustrative example is given to demonstrate our proposed algorithm.     

Weighting method for bi-level linear fractional programming problems

In this paper we consider the solution of a bi-level linear fractional programming problem (BLLFPP) by weighting method. A non-dominated solution set is obtained by this method. In this article decision makers (DMs) provide their preference bounds to the decision variables that is the upper and lower bounds to the decision variables they control. We convert the hierarchical system into scalar optimization problem (SOP) by finding proper weights using the analytic hierarchy process (AHP) so that objective functions of both levels can be combined into one objective function. Here the relative weights represent the relative importance of the objective functions.     

A global optimization algorithm for generalized semi-infinite,continuous minimax with coupled constraints and bi-level problems

We propose an algorithm for the global optimization of three problem classes: generalized semi-infinite, continuous coupled minimax and bi-level problems. We make no convexity assumptions. For each problem class, we construct an oracle that decides whether a given objective value is achievable or not. If a given value is achievable, the oracle returns a point with a value better than or equal to the target. A binary search is then performed until the global optimum is obtained with the desired accuracy. This is achieved by solving a series of appropriate finite minimax and min-max-min problems to global optimality. We use Laplace’s smoothing technique and a simulated annealing approach for the solution of these problems. We present computational examples for all three problem classes.     

A turning restriction design problem in urban road networks

Turning restriction is one of the commonest traffic management techniques and an effective low cost traffic improvement strategy in urban road networks. However, the literature has not paid much attention to the turning restriction design problem (TRDP), which aims to determine a set of intersections where turning restrictions should be implemented. In this paper, a bi-level programming model is proposed to formulate the TRDP. The upper level problem is to minimize the total travel cost from the viewpoint of traffic managers, and the lower level problem is to depict travelers’ route choice behavior based on stochastic user equilibrium (SUE) theory. We propose a branch and bound method (BBM), based on the sensitivity analysis algorithm (SAA), to find the optimal turning restriction strategy. A branch strategy and a bound strategy are applied to accelerate the solution process of the TRDP. The computational experiments give promising results, showing that the optimal turning restriction strategy can obviously reduce system congestion and are robust to the variations of both the dispersion parameter of the SUE problem and the level of demand.     

全系数模糊两层线性规划

利用结构元方法定义一种模糊数排序准则,对模糊系数(目标函数与约束条件中系数为有界模糊数情形)的隶属函数为非单调函数的情形,给出将全系数模糊两层线性规划等价转化为经典的线性规划的方法,并证明了其合理性.与其它方法相比较,该方法不仅约束条件少,而且运算方法简便.最后,将本文的方法运用到数值算例中,进一步表明该提法的有效性和广泛性.     

An M/G/1 queue under hysteretic vacation policy with an early startup and un-reliable server

This paper considers the bi-level control of an M/G/1 queueing system, in which an un-reliable server operates N policy with a single vacation and an early startup. The server takes a vacation of random length when he finishes serving all customers in the system (i.e., the system is empty). Upon completion of the vacation, the server inspects the number of customers waiting in the queue. If the number of customers is greater than or equal to a predetermined threshold m, the server immediately performs a startup time; otherwise, he remains dormant in the system and waits until m or more customers accumulate in the queue. After the startup, if there are N or more customers waiting for service, the server immediately begins serving the waiting customers. Otherwise the server is stand-by in the system and waits until the accumulated number of customers reaches or exceeds N. Further, it is assumed that the server breaks down according to a Poisson process and his repair time has a general distribution. We obtain the probability generating function in the system through the decomposition property and then derive the system characteristics