A Randomized Linear Programming Method for Computing Network Bid Prices

Talluri, Kalyan; Van Ryzin, Garrett
May 1999
Transportation Science;May99, Vol. 33 Issue 2, p207
Academic Journal
We analyze a randomized version of the deterministic linear programming (DLP) method for computing network bid prices. The method consists of simulating a sequence of realizations of itinerary demand and solving deterministic linear programs to allocate capacity to itineraries for each realization. The dual prices from this sequence are then averaged to form a bid price approximation. This randomized linear programming (RLP) method is only slightly more complicated to implement than the DLP method. We show that the RLP method can be viewed as a procedure for estimating the gradient of the expected perfect information (PI) network revenue. That is, the expected revenue obtained with full information on future demand realizations. The expected PI revenue can, in turn, be viewed as an approximation to the optimal value function. We establish conditions under which the RLP procedure provides an unbiased estimator of the gradient of the expected PI revenue. Computational tests are performed to evaluate the revenue performance of the RLP method compared to the DLP.


Related Articles

  • Computing Time-Dependent Bid Prices in Network Revenue Management Problems. Kunnumkal, Sumit; Topaloglu, Huseyin // Transportation Science;Feb2010, Vol. 44 Issue 1, p38 

    We propose a new method to compute bid prices in network revenue management problems. The novel aspect of our method is that it naturally provides dynamic bid prices that depend on how much time is left until departure. We show that our method provides an upper bound on the optimal total...

  • Dynamic Bid Prices in Revenue Management. Adelman, Daniel // Operations Research;Jul2007, Vol. 55 Issue 4, p647 

    We formally derive the standard deterministic linear program (LP) for bid-price control by making an affine functional approximation to the optimal dynamic programming value function. This affine functional approximation gives rise to a new LP that yields tighter bounds than the standard LP....

  • Simulated revenue impact of a new revenue management strategy under the assumption of realistic fare data. Weatherford, Larry // Journal of Revenue & Pricing Management;May2002, Vol. 1 Issue 1, p35 

    Most revenue management allocation models require inputs of the revenue value associated with the bookings expected in each price class. This paper examines the impacts of more realistic fare value assumptions on the revenue performance of a commonly used unit allocation optimisation model...

  • A Mathematical Programming Approach for the Solution of the Railway Yield Management Problem. Ciancimino, A.; Inzerillo, G.; Lucidi, S.; Palagi, L. // Transportation Science;May99, Vol. 33 Issue 2, p168 

    Railway passenger transportation plays a fundamental role in Europe, particularly in view of the growing number of trains offering valuable services such as high speed travel, high comfort, etc. Hence, it is advantageous to submit seat inventories to a Yield Management system to get the maximum...

  • A Randomized Linear Programming Method for Network Revenue Management with Product-Specific No-Shows. Kunnumkal, Sumit; Talluri, Kalyan; Topaloglu, Huseyin // Transportation Science;Feb2012, Vol. 46 Issue 1, p90 

    Revenue management practices often include overbooking capacity to account for customers who make reservations but do not show up. In this paper, we consider the network revenue management problem with no-shows and overbooking, where the show-up probabilities are specific to each product....

  • A Column Generation Algorithm for Choice-Based Network Revenue Management. Bront, Juan José Miranda; Méndez-Díaz, Isabel; Vulcano, Gustavo // Operations Research;May2009, Vol. 57 Issue 3, p769 

    During the past few years, there has been a trend to enrich traditional revenue management models built upon the independent demand paradigm by accounting for customer choice behavior. This extension involves both modeling and computational challenges. One way to describe choice behavior is to...

  • Coordinating the tourism supply chain using bid prices. Harewood, Stephen // Journal of Revenue & Pricing Management;Sep2008, Vol. 7 Issue 3, p266 

    A bid price control method for coordinating a decentralised tourism supply chain is presented in this paper. The method is applied to a supply chain channel involving a hotel and a retailer of tourism services. Information is shared between the hotel and the retailer by incorporating the...

  • Revenue management methods for the liner shipping industry. Zurheide, Sebastian; Fischer, Kathrin // Flexible Services & Manufacturing Journal;Sep2015, Vol. 27 Issue 2/3, p200 

    Due to changes in the industry which have led to opportunities for new market segmentations, revenue management (RM) methods have gained in importance for liner shipping companies in the recent past. Therefore, possible market segmentations of the liner shipping market and suitable RM methods...

  • Robust Controls for Network Revenue Management. Perakis, Georgia; Roels, Guillaume // Manufacturing & Service Operations Management;Winter2010, Vol. 12 Issue 1, p56 

    Revenue management models traditionally assume that future demand is unknown but can be described by a stochastic process or a probability distribution. Demand is, however, often difficult to characterize, especially in new or nonstationary markets. In this paper, we develop robust formulations...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics