对AGV路径规划A星算法的改进与验证

为了减少AGV(Automate Guide Vehicle,自动导引车)的运输路径长度和转折次数,提出了改进的A星算法,采用几何方法对传统A星算法规划出的路径进行进一步优化。首先遍历路径上的所有节点,剔除路径中冗余节点和不必要拐点,获取仅包含起点、必要拐点、终点的路径。最后计算AGV在拐点处的旋转角度及旋转方向,使AGV在拐点处能够调整自身姿态。并分别对传统A星算法、蚁群算法和改进A星算法进行了对比实验。实验结果表明该方法不仅保留了A星算法运算速度快的优点,还能够有效地规划出距离短且平滑的路径。提高了AGV的运行效率,降低了AGV的耗能。

基于Internet的二维优化下料方法及其实现技术

二维优化下料问题是一个NP -复杂性问题 ,每一种优化软件都是利用近似和启发式处理得到下料结果 ,不同的优化方法及其优化软件对不同的某些数据结构可能效果并不理想 ,企业又不可能购进大量不同的优化软件来选优。针对以上问题本文提出了一种基于Internet的二维优化下料解决方法 ,并给出了该方法的具体实现技术。实验表明 ,该方法将明显提高二维优化下料的总体优化效果。

HEURISTIC PARTICLE SWARM OPTIMIZATION ALGORITHM FOR AIR COMBAT DECISION-MAKING ON CMTA

Combining the heuristic algorithm （HA） developed based on the specific knowledge of the cooperative multiple target attack （CMTA） tactics and the particle swarm optimization （PSO）, a heuristic particle swarm optimization （HPSO） algorithm is proposed to solve the decision-making （DM） problem. HA facilitates to search the local optimum in the neighborhood of a solution, while the PSO algorithm tends to explore the search space for possible solutions. Combining the advantages of HA and PSO, HPSO algorithms can find out the global optimum quickly and efficiently. It obtains the DM solution by seeking for the optimal assignment of missiles of friendly fighter aircrafts （FAs） to hostile FAs. Simulation results show that the proposed algorithm is superior to the general PSO algorithm and two GA based algorithms in searching for the best solution to the DM problem.

HEURISTIC STUDY OF FLOWSHOP SCHEDULING TO MINIMIZE MEAN FLOW TIME WITH LOT TRANSFER CONSIDERED

Lot scheduling problem with idle time transfer between processes to minimize mean flow time is very important because to minimize mean flow time is to minimize work in process. But the problem is NP hard and no polynomial algorithm exists to guarantee optimal solution. Based the analysis the mathematical structure of the problem, the paper presents a new heuristic algorithm. Computer simulation shows that the proposed heuristic algorithm performs well in terms of both quality of solution and execution speed.

A Topology-Cognitive Algorithm Framework for Virtual Network Embedding Problem

The virtual network embedding/mapping problem is an important issue in network virtualization in Software-Defined Networking(SDN).It is mainly concerned with mapping virtual network requests,which could be a set of SDN flows,onto a shared substrate network automatically and efficiently.Previous researches mainly focus on developing heuristic algorithms for general topology virtual network.In practice however,the virtual network is usually generated with specific topology for specific purpose.Thus,it is a challenge to optimize the heuristic algorithms with these topology information.In order to deal with this problem,we propose a topology-cognitive algorithm framework,which is composed of a guiding principle for topology algorithm developing and a compound algorithm.The compound algorithm is composed of several subalgorithms,which are optimized for specific topologies.We develop star,tree,and ring topology algorithms as examples,other subalgorithms can be easily achieved following the same framework.The simulation results show that the topology-cognitive algorithm framework is effective in developing new topology algorithms,and the developed compound algorithm greatly enhances the performance of the Revenue/Cost(R/C) ratio and the Runtime than traditional heuristic algorithms for multi-topology virtual network embedding problem.

An Uncertain Programming Model for Land Use Structure Optimization to Promote Effectiveness of Land Use Planning

Land use structure optimization(LUSO) is an important issue for land use planning. In order for land use planning to have reasonable flexibility, uncertain optimization should be applied for LUSO. In this paper, the researcher first expounded the uncertainties of LUSO. Based on this, an interval programming model was developed, of which interval variables were to hold land use uncertainties. To solve the model, a heuristics based on Genetic Algorithm was designed according to Pareto Optimum principle with a confidence interval under given significance level to represent LUSO result. Proposed method was applied to a real case of Yangzhou, an eastern city in China. The following conclusions were reached. 1) Different forms of uncertainties ranged from certainty to indeterminacy lay in the five steps of LUSO, indicating necessary need of comprehensive approach to quantify them. 2) With regards to trade-offs of conflicted objectives and preferences to uncertainties, our proposed model displayed good ability of making planning decision process transparent, therefore providing an effective tool for flexible land use planning compiling. 3) Under uncertain conditions, land use planning effectiveness can be primarily enhanced by flexible management with reserved space to percept and hold uncertainties in advance.

A Fuzzy-based Adaptive Genetic Algorithm and Its Case Study in Chemical Engineering

Considering that the performance of a genetic algorithm （GA） is affected by many factors and their rela-tionships are complex and hard to be described,a novel fuzzy-based adaptive genetic algorithm （FAGA） combined a new artificial immune system with fuzzy system theory is proposed due to the fact fuzzy theory can describe high complex problems.In FAGA,immune theory is used to improve the performance of selection operation.And,crossover probability and mutation probability are adjusted dynamically by fuzzy inferences,which are developed according to the heuristic fuzzy relationship between algorithm performances and control parameters.The experi-ments show that FAGA can efficiently overcome shortcomings of GA,i.e.,premature and slow,and obtain better results than two typical fuzzy GAs.Finally,FAGA was used for the parameters estimation of reaction kinetics model and the satisfactory result was obtained.

Rescue vehicle allocation problem based on optimal reliable path under uncertainty

Consideration of the travel time variation for rescue vehicles is significant in the field of emergency management research.Because of uncertain factors,such as the weather or OD(origin-destination)variations caused by traffic accidents,travel time is a random variable.In emergency situations,it is particularly necessary to determine the optimal reliable route of rescue vehicles from the perspective of uncertainty.This paper first proposes an optimal reliable path finding(ORPF)model for rescue vehicles,which considers the uncertainties of travel time,and link correlations.On this basis,it investigates how to optimize rescue vehicle allocation to minimize rescue time,taking into account travel time reliability under uncertain conditions.Because of the non-additive property of the objective function,this paper adopts a heuristic algorithm based on the K-shortest path algorithm,and inequality techniques to tackle the proposed modified integer programming model.Finally,the numerical experiments are presented to verify the accuracy and effectiveness of the proposed model and algorithm.The results show that ignoring travel time reliability may lead to an over-or under-estimation of the effective travel time of rescue vehicles on a particular path,and thereby an incorrect allocation scheme.

4-D Trajectory Prediction and Dynamic Planning of Aircraft Taxiing Considering Time and Fuel

Most of the traditional taxi path planning studies assume that the aircraft is in uniform speed,and the optimization goal is the shortest taxi time.Although it is easy to solve,it does not consider the changes in the speed profile of the aircraft when turning,and the shortest taxi time does not necessarily bring the best taxi fuel consumption.In this paper,the number of turns is considered,and the improved A*algorithm is used to obtain the P static paths with the shortest sum of the straight-line distance and the turning distance of the aircraft as the feasible taxi paths.By balancing taxi time and fuel consumption,a set of Pareto optimal speed profiles are generated for each preselected path to predict the 4-D trajectory of the aircraft.Based on the 4-D trajectory prediction results,the conflict by the occupied time window in the taxiing area is detected.For the conflict aircraft,based on the priority comparison,the waiting or changing path is selected to solve the taxiing conflict.Finally,the conflict free aircraft taxiing path is generated and the area occupation time window on the path is updated.The experimental results show that the total taxi distance and turn time of the aircraft are reduced,and the fuel consumption is reduced.The proposed method has high practical application value and is expected to be applied in real-time air traffic control decision-making in the future.

Energy-constrained ferry route design for sparse wireless sensor networks

In recent years,using message ferries as mechanical carriers of data has been shown to be an effective way to collect information in sparse wireless sensor networks.As the sensors are far away from each other in such highly partitioned scenario,a message ferry needs to travel a long route to access all the sensors and carry the data collected from the sensors to the sink.Typically,practical constraints(e.g.,the energy)preclude a ferry from visiting all sensors in a single tour.In such case,the ferry can only access part of the sensors in each tour and move back to the sink to get the energy refilled.So,the energy-constrained ferry route design(ECFRD)problem is discussed,which leads to the optimization problem of minimizing the total route length of the ferry,while keeping the route length of each tour below a given constraint.The ECFRD problem is proved to be NP-hard problem,and the integer linear programming(ILP)formulation is given.After that,efficient heuristic algorithms are proposed to solve this problem.The experimental results show that the performances of the proposed algorithms are effective in practice compared to the optimal solution.

Traffic assignment problem under tradable credit scheme in a bi-modal stochastic transportation network: A cumulative prospect theory approach

The traffic equilibrium assignment problem under tradable credit scheme(TCS) in a bi-modal stochastic transportation network is investigated in this paper. To describe traveler’s risk-taking behaviors under uncertainty, the cumulative prospect theory(CPT) is adopted. Travelers are assumed to choose the paths with the minimum perceived generalized path costs, consisting of time prospect value(PV) and monetary cost. At equilibrium with a given TCS, the endogenous reference points and credit price remain constant, and are consistent with the equilibrium flow pattern and the corresponding travel time distributions of road sub-network. To describe such an equilibrium state, the CPT-based stochastic user equilibrium(SUE) conditions can be formulated under TCS. An equivalent variational inequality(VI) model embedding a parameterized fixed point(FP) model is then established, with its properties analyzed theoretically. A heuristic solution algorithm is developed to solve the model, which contains two-layer iterations. The outer iteration is a bisection-based contraction method to find the equilibrium credit price, and the inner iteration is essentially the method of successive averages(MSA) to determine the corresponding CPT-based SUE network flow pattern. Numerical experiments are provided to validate the model and algorithm.

Designing an optimal stope layout for underground mining based on a heuristic algorithm

An optimal layout or three-dimensional spatial distribution of stopes guarantees the maximum profitability over life span of an underground mining operation.Thus,stope optimization is one of the key areas in underground mine planning practice.However,the computational complexity in developing an optimal stope layout has been a reason for limited availability of the algorithms offering solution to this problem.This article shares a new and efficient heuristic algorithm that considers a three-dimensional ore body model as an input,maximizes the economic value,and satisfies the physical mining and geotechnical constraints for generating an optimal stope layout.An implementation at a copper deposit demonstrates the applicability and robustness of the algorithm.A parallel processing based modification improving the performance of the original algorithm in terms of enormous computational time saving is also presented.

Scheduling algorithm of dual-armed cluster tools with residency time and reentrant constraints

To solve the scheduling problem of dual-armed cluster tools for wafer fabrications with residency time and reentrant constraints,a heuristic scheduling algorithm was developed.Firstly,on the basis of formulating scheduling problems domain of dual-armed cluster tools,a non-integer programming model was set up with a minimizing objective function of the makespan.Combining characteristics of residency time and reentrant constraints,a scheduling algorithm of searching the optimal operation path of dual-armed transport module was presented under many kinds of robotic scheduling paths for dual-armed cluster tools.Finally,the experiments were designed to evaluate the proposed algorithm.The results show that the proposed algorithm is feasible and efficient for obtaining an optimal scheduling solution of dual-armed cluster tools with residency time and reentrant constraints.

Energy-Efficient Resource Allocation for Small-Cell Networks：A Stable Queue Perspective

The small-cell technology is promising for spectral-efficiency enhancement. However, it usually requires a huge amount of energy consumption. In this paper, queue state information and channel state information are jointly utilized to minimize the time average of overall energy consumption for a multi-carrier small-cell network, where the inter-cell interference is an intractable problem. Based on the Lyapunov optimization theory, the problem could be solved by dynamically optimizing the problem of user assignment, carrier allocation and power allocation in each time slot. As the optimization problem is NP-hard, we propose a heuristic iteration algorithm to solve it. Numerical results verify that the heuristic algorithm offers an approximate performance as the brute-force algorithm. Moreover, it could bring down the overall energy consumption to different degrees according to the variation of traffic load. Meanwhile, it could achieve the same sum rate as the algorithm which focuses on maximizing system sum rate.

Heuristic Genetic Algorithm for Discretization of Continuous Attributes in Rough Set Theory

Discretization based on rough set theory aims to seek the possible minimum number of the cut set without weakening the indiscemibility of the original decision system. Optimization of discretization is an NP-complete problem and the genetic algorithm is an appropriate method to solve it. In order to achieve optimal discretization, first the choice of the initial set of cut set is discussed, because a good initial cut set can enhance the efficiency and quality of the follow-up algorithm. Second, an effective heuristic genetic algorithm for discretization of continuous attributes of the decision table is proposed, which takes the significance of cut dots as heuristic information and introduces a novel operator to maintain the indiscernibility of the original decision system and enhance the local research ability of the algorithm. So the algorithm converges quickly and has global optimizing ability. Finally, the effectiveness of the algorithm is validated through experiment.

Cumulative prospect theory-based user equilibrium model with stochastic perception errors

The cumulative prospect theory(CPT) is applied to study travelers' route choice behavior in a degradable transport network. A cumulative prospect theory-based user equilibrium(CPT-UE) model considering stochastic perception error(SPE) within travelers' route choice decision process is developed. The SPE is conditionally dependent on the actual travel time distribution, which is different from the deterministic perception error used in the traditional logit-based stochastic user equilibrium. The CPT-UE model is formulated as a variational inequality problem and solved by a heuristic solution algorithm. Numerical examples are provided to illustrate the application of the proposed model and efficiency of the solution algorithm. The effects of SPE on the reference point determination, cumulative prospect value estimation, route choice decision and network performance evaluation are investigated.

Site selection of emergency material warehouse under fuzzy environment

The objective of this work was to determine the location of emergency material warehouses. For the site selection problem of emergency material warehouses, the triangular fuzzy numbers are respectively demand of the demand node, the distance between the warehouse and demand node and the cost of the warehouse, a bi-objective programming model was established with minimum total cost of the system and minimum distance between the selected emergency material warehouses and the demand node. Using the theories of fuzzy numbers, the fuzzy programming model was transformed into a determinate bi-objective mixed integer programming model and a heuristic algorithm for this model was designed. Then, the algorithm was proven to be feasible and effective through a numerical example. Analysis results show that the location of emergency material warehouse depends heavily on the values of degree a and weight wl. Accurate information of a certain emergency activity should be collected before making the decision.

Robust Virtual Network Embedding Based on Component Connectivity in Large-Scale Network

Virtual network embedding problem which is NP-hard is a key issue for implementing software-defined network which is brought about by network virtualization. Compared with other studies which focus on designing heuristic algorithms to reduce the hardness of the NP-hard problem we propose a robust VNE algorithm based on component connectivity in large-scale network. We distinguish the different components and embed VN requests onto them respectively. And k-core is applied to identify different VN topologies so that the VN request can be embedded onto its corresponding component. On the other hand, load balancing is also considered in this paper. It could avoid blocked or bottlenecked area of substrate network. Simulation experiments show that compared with other algorithms in large-scale network, acceptance ratio, average revenue and robustness can be obviously improved by our algorithm and average cost can be reduced. It also shows the relationship between the component connectivity including giant component and small components and the performance metrics.

Energy Efficient Switch Policy for Small Cells

Switch policy is essential for small cells to properly serve variable number of users in an energy efficient way.However,frequently switching small cell base stations(SBSs) may increase the network operating cost,especially when there is an nonnegligible start-up energy cost.To this end,by observing the variety of user number,we focus on the design of a switch policy which minimize the cumulative energy consumption.A given user transmission rate is guaranteed and the capability of SBSs are limited as well.According to the knowledge on user number variety,we classify the energy consumption problem into two cases.In complete information case,to minimize the cumulative energy consumption,an offline solution is proposed according to critical segments.A heuristic algorithm for incomplete information case(HAIIC) is proposed by tracking the difference of cumulative energy consumption.The upper bound of the Energy Consumption Ratio(ECR) for HAIIC is derived as well.In addition,a practical Q-learning based probabilistic policy is proposed.Simulation results show that the proposed HAIIC algorithm is able to save energy efficiently.

A new heuristic algorithm for general integer linear programming problems

A new heuristic algorithm is proposed for solving general integer linear programming problems. In the algorithm, the objective function hyperplane is used as a cutting plane, and then by introducing a special set of assistant sets, an efficient heuristic search for the solution to the integer linear program is carried out in the sets on the objective function hyperplane. A simple numerical example shows that the algorithm is efficient for some problems, and therefore, of practical interest.