Rank‐Cluster‐and‐Prune: An algorithm for generating clusters in complex set partitioning problems

Clustering problems are often difficult to solve due to nonlinear cost functions and complicating constraints. Set partitioning formulations can help overcome these challenges, but at the cost of a very large number of variables. Therefore, techniques such as delayed column generation must be used to solve these large integer programs. The underlying pricing problem can suffer from the same challenges (non‐linear cost, complicating constraints) as the original problem, however, making a mathematical programming approach intractable. Motivated by a real‐world problem in printed circuit board (PCB) manufacturing, we develop a search‐based algorithm (Rank‐Cluster‐and‐Prune) as an alternative, present computational results for the PCB problem to demonstrate the tractability of our approach, and identify a broader class of clustering problems for which this approach can be used. © 2009 Wiley Periodicals, Inc. Naval Research Logistics 2009     

What you should know about simulation and derivatives

Derivatives (or gradients) are important for both sensitivity analysis and optimization, and in simulation models, these can often be estimated efficiently using various methods other than brute‐force finite differences. This article briefly summarizes the main approaches and discusses areas in which the approaches can most fruitfully be applied: queueing, inventory, and finance. In finance, the focus is on derivatives of another sort. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

Ambulance location for maximum survival

This article proposes new location models for emergency medical service stations. The models are generated by incorporating a survival function into existing covering models. A survival function is a monotonically decreasing function of the response time of an emergency medical service (EMS) vehicle to a patient that returns the probability of survival for the patient. The survival function allows for the calculation of tangible outcome measures—the expected number of survivors in case of cardiac arrests. The survival‐maximizing location models are better suited for EMS location than the covering models which do not adequately differentiate between consequences of different response times. We demonstrate empirically the superiority of the survival‐maximizing models using data from the Edmonton EMS system. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

Analysis of artillery shoot‐and‐scoot tactics

Firing multiple artillery rounds from the same location has two main benefits: a high rate of fire at the enemy and improved accuracy as the shooter's aim adjusts to previous rounds. However, firing repeatedly from the same location carries significant risk that the enemy will detect the artillery's location. Therefore, the shooter may periodically move locations to avoid counter‐battery fire. This maneuver is known as the shoot‐and‐scoot tactic. This article analyzes the shoot‐and‐scoot tactic for a time‐critical mission using Markov models. We compute optimal move policies and develop heuristics for more complex and realistic settings. Spending a reasonable amount of time firing multiple shots from the same location is often preferable to moving immediately after firing an initial salvo. Moving frequently reduces risk to the artillery, but also limits the artillery's ability to inflict damage on the enemy.     

Aggregating courier deliveries

We consider the problem of efficiently scheduling deliveries by an uncapacitated courier from a central location under online arrivals. We consider both adversary‐controlled and Poisson arrival processes. In the adversarial setting we provide a randomized (3βΔ/2δ ? 1) ‐competitive algorithm, where β is the approximation ratio of the traveling salesman problem, δ is the minimum distance between the central location and any customer, and Δ is the length of the optimal traveling salesman tour overall customer locations and the central location. We provide instances showing that this analysis is tight. We also prove a 1 + 0.271Δ/δ lower‐bound on the competitive ratio of any algorithm in this setting. In the Poisson setting, we relax our assumption of deterministic travel times by assuming that travel times are distributed with a mean equal to the excursion length. We prove that optimal policies in this setting follow a threshold structure and describe this structure. For the half‐line metric space we bound the performance of the randomized algorithm in the Poisson setting, and show through numerical experiments that the performance of the algorithm is often much better than this bound.     

The Economic Effect of Military Facility Contraction: A Naval Case Study

The global financial turmoil of 2008 has resulted in the curtailment of military expenditure in most western countries. At a sub-regional-level reductions in the level of activity at a major military facility can have significant economic impact. In the light of this, the paper has two objectives: to analyse the impact of the decision to terminate naval shipbuilding at the United Kingdom’s Portsmouth Naval Base; and, for illustrative purposes, to examine the possible economic consequences of further contraction at the facility. In pursuit of these aims, it is necessary to establish the output, income and employment generated by the base using a bespoke input–output model. The methodology employed can, with appropriate adjustments, be utilised in other military or civilian contexts.     

Optimizing submarine berthing with a persistence incentive

Submarine berthing plans reserve mooring locations for inbound U.S. Navy nuclear submarines prior to their port entrance. Once in port, submarines may be shifted to different berthing locations to allow them to better receive services they require or to make way for other shifted vessels. However, submarine berth shifting is expensive, labor intensive, and potentially hazardous. This article presents an optimization model for submarine berth planning and demonstrates it with Naval Submarine Base, San Diego. After a berthing plan has been approved and published, changed requests for services, delays, and early arrival of inbound submarines are routine events, requiring frequent revisions. To encourage trust in the planning process, the effect on the solution of revisions in the input is kept small by incorporating a persistence incentive in the optimization model. © 1997 John Wiley & Sons, Inc. Naval Research Logistics 44: 301–318, 1997.     

Compromise allocation in multivariate stratified sampling: An integer solution

The problem of determining the sample sizes in various strata when several characteristics are under study is formulated as a nonlinear multistage decision problem. Dynamic programming is used to obtain an integer solution to the problem. © 1997 John Wiley & Sons, Inc.     

Environmental regulation in project‐based industries

We study the environmental regulation of industrial activities that are organized as projects. Applications arise in construction, ship and aircraft building, and film making, among other industries. Relative to manufacturing, environmental regulation is different in project‐based industries, due to the uniqueness and geographical diversity of projects, and a lack of product takeback programs. Because the amount of waste and pollution generated by project companies can be large, regulators need environmental policies to ensure reduction of waste and pollution. We consider a regulator who attempts to maximize social welfare. We model this problem as a bilevel nonlinear program. The upper level regulator specifies waste reduction targets, which the lower level project companies meet using waste stream reduction and remediation of pollution, while attempting to control their project costs. We find that high waste diversion targets lead to outcomes with little pollution, but excessive project costs and only modest waste stream reduction. Projects that have lower task precedence density, or that have pollutants with different environmental impacts, show larger increases in project cost and time resulting from regulation. We describe a subsidy for waste stream reduction that coordinates the system, and we estimate the value of coordination. We also describe a bonus that encourages truthful reporting by project companies, and evaluate the relative cost and effectiveness of the subsidy and the bonus. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 228–247, 2015