Multi-location transshipment problem with capacitated transportation

We consider coordination among stocking locations through replenishment strategies that take explicitly into consideration transshipments, transfer of a product among locations at the same echelon level. We incorporate transportation capacity such that transshipment quantities between stocking locations are bounded due to transportation media or the location’s transshipment policy. We model different cases of transshipment capacity as a capacitated network flow problem embedded in a stochastic optimization problem. Under the assumption of instantaneous transshipments, we develop a solution procedure based on infinitesimal perturbation analysis to solve the stochastic optimization problem, where the objective is to find the policy that minimizes the expected total cost of inventory, shortage, and transshipments. Such a numerical approach provides the flexibility to solve complex problems. Investigating two problem settings, we show the impact of transshipment capacity between stocking locations on system behavior. We observe that transportation capacity constraints not only increase total cost, they also modify the inventory distribution throughout the network.     

Multi-location transshipment problem with capacitated production

We consider coordination among stocking locations through replenishment strategies that explicitly take into account lateral transshipments, i.e., transfer of a product among locations at the same echelon level. Our basic contribution is the incorporation of supply capacity into the traditional transshipment model. Our goal is to analyze the impact on system behavior and on stocking locations’ performance of the fact that the supplier may fail to fulfill all the replenishment orders. We therefore formulate the capacitated supply scenario as a network flow problem embedded in a stochastic optimization problem, which is solved through a sample average approximation method. We find that, depending on the production capacity, system behavior can vary drastically. Moreover, in a production-inventory system, we find evidence that either capacity flexibility (i.e., extra production) or transshipment flexibility (i.e., pooling) is required to maintain a desired level of service.     

Optimal infrastructure design and expansion of broadband wireless access networks

This paper investigates the important infrastructure design and expansion problem for broadband wireless access networks subject to user demand constraints and system capacity constraints. For the problem, an integer program is derived and a heuristic solution procedure is proposed based on Lagrangean relaxation. In the computational experiments, our Lagrangean relaxation based algorithm can solve this complex design and expansion problem quickly and near optimally. Based on the test results, it is suggested that the proposed algorithm may be practically used for the infrastructure design and expansion problem for broadband wireless access networks.     

Implementation and analysis of a variant of the dual method for the capacitated transshipment problem

This paper presents a variant of the dual simplex method for the capacitated pure network problem and a computational analysis of this algorithm. This work includes the considerations of different list structures to store the original problem data and the basis and the testing of various procedures to select the leaving basic variable. This study also examines the sensitivity of the implementation to changes in problem parameters. The results show that the algorithm which is presented here is superior to earlier dual implementations.     

Optimal cost sharing for capacitated facility location games

We consider cost sharing for a class of facility location games, where the strategy space of each player consists of the bases of a player-specific matroid defined on the set of resources. We assume that resources have nondecreasing load-dependent costs and player-specific delays. Our model includes the important special case of capacitated facility location problems, where players have to jointly pay for opened facilities. The goal is to design cost sharing protocols so as to minimize the resulting price of anarchy and price of stability. We investigate two classes of protocols: basic protocols guarantee the existence of at least one pure Nash equilibrium and separable protocols additionally require that the resulting cost shares only depend on the set of players on a resource. We find optimal basic and separable protocols that guarantee the price of stability/price of anarchy to grow logarithmically/linearly in the number of players. These results extend our previous results (cf. von Falkenhausen & Harks, 2013), where optimal basic and separable protocols were given for the case of symmetric matroid games without delays.     

A capacitated hub location problem in freight logistics multimodal networks

In this paper we deal with a capacitated hub location problem arising in a freight logistics context; in particular, we have the need of locating logistics platforms for containers travelling via road and rail. The problem is modelled on a weighed multimodal network. We give a mixed integer linear programming model for the problem, having the goal of minimizing the location and shipping costs. The proposed formulation presents some novel features for modelling capacity bounds that are given both for the candidate hub nodes and the arcs incident to them; further, the containerised origin-destination (\(o-d)\) demand can be split among several platforms and different travelling modes. Note that here the network is not fully connected and only one hub for each \(o-d\) pair is used, serving both to consolidate consignments on less transport connections and as reloading point for a modal change. Results of an extensive computational experimentation performed with randomly generated instances of different size and capacity values are reported. In the test bed designed to validate the proposed model all the instances up to 135 nodes and 20 candidate hubs are optimally solved in few seconds by the commercial solver CPLEX 12.5.     

Optimum synthesis of discrete capacitated networks with multi-terminal commodity flow requirements

Network design problems arise in a wide range of applied areas including telecommunications, computer networks, and transportation. In this paper, we address the following discrete capacitated multi-terminal network design problem. Given a connected digraph G = (V,A), a set of L potential facilities to be installed on each arc, and a set of K multi-terminal (non-simultaneous) commodity flow requirements, the problem is to find a set of facilities to install in order to route the K nonsimultaneous flows while minimizing the total fixed plus variable costs. We describe an exact procedure for solving this problem based on Benders decomposition. Our algorithm includes several features that significantly improve the efficiency of the basic approach. Computational results attest to the efficacy of the proposed algorithm, which can solve medium- to large-scale problems to optimality.     

Optimal fourier-hermite expansion for estimation

The purpose of the paper is to present a systematic method for developing an approximate recursive estimator which is optimal for the given structure and approaches the best estimate, when the order of approximation increases.The minimal variance estimate is projected onto the Hilbert subspace of all Fourier-Hermite (FH) series, driven by the observations, with the same given index set. The projection results in a system of linear algebraic equations for the FH coefficients, the parameters of the desired approximate estimator.The estimator consists of finitely many Wiener integrals of the observations and a memoryless nonlinear postprocessor. The postprocessor is an arithmetic combination of the Hermite polynomials evaluated at the Wiener integrals. A couple of recursive methods for calculating the Wiener integrals are included.     

Optimal expansion of an existing network

Given an existing network, a list of arcs which could be added to the network, the arc costs and capacities, and an available budget, the problem considered in this paper is one of choosing which arcs to add to the network in order to maximize the maximum flow from a sources to a sinkt, subject to the budgetary constraint. This problem appears in a large number of practical situations which arise in connection with the expansion of electricity or gas supply, telephone, road or rail networks. The paper describes an efficient tree-search algorithm using bounds calculated by a dynamic programming procedure which are very effective in limiting the solution space explicitly searched. Computational results for a number of medium sized problems are described and computing times are seen to be very reasonable.     

Optimal lateral transshipment policies for a two location inventory problem with multiple demand classes

We consider an inventory model for spare parts with two stockpoints, providing repairable parts for a critical component of advanced technical systems. As downtime costs for these systems are expensive, ready–for–use spare parts are kept in stock to be able to quickly respond to a breakdown of a system. We allow for lateral transshipments of parts between the stockpoints upon a demand arrival. Each stockpoint faces demands from multiple demand classes. We are interested in the optimal lateral transshipment policy. There are three ways in which a demand can by satisfied: from own stock, via a lateral transshipment, or via an emergency procedure. Using stochastic dynamic programming, we characterize and prove the structure of the optimal policy, that is, the policy for satisfying the demands which minimizes the average operating costs of the system. This optimal policy is a threshold type policy, with state-dependent thresholds at each stockpoint for every demand class. We show a partial ordering in these thresholds in the demand classes. In addition, we derive conditions under which the so-called hold back and complete pooling policies are optimal, two policies that are often assumed in the literature. Furthermore, we study several model extensions which fit in the same modeling framework.     

Optimal allocation of stock levels and stochastic customer demands to a capacitated resource

This paper considers a new class of stochastic resource allocation problems that requires simultaneously determining the customers that a capacitated resource must serve and the stock levels of multiple items that may be used in meeting these customers’ demands. Our model considers a reward (revenue) for serving each assigned customer, a variable cost for allocating each item to the resource, and a shortage cost for each unit of unsatisfied customer demand in a single-period context. The model maximizes the expected profit resulting from the assignment of customers and items to the resource while obeying the resource capacity constraint. We provide an exact solution method for this mixed integer nonlinear optimization problem using a Generalized Benders Decomposition approach. This decomposition approach uses Lagrangian relaxation to solve a constrained multi-item newsvendor subproblem and uses CPLEX to solve a mixed-integer linear master problem. We generate Benders cuts for the master problem by obtaining a series of subgradients of the subproblem’s convex objective function. In addition, we present a family of heuristic solution approaches and compare our methods with several MINLP (Mixed-Integer Nonlinear Programming) commercial solvers in order to benchmark their efficiency and quality.     

Optimal multiple stage expansion of competence set

In this paper, we consider the expansion processes of competence sets which have asymmetric cost functions, intermediate skills, and compound skills; among the skills, cyclic connections are possible. We introduce the concept of the stage expansion process (SEP) of the competence set, and provide mathematical programming methods to find a minimal cost SEP and the ordering of expansion.     

Optimal expansion of subspaces for eigenvector approximations

We consider the problem of how to expand a given subspace for approximating an eigenvalue and eigenvector of a matrix A. Specifically, we consider which vector in the subspace, after multiplied by A, provides optimal expansion of the existing subspace for the eigenvalue problem. We determine the optimal vector, when the quality of subspace for approximation is measured by the angle between the subspace and the eigenvector. We have also derived some characterization of the angle that might lead to more practically useful choice of the expansion vector.     

An optimal capacity assignment for the robust design problem in capacitated flow networks

This paper proposes an exact algorithm to solve the robust design problem in a capacitated flow network in which each edge has several possible capacities. A capacitated flow network is popular in our daily life. For example, the computer network, the power transmission network, or even the supply chain network are capacitated flow networks. In practice, such network may suffer failure, partial failure or maintenance. Therefore, each edge in the network should be assigned sufficient capacity to keep the network functioning normally. The robust design problem (RDP) in a capacitated flow network is to search for the minimum capacity assignment of each edge such that the network still survived even under the edge’s failure. However, how to optimally assign the capacity to each edge is not an easy task. Although this kind of problem was known of NP-hard, this paper proposes an efficient exact algorithm to search for the optimal solutions for such a network and illustrates the efficiency of the proposed algorithm by numerical examples.     

Optimal control of single-server queueing networks

A general single-server queueing network model is considered. It is well-known that an optimal policy is determined by the largest-index policy. There is an index for each given queue and one allocates the server to a queue with largest current index. Using discounted dynamic programming we give a new and short proof of this result and derive some characterizations and bounds of the indices. Moreover, it is shown that an approximate largest-index policy yields an approximately optimal policy. These results lead to efficient methods for computing the indices. In particular, we present a general largest-remaining-index method.     

Optimal control of single-server fluid networks

We consider a stochastic single-server fluid network with both a discounted reward and a cost structure. It can be shown that the optimal policy is a priority index policy. The indices coincide with the optimal indices in a semi-Markovian Klimov problem. Several special cases like single-server reentrant fluid lines are considered. The approach we use is based on sample path arguments and Pontryagins maximum principle. This revised version was published online in June 2006 with corrections to the Cover Date.     

Optimal competence set expansion using deduction graphs

A competence set is a collection of skills used to solve a problem. Based on deduction graph concepts, this paper proposes a method of finding an optimal process so as to expand a decision maker's competence set to enable him to solve his problem confidently. Using the concept of minimum spanning tree, Yu and Zhang addressed the problem of the optimal expansion of competence sets. In contrast, the method proposed here enjoys the following advantages: it can deal with more general problems involving intermediate skills and compound skills; it can find the optimal solution by utilizing a 0–1 integer program; and it can be directly extended to treat multilevel competence set problems, and thus is more practically useful.This work was supported by the National Science Council, Taipei, Taiwan, Republic of China, Grant No. NSC-81-0301-H-009-501.     

Optimal network configuration and capacity expansion of railroads

Railroads ship individual cars according to blocking plans that route the cars in groups (blocks) that share common intermediate stops. An individual shipment is regrouped (reclassified) two to three times along the way from its origin to destination. Yards are crucial facilities of the rail network where cars are reclassified according to such blocking plans. Therefore, yard locations and the blocking plan impose the detour and classification of cars over the physical network. Yards are capacitated with respect to number of blocks made and number of cars classified; rail lines between major stations are capacitated with respect to number of cars that pass through. These restrictions are accounted for in designing the blocking plans. Changing the yard locations and expanding associated capacities may result in dramatic changes in blocking plans saving tens of millions of dollars in railroad transportation costs. We develop a mathematical programming formulation and propose solution methods for the yard location problem and the capacity expansion problems. We demonstrate that the railroads can save significantly by reconfiguring their networks.