智能搜救机器人在障碍地形的自主构型规划

为了解决带有辅助摆臂的智能搜救机器人自动规划构型以实现自主越障的难题,提出一种能够适应复杂地面形状的搜救机器人越障构型规划新方法,其核心是一种高适应性、高效率的机器人姿态预测算法。通过将地形表示为离散的点集,建立了搜救机器人的单侧姿态预测数学模型;进一步提出了快速求解该问题的算法,每秒可预测1 000～1 500个姿态。基于此,设计了机器人越障过程中状态、动作的评价指标,运用动态规划算法与滚动优化思想构建了具有优化能力的、能够实时运行的构型规划器。仿真与实物实验的结果表明,该方法能够使机器人自主调整构型穿越复杂地形,且相较强化学习算法和人工操作具有更平稳的越障效果。     

Discrete equal‐capacity p‐median problem

This paper examines the discrete equal‐capacity p‐median problem that seeks to locate p new facilities (medians) on a network, each having a given uniform capacity, in order to minimize the sum of distribution costs while satisfying the demand on the network. Such problems arise, for example, in local access and transport area telecommunication network design problems where any number of a set of p facility units can be constructed at the specified candidate sites (hence, the net capacity is an integer multiple of a given unit capacity). We develop various valid inequalities, a separation routine for generating cutting planes that are specific members of such inequalities, as well as an enhanced reformulation that constructs a partial convex hull representation that subsumes an entire class of valid inequalities via its linear programming relaxation. We also propose suitable heuristic schemes for this problem, based on sequentially rounding the continuous relaxation solutions obtained for the various equivalent formulations of the problem. Extensive computational results are provided to demonstrate the effectiveness of the proposed valid inequalities, enhanced formulations, and heuristic schemes. The results indicate that the proposed schemes for tightening the underlying relaxations play a significant role in enhancing the performance of both exact and heuristic solution methods for this class of problems. © 2000 John & Sons, Inc. Naval Research Logistics 47: 166–183, 2000.     

Selecting T for a periodic review inventory model with staggered deliveries

Consider a single‐item, periodic review, infinite‐horizon, undiscounted, inventory model with stochastic demands, proportional holding and shortage costs, and full backlogging. Orders can arrive in every period, and the cost of receiving them is negligible (as in a JIT setting). Every T periods, one audits the current stock level and decides on deliveries for the next T periods, thus incurring a fixed audit cost and—when one schedules deliveries—a fixed order cost. The problem is to find a review period T and an ordering policy that satisfy the average cost criterion. The current article extends an earlier treatment of this problem, which assumed that the fixed order cost is automatically incurred once every T periods. We characterize an optimal ordering policy when T is fixed, prove that an optimal review period T** exists, and develop a global search algorithm for its computation. We also study the behavior of four approximations to T** based on the assumption that the fixed order cost is incurred during every cycle. Analytic results from a companion article (where μ/σ is large) and extensive computational experiments with normal and gamma demand test problems suggest these approximations and associated heuristic policies perform well when μ/σ ≥ 2. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 329–352, 2000     

Models and algorithms for shuffling problems in steel plants

In this article, we study item shuffling (IS) problems arising in the logistics system of steel production. An IS problem here is to optimize shuffling operations needed in retrieving a sequence of steel items from a warehouse served by a crane. There are two types of such problems, plate shuffling problems (PSP) and coil shuffling problems (CSP), considering the item shapes. The PSP is modeled as a container storage location assignment problem. For CSP, a novel linear integer programming model is formulated considering the practical stacking and shuffling features. Several valid inequalities are constructed to accelerate the solving of the models. Some properties of optimal solutions of PSP and CSP are also derived. Because of the strong NP‐hardness of the problems, we consider some special cases of them and propose polynomial time algorithms to obtain optimal solutions for these cases. A greedy heuristic is proposed to solve the general problems and its worst‐case performances on both PSP and CSP are analyzed. A tabu search (TS) method with a tabu list of variable length is proposed to further improve the heuristic solutions. Without considering the crane traveling distance, we then construct a rolling variable horizon heuristic for the problems. Numerical experiments show that the proposed heuristic algorithms and the TS method are effective. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012     

Neighborhood search heuristics for selecting hierarchically well‐formulated subsets in polynomial regression

The importance of subset selection in multiple regression has been recognized for more than 40 years and, not surprisingly, a variety of exact and heuristic procedures have been proposed for choosing subsets of variables. In the case of polynomial regression, the subset selection problem is complicated by two issues: (1) the substantial growth in the number of candidate predictors, and (2) the desire to obtain hierarchically well‐formulated subsets that facilitate proper interpretation of the regression parameter estimates. The first of these issues creates the need for heuristic methods that can provide solutions in reasonable computation time; whereas the second requires innovative neighborhood search approaches that accommodate the hierarchical constraints. We developed tabu search and variable neighborhood search heuristics for subset selection in polynomial regression. These heuristics are applied to a classic data set from the literature and, subsequently, evaluated in a simulation study using synthetic data sets. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Newsvendor bounds and heuristics for serial supply chains with regular and expedited shipping

We study an infinite‐horizon, N‐stage, serial production/inventory system with two transportation modes between stages: regular shipping and expedited shipping. The optimal inventory policy for this system is a top–down echelon base‐stock policy, which can be computed through minimizing 2N nested convex functions recursively (Lawson and Porteus, Oper Res 48 (2000), 878–893). In this article, we first present some structural properties and comparative statics for the parameters of the optimal inventory policies, we then derive simple, newsvendor‐type lower and upper bounds for the optimal control parameters. These results are used to develop near optimal heuristic solutions for the echelon base‐stock policies. Numerical studies show that the heuristic performs well. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

A m‐parallel crane scheduling problem with a non‐crossing constraint

In this paper, we study a m‐parallel machine scheduling problem with a non‐crossing constraint motivated by crane scheduling in ports. We decompose the problem to allow time allocations to be determined once crane assignments are known and construct a backtracking search scheme that manipulates domain reduction and pruning strategies. Simple approximation heuristics are developed, one of which guarantees solutions to be at most two times the optimum. For large‐scale problems, a simulated annealing heuristic that uses random neighborhood generation is provided. Computational experiments are conducted to test the algorithms. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007.     

New results on rendezvous search on the interval

In a rendezvous search problem, two players are placed in a network and must try to meet each other in the least possible expected time. We look at rendezvous search on a discrete interval in which the players are initially placed using independent draws (usually assumed to be from the same distribution). Some optimal solutions are known if this distribution is uniform, and also for certain other special types of distribution. In this article, we present two new results. First, we characterize the complete set of solutions for the uniform case, showing that all optimal strategies must have two specific properties (namely, of being swept and strictly geodesic). Second, we relate search strategies on the interval to proper binary trees, and use this correspondence to derive a recurrence relation for solutions to the symmetric rendezvous problem for any initial distribution. This relation allows us to solve any such problem computationally by dynamic programming. Finally, some ideas for future research are discussed. © Wiley Periodicals, Inc. Naval Research Logistics 60: 454–467, 2013     

Search and the introduction of improved technologies

Modeling R&D as standard sequential search, we consider a monopolist who can implement a sequence of technological discoveries during the technology search process: he earns revenue on his installed technology while he engages in R&D to find improved technology. What is not standard is that he has a finite number of opportunities to introduce improved technology. We show that his optimal policy is characterized by thresholds ξ_i(x): introduce the newly found technology if and only if it exceeds ξ_i(x) when x is the state of the currently installed technology and i is the number of remaining introductions allowed. We also analyze a nonstationary learning‐by‐doing model in which the monopolist's experience in implementing new technologies imparts increased capability in generating new technologies. Because this nonstationary model is not in the class of monotone stopping problems, a number of surprising results hold and several seemingly obvious properties of the stationary model no longer hold. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Algorithms for the multi‐item multi‐vehicles dynamic lot sizing problem

We consider a two‐stage supply chain, in which multi‐items are shipped from a manufacturing facility or a central warehouse to a downstream retailer that faces deterministic external demand for each of the items over a finite planning horizon. The items are shipped through identical capacitated vehicles, each incurring a fixed cost per trip. In addition, there exist item‐dependent variable shipping costs and inventory holding costs at the retailer for items stored at the end of the period; these costs are constant over time. The sum of all costs must be minimized while satisfying the external demand without backlogging. In this paper we develop a search algorithm to solve the problem optimally. Our search algorithm, although exponential in the worst case, is very efficient empirically due to new properties of the optimal solution that we found, which allow us to restrict the number of solutions examined. Second, we perform a computational study that compares the empirical running time of our search methods to other available exact solution methods to the problem. Finally, we characterize the conditions under which each of the solution methods is likely to be faster than the others and suggest efficient heuristic solutions that we recommend using when the problem is large in all dimensions. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2006.     

A metaheuristic scheduling procedure for resource-constrained projects with cash flows

Resource-constrained project scheduling problems with cash flows (RCPSPCF) are complex, combinatorial optimization problems. Many heuristics have been reported in the literature that produce reasonable schedules in limited project environments. However, the lack of a heuristic that dominates under differing project conditions can lead to a suboptimal choice of an appropriate heuristic for scheduling any given project. This may result in poor schedules and monetary losses. This paper reports on the application of the tabu search metaheuristic procedure for the RCPSPCF. Strategies for neighborhood generation and candidate selection that exploit the special features of the problem are combined with a simple multiheuristic start procedure. Extensive experimentation, with multiple data sets and comparison with an upper bound, indicates a significant improvement, both in project Net Present Value (NPV) as well as the number of projects, where the metaheuristic outperforms the best known heuristics in the literature. More specifically, this procedure produces the best schedules in over 85% of the projects tested, in contrast to the best single-pass heuristics which have been shown to dominate in at most 20% of the same cases. This iterative, general purpose heuristic is able to adapt significantly better to the complex interactions of the many critical parameters of the RCPSPCF than single-pass heuristics that use more specific information about each project environment. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 912–927, 1999     

A search game taking account of attributes of searching resources

This article deals with a two‐person zero‐sum game called a search allocation game (SAG), in which a searcher and a target participate as players. The searcher distributes his searching resources in a search space to detect the target. The effect of resources lasts a certain period of time and extends to some areas at a distance from the resources' dropped points. On the other hand, the target moves around in the search space to evade the searcher. In the history of search games, there has been little research covering the durability and reachability of searching resources. This article proposes two linear programming formulations to solve the SAG with durable and reachable resources, and at the same time provide an optimal strategy of distributing searching resources for the searcher and an optimal moving strategy for the target. Using examples, we will analyze the influences of two attributes of resources on optimal strategies. © 2007 Wiley Periodicals, Inc. Naval Research Logistics 2008     

Using hybrid metaheuristics for the one‐way and two‐way network design problem

A network with traffic between nodes is known. The links of the network can be designed either as two‐way links or as one‐way links in either direction. The problem is to find the best configuration of the network which minimizes total travel time for all users. Branch and bound optimal algorithms are practical only for small networks (up to 15 nodes). Effective simulated annealing and genetic algorithms are proposed for the solution of larger problems. Both the simulated annealing and the genetic algorithms propose innovative approaches. These innovative ideas can be used in the implementation of these heuristic algorithms for other problems as well. Additional tabu search iterations are applied on the best results obtained by these two procedures. The special genetic algorithm was found to be the best for solving a set of test problems. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 449–463, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10026     

An algorithm for solving general fractional interval programming problems

A Linear Fractional Interval Programming problem (FIP) is the problem of extremizing a linear fractional function subject to two-sided linear inequality constraints. In this paper we develop an algorithm for solving (FIP) problems. We first apply the Charnes and Cooper transformation on (FIP) and then, by exploiting the special structure of the pair of (LP) problems derived, the algorithm produces an optimal solution to (FIP) in a finite number of iterations.     

A mathematical formulation and efficient heuristics for the dynamic container relocation problem

The container relocation problem (CRP) is concerned with emptying a single yard‐bay which contains J containers each following a given pickup order so as to minimize the total number of relocations made during their retrieval process. The CRP can be modeled as a binary integer programming (IP) problem and is known to be NP‐hard. In this work, we focus on an extension of the CRP to the case where containers are both received and retrieved from a single yard‐bay, and call it the dynamic container relocation problem. The arrival (departure) sequences of containers to (from) the yard‐bay is assumed to be known a priori. A binary IP formulation is presented for the problem. Then, we propose three types of heuristic methods: index based heuristics, heuristics using the binary IP formulation, and a beam search heuristic. Computational experiments are performed on an extensive set of randomly generated test instances. Our results show that beam search heuristic is very efficient and performs better than the other heuristic methods.Copyright © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 101–118, 2014     

Rendezvous of three agents on the line

This paper considers a three‐person rendezvous problem on the line which was introduced earlier by the authors. Three agents are placed at three consecutive integer value points on the real line, say 1, 2, and 3. Each agent is randomly faced towards the right or left. Agents are blind and have a maximum speed of 1. Their common aim is to gather at a common location as quickly as possible. The main result is the proof that a strategy given by V. Baston is the unique minimax strategy. Baston's strategy ensures a three way rendezvous in time at most 3.5 for any of the 3!2³ = 48 possible initial configurations corresponding to positions and directions of each agent. A connection is established between the above rendezvous problem and a search problem of L. Thomas in which two parents search separately to find their lost child and then meet again. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 244–255, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10005     

Modeling and solution for the ship stowage planning problem of coils in the steel industry

We consider a ship stowage planning problem where steel coils with known destination ports are to be loaded onto a ship. The coils are to be stowed on the ship in rows. Due to their heavy weight and cylindrical shape, coils can be stowed in at most two levels. Different from stowage problems in previous studies, in this problem there are no fixed positions on the ship for the coils due to their different sizes. At a destination port, if a coil to be unloaded is not at a top position, those blocking it need to be shuffled. In addition, the stability of ship has to be maintained after unloading at each destination port. The objective for the stowage planning problem is to minimize a combination of ship instability throughout the entire voyage, the shuffles needed for unloading at the destination ports, and the dispersion of coils to be unloaded at the same destination port. We formulate the problem as a novel mixed integer linear programming model. Several valid inequalities are derived to help reducing solution time. A tabu search (TS) algorithm is developed for the problem with the initial solution generated using a construction heuristic. To evaluate the proposed TS algorithm, numerical experiments are carried out on problem instances of three different scales by comparing it with a model‐based decomposition heuristic, the classic TS algorithm, the particle swarm optimization algorithm, and the manual method used in practice. The results show that for small problems, the proposed algorithm can generate optimal solutions. For medium and large practical problems, the proposed algorithm outperforms other methods. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 564–581, 2015     

任务分配问题的对称群方法

探讨了无人飞行器(UAV)编队的任务分配问题。任务分配是UAV协同控制的基础,其解是任务区域内各任务的一个排列。求解UAV任务分配问题的有效方法是能在合理的计算时间内找到近似最优解的启发式算法。用对称群描述UAV任务分配的搜索空间,基于右乘运算构造搜索邻域。仿真结果验证了群论禁忌搜索算法的有效性。     

基于禁忌搜索算法的指挥控制系统网络组织优化方法

基于复杂网络的拓扑结构优化理论与禁忌搜索算法,结合指挥控制系统的特点,建立了优化最优指挥与控制系统网络结构（Command and Control Architecture Network,C2AN）模型,并以复杂网络的网络效率和网络成本分别描述C2AN中的信息传播效率及构建C2AN的资源消耗,建立优化的目标函数,通过禁忌搜索算法获得了最优的C2AN。最后通过仿真实例,分析了最优C2AN生成过程及其基本统计特征。     

搜索路径给定时的搜索对策问题及其应用

搜索路径给定时的最优搜索方案问题,也可以理解为是关于搜索者和目标的二人对策问题,主要讨论了当搜索路径给定时的单个搜索者和单个目标的搜索对策问题。首先根据问题的特点,利用动态规划和迭代的方法,确定关于目标逃逸路径混合策略的最优分区,证明该分区是多面体凸集;针对目标不同逃逸路径的分区,求出搜索者的最大期望收益,再将问题转化为二人有限零和对策,计算出搜索者的支付矩阵,确定最优搜索策略。最后结合海军护航行动,对我舰载直升机搜索小型海盗船进行分析和计算,说明搜索路径给定时的最优搜索对策对于双方的资源分配和提高搜索效率具有一定的应用价值。