We consider a dynamic, stochastic extension to the transportation problem. For the deterministic problem, there are known necessary and sufficient conditions under which a greedy algorithm achieves the optimal solution. We define a distribution-free type of optimality and provide analogous necessary and sufficient conditions under which a greedy policy achieves this type of optimality in the dynamic, stochastic setting. These results are used to prove that a greedy algorithm is optimal when planning a type of air-traffic management initiative. We also provide weaker conditions under which it is possible to strengthen an existing policy. These results can be applied to the problem of matching passengers with drivers in an on-demand taxi service. They specify conditions under which a passenger and driver should not be left unassigned.

Abstract In this article we analyze certain matching problems that arise in ground delay program planning. Ground delay programs are air traffic flow management initiatives put in place when airport arrival demand is expected to exceed arrival capacity for an extended length of time, e.g. 4 h. Most of the problems we study can be modeled as assignment problems, where flights are assigned to arrival slots. In the context we analyze, however, these problems have important special structure, which allows us to develop special solution properties. In particular, solutions are measured both in terms of efficiency (delay minimization) and equity (delay distribution). We show that the theory of majorization provides a powerful tool in addressing solution equity. We consider problems with flight deletions and develop special solution properties and parametric methods. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009

Abstract At the sort facility in a large overnight package delivery operation, palletized loads are moved in a container (called an inbound ULD) from a plane to a bin, unloaded from the bin, and moved by forklift one item at a time from a bin to a rack. At the rack, each palletized load is loaded into a container (called an outbound ULD) and this outbound ULD is delivered to a plane for delivery to its final delivery airport. The purpose of this study was to determine the optimal design of this sort facility that acts as a hub in a hub‐and‐spoke system. For a given topology of the sort facility (a topology being the specification of the locations of the bins and the racks), a design of this sort facility is the assignment of inbound ULDs to bins and outbound ULDs to racks and the determination of the number of forklifts needed to carry out the sort. In this paper, the Bin and Rack Assignment Model (BRAM) is developed to perform this analysis; the objective of the BRAM is to minimize the daily operating and amortized capital cost of performing the sort. Since the BRAM is computationally difficult to solve, the BAM and RAM algorithm is developed to derive heuristic solutions to the BRAM. Several examples of the BAM and RAM algorithm are presented. A modification to the BAM and RAM algorithm for solving practical‐sized problems is then presented and future directions for this analysis are discussed. © 2002 Wiley Periodicals, Inc.

Asynchronous Transfer Mode (ATM) is a communications architecture for the provision of broadband integrated services digital networks. Two fundamental features of ATM networks are hierarchical routing and statistical multiplexing. This paper addresses the problem of laying out virtual paths (VPs), which are logical network links that provide direct connections between certain nodes. A bi-criteria integer-programming model is developed that includes a throughput-maximization objective, a delay/overhead minimization objective, and a diversity constraint whereby link-disjoint VPs are found so as to provide fault tolerance. The formulation employs a new model for approximating the effects of statistical multiplexing. An approximate solution method is developed, which employs constraint generation for bound tightening, and heuristics based on rounding of a linear programming solution.

The objective of air traffic flow management is to maintain safe and efficient use of airspace and airports by regulating the flow of traffic. We introduce a single-valued metric for post-operatively rating the performance of achieved traffic flow against targeted traffic flow. We provide variations on the metric, one of which factors out stochastic conditions upon which a plan is formulated, and show how these improve on current traffic control analysis techniques. The core of the metric is intuitive and simple, yet leads to an interesting optimization problem that can be efficiently solved via dynamic programming. Numerical results of the metric are given as well as a sample of the type of analysis that should follow a low rating by the metric. Although this metric was originally developed to rate the performance of ground delay programs, it is equally applicable to any setting in which the flow of discrete objects such as vehicles is controlled and later evaluated.

Abstract This paper addresses two classes of reliability analysis models: a network flow model and a project scheduling model. In each model, the arcs randomly and independently take on two possible states–an “operating” state and a “failed” state–corresponding to two different capacity/task‐time values, and the network is required to maintain a specified “threshold” max‐flow/project‐completion‐time value. In general, this problem is NP‐hard. We address the special case in which the difference between the lower and higher arc lengths is constant for every arc in the network. For these special cases, we show that if the underlying system is 1‐critical, i.e., minimally able to withstand a single component failure, then the probability that the system can maintain the required threshold for the flow and planar project scheduling model is computable in polynomial time. Both solutions are obtained by reducing the problems to the problem of determining the probability that the failed arcs in a directed acyclic graph lie on a single path or, equivalently, that the set of failed elements in a given partial order comprises a chain in that order. We also show how the basic approach can be used to generate bounds for systems that are “almost critical”.

There has been a growing demand for the development of tools to manage enterprise communication networks. A management information database is the heart of a network management system-it provides the interface between all functions of the network management system and, therefore, has to provide sophisticated functionality allied with high performance. The authors introduce the design of MANDATE (MAnaging Networks using DAtabase TEchnology), a proposed database system for effectively supporting the management of large enterprise networks. The MANDATE design makes a conscious attempt to take advantage of the special characteristics of network data and transactions, and of advances in database technology, to efficiently derive some of the required management functionality.>

Abstract This paper studies the reliability covering problem, in which given routes provides service to various stops (e.g., of a transit system). If the routes are subject to failure, it is desired to find the probability that all stops will be covered by an operating route. It is shown that this problem is NP‐hard even when routes are defined with respect to an underlying tree. Polynomially solvable cases are developed when some additional structure is imposed on the routes of a tree: e.g., when the routes are directed paths of a rooted directed tree. These cases generalize reliability computations for consecutive k‐out‐of‐n systems as well as the extensions to consecutively connected systems studied by Shanthikumar and by Hwang and Yao.

Abstract In this article, we develop and compare procedures for the approximate solution of weighted nonbipartite matching problems with generalized upper bound side constraints. The approaches we consider are all based on Lagrangean relaxation and dual ascent. We also use a knapsack‐based procedure for finding improved feasible solutions and a “ k ‐best” solution enumeration procedure to guarantee optimality. Our computational experiments addressed two issues: the choice of the best combination of a matching code and postoptimality routine and the choice of a dual ascent rule. Our recommended combination of procedures consistently produced solutions with a very small deviation from optimality without having to resort to the enumeration procedure.

Abstract In this paper we explore implementation issues related to the solution of the weighted matching problem defined on an undirected graph G = (V, E). We present algorithms based on the two different linear characterizations of the feasible solutions to the matching problem. Furthermore, we present two specialized implementations, one with an O (|V|3) time bound and one with an O(|V‖E| log |V|) time bound. Both of these implementations have storage requirements that are linear in |V| and |E|. We initially develop these algorithms as special implementations of the well‐known primaldual (blossom) algorithm and then show how the updates they perform have an interesting interpretation when the algorithms are viewed as methods that successively find shortest augmenting paths. Finally, we show that postoptimality analysis can be performed very efficiently within this setting.

Abstract In this article, computational procedures are presented for generating bounds on measures of network reliability. The two measures considered, reachability and connectedness, are the probability that there is an operating path from a node to all other nodes in a directed (respectively undirected) stochastic network. Our bounds, which are given in terms of polynomials in p , the common arc failure probability, are based on recent bounding results developed by the authors for the class of shellable independence systems. Two pairs of bounds are given: weaker bounds whose computation time is bounded by a polynomial in the size of the network and tighter bounds whose computation time is bounded by a polynomial in the size of the network and the number of minimum‐cardinality network cuts. Computational results are also given which evaluate the quality of the bounds. The generation of the bounds involves several interesting path and cut counting problems.

Several enumeration and reliability problems are shown to be # P-complete, and hence, at least as hard as NP-complete problems. Included are important problems in network reliability analysis, namely, computing the probability that a graph is connected and counting the number of minimum cardinality $(s,t)$-cuts or directed network cuts. Also shown to be # P-complete are counting vertex covers in a bipartite graph, counting antichains in a partial order, and approximating the probability that a graph is connected and the probability that a pair of vertices is connected.

Abstract This discussion session was concerned with the analysis of heuristics and the design of more effective heuristics. Initially, the group generated a list of evaluation criteria and discussed the strengths and weaknesses of each criterion. Next a classification of heuristic approaches was devised. Finally, the group compiled a list of promising research directions.

Abstract This paper considers the difficulty of computing several measures of network reliability on directed and undirected networks. Results concerning the NP‐difficulty of several network reliability analysis problems are unified and in several cases generalized to wider classes of measures. Reductions are also given that relate network reliability problems on directed and undirected networks and problems with and without node failures.

Abstract This paper considers the problem of finding the shortest path between an origin and destination pair in networks whose arc lengths are Euclidean distances. Dijkstra's algorithm and a modified version of Dijkstra's algorithm which is more adaptive to network topology are compared. We demonstrate on the infinite lattice network with diagonal arcs (a prototype of more general sparse Euclidean networks) that on the average the adaptive algorithm expands less than 8.3% the area that would be expanded by the Dijkstra algorithm and in the worst case it expands less than 10.7%. In addition, we present computational results for more general networks.