多模型估计方法

多模型方法是一种混合估计方法 ,相对于传统的估计方法而言 (例如 Kalman滤波 ) ,它特别适合于具有未知变参数或变结构系统的研究 ,因而在许多领域得到了成功应用。回顾了多模型方法的发展过程 ,对现有各种多模型估计方法进行了总结 ,并提出了研究方向     

Split delivery routing

This article examines a relaxed version of the generic vehicle routing problem. In this version, a delivery to a demand point can be split between any number of vehicles. In spite of this relaxation the problem remains computationally hard. Since only small instances of the vehicle routing problem are known to be solved using exact methods, the vehicle route construction for this problem version is approached using heuristic rules. The main contribution of this article to the existing body of literature on vehicle routing issues in (a) is presenting a new vehicle routing problem amenable to practical applications, and (b) demonstrating the potential for cost savings over similar “traditional” vehicle routing when implementing the model and solutions presented here. The solution scheme allowing for split deliveries is compared with a solution in which no split deliveries are allowed. The comparison is conducted on six sets of 30 problems each for problems of size 75, 115, and 150 demand points (all together 540 problems). For very small demands (up to 10% of vehicle's capacity) no significant difference in solutions is evident for both solution schemes. For the other five problem sets for which point demand exceeds 10% of vehicle's capacity, very significant cost savings are realized when allowing split deliveries. The savings are significant both in the total distance and the number of vehicles required. The vehicles' routes constructed by our procedure tend to cover cohesive geographical zones and retain some properties of optimal solutions.     

The fixed charge problem

The fixed charge problem is a nonlinear programming problem of practical interest in business and industry. Yet, until now no computationally feasible exact method of solution for large problems had been developed. In this paper an exact algorithm is presented which is computationally feasible for large problems. The algorithm is based upon a branch and bound approach, with the additional feature that the amount of computer storage required remains constant throughout (for a problem of any given size). Also presented are three suboptimal heuristic algorithms which are of interest because, although they do not guarantee that the true optimal solution will be found, they usually yield very good solutions and are extremely rapid techniques. Computational results are described for several of the heuristic methods and for the branch and bound algorithm.     

Solving a selected class of location problems by exploiting problem structure: A decomposition approach

For many combinatorial optimization problems that are NP-hard, a number of special cases exist that can be solved in polynomial time. This paper addresses the issue of solving one such problem, the well-known m-median problem with mutual communication (MMMC), by exploiting polynomially solvable special cases of the problem. For MMMC, a dependency graph is defined that characterizes the structure of the interactions between decision variables. A Lagrangian decomposition scheme is proposed that partitions the problem into two or more subproblems, each having the same structure as the original problem, but with simpler dependency graphs. The dual problems are solved using subgradient or multiplier adjustment methods. An efficient method of adjusting the multiplier values is given. Computational results are reported that show the method to be quite effective. In addition, applications of the approach to other difficult location problems is discussed. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 791–815, 1998     

Gabor二进制编码异源图像匹配方法

异源图像匹配是图像处理领域尚未解决的问题。其中,合成孔径雷达图像与光学图像差异较大,用现有方法匹配通常难以得到满意结果。针对这个问题,提出一种基于Gabor编码的异源图像匹配方法:选取一组Gabor滤波器,分别对大图和小图进行Gabor卷积;采用池化方法对卷积结果进行压缩表示;对池化结果二值化并转换为二进制表示得到Gabor二进制编码特征;采用二进制位操作计算实时图与基准图对应窗口特征的相似性,相似性最大值对应图像匹配结果。本方法采用二进制对图像进行描述,减少了计算量,同时也更好地描述了异源图像间的共性特征。实验结果表明,本方法具有较高的匹配概率,计算时间少于现有方法。     

An efficient algorithm for the location-allocation problem with rectangular regions

The location-allocation problem for existing facilities uniformly distributed over rectangular regions is treated for the case where the rectilinear norm is used. The new facilities are to be located such that the expected total weighted distance is minimized. Properties of the problem are discussed. A branch and bound algorithm is developed for the exact solution of the problem. Computational results are given for different sized problems.     

Diffusion approximation to the G/G/R machine repair problem with warm standby spares

The G/G/R machine repair problem with M operating machines, S warm standby spares, and R repairmen is studied as a diffusion process. The steady-state equations are formulated as diffusion equations subject to two reflecting barriers. The approximate diffusion parameters of the diffusion equations are obtained (1) under the assumption that the input characteristics of the problem are defined only by their first two moments rather than their probability distribution function, (2) under the assumption of heavy traffic approximation, that is, when queues of failed machines in the repair stage are almost always nonempty, and (3) using well-known asymptotic results from renewal theory. Expressions for the probability density functions of the number of failed machines in the system are obtained. A study of the derived approximate results, compared to some of the exact results, suggests that the diffusion approach provides a useful method for solving complex machine-repair problems.     

A nested benders decomposition approach for telecommunication network planning

Despite its ability to result in more effective network plans, the telecommunication network planning problem with signal‐to‐interference ratio constraints gained less attention than the power‐based one because of its complexity. In this article, we provide an exact solution method for this class of problems that combines combinatorial Benders decomposition, classical Benders decomposition, and valid cuts in a nested way. Combinatorial Benders decomposition is first applied, leading to a binary master problem and a mixed integer subproblem. The subproblem is then decomposed using classical Benders decomposition. The algorithm is enhanced using valid cuts that are generated at the classical Benders subproblem and are added to the combinatorial Benders master problem. The valid cuts proved efficient in reducing the number of times the combinatorial Benders master problem is solved and in reducing the overall computational time. More than 120 instances of the W‐CDMA network planning problem ranging from 20 demand points and 10 base stations to 140 demand points and 30 base stations are solved to optimality. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

导弹飞行试验破片速度测定方法及其误差修正模型研究

破片速度的测量是导弹实弹飞行试验中一项难度较高的课题,准确的测量结果对于科学评价武器毁伤效能等技术指标具有十分重要的意义.立足国内技术现状,综述了导弹破片速度测量评定的一般方法,分析了各方法的基本原理,针对每种方法探讨了测量评定破片速度所存在的误差源.结合导弹实弹飞行试验特点及靶场试验实际情况,重点对采用靶网法测量单枚破片速度的误差及误差源进行了分析,给出了误差修正模型及提高测速精度的技术措施,并指出了靶场现有破片测速方案的不足和改进方向.论文成果在靶场实践中得到了部分应用.     

An approximate solution method for the fixed charge problem

In the absence, to date, of an exact method for solving the linear programming problem with fixed charges, two heuristic methods have been proposed and extensively investigated, computationally, for moderate sized problems. The results indicate that the heuristic methods produce optimal solutions in well over 90 percent of the several hundred problems investigated and very close to optimal (a few percent) in the remaining cases. Hence it should be of practical significance to practitioners in the field.     

Branch‐and‐price‐and‐cut for the manpower routing problem with synchronization constraints

In this article, we propose a branch‐and‐price‐and‐cut (BPC) algorithm to exactly solve the manpower routing problem with synchronization constraints (MRPSC). Compared with the classical vehicle routing problems (VRPs), the defining characteristic of the MRPSC is that multiple workers are required to work together and start at the same time to carry out a job, that is, the routes of the scheduling subjects are dependent. The incorporation of the synchronization constraints increases the difficulty of the MRPSC significantly and makes the existing VRP exact algorithm inapplicable. Although there are many types of valid inequalities for the VRP or its variants, so far we can only adapt the infeasible path elimination inequality and the weak clique inequality to handle the synchronization constraints in our BPC algorithm. The experimental results at the root node of the branch‐and‐bound tree show that the employed inequalities can effectively improve the lower bound of the problem. Compared with ILOG CPLEX, our BPC algorithm managed to find optimal solutions for more test instances within 1 hour. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 138–171, 2016     

高超声速流动计算中LU-SGS隐式算法的应用研究

在高超声速条件下,对原始LU-SGS格式及其改进方法的收敛速度做了深入地比较分析,目的是进一步更好地将LU-SGS算法用于工程上复杂外形的计算模拟当中。二维圆柱,三维钝锥及空天飞机算例的结果表明：(i)对于高超声速粘性流动的计算,粘性项应进行隐式处理;(ii)BLU-SGS方法给出的内迭代方式的收敛性优于DP-LUR方法所给出的内迭代方式;(iii)LU-SGS算法中雅克比系数矩阵的计算方式对计算量及收敛性影响较大,若采用精确的矩阵形式则在流动无分离情况下能取得快速收敛的效果,而在含有流动分离的情况因受稳定性的影响精确的矩阵形式的收敛表现不及对角近似形式。     

网络系统可靠性近似估算方法的对比研究

在讨论了网络系统可靠性计算难题的基础上,以满足工程实际的精度需要并减少分析计算工作量为目标,对现有的4种近似估算网络系统可靠性的方法进行了分析,指出了各种方法产生误差的原因,定性分析了有关方法为减少误差所采取措施的合理性。针对2种不同复杂程度的典型网络系统,通过数值算例,给出了单元可靠度不同情形下的系统可靠度计算值;与精确算法对比之后,得到了量化的误差.基于对各方法的工作量和误差的综合分析,给出了具有工程指导意义的建议.     

基于改进OMP算法的跳频信号跳变时刻精确估计

跳变时刻是跳频信号最重要的参数之一,精确估计跳变时刻有助于正确接收跳频信号,准确获取跳周期、跳频频率等参数。但是现有方法得到的跳变时刻精度不高,抗干扰能力较弱,为此提出了一种基于改进OMP算法的跳变时刻精确估计新方法。首先根据跳频信号原理建立了跳变时刻估计的稀疏表示模型;然后用改进OMP算法求解该模型提取跳变时刻。理论分析和仿真结果证明了该方法能够获取高精度的跳变时刻,估计性能优于现有算法。     

Computing the discounted return in markov and semi-markov chains

This paper addresses the problem of computing the expected discounted return in finite Markov and semi-Markov chains. The objective is to reveal insights into two questions. First, which iterative methods hold the most promise? Second, when are interative methods preferred to Gaussian elimination? A set of twenty-seven randomly generated problems is used to compare the performance of the methods considered. The observations that apply to the problems generated here are as follows: Gauss-Seidel is not preferred to Pre-Jacobi in general. However, if the matrix is reordered in a certain way and the author's row sum extrapolation is used, then Gauss-Seidel is preferred. Transforming a semi-Markov problem into a Markov one using a transformation that comes from Schweitzer does not yield improved performance. A method analogous to symmetric successive overrelaxation (SSOR) in numerical analysis yields improved performance, especially when the row-sum extrapolation is used only sparingly. This method is then compared to Gaussian elimination and is found to be superior for most of the problems generated.     

Comparative evaluation of prior versus progressive articulation of preference in bicriterion optimization

Procedures for solving multiple criteria problems are receiving increasing attention. Two major solution approaches are those involving prior articulation and progressive articulation of preference information. A progressive articulation (interactive) optimization approach, called the Paired Comparison Method (PCM) is compared to the prior articulation approach of a priori utility function measurement in a quality control decision environment from the perspective of the decision maker. The three major issues investigated included: (1) the ease of use of each method, (2) the preferences of solutions obtained, and (3) the insight provided by the methodology into the nature and structure of the problem. The problem setting involved management students who were rquired to determine an acceptance sampling plan using both methods. The PCM provided the most preferred solutions and was considered easier to use and understand. The prior articulation of preference method was found to give more insight into the problem structure. The results suggest that a hybrid approach, combining both prior preference assessment and an interactive procedure exploiting the advantages of each, should be employed to solve multiple criteria problems.     

A selective newsvendor approach to order management

Consider a supplier offering a product to several potential demand sources, each with a unique revenue, size, and probability that it will materialize. Given a long procurement lead time, the supplier must choose the orders to pursue and the total quantity to procure prior to the selling season. We model this as a selective newsvendor problem of maximizing profits where the total (random) demand is given by the set of pursued orders. Given that the dimensionality of a mixed‐integer linear programming formulation of the problem increases exponentially with the number of potential orders, we develop both a tailored exact algorithm based on the L‐shaped method for two‐stage stochastic programming as well as a heuristic method. We also extend our solution approach to account for piecewise‐linear cost and revenue functions as well as a multiperiod setting. Extensive experimentation indicates that our exact approach rapidly finds optimal solutions with three times as many orders as a state‐of‐the‐art commercial solver. In addition, our heuristic approach provides average gaps of less than 1% for the largest problems that can be solved exactly. Observing that the gaps decrease as problem size grows, we expect the heuristic approach to work well for large problem instances. © 2008 Wiley Periodicals, Inc. Naval Research Logistics 2008     

Optimizing the allocation of components to kits in small-lot,multiechelon assembly systems

The kitting problem in multiechelon assembly systems is to allocate on-hand stock and anticipated future deliveries to kits so that cost is minimized. This article structures the kitting problem and describes several preprocessing methods that are effective in refining the formulation. The model is resolved using an optimizing approach based on Lagrangian relaxation, which yields a separable problem that decomposes into a subproblem for each job. The resulting subproblems are resolved using a specialized dynamic programming algorithm, and computational efficiency is enhanced by dominance properties devised for that purpose. The Lagrangian problem is resolved effectively using subgradient optimization and a specialized branching method incorporated in the branch-and-bound procedure. Computational experience demonstrates that the specialized approach outperforms the general-purpose optimizer OSL. The new solution approach facilitates time-managed flow control, prescribing kitting decisions that promote cost-effective performance to schedule. © 1994 John Wiley & Sons. Inc.     

Use of completely reduced matrices in solving transportation problems with fixed charges

This paper shows how completely reduced matrices can be used in obtaining exact or approximate solutions to transportation problems with fixed charges. It does not treat methods for obtaining reduced matrices, which are available elsewhere, but it does discuss the problem of obtaining a completely reduced matrix, and then a general parametric solution to the primal problem, from any particular solution. Methods for obtaining particular solutions with determinacies of maximum order (solutions for the constant fixed charges problem) are then presented. The paper terminates with a discussion of methods which are useful in obtaining approximations to solutions of fixed charges problems with charges not constant.