Co-evolutionary algorithms to solve hierarchized Steiner tree problems in telecommunication networks

This study investigates a hierarchized Steiner tree problem in telecommunication networks. In such networks, users must be connected to capacitated hubs. Additionally, selected hubs must be connected to each other and to extra hubs, if necessary, by considering the latency of the resultant network. A connection between hubs can be considered to be a Steiner tree. This Steiner tree problem is modeled as a bi-level mathematical programming problem that considers two decision levels. In the upper-level, the allocation of users to hubs is performed to minimize the total network connection cost. The lower-level minimizes the user latency concerning the information that flows through the capacitated hubs. Further, two co-evolutionary schemes are developed to solve this bi-level model. The first scheme is an individual–population approach, whereas the second scheme is the traditional population–population approach. The first proposed algorithm exploits the structure of the problem by employing parallel computing in one of the populations. Numerical results depict the effectiveness of the proposed algorithms when the lower-level problem cannot be optimally solved efficiently. Furthermore, the advantages of the proposed schemes over an evolutionary one are exhibited. Finally, the hybridization of both co-evolutionary schemes is implemented to improve the semi-feasible solutions obtained by the second scheme, showing its effectiveness to solve the problem.     

A bi-level school bus routing problem with bus stops selection and possibility of demand outsourcing

This paper develops a bi-level mathematical model for the school bus routing problem aiming at designing an efficient transportation system considering the possibility of predicting the students’ response. In the real world, the demand for using private cars depends on how well public transportation systems are operating especially in metropolitan cities. An inefficient public transportation will lead to an increase in the demand for using private cars. This issue will result in problems such as increased traffics and urban pollutions. To address this issue, an efficient public transportation system is designed by developing a new bi-level mathematical model. In the proposed model, the designer of the public transportation system, as the upper-level decision-maker, will locate appropriate bus stops and identify bus navigation routes. Subsequently, the decision regarding the allocation of students to transportation systems or outsourcing them will be made at the lower level which is considered as an operational-level decision-making. To solve this problem, two hybrid metaheuristic approaches named GA-EX-TS and SA-EX-TS have been proposed based on location-allocation-routing (LAR) strategy. The performance of these proposed methods is compared with exact solutions achieved from an explicit enumeration approach followed in the small-scale instances. Finally, the proposed approaches are used to solve 50 random instance problems. Comparing the results of the two tuned hybrid algorithms and conducting the sensitivity analysis of the model provide evidence for the good performance of the proposed approach.     

Integrate multi-agent planning in hinterland transport: Design,implementation and evaluation

This paper addresses the planning issue in hinterland barge transport domain, characterized by limited information sharing, lack of cooperation and conflict of interest among different parties (terminal and barge party). The planning problem is formulated as a novel Stackelberg game to model a leader–followers bi-level optimization problem. A hybrid algorithm is developed that concerns different objectives (vessel turn around and terminal berthing capacity) simultaneously while fulling pre-defined operational constraints. The presented algorithm is outlined in a hierarchical way and embedded into dedicated agents as decision-making kernel. We describe the architecture and the implementation of the proposed mediator-based multi agent system and overall coupling framework include agent identification, coordination and decision making. A case study evaluates the performance of our approach in terms of global optimality compared with other related approach.     

A bi-level programming for logistics network design with system-optimized flows

This paper proposes a bi-level programming for a logistics network design problem with system-optimized flows. We applied the Wardrop’s second principle to the logistics network design problem. A system-optimized logistics network design problem can be formulated as a bi-level program. For the system-optimized flows, a user equilibrium traffic assignment problem with marginal costs can be solved at the lower level problem. Due to the non-differentiability of the perturbed solutions in system-optimized flows, we present a novel solution algorithm to efficiently solve the logistics network design problem. By using the subgradients of the objective function, a new projection method is proposed with global convergence. Numerical calculations are implemented using a grid-size hypothetical network and comparisons are made with other alternatives in solving the logistics network design problem. Numerical results disclose that the proposed method has successful solved the logistics network design problem and achieved significant performance both in computational efficacy and cost reduction when compared to other alternatives.     

Analysis of different approaches to cross-dock truck scheduling with truck arrival time uncertainty

This paper studies scheduling of inbound trucks at the inbound doors of a cross-dock facility under truck arrival time uncertainty. Arrival time of an inbound truck is considered to be unknown. In particular, the cross-dock operator only acknowledges the arrival time window of each truck, i.e., the lower and upper bounds of any inbound truck’s arrival time. In absence of any additional information, the cross-dock operator may use three approaches to determine a scheduling strategy: deterministic approach (which assumes expected truck arrival times are equal to their mid-arrival time windows), pessimistic approach (which assumes the worst truck arrivals will be realized), and optimistic approach (which assumes the best truck arrivals will be realized). In this paper, a bi-level optimization problem is formulated for pessimistic and optimistic approaches. We discuss a Genetic Algorithm (GA) to solve the truck-to-door assignments for given truck arrival times, which solves the deterministic approach. Then the GA is modified to solve the bi-level formulations of the pessimistic and the optimistic approaches. Our numerical studies show that an hybrid approach regarding the pessimistic and the optimistic approaches may outperform all of the three approaches in certain cases.     

Bi-level programming enabled design of an intelligent maritime search and rescue system

This paper studies an intelligent maritime search and rescue (SAR) system problem. According to historical accidents and available SAR equipment information, a bi-level mixed-integer programming (MIP) model is proposed to determine the type and number of SAR equipment allocated to activated stations. Particle swarm optimization (PSO) algorithm and genetic algorithm (GA) algorithm are applied to solve the proposed mathematical model. Computational experiments based on real instances in the East Sea China not only validate the effectiveness of the bi-level MIP model in balancing two objectives during decision process, but also indicate that PSO algorithm is better than GA algorithm to solve the proposed model and generate reasonable equipment allocation plans. Some managerial implications are also outlined on the basis of the numerical experiments.     

A comprehensive modeling framework for hazmat network design,hazmat response team location,and equity of risk

This paper considers a bi-level hazmat transportation network design problem in which hazmat shipments have to be transported over a road network between specified origin-destination points. The bi-level framework involves a regulatory authority and hazmat carriers. The control variables for the regulatory authority are locations of hazmat response teams and which additional links to include for hazmat travel. The regulatory authority (upper level) aims to minimize the maximum transport risk incurred by a transportation zone, which is related to risk equity. Our measure of risk incorporates the average response time to the hazmat incidents. Hazmat carriers (lower level) seek to minimize their travel cost. Using optimality conditions, we reformulate the non-linear bi-level model as a single-level mixed integer linear program, which is computationally tractable for medium size problems using a commercial solver. For large size problems, we propose a greedy heuristic approach, which we empirically demonstrate to find good solutions with reasonable computational effort. We also seek a robust solution to capture stochastic characteristics of the model. Experimental results are based on popular test networks from the Sioux Falls and Albany areas.     

A fuzzy bi-criteria transportation problem

In this paper, a fuzzy bi-criteria transportation problem is studied. Here, the model concentrates on two criteria: total delivery time and total profit of transportation. The delivery times on links are fuzzy intervals with increasing linear membership functions, whereas the total delivery time on the network is a fuzzy interval with a decreasing linear membership function. On the other hand, the transporting profits on links are fuzzy intervals with decreasing linear membership functions and the total profit of transportation is a fuzzy number with an increasing linear membership function. Supplies and demands are deterministic numbers. A nonlinear programming model considers the problem using the max–min criterion suggested by Bellman and Zadeh. We show that the problem can be simplified into two bi-level programming problems, which are solved very conveniently. A proposed efficient algorithm based on parametric linear programming solves the bi-level problems. To explain the algorithm two illustrative examples are provided, systematically.     

Optimizing reserve capacity of urban road networks in a discrete Network Design Problem

This paper addresses the problem of designing of street directions and lane additions in urban road networks, based on the concept of reserve capacity. Reserve capacity is identified by the largest multiplier applied to a given existing demand matrix, that can be allocated to a network without violating the arc capacities. Having a two-way streets base network and the allowable street lane additions, the problem is to find the optimum configuration of street directions and two-way street lane allocations, and the optimum selection of street lane addition projects, in a way that the reserve capacity of the network is maximized. The problem is considered in two variations; in the first variation no restriction is imposed on the symmetricity of lane allocations for two-way streets, and in the second variation, two-way street lane allocations are restricted to be symmetric. The proposed problems are modeled as mixed-integer bi-level mathematical problems. A hybrid genetic algorithm and an evolutionary simulated annealing algorithm are proposed to solve the models. Computational results for both problem variations are presented.     

城市快速路网匝道与污染控制双层多目标规划模型

基于环境容量和交通容量,建立了一个双层多目标规划模型描述城市快速道路网的污染控制与匝道控制,并考虑了用户的路径选择行为．设计了基于改进遗传算法的启发式求解算法。该算法借助不可微精确罚函数将约束问题转化为单个无约束问题来解决,采用混合杂交和间歇变异提高算法的搜索能力．最后。通过算例说明该模型及算法的有效性．     

Stackelberg–Nash equilibrium of pricing and inventory decisions in duopoly supply chains using a nested evolutionary algorithm

Pricing and inventory control in a competing environment, as separate entities, have attracted much attention from academics and practitioners. However, integrating these decisions in a competitive setting has not been significantly analyzed by academics, but is of great significance to practitioners. In this study, the joint decision on price and inventory control of a deterioration product is investigated in a duopoly setting. We consider two competing supply chains, each consisting of one manufacturer and one retailer. Each manufacturer, as the leader of their supply chain determines the wholesale price to maximize their profit, while the retailer as the follower should determine the retail price and inventory cycle to maximize his or her profit. Using a game theoretic approach, we formulate in-chain, and chain-to-chain competition as a bi-level programming problem, and analyze Stackelberg–Nash equilibrium of the problem. Furthermore, two versions of a nested algorithm are proposed to obtain the equilibrium. Both versions employ a modified threshold-accepting (TA) algorithm to solve the first level of the problem. However, while the first version utilizes the modified TA algorithm to deal with the second level of the problem, the second version applies a differential evolution (DE) approach. Eventually, a numerical study is carried out not only to compare two developed versions of the algorithm, but also to implement the sensitivity analysis of main parameters. Based on numerical experiments, although the accuracy of both versions of algorithm are alike, using TA is more computationally efficient than using DE. Furthermore, despite the permissibility of partial backlogging, it has never occurred in equilibrium points due to in-chain and chain-to-chain competition.     

A feedback neural network for solving convex quadratic bi-level programming problems

In this paper, a feedback neural network model is proposed for solving a class of convex quadratic bi-level programming problems based on the idea of successive approximation. Differing from existing neural network models, the proposed neural network has the least number of state variables and simple structure. Based on Lyapunov theories, we prove that the equilibrium point sequence of the feedback neural network can approximately converge to an optimal solution of the convex quadratic bi-level problem under certain conditions, and the corresponding sequence of the function value approximately converges to the optimal value of the convex quadratic bi-level problem. Simulation experiments on three numerical examples and a portfolio selection problem are provided to show the efficiency and performance of the proposed neural network approach.     

A bi-level programming model for protection of hierarchical facilities under imminent attacks

Disorders caused by deliberate sabotage and terrorist attacks have always been considered as a major threat by the governments. Hence, identifying and planning for strengthening of critical facilities have become a priority for more security and safety. This paper presents a bi-level formulation of the r-interdiction median problem with fortification for critical hierarchical facilities. In the developed bi-level formulation, the defender, as the leader, decides to protect a certain number of facilities in each level of the hierarchical system in order to minimize the impact of the most disruptive attacks to unprotected facilities. On the other hand the attacker, as the follower, with full information about protected facilities, makes his interdiction plan to maximize the total post-attack cost incurred to the defender. We develop three metaheuristic algorithms and an exhaustive enumeration method to solve the introduced problem. Extensive computational tests on a set of randomly generated instances demonstrate the effectiveness of the developed algorithms.     

钢铁企业年度生产计划的研究

针对多分厂、多机型的钢铁企业年度生产计划问题,建立一个以提高经济效益为目的,包含生产工艺、资源和能力等约束的多层递阶优化数学模型,并研究了模型的算法．该算法首先从产品结构的角度将多层问题转换为两层模型,然后对此两层模型利用遗传算法和二阶段法进行求解．仿真结果表明了该模型和算法的有效性和可行性．     

A bi-level interactive decision support framework to identify data mining-oriented electronic health record architectures

Nowadays, many healthcares are generating and collecting a huge amount of medical data. Due to the difficulty of analyzing this massive volume of data using traditional methods, medical data mining on Electronic Health Record (EHR) has been a major concern in medical research. Therefore, it is necessary to assess EHR architectures based on the capabilities of extracting useful medical knowledge from a huge amount of EHR databases. In this paper, we develop a bi-level interactive decision support framework to identify data mining-oriented EHR architectures. The contribution of this bi-level framework is fourfold: (1) it develops Interactive Simple Additive Weighting (ISAW) model from an individual single-level environment to a group bi-level environment; (2) it utilizes decision makers’ preferences gradually in the course of interactions to reach to a consensus on an data mining-oriented EHR architecture; (3) it considers fuzzy logic and fuzzy sets to represent ambiguous, uncertain or imprecise information; and (4) it synthesizes a representative outcome based on qualitative and quantitative indicators in the EHR assessment process. A case study demonstrates the applicability of the proposed bi-level interactive framework for benchmarking a national data mining-oriented EHR.     

Healthcare service configuration based on project scheduling

Configuration has been recognized as an effective methodology to provide high product variety that caters to individual customer’s needs in the manufacturing industry. For healthcare service configuration, this decision-making process can be taken as service package creation and treated analogously as a project, which is defined as a collection of tasks. This research develops a decision support model to integrate individual patients into the healthcare service configuration process. The healthcare service configuration is formulated as a Resource Constrained Project Scheduling Problem (RCPSP), and a bi-level optimization algorithm based on Genetic Algorithm (GA) is developed for problem solving. The methodology and algorithm are implemented with a case study based on the data obtained from a general hospital in Singapore, which has demonstrated the applicability of healthcare service configuration.     

军用飞机自动测试系统被测对象分析确认

目前对军机ATS的研究关注点大多着眼于具体ATE平台以及TPS等的技术实现,而并未从飞机级总体需求出发,进行系统性的需求分析研究。本文从两级维修体制的保障需求出发,进行军用飞机自动测试系统被测对象的分析确认研究。确定了分析确认过程分初步筛选和深度分析确认两步走的策略,并提出了两步走中需要着重考虑的因素。     

基于迭代的部分传输序列备选信号相关性降低峰均功率比算法

部分传输序列(PTS)算法能够有效降低正交频分复用(OFDM)系统中高峰均功率比(PAPR)问题,并且不会引入失真,但PTS算法具有较高的复杂度。针对该问题,提出一种称为相关循环迭代的PTS(CC-IPTS)新算法。该算法利用迭代PTS在搜索最优相位因子时相邻相位因子间的关系以及迭代PTS(IPTS)中备选信号间相关性的特点,进行循环迭代。仿真结果表明,所提算法不但取得了较低的算法复杂度,还有效降低了峰均功率比。     

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

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

     

A multi-objective bi-level location planning problem for stone industrial parks

This paper focuses on a stone industrial park location problem with a hierarchical structure consisting of a local government and several stone enterprises under a random environment. In contrast to previous studies, conflicts between the local authority and the stone enterprises are considered. The local government, being the leader in the hierarchy, aims to minimize both total pollution emissions and total development and operating costs. The stone enterprises, as the followers in the hierarchy, only aim to minimize total costs. In addition, unit production cost and unit transportation cost are considered random variables. This complicated multi-objective bi-level optimization problem poses several challenges, including randomness, two-level decision making, conflicting objectives, and difficulty in searching for the optimal solutions. Various approaches are employed to tackle these challenges. In order to make the model trackable, expected value operator is used to deal with the random variables in the objective functions and a chance constraint-checking method is employed to deal with such variables in the constraints. The problem is solved using a bi-level interactive method based on a satisfactory solution and Adaptive Chaotic Particle Swarm Optimization (ACPSO). Finally, a case study is conducted to demonstrate the practicality and efficiency of the proposed model and solution algorithm. The performance of the proposed bi-level model and ACPSO algorithm was highlighted by comparing to a single-level model and basic PSO and GA algorithms.