Balancing a one‐way corridor capacity and safety‐oriented reliability: A stochastic optimization approach for metro train timetabling

In urban rail transit systems of large cities, the headway and following distance of successive trains have been compressed as much as possible to enhance the corridor capacity to satisfy extremely high passenger demand during peak hours. To prevent train collisions and ensure the safety of trains, a safe following distance of trains must be maintained. However, this requirement is subject to a series of complex factors, such as the uncertain train braking performance, train communication delay, and driver reaction time. In this paper, we propose a unified mathematical framework to analyze the safety‐oriented reliability of metro train timetables with different corridor capacities, that is, the train traffic density, and determine the most reliable train timetable for metro lines in an uncertain environment. By employing a space‐time network representation in the formulations, the reliability‐based train timetabling problem is formulated as a nonlinear stochastic programming model, in which we use 0‐1 variables to denote the time‐dependent velocity and position of all involved trains. Several reformulation techniques are developed to obtain an equivalent mixed integer programming model with quadratic constraints (MIQCP) that can be solved to optimality by some commercial solvers. To improve the computational efficiency of the MIQCP model, we develop a dual decomposition solution framework that decomposes the primal problem into several sets of subproblems by dualizing the coupling constraints across different samples. An exact dynamic programming combined with search space reduction strategies is also developed to solve the exact optimal solutions of these subproblems. Two sets of numerical experiments, which involve a relatively small‐scale case and a real‐world instance based on the operation data of the Beijing subway Changping Line are implemented to verify the effectiveness of the proposed approaches.     

An integer programming model for the weekly tour scheduling problem

We study a workforce planning and scheduling problem in which weekly tours of agents must be designed. Our motivation for this study comes from a call center application where agents serve customers in response to incoming phone calls. Similar to many other applications in the services industry, the demand for service in call centers varies significantly within a day and among days of the week. In our model, a weekly tour of an agent consists of five daily shifts and two days off, where daily shifts within a tour may be different from each other. The starting times of any two consecutive shifts, however, may not differ by more than a specified bound. Furthermore, a tour must also satisfy constraints regarding the days off, for example, it may be required that one of the days off is on a weekend day. The objective is to determine a collection of weekly tours that satisfy the demand for agents' services, while minimizing the total labor cost of the workforce. We describe an integer programming model where a weekly tour is obtained by combining seven daily shift scheduling models and days‐off constraints in a network flow framework. The model is flexible and can accommodate different daily models with varying levels of detail. It readily handles different days‐off rules and constraints regarding start time differentials in consecutive days. Computational results are also presented. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 607–624, 2001.     

The multicommodity network flow model revised to include vehicle per time period and node constraints

The minimum-cost formulation of the problem of determining multicommodity flows over a capacitated network subject to resource constraints has been treated in previobs papers. In those treatments only capacitated arcs were assumed and a uniform unit of measure like short tons was used for all commodities. This paper treats the effect of constraints on the nodes of the network, allows the commodities to be measured in their “natural” units and allows the network capacities to be expressed in vehicles per time period-in some cases giving a more accurate representation of the capacities of the network. This paper describes the solution procedure which uses the column generation technique; it also discusses computational experience.     

A note on a constrained replacement model for ships subject to degradations in utility

In a recent paper, Peter J. Kalman considers a stochastic constrained optimal replacement model using the case of ship replacement as an example. However, the development of the constrained model proposed is not pursued and the optimal interval between replacements is determined in the absence of constraints. Among other things, it is the purpose of the present paper to extend the previous results to develop explicit types of constraints for the case of ship replacement and to determine how the optimal replacement interval may change as a result of these constraints. The constraints are concerned with the state of readiness of each ship in a group of ships. Readiness is assumed to be measured on an ordinal valued utility scale. It is proposed that ordinal valued data on ship combat readiness ratings collected by the Navy may be a useful source of empirical information for a model of the type discussed.     

Coordinated replenishments from multiple suppliers with price discounts

In this study we present an integer programming model for determining an optimal inbound consolidation strategy for a purchasing manager who receives items from several suppliers. The model considers multiple suppliers with limited capacity, transportation economies, and quantity discounts. We propose an integrated branch and bound procedure for solving the model. This procedure, applied to a Lagrangean dual at every node of the search tree, combines the subgradient method with a primal heuristic that interact to change the Lagrangean multipliers and tighten the upper and lower bounds. An enhancement to the branch and bound procedure is developed using surrogate constraints, which is found to be beneficial for solving large problems. We report computational results for a variety of problems, with as many as 70,200 variables and 3665 constraints. Computational testing indicates that our procedure is significantly faster than the general purpose integer programming code OSL. A regression analysis is performed to determine the most significant parameters of our model. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 579–598, 1998     

Equitable bandwidth allocation in content distribution networks

Applications for content distribution over networks, such as Video‐on‐Demand (VOD), are expected to grow significantly over time. Effective bandwidth allocation schemes that can be repeatedly executed must be deployed since new programs are often installed at various servers while other are deleted. We present a model for bandwidth allocation in a content distribution network that consists of multiple trees, where the root of each tree has a server that broadcasts multiple programs throughout the tree. Each network link has limited capacity and may be used by one or more of these trees. The model is formulated as an equitable resource allocation problem with a lexicographic maximin objective function that attempts to provide equitable service performance for all requested programs at the various nodes. The constraints include link capacity constraints and tree‐like ordering constraints imposed on each of the programs. We present an algorithm that provides an equitable solution in polynomial time for certain performance functions. At each iteration, the algorithm solves single‐link maximin optimization problems while relaxing the ordering constraints. The algorithm selects a bottleneck link, fixes various variables at their lexicographic optimal solution while enforcing the ordering constraints, and proceeds with the next iteration. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Allocation of carrier-based attack aircraft using non-linear programming

The paper presents the formulation and several solutions of a model for allocating a fixed number of aircraft to carriers and to missions. The amount of damage that can be inflicted is maximized. A nonseparable concave nonlinear objective function expresses diminishing marginal damage. Linear constraints on aireraft, carrier space, and aircraft availability for missions are included. The model is solved using the sequential unconstrained minimization technique (SUMT). The model is presented in terms of a scenario. Several different exponential damage functions are treated, and S-shaped damage functions are discussed.     

A combination of Lagrangian relaxation and column generation for order batching in steelmaking and continuous‐casting production

This article considers the order batching problem in steelmaking and continuous‐casting production. The problem is to jointly specify the slabs needed to satisfy each customer order and group all the slabs of different customer orders into production batches. A novel mixed integer programming model is formulated for the problem. Through relaxing the order assignment constraints, a Lagrangian relaxation model is then obtained. By exploiting the relationship between Lagrangian relaxation and column generation, we develop a combined algorithm that contains nested double loops. At the inner loop, the subgradient method is applied for approximating the Lagrangian dual problem and pricing out columns of the master problem corresponding to the linear dual form of the Lagrangian dual problem. At the outer loop, column generation is employed to solve the master problem exactly and adjust Lagrangian multipliers. Computational experiments are carried out using real data collected from a large steel company, as well as on large‐scaled problem instances randomly generated. The results demonstrate that the combined algorithm can obtain tighter lower bound and higher quality solution within an acceptable computation time as compared to the conventional Lagrangian relaxation algorithm. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

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     

On the optimal detection of an underwater intruder in a channel using unmanned underwater vehicles

Given a number of patrollers that are required to detect an intruder in a channel, the channel patrol problem consists of determining the periodic trajectories that the patrollers must trace out so as to maximized the probability of detection of the intruder. We formulate this problem as an optimal control problem. We assume that the patrollers' sensors are imperfect and that their motions are subject to turn‐rate constraints, and that the intruder travels straight down a channel with constant speed. Using discretization of time and space, we approximate the optimal control problem with a large‐scale nonlinear programming problem which we solve to obtain an approximately stationary solution and a corresponding optimized trajectory for each patroller. In numerical tests for one, two, and three underwater patrollers, an underwater intruder, different trajectory constraints, several intruder speeds and other specific parameter choices, we obtain new insight—not easily obtained using simply geometric calculations—into efficient patrol trajectory design under certain conditions for multiple patrollers in a narrow channel where interaction between the patrollers is unavoidable due to their limited turn rate.© 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

The defence firm of the future

This paper offers the personal view of a senior executive in the Defence Procurement Agency about the future requirements of the defence industry’s principal UK customer. The focus here is on trying to identify the type of corporate behaviour and range of skill sets that the UK Government will need from defence suppliers, both primes and supply chain companies in the future. The concluding message from this ‘Customer View’ is that there is likely to be a continuing market for the company that specializes in delivering defence capability. It will be a company that will be looking for a long‐term relationship, with a specialist knowledge of its various national customers and a willingness to work openly and closely with them. It will be agile in its ability to bring together diverse technologies, to package them as a system and to deliver them either as hardware or as a service. Such suppliers will also need to innovate and to adapt at least as rapidly as the threats that they seek to counter.     

Cyclic preference scheduling for nurses using branch and price

This paper presents a new methodology to solve the cyclic preference scheduling problem for hourly workers. The focus is on nurse rostering but is applicable to any organization in which the midterm scheduling decision must take into account a complex of legal, institutional, and preferential constraints. The objective is to strike a balance between satisfying individual preferences and minimizing personnel costs. The common practice is to consider each planning period independently and to generate new rosters at the beginning of each. To reduce some of the instability in the process, there is a growing trend toward cyclic schedules, which are easier to manage and are generally perceived to be more equitable. To address this problem, a new integer programming model is presented that combines the elements of both cyclic and preference scheduling. To find solutions, a branch‐and‐price algorithm is developed that makes use of several branching rules and an extremely effective rounding heuristic. A unique feature of the formulation is that the master problem contains integer rather than binary variables. Computational results are reported for problem instances with up to 200 nurses. Most were solved within 10 minutes and many within 3 minutes when a double aggregation approach was applicable. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007.     

Comparable deterrence – target,criteria and purpose

The last decade has seen several advances in the study of deterrence. These advances have sparked some strong disagreements regarding interpretation of the models and what their contributions signify. This paper appraises the discussions from a model theoretic perspective. It is argued that when comparing rivalling models three aspects; (i) target, (ii) criteria and (iii) type of purpose should be taken into account in order to make a proper appraisal. Informed by these aspects it is evident that the three deterrence models analysed address different aspects, in different ways and to different ends. From this perspective, the so-called Perfect Deterrence model must be recognised as a clear advancement in the research field. Model comparison will always be context relative and a plurality of models should be viewed favourably.     

Communication: Wrap‐up on the cost of the gulf war

This paper discusses how crises and war may “disrupt” company activities, and how companies adapt to these disruptions. Croatia is used as a case study. The original hypothesis was that war led to breaks in physical flows: in other words, that companies experienced difficulties in importing and obtaining supplies of goods. Instead, it appears that loss of customers and severely worsened conditions of payment were the principal problems for Croatian companies. Although it does not fall within the scope of this investigation, it is interesting to note that the Croatian government has not imposed any direct rationing on the industrial sector, but rather via the banking system.     

A game theoretic approach to a two firm bidding problem

In this paper a model is developed for determining optimal strategies for two competing firms which are about to submit sealed tender bids on K contracts. A contract calls for the winning firm to supply a specific amount of a commodity at the bid price. By the same token, the production of that commodity involves various amounts of N different resources which each firm possesses in limited quantities. It is assumed that the same two firms bid on each contract and that each wants to determine a bidding strategy which will maximize its profits subject to the constraint that the firm must be able to produce the amount of products required to meet the contracts it wins. This bidding model is formulated as a sequence of bimatrix games coupled together by N resource constraints. Since the firms' strategy spaces are intertwined, the usual quadratic programming methods cannot be used to determine equilibrium strategies. In lieu of this a number of theorems are given which partially characterize such strategies. For the single resource problem techniques are developed for determining equilibrium strategies. In the multiple resource problem similar methods yield subequilibrium strategies or strategies that are equilibrium from at least one firm's point of view.     

装备采购委托代理关系分析

针对目前采用的委托方对代理方的激励与约束机制设计,利用博弈论方法分析了监督策略成本会引起最优解迁移,并以实例予以了说明.同时,给出了军事经济效能观测指标的选择原则和多行动代理方的激励机制设计原则.     

飞机发动机关键系统智能故障诊断方法

飞机发动机是一个非常复杂的大系统,由于其结构复杂,工作环境恶劣,对其关键系统的故障进行准确诊断始终是困扰业界的技术瓶颈之一。提出了采用EMD小波阈值降噪与主元分析相结合的方法,对飞机发动机气路系统故障诊断进行了深入研究。针对某型真实飞机发动机进行测试试验采集的气路多参量数据,首先采用经验模态分解(Empirical Mode Decomposition,EMD)对气路系统各参量信号进行EMD分解,然后采用软阈值函数对其进行降噪,并进行信号重构,从而可得到飞机发动机气路工作状态有效数据。在此基础上,设计了飞机发动机气路系统主元分析故障诊断模型,并结合预处理得到的飞机发动机气路有效数据,运用所设计的主元分析故障诊断模型对飞机发动机进行故障诊断技术研究。研究结果表明,所提出的方法能够很好地诊断出飞机发动机气路系统实际运行时所出现的故障,具有重要的实际应用价值,并有广泛的应用前景。     

Machine sequencing: Disjunctive graphs and degree-constrained subgraphs

In two earlier papers, we proposed algorithms for finding an optimal sequence of processing m items on q machines, by finding a minimaximal path in a disjunctive network. In a third paper, this latter model was generalized (from 2-state to 3-state disjunctive graphs) so as to accommodate project scheduling with resource constraints. In this paper, we discuss another algorithm for the (2-state) disjunctive network problem, closely related to those mentioned above. To make the paper self-contained, section 2 briefly describes the problem. Section 3 introduces a class of constraints which forms the basis of the algorithm discussed in section 4. The constraints have only 1, ?1, or 0 as coefficients on the left-hand side, integers on the right-hand side. The whole procedure of generating these constraints and finding a feasible solution whenever a new constraint is added, can be interpreted (section 5) as a process of generating a graph with degree-constraints on its nodes, and then finding a subgraph satisfying the degree-constraints. The nodes of the graph are generated by solving a critical-path-problem, the feasible subgraphs are found by implicit enumeration.     

A heuristic with tie breaking for certain 0–1 integer programming models

A heuristic for 0–1 integer programming is proposed that features a specific rule for breaking ties that occur when attempting to determine a variable to set to 1 during a given iteration. It is tested on a large number of small- to moderate-sized randomly generated generalized set-packing models. Solutions are compared to those obtained using an existing well-regarded heuristic and to solutions to the linear programming relaxations. Results indicate that the proposed heuristic outperforms the existing heuristic except for models in which the number of constraints is large relative to the number of variables. In this case, it performs on par with the existing heuristic. Results also indicate that use of a specific rule for tie breaking can be very effective, especially for low-density models in which the number of variables is large relative to the number of constraints.     

The parallel replacement problem with demand and capital budgeting constraints

A generalized parallel replacement problem is considered with both fixed and variable replacement costs, capital budgeting, and demand constraints. The demand constraints specify that a number of assets, which may vary over time, are required each period over a finite horizon. A deterministic, integer programming formulation is presented as replacement decisions must be integer. However, the linear programming relaxation is shown to have integer extreme points if the economies of scale binary variables are fixed. This allows for the efficient computation of large parallel replacement problems as only a limited number of 0–1 variables are required. Examples are presented to provide insight into replacement rules, such as the “no‐splitting‐rule” from previous research, under various demand scenarios. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 40–56, 2000