Navegar

Colección

Datos Estadísticas

Artículo

Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

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 assume that each customer belongs to a segment, which is characterized by a consideration set, i.e., a subset of the products provided by the firm that a customer views as options. Customers choose a particular product according to a multinomial-logit criterion, a model widely used in the marketing literature. In this paper, we consider the choice-based, deterministic, linear programming model (CDLP) of Gallego et al. (2004) [Gallego, G., G. Iyengar, R. Phillips, A. Dubey. 2004. Managing flexible products on a network. Technical Report CORC TR-2004-01, Department of Industrial Engineering and Operations Research, Columbia University, New York], and the follow-up dynamic programming decomposition heuristic of van Ryzin and Liu (2008) [van Ryzin, G. J., Q. Liu. 2008. On the choice-based linear programming model for network revenue management. Manufacturing Service Oper. Management 10(2) 288-310]. We focus on the more general version of these models, where customers belong to overlapping segments. To solve the CDLP for real-size networks, we need to develop a column generation algorithm. We prove that the associated column generation subproblem is indeed NP-hard and propose a simple, greedy heuristic to overcome the complexity of an exact algorithm. Our computational results show that the heuristic is quite effective and that the overall approach leads to high-quality, practical solutions. ©2009 INFORMS.

Registro:

Documento: Artículo
Título:A column generation algorithm for choice-based network revenue management
Autor:Bront, J.J.M.; Méndez-Díaz, I.; Vulcano, G.
Filiación:Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires, Argentina
Department of Information, Operations and Management Sciences, Stern School of Business, New York University, New York, NY 10012, United States
Palabras clave:Analysis of algorithms: computational complexity; Linear applications; Marketing: choice models; Programming: fractional; Analysis of algorithms: computational complexity; Columbia University; Column generation; Computational challenges; Computational results; Customer choice; Exact algorithms; Flexible products; General version; Greedy heuristics; High quality; Linear applications; Linear programming models; Manufacturing service; Multinomials; New York; NP-hard; Phillips; Practical solutions; Programming: fractional; Real-size networks; Revenue management; Algorithms; Computational complexity; Customer satisfaction; Dynamic programming; Heuristic algorithms; Heuristic methods; Linearization; Management; Sales; Systems engineering; Wireless telecommunication systems; Network management
Año:2009
Volumen:57
Número:3
Página de inicio:769
Página de fin:784
DOI: http://dx.doi.org/10.1287/opre.1080.0567
Título revista:Operations Research
Título revista abreviado:Oper Res
ISSN:0030364X
CODEN:OPREA
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0030364X_v57_n3_p769_Bront

Referencias:

  • Algers, S., Besser, M., Modeling choice of flight and booking class: A study using stated preference and revealed preference data (2001) Internat. J. Services Tech. Management, 2, pp. 28-45
  • Andersson, E.S., Passenger choice analysis for seat capacity control: A pilot project in scandinavian airlines (1998) Internat. Trans. Oper Res., 5, pp. 471-486
  • Belobaba, P.P., Hopperstad, C., Boeing/MIT simulation study: PODS results update (1999) Proc. 1999 AGIFORS Reservations and Yield Management Study Group Sympos, , London
  • Boyd, E.A., Kallesen, R., The science of revenue management when passengers purchase the lowest available fare (2004) J. Revenue Pricing Management, 3, pp. 171-177
  • Cardell, N., Dunbar, F., Measuring the societal impacts of automobile downsizing (1980) Transportation Res. Ae, 14, pp. 423-434
  • Chen, K., Hausman, W., Technical note: Mathematical properties of the optimal product line selection problem using choice-based conjoint analysis (2000) Management Sci., 46, pp. 327-332
  • Dobson, G., Kalish, S., Positioning and pricing of a product line: Formulation and heuristics (1988) Marketing Sci., 7, pp. 107-125
  • Gallego, G., Iyengar, G., Phillips, R., Dubey, A., Managing flexible products on a network (2004) Technical Report CORC TR-2004-01, , Department of Industrial Engineering and Operations Research, Columbia University, New York
  • Garey, M.R., Johnson, D.S., (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness, , W. H. Freeman and Company, San Francisco
  • Green, P., Krieger, A., Models and heuristics for product line selection (1985) Marketing Sci., 4, pp. 1-19
  • Hammer, P., Rudeanu, S., (1968) Boolean Methods in Operations Research and Related Areas, , Springer, Berlin
  • Hansen, P., Poggi De Aragão, M., Carneiro Ribeiro, C., Hyperbolic 0-1 programming and query optimization in information retrieval (1991) Math. Programming, 52, pp. 256-263
  • Hanson, W., Martin, K., Optimizing multinomial logit profit functions (1996) Management Sci., 42, pp. 992-1003
  • Kohli, R., Krishnamurti, R., A heuristic approach to product design (1987) Management Sci., 33, pp. 1123-1133
  • Kök, G., Fisher, M., Vaidyanathan, R., Assortment planning: Review of literature and industry practice (2008) Retail Supply Chain Management, , N. Agrawal, S. A. Smith, Eds. Springer
  • McBride, R., Zufryden, F., An integer programming approach to optimal product-line selection (1988) Marketing Sci., 7, pp. 126-140
  • McFadden, D., Train, K., Mixed MNL models for discrete response (2000) J. Appl. Econometrics, 15, pp. 447-470
  • Prokopyev, O., Huang, H., Pardalos, P., On complexity of unconstrained hyperbolic 0-1 programming problems (2005) Oper. Res. Lett., 33, pp. 312-318
  • Prokopyev, O., Meneses, C., Oliveira, C., Pardalos, P., On multiple-ratio hyperbolic 0-1 programming problems (2005) Pacific J. Optim., 1 (2), pp. 327-345
  • Ratliff, R., Multi-flight demand untruncation with recapture (2006) 2006 AGIFORS Revenue Management and Cargo Study Group Conf., , Cancún, Mexico
  • Talluri, K.T., Van Ryzin, G.J., (2004) The Theory and Practice of Revenue Management, , Kluwer Academic Publishers, New York
  • Talluri, K.T., Van Ryzin, G.J., Revenue management under a general discrete choice model of consumer behavior (2004) Management Sci., 50, pp. 15-33
  • Train, K., Discrete choice methods with simulation (2003) Cambridge University Press, , New York
  • Van Ryzin, J.G., Models of demand (2005) J. Revenue Pricing Management, 4, pp. 204-210
  • Van Ryzin, G.J., Liu, Q., On the choice-based linear programming model for network revenue management (2008) Manufacturing Service Oper. Management, 10 (2), pp. 288-310
  • Van Ryzin, G.J., Vulcano, G., Computing virtual nesting controls for network revenue management under customer choice behavior (2008) Manufacturing Service Oper. Management, 10 (3), pp. 448-467
  • Vulcano, G., Van Ryzin, G., Chaar, W., (2008) Choice-based Revenue Management: An Empirical Study of Estimation and Optimization, , Working Paper, New York University
  • Williamson, E., (1992) Airline Network Seat Inventory Control: Methodologies and Revenue Impacts, , Ph.D. Thesis, Flight Transportation Laboratory, Massachusetts Institute of Technology, Cambridge, MA
  • Wu, T., A note on a global approach for general 0-1 fractional programming (1997) Eur. J. Oper. Res., 101, pp. 220-223
  • Zhang, D., Adelman, D., (2006) An Approximate Dynamic Programming Approach to Network Revenue Management with Customer Choice, , Working Paper, Graduate School of Business, University of Chicago, Chicago
  • Zhang, D., Cooper, W.L., Revenue management for parallel flights with customer-choice behavior (2005) Oper. Res., 53, pp. 415-431

Citas:

---------- APA ----------
Bront, J.J.M., Méndez-Díaz, I. & Vulcano, G. (2009) . A column generation algorithm for choice-based network revenue management. Operations Research, 57(3), 769-784.
http://dx.doi.org/10.1287/opre.1080.0567
---------- CHICAGO ----------
Bront, J.J.M., Méndez-Díaz, I., Vulcano, G. "A column generation algorithm for choice-based network revenue management" . Operations Research 57, no. 3 (2009) : 769-784.
http://dx.doi.org/10.1287/opre.1080.0567
---------- MLA ----------
Bront, J.J.M., Méndez-Díaz, I., Vulcano, G. "A column generation algorithm for choice-based network revenue management" . Operations Research, vol. 57, no. 3, 2009, pp. 769-784.
http://dx.doi.org/10.1287/opre.1080.0567
---------- VANCOUVER ----------
Bront, J.J.M., Méndez-Díaz, I., Vulcano, G. A column generation algorithm for choice-based network revenue management. Oper Res. 2009;57(3):769-784.
http://dx.doi.org/10.1287/opre.1080.0567