Near-optimal design of Global Positioning System (GPS) networks using the Tabu Search technique

This paper describes an optimization technique based on an heuristic procedure which is applied to analyse and improve the efficiency of the design of Global Positioning System (GPS) surveying networks. GPS is a valuable survey tool because of its ability to increase the accuracy, speed and flexibility of a survey. A GPS network can be defined as a number of stations, which are co-ordinated by a series of sessions, formed by placing receivers on stations. The goal is to select the best order in which these sessions can be organised to give the best possible schedule. Generally, solving large networks to optimality requires impractical computational time. This paper proposes a Tabu Search technique which provides optimal or near-optimal solutions for large networks with an acceptable amount of computational effort. Computational results for several case studies with known and unknown optimal schedules have been presented to assess the performance of the proposed technique.     

Optimal Network Design for Wireless Local Area Network

Network design for wireless local area networks is an important issue in the deployment of these networks. Research activities are presently being undertaken in two major areas: determining the location of base stations (BSs) and assigning the frequency channels for these stations. Our BS location problem selects a set of BSs to provide the best demand area coverage and maximize the signal level and physical area attendance priority. Adequate channel assignment reduces signal interference and improves network throughput. This paper reports a real world experiment where we applied the concepts of two classical outdoor problems namely the optimal BS location problem and the fixed channel assignment problem to build a WLAN into an indoor environment. We propose a mathematical model that we solve by a commercial software and report the computational results.     

Global Solution Approach for a Nonconvex MINLP Problem in Product Portfolio Optimization

The rigorous and efficient determination of the global solution of a nonconvex MINLP problem arising from product portfolio optimization introduced by Kallrath (2003) is addressed. The objective of the optimization problem is to determine the optimal number and capacity of reactors satisfying the demand and leading to a minimal total cost. Based on the model developed by Kallrath (2003), an improved formulation is proposed, which consists of a concave objective function and linear constraints with binary and continuous variables. A variety of techniques are developed to tighten the model and accelerate the convergence to the optimal solution. A customized branch and bound approach that exploits the special mathematical structure is proposed to solve the model to global optimality. Computational results for two case studies are presented. In both case studies, the global solutions are obtained and proved optimal very efficiently in contrast to available commercial MINLP solvers.     

多层防御模式下武器目标分配决策的群体智能优化算法

武器目标分配(WTA)是军事运筹学中经典的NP完全问题,迄今为止未找到求精确解的多项式时间算法.针对武器数量、布防空间、运行维护成本以及人力资源等多约束下的多层防御WTA问题,采用粒子群优化(PSO)和蚁群优化(ACO)两种群体智能算法求解.给出了PSO和ACO算法实现方案,通过一个算例评估两个算法的性能.结果表明,两种算法都能给出高质量的近似最优解,对求解WTA问题是有效的.PSO在解的质量、算法鲁棒性和计算效率方面均优于ACO.     

A Combinatorial user optimal dynamic traffic assignment algorithm

This paper introduces a polynomial combinatorial optimization algorithm for the dynamic user optimal problem. The approach can efficiently solve single destination networks and can be potentially extended to heuristically solve multidestinational networks. In the model, traffic is propagated according to sound traffic flow theoretical models rather than link exit functions; thereby allowing link queue evolution to be modeled more precisely. The algorithm is designed, proven, implemented and computationally tested.     

Heuristic algorithms for siting alternative-fuel stations using the Flow-Refueling Location Model

This paper presents three heuristic algorithms that solve for the optimal locations for refueling stations for alternative-fuels, such as hydrogen, ethanol, biodiesel, natural gas, or electricity. The Flow-Refueling Location Model (FRLM) locates refueling stations to maximize the flow that can be refueled with a given number of facilities. The FRLM uses path-based demands, and because of the limitations imposed by the driving range of vehicles, longer paths require combinations of more than one station to refuel round-trip travel. A mixed-integer linear programming (MILP) version of the model has been formulated and published and could be used to obtain an optimal solution. However, because of the need for combinations of stations to satisfy demands, a realistic problem with a moderate size network and a reasonable number of candidate sites would be impractical to generate and solve with MILP methods. In this research, heuristic algorithms—specifically the greedy-adding, greedy-adding with substitution and genetic algorithm—are developed and applied to solve the FRLM problem. These algorithms are shown to be effective and efficient in solving complex FRLM problems. For case study purposes, the heuristic algorithms are applied to locate hydrogen-refueling stations in the state of Florida.     

Exact algorithms for multi-criteria multi-modal shortest path with transfer delaying and arriving time-window in urban transit network

This paper investigates the solution algorithms for the multi-criteria multi-modal shortest path problem (M-SPP), which belongs to the set of problems known as NP-hard, in urban transit network (UTN). The related M-SPP is one of the important and practical problems in several fields such as urban transportation system and freight transportation. The UTN is composed of multiple modes (e.g., automobile, bus, subway, light rail, pedestrian and so on). To get their destination, the passengers can alternate between different modes. As a special demand, the time-window is usually associated with the M-SPP. Because of the service time-limit of modes, the available modes at a stop are varied with the time. So the optimal M-SPP with arriving time-window cannot be simply obtained by finding the optimal M-SPP firstly and then reversely deducing the leaving time-window of the origin according to the arriving time-window of destination. In this paper, the M-SPP with arriving time-window is firstly proposed. To solve the multi-criteria M-SPPs (MM-SPP) with transfer delaying, an improved exact label correcting algorithm (LCA) is designed and, to solve the proposed MM-SPPs with both of transfer delaying and arriving time-window, an exact reverse LCA is designed. Finally, some computing examples are given to test the effectiveness of the designed algorithms.     

An analysis of a mixed finite element method for the Navier-Stokes equations

Summary A simple mixed finite element method is developed to solve the steady state, incompressible Navier-Stokes equations in a neighborhood of an isolated—but not necessarily unique—solution. Convergence is established under very mild restrictions on the triangulation, and, when the solution is sufficiently smooth, optimal error bounds are obtained.     

A travel demand management strategy: The downtown space reservation system

In this paper, a Travel Demand Management strategy known as the Downtown Space Reservation System (DSRS) is introduced. The purpose of this system is to facilitate the mitigation of traffic congestion in a cordon-based downtown area by requiring people who want to drive into this area to make reservations in advance. An integer programming formulation is provided to obtain the optimal mix of vehicles and trips that are characterized by a series of factors such as vehicle occupancy, departure time, and trip length with an objective of maximizing total system throughput and revenue. Based upon the optimal solution, an “intelligent” module is built using artificial neural networks that enables the transportation authority to make decisions in real time on whether to accept an incoming request. An example is provided that demonstrates that the solution of the “intelligent” module resembles the optimal solution with an acceptable error rate. Finally, implementation issues of the DSRS are addressed.     

A Reduced-Load Equivalence for Generalised Processor Sharing Networks with Long-Tailed Input Flows

We consider networks where traffic is served according to the Generalised Processor Sharing (GPS) principle. GPS-based scheduling algorithms are considered important for providing differentiated quality of service in integrated-services networks. We are interested in the workload of a particular flow i at the bottleneck node on its path. Flow i is assumed to have long-tailed traffic characteristics. We distinguish between two traffic scenarios, (i) flow i generates instantaneous traffic bursts and (ii) flow i generates traffic according to an on/off process. In addition, we consider two configurations of feed-forward networks. First we focus on the situation where other flows join the path of flow i. Then we extend the model by adding flows which can branch off at any node, with cross traffic as a special case. We prove that under certain conditions the tail behaviour of the workload distribution of flow i is equivalent to that in a two-node tandem network where flow i is served in isolation at constant rates. These rates only depend on the traffic characteristics of the other flows through their average rates. This means that the results do not rely on any specific assumptions regarding the traffic processes of the other flows. In particular, flow i is not affected by excessive activity of flows with heavier-tailed traffic characteristics. This confirms that GPS has the potential to protect individual flows against extreme behaviour of other flows, while obtaining substantial multiplexing gains.     

A mathematical programming-based scheduling framework for multitasking environments

A new paradigm along with a mixed (binary) integer-linear programming model is developed for scheduling tasks in multitasking environments, for which the number of completed tasks is not a good measure. One special case falls into the realm of deteriorating jobs. Polynomial time optimal solution algorithms are presented for this and one other special case. As the complexity of the original problem is believed to be strongly NP-hard, an efficient solution algorithm, based on tabu search, is developed to solve the problem. Small, medium, and large size problems are solved, and the solution obtained from the algorithm is compared with that of the optimal solution or the upper bound found from using the Lagrangian relaxation. Where it was measurable, the search algorithm gave quantifiably good quality solutions, and in all cases it had a much better time efficiency than the branch-and-bound enumeration method. A detailed statistical experiment, based on the split-plot design, is developed to identify the characteristics of the tabu search algorithm, thus guaranteeing a solution that is significantly better in quality. A conjecturing technique is introduced for problems with very large planning horizons. This technique had remarkable time efficiency with no apparent loss of quality.     

Fixed Rank Filtering for Spatio-Temporal Data

Datasets from remote-sensing platforms and sensor networks are often spatial, temporal, and very large. Processing massive amounts of data to provide current estimates of the (hidden) state from current and past data is challenging, even for the Kalman filter. A large number of spatial locations observed through time can quickly lead to an overwhelmingly high-dimensional statistical model. Dimension reduction without sacrificing complexity is our goal in this article. We demonstrate how a Spatio-Temporal Random Effects (STRE) component of a statistical model reduces the problem to one of fixed dimension with a very fast statistical solution, a methodology we call Fixed Rank Filtering (FRF). This is compared in a simulation experiment to successive, spatial-only predictions based on an analogous Spatial Random Effects (SRE) model, and the value of incorporating temporal dependence is quantified. A remote-sensing dataset of aerosol optical depth (AOD), from the Multi-angle Imaging SpectroRadiometer (MISR) instrument on the Terra satellite, is used to compare spatio-temporal FRF with spatial-only prediction. FRF achieves rapid production of optimally filtered AOD predictions, along with their prediction standard errors. In our case, over 100,000 spatio-temporal data were processed: Parameter estimation took 64.4 seconds and optimal predictions and their standard errors took 77.3 seconds to compute. Supplemental materials giving complete details on the design and analysis of a simulation experiment, the simulation code, and the MISR data used are available on-line.     

Genetic algorithms applied to the solution of hybrid optimal control problems in astrodynamics

Many space mission planning problems may be formulated as hybrid optimal control problems, i.e. problems that include both continuous-valued variables and categorical (binary) variables. There may be thousands to millions of possible solutions; a current practice is to pre-prune the categorical state space to limit the number of possible missions to a number that may be evaluated via total enumeration. Of course this risks pruning away the optimal solution. The method developed here avoids the need for pre-pruning by incorporating a new solution approach using nested genetic algorithms; an outer-loop genetic algorithm that optimizes the categorical variable sequence and an inner-loop genetic algorithm that can use either a shape-based approximation or a Lambert problem solver to quickly locate near-optimal solutions and return the cost to the outer-loop genetic algorithm. This solution technique is tested on three asteroid tour missions of increasing complexity and is shown to yield near-optimal, and possibly optimal, missions in many fewer evaluations than total enumeration would require.     

Optimal dynamic routing in Flexible Manufacturing Systems with limited buffers

An optimal routing policy is obtained for Flexible Manufacturing Systems (FMSs) with limited buffers at the work stations. This policy is used to effectively drive a robotic material handling system. The routing decisions are made by a supervising computer on a real-time basis in order to avoid any work station running out of inputs and to control the blocking of the material handling system. Using our model, general material handling times can be assumed. The optimal policy and several key performance measures are computed, following the problem formulation as a continuous-time, semi-Markovian decision process. Fast convergence and computational stability are ensured by the ergodic solution algorithm augmented to solve the functional equations of the renewal process. The solution algorithm was implemented, tested on an extensive range of problems regarding the structure and the performance of the optimal policy. Complex environments involving diverse processing times, as well as very limited buffer storage, were examined. The interaction between the allocation of buffer spaces to work stations, the structural properties of the optimal monotone (threshold-type) policy and the system performance are also investigated.     

A decomposition heuristics for the container ship stowage problem

In this paper we face the problem of stowing a containership, referred to as the Master Bay Plan Problem (MBPP); this problem is difficult to solve due to its combinatorial nature and the constraints related to both the ship and the containers. We present a decomposition approach that allows us to assign a priori the bays of a containership to the set of containers to be loaded according to their final destination, such that different portions of the ship are independently considered for the stowage. Then, we find the optimal solution of each subset of bays by using a 0/1 Linear Programming model. Finally, we check the global ship stability of the overall stowage plan and look for its feasibility by using an exchange algorithm which is based on local search techniques. The validation of the proposed approach is performed with some real life test cases. This work has been developed within the research area: “The harbour as a logistic node” of the Italian Centre of Excellence on Integrated Logistics (CIELI) of the University of Genoa, Italy     

A fuzzy clustering application to precise orbit determination

In recent years, fuzzy logic techniques have been successfully applied in geodesy problems, in particular to GPS. The aim of this work is to test a fuzzy-logic method with an enhanced probability function as a tool to provide a reliable criteria for weighting scheme for satellite-laser-ranging (SLR) station observations, seeking to optimize their contribution to the precise orbit determination (POD) problem. The data regarding the stations were provided by the International Laser Ranging Service (ILRS), NASA/Crustal Dynamics Data Information System (CDDIS) provided the satellite data for testing the method. The software for processing the data is GEODYN II provided by NASA/Goddard Space Flight Center (GSFC). Factors to be considered in the fuzzy-logic clustering are: the total number of LAGEOS passes during the past 12 months, the stability measure of short- and long-term biases, the percentage of LAGEOS normal points that were accepted in CSR weekly LAGEOS analysis, and the RMS uncertainty of the station coordinates. A fuzzy-logic statistical method allows classifying the stations through a clear ‘degree of belonging’ to each station group. This degree of belonging translates into a suitable weight to be assigned to each station in the global solution. The first tests carried out showed improvements in the RMS of the global POD solution as well as individual stations, to within a few millimeters. We expect further work would lead to further improvements.     

Solution approaches for the capacitated single allocation hub location problem using ant colony optimisation

Hub and spoke type networks are often designed to solve problems that require the transfer of large quantities of commodities. This can be an extremely difficult problem to solve for constructive approaches such as ant colony optimisation due to the multiple optimisation components and the fact that the quadratic nature of the objective function makes it difficult to determine the effect of adding a particular solution component. Additionally, the amount of traffic that can be routed through each hub is constrained and the number of hubs is not known a-priori. Four variations of the ant colony optimisation meta-heuristic that explore different construction modelling choices are developed. The effects of solution component assignment order and the form of local search heuristics are also investigated. The results reveal that each of the approaches can return optimal solution costs in a reasonable amount of computational time. This may be largely attributed to the combination of integer linear preprocessing, powerful multiple neighbourhood local search heuristic and the good starting solutions provided by the ant colonies.     

Optimal Sequencing of Servers in the Two-Station Series Queueing System

This paper deals with determining an optimal sequence of service stations in a series queueing system. Optimality is defined in terms of the total time spent waiting for service. Sequences are compared on the basis of the moments of their steady-state total waiting time. In addition, the rules of stochastic dominance are applied which allow comparison of sequences on the basis of their waiting time distributions. Analytical results in the sequencing of service stations in series queues have been limited to stations with constant or exponential service times. This study extends the investigation to service distributions with varying degrees of statistical regularity given by the family of Erlang distributions.Relationships are developed for predicting optimal sequences. Validation is accomplished by simulating a number of systems and comparing the waiting time distribution functions for each sequence. The relationships are shown to be good predictors and useful in the study and design of systems of servers in series.     

A probabilistic model applied to emergency service vehicle location

This paper is concerned with the formulation and the solution of a probabilistic model for determining the optimal location of facilities in congested emergency systems. The inherent uncertainty which characterizes the decision process is handled by a new stochastic programming paradigm which embeds the probabilistic constraints within the traditional two-stage framework. The resulting model drops simplifying assumptions on servers independence allowing at the same time to handle the spatial dependence of demand calls. An exact solution method and different tailored heuristics are presented to efficiently solve the problem. Computational experience is reported with application to various networks.     

Deriving solution value bounds from the ADMM

Optimization Letters - This short paper describes a simple subgradient-based techniques for deriving bounds on the optimal solution value when using the ADMM to solve convex optimization problems....