Knowledge that Transforms

Two continuous time formulations of the dynamic traffic assignment problem are considered, one that corresponds to system optimization and the other to a version of user optimization on a single mode network using optimal control theory. Pontryagin's necessary conditions are analyzed and given economic interpretations that correspond to intuitive notions regarding dynamic system optimized and dynamic user optimized traffic flow patterns. Notably, we offer the first dynamic generalization of Beckmann's equivalent optimization problem for static user optimized traffic assignment in the form of an optimal control problem. The analysis further establishes that a constraint qualification and convexity requirements for the Hamiltonian, which together ensure that the necessary conditions are also sufficient, are satisfied under commonly encountered regularity conditions.

The Markov decision problem of locating a policy to maximize the long-run average reward subject to K long-run average cost constraints is considered. It is assumed that the state and action spaces are finite and the law of motion is unichain, that is, every pure policy gives rise to a Markov chain with one recurrent class. It is first proved that there exists an optimal stationary policy with a degree of randomization no greater than K; consequently, it is never necessary to randomize in more than K states. A linear program produces the optimal policy with limited randomization. For the special case of a single constraint, we also address the problem of finding optimal nonrandomized, but nonstationary, policies. We show that a round-robin type policy is optimal, and conjecture the same for a steering policy that depends on the entire past history of the process, but whose implementation requires essentially no more storage than that of a pure policy.

The application of booking limits on the number of seats available at different prices on the same flight allows airlines to increase revenues. Effective seat inventory control by an airline depends on forecasts of future bookings, the revenue values associated with each fare type, and an ability to make systematic tradeoffs between booking requests so as to maximize total flight revenues. This article describes the implementation of a computerized system for making these tradeoffs and setting booking limits on future flights at Western Airlines in early 1987. The Expected Marginal Seat Revenue (EMSR) decision model developed for this application takes account of the uncertainty associated with estimates of future demand as well as the nested structure of booking limits in airline reservations systems. The Automated Booking Limit System implemented at Western made use of the EMSR model to set and revise booking limits periodically prior to flight departure. Although the system did not take into account several important components of the seat inventory control problem, a revenue impact test on a sample of actual flights showed a significant revenue improvement over the judgmental methods used previously.