基于客户选择的网络收益管理问题的列生成算法

摘要

本文考虑了一种基于客户选择的确定性的网络收益管理问题,它区别于传统的基于独立需求的收益管理问题.假设每位到达的顾客归属于某一个组别,而每个组别对应于一个选择集.同时假设顾客选定某一产品的概率服从多元选择回归分布.针对问题求解时会遇到的维数灾问题,设计了一种列生成算法,将原问题分解为一个松弛主问题和一个价格子问题,由于价格子问题是一个NP完全问题,进而设计了一个易于实现的贪婪启发式算法求解子问题.实验结果表明本文所设计的列生成算法以及贪婪启发式算法对于求解大规模的网络收益管理问题是十分有效的,可以获得高质量的解.