Dissertation/Thesis Abstract

Asymptotically optimal heuristics for network Revenue Management
by Jasin, Stefanus, Ph.D., Stanford University, 2011, 100; 3471011
Abstract (Summary)

We consider a network Revenue Management (RM) problem with multiple products and resources. Prices are assumed to be fixed. The objective is to design a dynamic resource allocation control in order to maximize expected revenue. As it is, the problem is computationally intractable and so the literature documents many attempts to develop near-optimal heuristics. Recently there has been some interests in studying the performance of heuristics constructed using the solutions of the so-called Deterministic Linear Program (DLP) formulation of the original RM problem. The appeal is obvious - an LP is easy to solve, and the formulation also lends itself to many intuitive interpretations. The drawback, however, is also obvious - the LP formulation only takes into account first-order information (i.e. expected value of future demand) and ignores the rest. A way to partly overcome this issue is by re-optimizing the control several times throughout the selling horizon. But how good is such approach?

We show that the benefit of re-optimization depends largely on the specific of heuristics being used. That is, different LP-based heuristics may have very different performance under frequent re-optimization. Our main result: there exists an LP-based heuristic that has O(1) expected loss under sufficiently frequent re-optimization. That is, the loss of this heuristic is independent of the size of the problem. We also extend the result to a more general case with customer choice.

Indexing (document details)
Advisor: Kumar, Sunil
Commitee:
School: Stanford University
School Location: United States -- California
Source: DAI-B 72/11, Dissertation Abstracts International
Source Type: DISSERTATION
Subjects: Operations research
Keywords: Resource allocation, Revenue management
Publication Number: 3471011
ISBN: 978-1-124-83094-0
Copyright © 2019 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy
ProQuest