The off-line group seat reservation problem

In this paper we address the problem of assigning seats in a train for a group of people traveling together. We consider two variants of the problem. One is a special case of two-dimensional knapsack where we consider the train as having fixed size and the objective is to maximize the utilization of the seats in the train. The second is a special case of two-dimensional bin packing where all requests must be accommodated while trying to minimize the number of passenger cars needed. For both variants of the problem we present a number of bounds and develop exact algorithms. Computational results are presented for various instances based on realistic data, and from the packing literature adapted to the problems addressed.     

A procurement model using capacity reservation

In this paper we model a scenario where a buyer reserves capacity from one or more suppliers in the presence of demand uncertainty. We explicitly derive suppliers’ capacity reservation price, which is a function of their capacity, amount of capacity reserved by the buyer and other parameters. The buyer operates in a “built-to-order” environment and needs to decide how much capacity to reserve and from how many suppliers. For a strategy of equal allocation of capacity among the selected suppliers we develop closed form solutions and show that the model is robust to the number of suppliers from whom capacity is procured through reservation. When the parameters of demand distribution changes the supply base is likely to remain more or less the same. Our analysis further shows that increasing the number of pre-qualified suppliers does not provide significant advantages to the buyer. On the other hand, a pre-qualified supply base with greater capacity heterogeneity will benefit the buyer.     

Optimal trunk reservation for an overloaded link

We consider a single overloaded link with a large number of circuits which is offered two kinds of calls. The traffic intensity of the primary calls is assumed to be strictly less than 1, and R of the circuits are reserved for these. Rewards are generated when calls are accepted, and it is assumed that the reward for primary calls is greater than that for secondary calls. We determine the trunk reservation parameter R which asymptotically maximizes the long run average reward.     

Economic lot sizing: The capacity reservation model

Capacity reservation contracts allow a consumer to purchase up to a certain capacity at a unit price lower than that of the spot market, while the consumer’s excess orders are realized at the spot price. In this paper, we consider a lot sizing problem where the consumer places orders following a capacity reservation contract. In particular, we study the general problem and the polynomial time solvable special cases of the problem and propose corresponding algorithms for them.     

A critically loaded multirate link with trunk reservation

We consider a loss system model of interest in telecommunications. There is a single service facility with N servers and no waiting room. There are K types of customers, with type ί customers requiring A _ί servers simultaneously. Arrival processes are Poisson and service times are exponential. An arriving type ί customer is accepted only if there are Rί(⩾A_ί ) idle servers. We examine the asymptotic behavior of the above system in the regime known as critical loading where both N and the offered load are large and almost equal. We also assume that R ₁,..., R _K-1 remain bounded, while R _K ^N ←∞ and R _K ^N /√N ← 0 as N ← ∞. Our main result is that the K dimensional “queue length” process converges, under the appropriate normalization, to a particular K dimensional diffusion. We show that a related system with preemption has the same limit process. For the associated optimization problem where accepted customers pay, we show that our trunk reservation policy is asymptotically optimal when the parameters satisfy a certain relation. This revised version was published online in June 2006 with corrections to the Cover Date.     

A hybrid model for airline seat inventory control of the multi-leg problems

To address the discrepancy between dynamic models and industrial practice in airline revenue management, we propose a hybrid model for the multi-leg problem that integrates static and dynamic models. We formulate the problem using a stochastic dynamic program and characterize the optimal booking policy as a switching-curve (surface) type.     

Speculative production and anticipative reservation of reactive capacity by a multi-product newsvendor

In this paper the optimal sourcing decisions of a multi-product newsvendor prior to the selling season of the products are studied. To satisfy the uncertain demands, the newsvendor can either utilize speculative production, or anticipatively reserve capacity. During the selling season when demand has become known, the newsvendor can utilize its reserved capacity and reactively satisfy demand uncovered by its speculative production. For the case where capacity for speculative production may be limited, but potential reservation of reactive capacity is unlimited two capacity reservation settings are analyzed and compared. In the first one capacity for each product has to be reserved separately, while in the second setting one joint capacity reservation for all products is permitted which can then be allocated to the different products optimally during the selling season. For the case of separate individual reservations the optimal strategies are analytically derived and structural insights concerning their existence are presented. As the model allowing for joint reservation can not be tackled analytically in general an approximation based on an LP formulation is used. Through a numerical example insights on the value of the increased flexibility induced by joint reservation, the cost-premium acceptable for joint reservation and the relative levels of capacity reservation in the two settings are given.     

A mathematical model for a capacity reservation contract

It is common practice in many industries to use a replenishment contract with a mechanism of capacity reservation. In this paper, we focus on a multi-period capacity reservation contract practiced between a buyer, who buys a single type of product and sells it to end-customers, and two or more heterogeneous suppliers, who produce and replenish the product as agreed upon contractually.In this paper, a mathematical model including several key features of a real contract is developed for a single supplier situation from the buyer’s perspective. It is then extended to a multiple supplier model for a system in which there are several heterogeneous suppliers with different capacities and prices. A rolling-horizon implementation strategy is suggested for the efficient application of the models. Extensive computational experiments demonstrate that the model and strategy can produce cost effective contractual terms for the buyer within a few seconds.     

A capacity reservation game for suppliers with multiple blocks of capacity

This paper studies a supplier competition model in which a buyer reserves capacity from a number of suppliers that each have multiple blocks of capacity (e.g., production or power plants). The suppliers each submit a bid that specifies a reservation price and an execution price for every block, and the buyer determines what blocks to reserve. This game involves both external competition between suppliers and internal competition between blocks from each supplier. We characterize the properties of pure-strategy Nash equilibria for the game. Such equilibria may not always exist, and we provide the conditions under which they do.     

Implementation strategies of a contract-based MRI examination reservation process for stroke patients

Timely imaging examinations are critical for stroke patients due to the potential life threat. We have proposed a contract-based Magnetic Resonance Imaging (MRI) reservation process [1] in order to reduce their waiting time for MRI examinations. Contracted time slots (CTS) are especially reserved for Neural Vascular Department (NVD) treating stroke patients. Patients either wait in a CTS queue for such time slots or are directed to Regular Time Slot (RTS) reservation. This strategy creates “unlucky” patients having to wait for lengthy RTS reservation. This paper proposes and analyzes other contract implementation strategies called RTS reservation strategies. These strategies reserve RTS for NVD but do not direct patients to regular reservations. Patients all wait in the same queue and are served by either CTS or RTS on a FIFO (First In First Out) basis. We prove that RTS reservation strategies are able to reduce the unused time slots and patient waiting time. Extensive numerical results are presented to show the benefits of RTS reservation and to compare various RTS reservation strategies.     

A travel demand management strategy: The downtown space reservation system

In this paper, a Travel Demand Management strategy known as the Downtown Space Reservation System (DSRS) is introduced. The purpose of this system is to facilitate the mitigation of traffic congestion in a cordon-based downtown area by requiring people who want to drive into this area to make reservations in advance. An integer programming formulation is provided to obtain the optimal mix of vehicles and trips that are characterized by a series of factors such as vehicle occupancy, departure time, and trip length with an objective of maximizing total system throughput and revenue. Based upon the optimal solution, an “intelligent” module is built using artificial neural networks that enables the transportation authority to make decisions in real time on whether to accept an incoming request. An example is provided that demonstrates that the solution of the “intelligent” module resembles the optimal solution with an acceptable error rate. Finally, implementation issues of the DSRS are addressed.     

Coordination mechanism for capacity reservation by considering production time,production rate and order quantity

In this paper we study the coordination of a dyadic supply chain producing a high-tech product by contracts. The product has a short life cycle and the buyer faces stochastic demands during the selling period. We consider the production time, which causes the inventory costs on supplier’s side. As the supplier builds production capacity in advance, the production rate is limited to the capacity created during the production time. In addition, we take into account the inventory cost and operational cost for the buyer. We examine the model under both full information and partial information updating situations, and propose a coordinating contract for each case. Our analysis includes the study of members’ decisions under both forced and voluntary compliance regimes. Numerical results are presented to provide more insights into the models developed and the mechanisms proposed.     

Dual sourcing using capacity reservation and spot market: Optimal procurement policy and heuristic parameter determination

This contribution focuses on the cost-effective management of the combined use of two procurement options: the short-term option is given by a spot market with random price, whereas the long-term alternative is characterized by a multi period capacity reservation contract with fixed purchase price and reservation level. A reservation cost, proportional with the reservation level, has to be paid for the option of receiving any amount per period up to the reservation level. A long-term decision has to be made regarding the reserved capacity level, and then it has to be decided – period by period – which quantities to procure from the two sources. Considering the multi-period problem with stochastic demand and spot price, the structure of the optimal combined purchasing policy is derived using stochastic dynamic programming. Exploiting these structural properties, an advanced heuristic is developed to determine the respective policy parameters. This heuristic is compared with two rolling-horizon approaches which use the one-period and two-period optimal solution. A comprehensive numerical study reveals that the approaches based on one-period and two-period solutions have considerable drawbacks, while the advanced heuristic performs very well compared to the optimal solution. Finally, by exploiting our numerical results we give some insights into the system’s behavior under problem parameter variations.     

Optimum inputs for state identification

The problem of choosing optimum inputs for identifying the state of a linear system with nonlinear observations is discussed. An optimum input is defined and characterized. A suboptimum input is introduced to facilitate the analysis and computation. Finally, a numerical example is given to illustrate the technique.     

A factorization method for the solution of constrained linear least squares problems allowing subsequent data changes

Summary In this paper we describe how to use Gram-Schmidt factorizations of Daniel et al. [1] to realize the method of [8] for solving linearly constrained linear least squares problems. The main advantage of using these factorizations is that it is relatively easy to take data changes into account, if necessary.The algorithm is compared numerically with two other codes, one of them published by Lawson and Hanson [3]. Further computational tests show the efficiency of the proposed methods, if a few data of the original problem are changed subsequently.This paper was sponsored by Deutsche Forschungsgemeinschaft, Bonn-Bad Godesberg