Bi-level programming model for reconstruction of urban branch road network

Considering the decision-making variables of the capacities of branch roads and the optimization targets of lowering the saturation of arterial roads and the reconstruction expense of branch roads, the bi-level programming model for reconstructing the branch roads was set up. The upper level model was for determining the enlarged capacities of the branch roads, and the lower level model was for calculating the flows of road sections via the user equilibrium traffic assignment method. The genetic algorithm for solving the bi-level model was designed to obtain the reconstruction capacities of the branch roads. The results show that by the bi-level model and its algorithm, the optimum scheme of urban branch roads reconstruction can be gained, which reduces the saturation of arterial roads apparently, and alleviates traffic congestion. In the data analysis the arterial saturation decreases from 1.100 to 0.996, which verifies the micro-circulation transportation's function of urban branch road network.

An Alternative Approach for Solving Bi-Level Programming Problems

An algorithm is proposed in this paper for solving two-dimensional bi-level linear programming problems without making a graph. Based on the classification of constraints, algorithm removes all redundant constraints, which eliminate the possibility of cycling and the solution of the problem is reached in a finite number of steps. Example to illustrate the method is also included in the paper.

Bi-Level Programming for the Optimal Nonlinear Distance-Based Transit Fare Structure Incorporating Principal-Agent Game

The urban transit fare structure and level can largely affect passengers’travel behavior and route choices.The commonly used transit fare policies in the present transit network would lead to the unbalanced transit assignment and improper transit resources distribution.In order to distribute transit passenger flow evenly and efficiently,this paper introduces a new distance-based fare pattern with Euclidean distance.A bi-level programming model is developed for determining the optimal distance-based fare pattern,with the path-based stochastic transit assignment(STA)problem with elastic demand being proposed at the lower level.The upper-level intends to address a principal-agent game between transport authorities and transit enterprises pursing maximization of social welfare and financial interest,respectively.A genetic algorithm(GA)is implemented to solve the bi-level model,which is verified by a numerical example to illustrate that the proposed nonlinear distance-based fare pattern presents a better financial performance and distribution effect than other fare structures.

Bilevel Programming Model for Joint Scheduling of Arrival and Departure Flights Based on Traffic Scenario

In order to meet the needs of collaborative decision making,considering the different demands of air traffic control units,airlines,airports and passengers in various traffic scenarios,the joint scheduling problem of arrival and departure flights is studied systematically.According to the matching degree of capacity and flow,it is determined that the traffic state of arrival/departure operation in a certain period is peak or off-peak.The demands of all parties in each traffic state are analyzed,and the mathematical models of arrival/departure flight scheduling in each traffic state are established.Aiming at the four kinds of joint operation traffic scenarios of arrival and departure,the corresponding bi-level programming models for joint scheduling of arrival and departure flights are established,respectively,and the elitism genetic algorithm is designed to solve the models.The results show that:Compared with the first-come-firstserved method,in the scenarios of arrival peak&departure off-peak and arrival peak&departure peak,the departure flight equilibrium satisfaction is improved,and the runway occupation time of departure flight flow is reduced by 38.8%.In the scenarios of arrival off-peak&departure off-peak and departure peak&arrival off-peak,the arrival flight equilibrium delay time is significantly reduced,the departure flight equilibrium satisfaction is improved by 77.6%,and the runway occupation time of departure flight flow is reduced by 46.6%.Compared with other four kinds of strategies,the optimal scheduling method can better balance fairness and efficiency,so the scheduling results are more reasonable.

A Lagrange Relaxation Based Approach to Solve a Discrete-Continous Bi-Level Model

In this work we propose a solution method based on Lagrange relaxation for discrete-continuous bi-level problems, with binary variables in the leading problem, considering the optimistic approach in bi-level programming. For the application of the method, the two-level problem is reformulated using the Karush-Kuhn-Tucker conditions. The resulting model is linearized taking advantage of the structure of the leading problem. Using a Lagrange relaxation algorithm, it is possible to find a global solution efficiently. The algorithm was tested to show how it performs.

A Novel Stackelberg-Game-Based Energy Storage Sharing Scheme Under Demand Charge

Demand response(DR)using shared energy storage systems(ESSs)is an appealing method to save electricity bills for users under demand charge and time-of-use(TOU)price.A novel Stackelberg-game-based ESS sharing scheme is proposed and analyzed in this study.In this scheme,the interactions between selfish users and an operator are characterized as a Stackelberg game.Operator holds a large-scale ESS that is shared among users in the form of energy transactions.It sells energy to users and sets the selling price first.It maximizes its profit through optimal pricing and ESS dispatching.Users purchase some energy from operator for the reduction of their demand charges after operator's selling price is announced.This game-theoretic ESS sharing scheme is characterized and analyzed by formulating and solving a bi-level optimization model.The upper-level optimization maximizes operator's profit and the lower-level optimization minimizes users'costs.The bi-level model is transformed and linearized into a mixed-integer linear programming(MILP)model using the mathematical programming with equilibrium constraints(MPEC)method and model linearizing techniques.Case studies with actual data are carried out to explore the economic performances of the proposed ESS sharing scheme.

Efficient Origin-Destination Estimation Using Microscopic Traffic Simulation with Restricted Rerouting

Traffic simulators are utilized to solve a variety of traffic-related problems.For such simulators,origin-destination(OD)traffic volumes as mobility demands are required to input,and we need to estimate them.The authors regard an OD estimation as a bi-level programming problem,and apply a microscopic traffic simulation model to it.However,the simulation trials can be computationally expensive if full dynamic rerouting is allowed,when employing multi-agent-based models in the estimation process.This paper proposes an efficient OD estimation method using a multi-agent-based simulator with restricted dynamic rerouting to reduce the computational load.Even though,in the case of large traffic demand,the restriction on dynamic rerouting can result in heavier congestion.The authors resolve this problem by introducing constraints of the bi-level programming problem depending on link congestion.Test results show that the accuracy of the link traffic volume reproduced with the proposed method is virtually identical to that of existing methods but that the proposed method is more computationally efficient in a wide-range or high-demand context.

Adaptive path planning for unmanned aerial vehicles based on bi-level programming and variable planning time interval

This paper presents an adaptive path planner for unmanned aerial vehicles （UAVs） to adapt a real-time path search procedure to variations and fluctuations of UAVs’ relevant performances, with respect to sensory capability, maneuverability, and flight velocity limit. On the basis of a novel adaptability-involved problem statement, bi-level programming （BLP） and variable planning step techniques are introduced to model the necessary path planning components and then an adaptive path planner is developed for the purpose of adaptation and optimization. Additionally, both probabilistic-risk-based obstacle avoidance and performance limits are described as path search constraints to guarantee path safety and navigability. A discrete-search-based path planning solution, embedded with four optimization strategies, is especially designed for the planner to efficiently generate optimal flight paths in complex operational spaces, within which different surface-to-air missiles （SAMs） are deployed. Simulation results in challenging and stochastic scenarios firstly demonstrate the effectiveness and efficiency of the proposed planner, and then verify its great adaptability and relative stability when planning optimal paths for a UAV with changing or fluctuating performances.

Stochastic Bi-level Programming Model for Home Healthcare Scheduling Problems Considering the Degree of Satisfaction with Visit Time

Home health care(HHC)includes a wide range of healthcare services that are performed in customers'homes to help them recover.With the constantly increasing demand for health care,HHC policymakers are eager to address routing and scheduling problems from the perspective of optimization.In this paper,a bi-level programming model for HHC routing and scheduling problems with stochastic travel times is proposed,in which the degree of satisfaction with the visit time is simultaneously considered.The upper-level model is formulated for customer assignment with the aim of minimizing the total operating cost,and the lower-level model is formulated as a routing problem to maximize the degree of satisfaction with the visit time.Consistent with Stackelberg game decision-making,the trade-off relationship between these two objectives can be achieved spontaneously so as to reach an equilibrium state.A three-stage hybrid algorithm combining an iterated local search framework,which uses a large neighborhood search procedure as a sub-heuristic,a set-partitioning model,and a post-optimization method is developed to solve the proposed model.Numerical experiments on a set of instances including 10 to 100 customers verify the effectiveness of the proposed model and algorithm.

Bus frequency optimization in a large-scale multi-modal transportation system:integrating 3D-MFD and dynamic traffic assignment

A properly designed public transport system is expected to improve traffic efficiency.A high-frequency bus service would decrease the waiting time for passengers,but the interaction between buses and cars might result in more serious congestion.On the other hand,a low-frequency bus service would increase the waiting time for passengers and would not reduce the use of private cars.It is important to strike a balance between high and low frequencies in order to minimize the total delays for all road users.It is critical to formulate the impacts of bus frequency on congestion dynamics and mode choices.However,as far as the authors know,most proposed bus frequency optimization formulations are based on static demand and the Bureau of Public Roads function,and do not properly consider the congestion dynamics and their impacts on mode choices.To fill this gap,this paper proposes a bi-level optimization model.A three-dimensional Macroscopic Fundamental Diagram based modeling approach is developed to capture the bi-modal congestion dynamics.A variational inequality model for the user equilibrium in mode choices is presented and solved using a double projection algorithm.A surrogate model-based algorithm is used to solve the bi-level programming problem.

Coordination of Multi-leaders and Multi-followers in Supply Chain of Value-Added Telecom Services

In order to study supply chain of the telecom value-added service,a multi-leaders and multi-followers Stackelberg game model with multiple telecom operators and multiple service providers whose income is composed of information fee division and advertisement was constructed.Then a demonstration was simulated,and the results were compared with the situation of service providers' income only from information fee division.The simulated and compared results indicate that,the enterprises in the supply chain have the nature of pursuing the maximum profits in capital markets;meanwhile,first-mover advantages and some enterprise can get more profits with the information asymmetry.

Integrated reliability of travel time and capacity of urban road network under ice and snowfall conditions

In order to evaluate and integrate travel time reliability and capacity reliability of a road network subjected to ice and snowfall conditions,the conceptions of travel time reliability and capacity reliability were defined under special conditions.The link travel time model(ice and snowfall based-bureau public road,ISB-BPR) and the path choice decision model(elastic demand user equilibrium,EDUE) were proposed.The integrated reliability was defined and the model was set up.Monte Carlo simulation was used to calculate the model and a numerical example was provided to demonstrate the application of the model and efficiency of the solution algorithm.The results show that the intensity of ice and snowfall,the traffic demand and supply,and the requirements for level of service(LOS) have great influence on the reliability of a road network.For example,the reliability drops from 65% to 5% when the traffic demand increases by 30%.The comprehensive performance index may be used for network planning,design and maintenance.

Air Route Network Generation Based on Traffic Assignment

Air route network is the carrier of air traffic flow,and traffic assignment is a method to verify the rationality of air route network structure.Therefore,air route network generation based on traffic assignment has been becoming the research focus of airspace programming technology.Based on link prediction technology and optimization theory,a bi-level programming model is established in the paper.The model includes an upper level of air route network generation model and a lower level of traffic assignment model.The air route network structure generation incorporates network topology generation algorithm based on link prediction technology and optimal path search algorithm based on preference,and the traffic assignment adopts NSGA-Ⅲalgorithm.Based on the Python platform NetworkX complex network analysis library,a network of 57 airports,383 nodes,and 635 segments within China Airspace Beijing and Shanghai Flight Information Regions and 187975 sorties of traffic are used to simulate the bilevel model.Compared with the existing air route network,the proposed air route network can decrease the cost by 50.624%,lower the flight conflict coefficient by 33.564%,and reduce dynamic non-linear coefficient by 7.830%.

Non-probabilistic Robust Optimal Design Method

For the purpose of dealing with uncertainty factors in engineering optimization problems, this paper presents a new non-probabilistic robust optimal design method based on maximum variation estimation. The method analyzes the effect of uncertain factors to objective and constraints functions, and then the maximal variations to a solution are calculated. In order to guarantee robust feasibility the maximal variations of constraints are added to original constraints as penalty term; the maximal variation of objective function is taken as a robust index to a solution; linear physical programming is used to adjust the values of quality characteristic and quality variation, and then a bi-level mathematical robust optimal model is constructed. The method does not require presumed probability distribution of uncertain factors or continuous and differentiable of objective and constraints functions. To demonstrate the proposed method, the design of the two-bar structure acted by concentrated load is presented. In the example the robustness of the normal stress, feasibility of the total volume and the buckling stress are studied. The robust optimal design results show that in the condition of maintaining feasibility robustness, the proposed approach can obtain a robust solution which the designer is satisfied with the value of objective function and its variation.

Modeling the Parking Pricing of Multiple Parking Facilities under Different Operation Regimes

To explore the parking pricing of multiple parking facilities, this paper proposes a bi-level programming model, in which the interactions between parking operators and travelers are explicitly considered. The upper-level sub-model simulates the price decision-making behaviors of the parking operators whose objectives may vary under different operation regimes, such as monopoly market, oligopoly competition, and social optimum. The lower level represents a network equilibrium model that simulates how travelers choose modes, routes, and parking facilities. The proposed model is solved by a sensitivity based algorithm, and applied to a numerical experiment, in which three types of parking facilities are studied, i.e., the off-road parking lot, the curb parking lot, and the parking-and-ride (P&R) facility. The results show in oligopoly market that the level of parking price reaches the lowest point, nonetheless the social welfare decreases to the lowest simultaneously;and the share of P&R mode goes to the highest value, however the total network costs rise also to the highest. While the monopoly market and the social optimum regimes result in solutions of which P&R facilities suffer negative profits and have to be subsidized.

Model and algorithm of optimizing alternate traffic restriction scheme in urban traffic network

An optimization model and its solution algorithm for alternate traffic restriction(ATR) schemes were introduced in terms of both the restriction districts and the proportion of restricted automobiles. A bi-level programming model was proposed to model the ATR scheme optimization problem by aiming at consumer surplus maximization and overload flow minimization at the upper-level model. At the lower-level model, elastic demand, mode choice and multi-class user equilibrium assignment were synthetically optimized. A genetic algorithm involving prolonging codes was constructed, demonstrating high computing efficiency in that it dynamically includes newly-appearing overload links in the codes so as to reduce the subsequent searching range. Moreover,practical processing approaches were suggested, which may improve the operability of the model-based solutions.

Optimal planning of energy storage system in active distribution system based on fuzzy multi-objective bi-level optimization

A fuzzy multi-objective bi-level optimization problem is proposed to model the planning of energy storage system(ESS) in active distribution systems(ADS). The proposed model enables us to take into account how optimal operation strategy of ESS in the lower level can affect and be affected by the optimal allocation of ESS in the upper level. The power characteristic model of micro-grid(MG)and typical daily scenarios are established to take full consideration of time-variable nature of renewable energy generations(REGs) and load demand while easing the burden of computation. To solve the bi-level mixed integer problem, a multi-subgroup hierarchical chaos hybrid algorithm is introduced based on differential evolution(DE) and particle swarm optimization(PSO). The modified IEEE-33 bus benchmark distribution system is utilized to investigate the availability and effectiveness of the proposed model and the hybrid algorithm. Results indicate that the planningmodel gives an adequate consideration to the optimal operation and different roles of ESS, and has the advantages of objectiveness and reasonableness.

A Chaotic Approach for the Bi-level Discrete Equilibrium Network Design Problem

A chaotic algorithm for providing a solution to the bi-level Discrete Equilibrium Network Design Problem （NDP） is discussed following an introduction of the Discrete Network Design Problem （DNDP） model and Chaos Optimization Algorithms （COA）. A description of the chaotic approach for the DNDP model is described in details. Then a numerical example for the DNDP is carried out to investigate the chaotic approach. The results have been encouraging, indicating that the chaotic approach has great potential ability in finding the optimal solution of DNDP models.

Optimizing Emergency Logistics for the Offsite Hazardous Waste Management

Hazardous wastes pose increasing threats to people and environment during the processes of offsite collection,storage,treatment,and disposal.A novel game theoretic model,including two levels,is developed for the corresponding optimization of emergency logistics,where the upper level indicates the location and capacity problem for the regulator,and the lower level reflects the allocation problem for the emergency commander.Different from other works in the literature,we focus on the issue of multi-quality coverages (full and partial coverages) in the optimization of facility location and allocation.To be specific,the regulator decides the location plan and the corresponding capacity of storing emergency groups for multiple types of hazmats,so to minimizes the total potential environmental risk posed by incident sites;while the commander minimizes the total costs to provide an efficient allocation policy.To solve the bi-level programming model,two solution techniques,namely a KKT condition approach and a heuristic model,are designed and compared.The proposed model and solution techniques are then applied to a hypothetical case and a real-world case to demonstrate the practicality and provide managerial insights.

Congestion management with demand response considering uncertainties of distributed generation outputs and market prices

In recent years,much attention has been devoted to the development and applications of smart grid technologies,with special emphasis on flexible resources such as distributed generations(DGs),energy storages,active loads,and electric vehicles(EVs).Demand response(DR) is expected to be an effective means for accommodating the integration of renewable energy generations and mitigating their power output fluctuations.Despite their potential contributions to power system secure and economic operation,uncoordinated operations of these flexible resources may result in unexpected congestions in the distribution system concerned.In addition,the behaviors and impacts of flexible resources are normally highly uncertain and complex in deregulated electricity market environments.In this context,this paper aims to propose a DR based congestion management strategy for smart distribution systems.The general framework and procedures for distribution congestion management is first presented.A bi-level optimization model for the day-ahead congestion management based on the proposed framework is established.Subsequently,the robust optimization approach is introduced to alleviate negative impacts introduced by the uncertainties of DG power outputs and market prices.The economic efficiency and robustness of the proposed congestion management strategy is demonstrated by an actual 0.4 kV distribution system in Denmark.