Branch and bound algorithms for the bus evacuation problem

The bus evacuation problem (BEP) is a vehicle routing problem that arises in emergency planning. It models the evacuation of a region from a set of collection points to a set of capacitated shelters with the help of buses, minimizing the time needed to bring the last person out of the endangered region.     

An algorithm for the optimization of nonbifurcated flows in computer communication networks

For practical reasons, many computer communications networks currently in operation use single path routing, also called nonbifurcated routing: the traffic of every end to end communication is constrained to follow at most one single path at a time. The determination of optimal nonbifurcated flows is therefore a problem which confronts many network designers. In this paper, two important features of the classical nonbifurcated flow deviation algorithm, originally proposed by Fratta et al. are improved: the path length metric and the starting flow calculation. Tested on different examples, the essential gain is brought by a heuristic which provides a starting flow which is already a reasonable approximation of the global nonbifurcated optimum. Compared with the initial algorithm, this starting flow leads, with less computing time, to solutions which are closer to the optimum.     

Routing and scheduling on evacuation path networks using centralized hybrid approach

We examine the problem of finding evacuation routes from an urban building and out of its predetermined neighborhood. We propose a centralized hybrid approach for time-dependent point-to-point evacuation routing and scheduling, which is a novel spatio-temporal algorithm with discrete optimization models as sub problems. This algorithm does account for node and arc capacities and objects in transit over dynamic networks for routing and scheduling in a deterministic setting. A recent efficient method is selected for comparative analysis. For conducting this analysis, we used real case problems for finding evacuation paths from a building and out of a predetermined neighborhood of the building. The key results reveal the effectiveness of the proposed centralized hybrid approach for solving evacuation routing and scheduling problems.     

An optimization model for the container pre-marshalling problem

In most container yards around the world, containers are stacked high to utilize yard space more efficiently. In these yards, one major factor that affects their operational efficiency is the need to re-shuffle containers when accessing a container that is buried beneath other containers. One way to achieve higher loading efficiency is to pre-marshal the containers in such a way that it fits the loading sequence. In this research, we present a mathematical model for the container pre-marshalling problem. With respect to a given yard layout and a given sequence that containers are loaded onto a ship, the model yields a plan to re-position the export containers within the yard, so that no extra re-handles will be needed during the loading operation. The optimization goal is to minimize the number of container movements during pre-marshalling. The resulting model is an integer programming model composed of a multi-commodity flow problem and a set of side constraints. Several possible variations of the model as well as a solution heuristic are also discussed. Computation results are provided.     

A constrained binary knapsack approximation for shortest path network interdiction

A modified shortest path network interdiction model is approximated in this work by a constrained binary knapsack which uses aggregated arc maximum flow as the objective function coefficient. In the modified shortest path network interdiction problem, an attacker selects a path of highest non-detection probability on a network with multiple origins and multiple available targets. A defender allocates a limited number of resources within the geographic region of the network to reduce the maximum network non-detection probability between all origin-target pairs by reducing arc non-detection probabilities and where path non-detection probability is modeled as a product of all arc non-detection probabilities on that path. Traditional decomposition methods to solve the shortest path network interdiction problem are sensitive to problem size and network/regional complexity. The goal of this paper is to develop a method for approximating the regional allocation of defense resources that maintains accuracy while reducing both computational effort and the sensitivity of computation time to network/regional properties. Statistical and spatial analysis methods are utilized to verify approximation performance of the knapsack method in two real-world networks.     

Exploratory research on reading cognition and escape-route planning using building evacuation plan diagrams

The purpose of evacuation plan diagrams is for readers to comprehend and then plan an evacuation route. However, comprehending such diagrams involves complex issues that have yet to be addressed by research. This study aims to investigate how Taiwanese people interpret evacuation plan diagrams in their buildings. Issues of interest include the amount of time that it takes for a member of the general public to read a diagram and the time that they spend planning their escape route. Correlated and influencing factors are analyzed. The floor plan of an actual department store was used as the diagram for cognitive testing. A method of stimulated measurement was conducted over the Internet. The results of the experiment showed that the time it takes to plan an escape route is about 1.1 to 2 times longer than its reading time. This indicates that there is a significant time difference between diagram interpretation and stimulated planning. It was found that the longer it takes to read a diagram, the longer it takes to plan an escape route. In addition, to understand the difference between interpretations by the general public versus those with an architectural background, an analysis showed that the general public takes two to three times longer than architectural professionals to read a diagram and plan an escape route. Consequently, improvements in reading diagrams could help in the planning of a more efficient escape route. Furthermore, through our analysis, we found that the design of diagram symbols must satisfy conventional use and also that diagrams must avoid the use of metaphorical and abstract symbols. Diagrams that follow our guidelines will generally result in more effective and efficient conveyance of the intended message, thereby assisting in an emergency.     

A hybrid hierarchical agent-based simulation approach for buildings indoor layout evaluation based on the post-earthquake evacuation

In the aftermath of severe earthquakes, building occupants evacuation behaviour is a vital indicator of the performance of an indoor building design. However, earthquake evacuation has been systematically neglected in the current building design practice. Arguably, one of the primary reasons for this is that post-earthquake evacuation behaviour is complex and distinct from all other types of evacuation behaviours such as fire. Thus, a comprehensive approach to considering the integration of human evacuation behaviour and a building's indoor layout design, mainly focused on non-structural damage, has been consistently neglected in the literature. In this paper, a hierarchical hybrid Agent-Based Model (ABM) framework integrated with a Cellular Automata (CA) and a 2D Building Information Model (BIM) damage visualisation to consider an approximation of non-structural damage has been developed. The proposed ABM incorporates learning mechanisms and human psychological aspects influencing evacuees' utility during the navigation process. The proposed approach was verified by comparing the results to previous real-life post-earthquake evacuation data and a “model to model” comparison of results from the existing relevant studies. The model prototype was successfully tested to simulate the pedestrian evacuation process from one floor of the new engineering building at The University of Auckland, New Zealand. The proposed simulation approach has been carried out for two different internal layout design alternatives where five population sizes are evacuated through different scenarios. The outputs from this study can be used to improve the design's compatibility of the building's indoor layout with the occupants' post-earthquake evacuation behaviour.     

Complexity and design of QoS routing algorithms in wireless mesh networks

Quality of service (QoS) provisioning in wireless mesh networks (WMNs) is an open issue to support emerging multimedia services. In this paper, we study the problem of QoS provisioning in terms of end-to-end bandwidth allocation in WMNs. It is challenging due to interferences in the networks. We consider widely used interference models and show that except a few special cases, the problem of finding a feasible path is NP-complete under the models. We propose a k-shortest path based algorithmic framework to solve this problem. We also consider the problem of optimizing network performance by on-line dynamic routing, and adapt commonly used conventional QoS routing metrics to be used in WMNs. We find the optimal solutions for these problems through formulating them as optimization models. A model is developed to check the existence of a feasible path and another to find the optimal path for a demand; moreover, an on-line optimal QoS routing algorithm is developed. Comparing the algorithms implemented by the proposed framework with the optimization models shows that our solution can find existing feasible paths with high probability, efficiently optimizes path lengths, and has a comparable performance to the optimal QoS routing algorithm. Furthermore, our results show that contrary to wireline networks, minimizing resource consumption should be preferred over load distribution even in lightly loaded WMNs.     

A model for evacuation risk assessment with consideration of pre- and post-disaster factors

In urban areas, the occurrence of disasters can cause extensive damage to human society. For this reason, evacuation, regarded as a critical course of action to relocate people and property, helps to alleviate loss of life and property to a great extent. Risk associated with evacuation is an abstract concept that cannot be easily conceptualized. This paper develops a model for assessing and visualizing the risks associated with the evacuation process in response to potential catastrophes. Understanding of evacuation risk, the potential for losing transport connections and the difficulty of transferring rescue resources, was previously limited by considering pre-disaster factors only. This study mitigates such limitation by extending previous research to include the contingent post-disaster factors that have received scant attention to date. Two contingent post-disaster factors: the spatial impact of the disaster and the potential for traffic congestion caused by the evacuee routing behaviors, are discussed in detail and integrated into the model along with other pre-disaster factors. A case study on the transportation network of Beijing, China is used to demonstrate the value of the model. This paper asserts that the notion of evacuation risk is not a static evaluation of such factors as road vulnerability; rather it involves a dynamic process where contingent factors associated with disastrous events play a role. This model can help city emergency planners to identify urban infrastructures that may hinder an efficient evacuation process because of their deficient configuration.     

A three-stage approach for the resource-constrained shortest path as a sub-problem in column generation

This paper focuses on the common scenario in which the resource-constrained shortest path problem (RCSP) on an acyclic graph is a sub-problem in the context of column generation. It proposes a pseudo-polynomial time, three-stage solution approach. Stages 1 (preprocessing) and 2 (setup) are implemented one time to transform RCSP into a shortest path problem, which is solved by stage 3 (iterative solution) at each column generation iteration, each time with different arc costs. This paper analyzes certain properties related to each stage as well as algorithm complexity. Computational tests compare the performances of this method, a state-of-the-art label-setting algorithm, and CPLEX optimization software on four classes of instances, each of which involves either one or multiple resources, and show that the new method is effective. The new method outperforms the label-setting algorithm when resource limitations are tight—as can be expected in practice, and outperforms CPLEX for all tested instances. The label-setting algorithm outperforms CPLEX for all single-resource RCSP instances and almost all multiple-resource RCSP instances.     

Energy efficient routing algorithm for fiber-wireless access networks: A network formation game approach

New multimedia services and ubiquitous networking pose great challenges on existing access network infrastructures. To cope with such requirements new access technologies, such as the fiber-wireless (FiWi), are being developed. Together with the emergence of new access networks, efforts are being made to reduce the amount of energy required to provide services. Indeed, this issue plays an increasingly important role. Here we propose an energy efficient routing algorithm for FiWi access networks. The main idea is to exploit the multipath capabilities of the wireless mesh front end of FiWi access networks to create energy efficient routes that optimize the sleeping and active periods of all ONUs and wireless nodes. To achieve this goal, an energy efficient network model based on network formation game theory is used. This model allows several network formation processes to be compared in regard to the energy efficiency of the routes they generate. Our results reveal that the farsighted network formation process establishes the most energy efficient routes, meaning that the choices done by this formation process were the best ones. However, this farsighted process is computationally expensive. For this reason a heuristic algorithm is developed, which explores the most energy efficient choices taken by the network formation processes, and farsighted process in particular. Results show that the proposed heuristic is able to obtain results close to the farsighted process.     

软件定义网络中基于网络切片和ILP模型的路由方案

针对软件定义网络(SDN)中数据层的路由优化问题,提出一种基于网络切片和 整数线性规划(ILP) 多约束优化的路由方案。首先,根据多租户业务的链路需求,基于Kruskal算法对数据层中的链路资源进行网络切片,尽可能形成相互隔离的租户子网络。然后,在考虑链路约束和租户业务的服务质量(QoS)约束下, 以最小化传输延迟为目标, 构建一个ILP整数线性规划(ILP)路由优化模型,并获得最佳的路由方案。仿真结果表明,所获得的路由方案具有较少的共享链路,有效降低了链路拥塞和传输延迟。     

An efficient integer programming formulation for the assignment of base stations to controllers in cellular networks

In mobile networks, the assignment of base stations to controllers when planning the network has a strong impact on network performance. In a previous paper, the authors formulated the assignment of base stations to packet controllers in GSM-EDGE Radio Access Network (GERAN) as a graph partitioning problem, which was solved by a heuristic method. In this paper, an exact method is presented to find optimal solutions that can be used as a benchmark. The proposed method is based on an effective re-formulation of the classical integer linear programming model of the graph partitioning problem, which is solved by the branch-and-cut algorithm in a commercial optimization package. Performance assessment is based on an extensive set of problem instances built from data of a live network. Preliminary analysis shows some properties of the graphs in this problem justifying the limitations of heuristic approaches and the need for more sophisticated methods. Results show that the proposed method outperforms classical heuristic algorithms used for benchmarking, even under runtime constraints. Likewise, it improves the efficiency of exact methods previously applied to similar problems in the cellular field.     

帆船比赛航行路径优化与仿真

针对帆船在海上行驶所具有的模糊性和不定性的复杂环境特点,提出基于分区段优化和进化规划的帆船航行路径优化方法。该方法在比赛区域建立二维平面坐标系,将整个航程划分为若干区段,每个区段以帆船无约束的航向决策综合评价函数为基础,利用进化规划全局优化搜索进行路径优化,综合得到全航程最优路径。在此理论基础上,进行优化路径的仿真。仿真结果表明,该路径优化方法能够取得较好的规划结果,对于帆船科学训练具有很好的指导作用。     

Detecting infeasibility and generating cuts for mixed integer programming using constraint programming

We study a hybrid MIP/CP solution approach in which CP is used for detecting infeasibilities and generating cuts within a branch-and-cut algorithm for MIP. Our framework applies to MIP problems augmented by monotone constraints that can be handled by CP. We illustrate our approach on a generic multiple machine scheduling problem, and present a number of computational experiments.     

Mobile robot path planning using artificial bee colony and evolutionary programming

In this paper, an evolutionary approach to solve the mobile robot path planning problem is proposed. The proposed approach combines the artificial bee colony algorithm as a local search procedure and the evolutionary programming algorithm to refine the feasible path found by a set of local procedures. The proposed method is compared to a classical probabilistic roadmap method (PRM) with respect to their planning performances on a set of benchmark problems and it exhibits a better performance. Criteria used to measure planning effectiveness include the path length, the smoothness of planned paths, the computation time and the success rate in planning. Experiments to demonstrate the statistical significance of the improvements achieved by the proposed method are also shown.     

Efficient solution techniques for the integrated coverage, sink location and routing problem in wireless sensor networks

Sensors are tiny electronic devices having limited battery energy and capability for sensing, data processing and communicating. They can collectively behave to provide an effective wireless network that monitors a region and transmits the collected information to gateway nodes called sinks. Most of the applications require the operation of the network for long periods of times, which makes the efficient management of the available energy resources an important concern. There are three major issues in the design of sensor networks: sensor deployment or the coverage of the sensing area, sink location, and data routing. In this work, we consider these three design problems within a unified framework and develop two mixed-integer linear programming formulations. They are difficult to solve exactly. However, it is possible to compute good feasible solutions of the sink location and routing problems easily, when the sensors are deployed and their locations in the sensor field become known. Therefore, we propose a tabu search heuristic that tries to identify the best sensor locations satisfying the coverage requirements. The objective value corresponding to each set of sensor locations is calculated by solving the sink location and routing problem. Computational tests carried out on randomly generated test instances indicate that the proposed hybrid approach is both accurate and efficient.     

A two-stage stochastic programming approach for project planning with uncertain activity durations

This paper investigates the problem of setting target finish times (due dates) for project activities with random durations. Using two-stage integer linear stochastic programming, target times are determined in the first stage followed by the development of a detailed project schedule in the second stage. The objective is to balance (1) the cost of project completion as a function of activity target times with (2) the expected penalty incurred by deviating from the specified values. It is shown that the results may be significantly different when deviations are considered, compared to when activities are scheduled as early as possible in the traditional way. For example, the optimal target completion time for a project may be greater than the makespan of the early-start schedules under any scenario. To find solutions, an exact algorithm is developed for the case without a budget constraint and is used as a part of a heuristic when crashing is permitted. All computational procedures are demonstrated on a set of 150 benchmark problems consisting of 90 activities each.     

动态未知环境下一种Hopfield神经网络路径规划方法

针对动态未知环境下移动机器人路径规划问题,采用一种有效的局部连接Hopfiled神经网络(Hopfield Neural Networks,HNN)来表示机器人的工作空间.机器人在HNN所形成的动态数值势场上进行爬山搜索法来形成避碰路径,并且不存在非期望的局部吸引点.HNN权值设计中考虑了路径安全性因素,通过在障碍物附件形成局部虚拟排斥力来形成安全路径.HNN的连接权是非对称的,并且考虑了信号传播时延.分析了HNN的稳定性,所给稳定性条件和时延无关.HNN模型中突出了最大传播激励,从而使得HNN具有更广的稳定性范围并能表示具有更多节点的机器人工作空间.为对该HNN有效仿真求解,结合约束距离变换和HNN的时延性,给出了单处理器上高效的串行模拟方案,规划路径的时间复杂度为O(N)(N是HNN中神经元的数目),使得路径重规划能快速在线进行.仿真和实验表明该方法的有效性.