基于群体协同的驱护编队中近程防空的系统效能

针对中近程反导的具体要求,分析了典型的驱护编队反导模式下编群队形特点,研究了指挥舰与护卫舰的队形关联性,探讨了基于信息化作战模式的抗饱和攻击能力,建立了基于多目标优化的最保守与最乐观情况下的抗饱和攻击模型,得到舰艇编队协同防空的系统效能,对驱护编队防空反导指挥决策具有很强的参考价值。     

Capacity allocation to sales agents in a decentralized logistics network

Many logistics systems operate in a decentralized way, while most optimization models assume a centralized planner. One example of a decentralized system is in some sea cargo companies: sales agents, who share ship capacity on a network, independently accept cargo from their location and contribute to the revenue of the system. The central headquarters does not directly control the agents' decisions but can influence them through system design and incentives. In this paper, we model the firm's problem to determine the best capacity allocation to the agents such that system revenue is maximized. In the special case of a single‐route, we formulate the problem as a mixed integer program incorporating the optimal agent behavior. For the NP‐hard multiple‐route case, we propose several heuristics for the problem. Computational experiments show that the decentralized system generally performs worse when network capacity is tight and that the heuristics perform reasonably well. We show that the decentralized system may perform arbitrarily worse than the centralized system when the number of locations goes to infinity, although the choice of sales incentive impacts the performance. We develop an upper bound for the decentralized system, where the bound gives insight on the performance of the heuristics in large systems. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

Subspace dynamic‐simplex linear interpolation search for mixed‐integer black‐box optimization problems

Design and management of complex systems with both integer and continuous decision variables can be guided using mixed‐integer optimization models and analysis. We propose a new mixed‐integer black‐box optimization (MIBO) method, subspace dynamic‐simplex linear interpolation search (SD‐SLIS), for decision making problems in which system performance can only be evaluated with a computer black‐box model. Through a sequence of gradient‐type local searches in subspaces of solution space, SD‐SLIS is particularly efficient for such MIBO problems with scaling issues. We discuss the convergence conditions and properties of SD‐SLIS algorithms for a class of MIBO problems. Under mild conditions, SD‐SLIS is proved to converge to a stationary solution asymptotically. We apply SD‐SLIS to six example problems including two MIBO problems associated with petroleum field development projects. The algorithm performance of SD‐SLIS is compared with that of a state‐of‐the‐art direct‐search method, NOMAD, and that of a full space simplex interpolation search, Full‐SLIS. The numerical results suggest that SD‐SLIS solves the example problems efficiently and outperforms the compared methods for most of the example cases. © 2017 Wiley Periodicals, Inc. Naval Research Logistics 64: 305–322, 2017     

The one‐warehouse multiretailer problem with an order‐up‐to level inventory policy

We consider a two‐level system in which a warehouse manages the inventories of multiple retailers. Each retailer employs an order‐up‐to level inventory policy over T periods and faces an external demand which is dynamic and known. A retailer's inventory should be raised to its maximum limit when replenished. The problem is to jointly decide on replenishment times and quantities of warehouse and retailers so as to minimize the total costs in the system. Unlike the case in the single level lot‐sizing problem, we cannot assume that the initial inventory will be zero without loss of generality. We propose a strong mixed integer program formulation for the problem with zero and nonzero initial inventories at the warehouse. The strong formulation for the zero initial inventory case has only T binary variables and represents the convex hull of the feasible region of the problem when there is only one retailer. Computational results with a state‐of‐the art solver reveal that our formulations are very effective in solving large‐size instances to optimality. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

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     

Resource allocation with lumpy demand: To speed or not to speed?

In the classical EPQ model with continuous and constant demand, holding and setup costs are minimized when the production rate is no larger than the demand rate. However, the situation may change when demand is lumpy. We consider a firm that produces multiple products, each having a unique lumpy demand pattern. The decision involves determining both the lot size for each product and the allocation of resources for production rate improvements among the products. We find that each product's optimal production policy will take on only one of two forms: either continuous production or lot‐for‐lot production. The problem is then formulated as a nonlinear nonsmooth knapsack problem among products determined to be candidates for resource allocation. A heuristic procedure is developed to determine allocation amounts. The procedure decomposes the problem into a mixed integer program and a nonlinear convex resource allocation problem. Numerical tests suggest that the heuristic performs very well on average compared to the optimal solution. Both the model and the heuristic procedure can be extended to allow the company to simultaneously alter both the production rates and the incoming demand lot sizes through quantity discounts. Extensions can also be made to address the case where a single investment increases the production rate of multiple products. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004.     

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     

New inequalities for finite and infinite group problems from approximate lifting

In this paper, we derive new families of facet‐defining inequalities for the finite group problem and extreme inequalities for the infinite group problem using approximate lifting. The new valid inequalities for the finite group problem include two‐ and three‐slope facet‐defining inequalities as well as the first family of four‐slope facet‐defining inequalities. The new valid inequalities for the infinite group problem include families of two‐ and three‐slope extreme inequalities. These new inequalities not only illustrate the diversity of strong inequalities for the finite and infinite group problems, but also provide a large variety of new cutting planes for solving integer and mixed‐integer programming problems. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

Technical note: A computationally efficient algorithm for undiscounted Markov decision processes with restricted observations

We present a computationally efficient procedure to determine control policies for an infinite horizon Markov Decision process with restricted observations. The optimal policy for the system with restricted observations is a function of the observation process and not the unobservable states of the system. Thus, the policy is stationary with respect to the partitioned state space. The algorithm we propose addresses the undiscounted average cost case. The algorithm combines a local search with a modified version of Howard's (Dynamic programming and Markov processes, MIT Press, Cambridge, MA, 1960) policy iteration method. We demonstrate empirically that the algorithm finds the optimal deterministic policy for over 96% of the problem instances generated. For large scale problem instances, we demonstrate that the average cost associated with the local optimal policy is lower than the average cost associated with an integer rounded policy produced by the algorithm of Serin and Kulkarni Math Methods Oper Res 61 (2005) 311–328. © 2008 Wiley Periodicals, Inc. Naval Research Logistics 2009     

Expansion planning for waste‐to‐energy systems using waste forecast prediction sets

We consider an expansion planning problem for Waste‐to‐Energy (WtE) systems facing uncertainty in future waste supplies. The WtE expansion plans are regarded as strategic, long term decisions, while the waste distribution and treatment are medium to short term operational decisions which can adapt to the actual waste collected. We propose a prediction set uncertainty model which integrates a set of waste generation forecasts and is constructed based on user‐specified levels of forecasting errors. Next, we use the prediction sets for WtE expansion scenario analysis. More specifically, for a given WtE expansion plan, the guaranteed net present value (NPV) is evaluated by computing an extreme value forecast trajectory of future waste generation from the prediction set that minimizes the maximum NPV of the WtE project. This problem is essentially a multiple stage min‐max dynamic optimization problem. By exploiting the structure of the WtE problem, we show this is equivalent to a simpler min‐max optimization problem, which can be further transformed into a single mixed‐integer linear program. Furthermore, we extend the model to optimize the guaranteed NPV by searching over the set of all feasible expansion scenarios, and show that this can be solved by an exact cutting plane approach. We also propose a heuristic based on a constant proportion distribution rule for the WtE expansion optimization model, which reduces the problem into a moderate size mixed‐integer program. Finally, our computational studies demonstrate that our proposed expansion model solutions are very stable and competitive in performance compared to scenario tree approaches. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 47–70, 2016     

Formulations for dynamic lot sizing with service levels

In this article, we study deterministic dynamic lot‐sizing problems with a service‐level constraint on the total number of periods in which backlogs can occur over a finite planning horizon. We give a natural mixed integer programming formulation for the single item problem (LS‐SL‐I) and study the structure of its solution. We show that an optimal solution to this problem can be found in \begin{align*}\mathcal O(n^2\kappa)\end{align*} time, where n is the planning horizon and \begin{align*}\kappa=\mathcal O(n)\end{align*} is the maximum number of periods in which demand can be backlogged. Using the proposed shortest path algorithms, we develop alternative tight extended formulations for LS‐SL‐I and one of its relaxations, which we refer to as uncapacitated lot sizing with setups for stocks and backlogs. {We show that this relaxation also appears as a substructure in a lot‐sizing problem which limits the total amount of a period's demand met from a later period, across all periods.} We report computational results that compare the natural and extended formulations on multi‐item service‐level constrained instances. © 2013 Wiley Periodicals, Inc. Naval Research Logistics, 2013     

Expedients for solving some specially structured mixed-integer programs

In this paper we consider dual angular and angular structured mixed integer programs which arise in some practical applications. For these problems we describe efficient methods for generating a desirable set of Benders' cuts with which one may initialize the partitioning scheme of Benders. Our research is motivated by the computational experience of McDaniel and Devine who have shown that the set of Benders' cuts which are binding at the optimum to the linear relaxation of the mixed integer program, play an important role in determining an optimal mixed integer solution. As incidental results in our development, we provide some useful remarks regarding Benders' and Dantzig-Wolfe's decomposition procedures. The computational experience reported seems to support the expedients recommended in this paper.     

Competition under time‐varying demands and dynamic lot sizing costs

We develop a competitive pricing model which combines the complexity of time‐varying demand and cost functions and that of scale economies arising from dynamic lot sizing costs. Each firm can replenish inventory in each of the T periods into which the planning horizon is partitioned. Fixed as well as variable procurement costs are incurred for each procurement order, along with inventory carrying costs. Each firm adopts, at the beginning of the planning horizon, a (single) price to be employed throughout the horizon. On the basis of each period's system of demand equations, these prices determine a time series of demands for each firm, which needs to service them with an optimal corresponding dynamic lot sizing plan. We establish the existence of a price equilibrium and associated optimal dynamic lotsizing plans, under mild conditions. We also design efficient procedures to compute the equilibrium prices and dynamic lotsizing plans.© 2008 Wiley Periodicals, Inc. Naval Research Logistics 2009     

Capacitated lot‐sizing and scheduling with parallel machines,back‐orders,and setup carry‐over

We address the capacitated lot‐sizing and scheduling problem with setup times, setup carry‐over, back‐orders, and parallel machines as it appears in a semiconductor assembly facility. The problem can be formulated as an extension of the capacitated lot‐sizing problem with linked lot‐sizes (CLSPL). We present a mixed integer (MIP) formulation of the problem and a new solution procedure. The solution procedure is based on a novel “aggregate model,” which uses integer instead of binary variables. The model is embedded in a period‐by‐period heuristic and is solved to optimality or near‐optimality in each iteration using standard procedures (CPLEX). A subsequent scheduling routine loads and sequences the products on the parallel machines. Six variants of the heuristic are presented and tested in an extensive computational study. © 2009 Wiley Periodicals, Inc. Naval Research Logistics 2009     

An exact network flow formulation for cell‐based evacuation in urban areas

In the literature two common macroscopic evacuation planning approaches exist: The dynamic network flow approach and the Cell–Transmission–Based approach. Both approaches have advantages and disadvantages. Many efficient solution approaches for the dynamic network flow approach exist so that realistic problem instances can be considered. However, the consideration of (more) realistic aspects (eg, density dependent travel times) results in non‐linear model formulations. The Cell‐Transmission‐Based approach on the other hand considers realistic traffic phenomena like shock waves and traffic congestion, but this approach leads to long computational times for realistic problem instances. In this article, we combine the advantages of both approaches: We consider a Cell‐Transmission‐Based Evacuation Planning Model (CTEPM) and present a network flow formulation that is equivalent to the cell‐based model. Thus, the computational costs of the CTEPM are enormously reduced due to the reformulation and the detailed representation of the traffic flow dynamics is maintained. We investigate the impacts of various evacuation scenario parameters on the evacuation performance and on the computational times in a computational study including 90 realistic instances.     

Dynamic capacity reservation and due date quoting in a make‐to‐order system

We consider a make‐to‐order manufacturer facing random demand from two classes of customers. We develop an integrated model for reserving capacity in anticipation of future order arrivals from high priority customers and setting due dates for incoming orders. Our research exhibits two distinct features: (1) we explicitly model the manufacturer's uncertainty about the customers' due date preferences for future orders; and (2) we utilize a service level measure for reserving capacity rather than estimating short and long term implications of due date quoting with a penalty cost function. We identify an interesting effect (“t‐pooling”) that arises when the (partial) knowledge of customer due date preferences is utilized in making capacity reservation and order allocation decisions. We characterize the relationship between the customer due date preferences and the required reservation quantities and show that not considering the t‐pooling effect (as done in traditional capacity and inventory rationing literature) leads to excessive capacity reservations. Numerical analyses are conducted to investigate the behavior and performance of our capacity reservation and due date quoting approach in a dynamic setting with multiple planning horizons and roll‐overs. One interesting and seemingly counterintuitive finding of our analyses is that under certain conditions reserving capacity for high priority customers not only improves high priority fulfillment, but also increases the overall system fill rate. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

Mathematical formulation and heuristic algorithm for the block relocation and loading problem

This study considers the block relocation and loading problem in container terminals. The optimal loading sequence and relocation location are simultaneously decided on the basis of the desired ship‐bay and initial yard space configuration. An integer linear programming model is developed to minimize the number of relocations in the yard space on the basis of no shifts in the ship bay. The accuracy of the model is tested on small‐scale scenarios by using CPLEX. Considering the problem size in the real world, we present a rule‐based heuristic method that is combined with a mathematical model for the removal, loading, and relocation operations. The influence of rules on algorithm performance is also analyzed, and the heuristic algorithm is compared with different types of algorithms in the literature. The extensive numerical experiments show the efficiency of the proposed heuristic algorithm.     

Repairable consecutive‐k‐out‐of‐n: F system with Markov dependence

In this article, a model for a repairable consecutive‐k‐out‐of‐n: F system with Markov dependence is studied. A binary vector is used to represent the system state. The failure rate of a component in the system depends on the state of the preceding component. The failure risk of a system state is then introduced. On the basis of the failure risk, a priority repair rule is adopted. Then the transition density matrix can be determined, and the analysis of the system reliability can be conducted accordingly. One example each of a linear and a circular system is then studied in detail to explain the model and methodology developed in this paper. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 18–39, 2000     

A two‐echelon inventory‐location problem with service considerations

We study the problem of designing a two‐echelon spare parts inventory system consisting of a central plant and a number of service centers each serving a set of customers with stochastic demand. Processing and storage capacities at both levels of facilities are limited. The manufacturing process is modeled as a queuing system at the plant. The goal is to optimize the base‐stock levels at both echelons, the location of service centers, and the allocation of customers to centers simultaneously, subject to service constraints. A mixed integer nonlinear programming model (MINLP) is formulated to minimize the total expected cost of the system. The problem is NP‐hard and a Lagrangian heuristic is proposed. We present computational results and discuss the trade‐off between cost and service. © 2009 Wiley Periodicals, Inc. Naval Research Logistics 2009     

Optimal retail assortments for substitutable items purchased in sets

We consider the problem of optimizing assortments in a multi‐item retail inventory system. In addition to the usual holding and stockout costs, there is a fixed cost for including any item in the assortment. Customers' preferences for items include both probabilistic substitution patterns and the desire to purchase sets of complementary items. We develop a demand model to capture this behavior, and derive tractable approximations that allow us to formulate the optimization problem as a 0–1 mixed integer linear program. Numerical examples are solved to illustrate key insights into how both complementary and substitute items affect the optimal assortment and the expected profit. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 793–822, 2003.