An interactive optimization system for bulk-cargo ship scheduling

This article considers the efficient scheduling of a fleet of ships engaged in pickup and delivery of bulk cargoes. Our optimization system begins by generating a menu of candidate schedules for each ship. This menu can contain all feasible solutions, which guarantees we will find an optimal solution or can be heuristically limited to contain only those schedules likely to be in an optimal solution. The problem of choosing from this menu an optimal schedule for the fleet is formulated as a set-packing problem and solved with a dual algorithm. Computational experience is presented based on real data obtained from the Military Sealift Command of the U. S. Navy. Run times for this data were reasonable and solutions were generated with the potential of saving up to about $30 million per year over the manual system currently in place. We also describe a color-graphics interface developed to facilitate interaction with the optimization system.     

Probability inequalities via negative dependence for random variables conditioned on order statistics

Distributions are studied which arise by considering independent and identically distributed random variables conditioned on events involving order statistics. It is shown that these distributions are negatively dependent in a very strong sense. Furthermore, bounds are found on the distribution functions. The conditioning events considered occur naturally in reliability theory as the time to system failure for k-out-of-n systems. An application to systems formed with “second-hand” components is given.     

The many-on-one stochastic duel

The general many-on-one stochastic duel conditioned on the order in which targets are attacked is investigated, and the state probabilities are derived for the first time. The results are illustrated by an example of a three-on-one stochastic duel with negative exponential interfiring times. Some aspects of the tradeoff between individual firepower and the nominal size of a force are investigated.     

Inventory/routing: Reduction from an annual to a short-period problem

The inventory-routing problem is a distribution problem in which each customer maintains a local inventory of a product such as heating oil and consumes a certain amount of that product each day. Given a central supplier, the objective is to minimize the annual delivery costs while attempting to insure that no customer runs out of the commodity at any time. In this article we present a procedure for reducing the long-term version of this problem to a single-period problem, which can be attacked using standard routing algorithms. The reduction procedure involves the definition of single-period costs that reflect long-term costs, the definition of a safety stock level and a specification of the customer subset to be considered during a single period.     

Models of sensor operations for border surveillance

This article is motivated by the diverse array of border threats, ranging from terrorists to arms dealers and human traffickers. We consider a moving sensor that patrols a certain section of a border with the objective to detect infiltrators who attempt to penetrate that section. Infiltrators arrive according to a Poisson process along the border with a specified distribution of arrival location, and disappear a random amount of time after their arrival. The measures of effectiveness are the target (infiltrator) detection rate and the time elapsed from target arrival to target detection. We study two types of sensor trajectories that have constant endpoints, are periodic, and maintain constant speed: (1) a sensor that jumps instantaneously from the endpoint back to the starting‐point, and (2) a sensor that moves continuously back and forth. The controlled parameters (decision variables) are the starting and end points of the patrolled sector and the velocity of the sensor. General properties of these trajectories are investigated. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

The effect of crowd density on the expected number of casualties in a suicide attack

Utilizing elementary geometric and probability considerations, we estimate the effect of crowd blocking in suicide bombing events. It is shown that the effect is quite significant. Beyond a certain threshold, the expected number of casualties decreases with the number of people in the arena. The numerical results of our model are consistent with casualty data from suicide bombing events in Israel. Some operational insights are discussed. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

Optimality of the greedy shooting strategy in the presence of incomplete damage information

Consider a situation where a single shooter engages, sequentially, a cluster of targets that may vary in terms of vulnerability and value or worth. Following the shooting of a round of fire at a certain target, the latter may either be killed or remain alive. We assume neither partial nor cumulative damage. If the target is killed, there is a possibility that the shooter is not aware of that fact and may keep on engaging that target. If the shooter recognizes a killed target as such, then this target is considered to be evidently killed. If the objective is to maximize the weighted expected number of killed targets, where the weight reflects the value of a target, then it is shown that a certain type of a shooting strategy, called a Greedy Strategy, is optimal under the general assumption that the more a target is engaged, but still not evidently killed, the less is the probability that the next round will be effective. If all weights are equal, then the greedy shooting strategy calls to engage, at each round, the least previously engaged target that is not evidently killed. © 1997 John Wiley & Sons, Inc. Naval Research Logistics 44: 613–622, 1997     

Cost allocation in continuous-review inventory models

A centralized inventory system serves a number of stores with common ownership, and thus reliable and timely information sharing. Each of them pays a share of the inventory cost, and the reward structure leaves the owners of individual stores rewarded for their individual performance. Appropriate selection of a cost allocation method is important if such a centralized system is to last. In this work we propose three necessary criteria—stability (core of a related cooperative game), justifiability (consistency of benefits with costs), and polynomial computability. For a concrete example we demonstrate that common allocation procedures may not meet all three tests, and we present a method that that meets all three criteria. This kind of cost allocation analysis helps the common management to evaluate the trade-offs in choosing an allocation scheme for the cost of inventory centralization. © 1996 John Wiley & Sons, Inc.     

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.