A Randomized Linear Programming Method for Computing Network Bid Prices

Kalyan Talluri and Garrett van Ryzin
Additional contact information
Kalyan Talluri: Universitat Pompeu Fabra, Barcelona, Spain
Garrett van Ryzin: Columbia University, New York, New York

Transportation Science, 1999, vol. 33, issue 2, 207-216

Abstract: 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.

Date: 1999
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (63)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.33.2.207 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:33:y:1999:i:2:p:207-216

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().