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

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

　　郭宇1，茹海鹏2

　　（1.沈阳理工大学 理学院，辽宁 沈阳 1110168；2.沈鼓集团， 辽宁 沈阳 1110012）

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

　　关 键 词： 选择行为；收益管理；列生成；整数规划

　　中图分类号：TP301.6 文献标志码：A

　　收益管理问题即是在一个有限的时间区间内，根据当前具备的运能（或产能）以及客户对其的需求对其进行分配，以使得收益最大化。收益管理问题普遍存在于很多服务运输行业，比如航线设计、铁路运输以及旅馆业等[1-3]。本文将以航线设计为背景对该问题进行研究。

　　1  问题描述

　　考虑一个航线网络设计问题，假设有 段航段，可以组合成 条航线。如图1所示，共有6段航段，组成了2条航线（分别用实线和虚线表示）。航线的集合记为 ，各航段的初始运力记为 ，定义覆盖矩阵 ，当航线 包含航段 时，有 ，否则 。从而 的第 列（记为 ）即表示航线 所行经的航段集合，而 的第 行（记为 ）则表示航段 上所走过的航线集合。该网络问题的状态设为各航段的剩余运力，记为 。航线设计的有效时长 被分为若干个阶段，以 标记。假设每个时间段内最多只有一个顾客到达（设到达率为 ），且对某条航线的需求为一个单位。将顾客需求分为 个组别，每个组别分别对应于一个需求集 ，且不同组别的需求集可以重叠。每个顾客属于组别 的概率为 ，显然 。

　　图1 航段、航线示意图

　　航空公司需要确定在每个时间段内所提供的航线集合（记为 ），称之为供应集。对于一个给定的供应集 ，乘客选择航线 的概率为 ，则乘客不选择任何航线的概率为 。组别 的乘客对其选择集 中的不同航线有一个偏好权重，用偏好向量 表示，则有 ，其中 表示组别 的乘客选择航线 的概率。

　　2  数学模型

　　根据上一节对问题的描述以及对参数符号的定义和说明，将以航线设计为背景的网络收益管理问题建立数学模型如下：

　　其中 为决策变量，表示供应集 的有效时长。目标函数（1）表示如何确定 可以获得最高的期望收益；约束（2）表示所提供的航线方案需要满足各航段的最大运力；约束（3）表示所有供应集的有效时长总和不能超过总时长；约束（4）表示各有效时长的非负约束。

　　3  问题求解

　　虽然上一节所建模型为一个线性规划，但是注意到当有 条航线时，变量的数量为 ，这表明问题的规模随着航线数量的增加成指数级增长，如果直接采用单纯性算法容易使得问题的求解陷入维数灾，而列生成算法即是求解大规模线性规划的一个有效算法[4]。由于在线性规划中，最优解中基变量的个数不可能超过约束数，对于大量的非基变量所对应的的列，没有必要求解和保存。列生成算法的出发点就是基于这样一个事实。将原问题记为MP，而从MP包含的列集中选出部分列构成子集，即可得到一个限制主问题，记为RMP。列生成的基本思想是，首先采用启发式构成一个RMP，根据单纯形算法求得RMP的最优解及其对偶最优解 （称为“影子价格”）；再计算检验数 ，对于最小化问题，如果能证明对所有列的检验数都有 ，则由线性规划的对偶理论可知已经获得原问题的最优解，算法终止；而如果存在 的列，则通过求解子问题（SP）找出 的列，并将其加入RMP，对RMP重新使用单纯形算法求解。上述过程循环进行直至满足终止条件，即所有 。

　　3.1 列生成算法求解航线设计问题

　　设给定一个初始的子集 ，可得原问题的松弛主问题如下：

　　又设 分别表示约束（6）、（7）的对偶变量（即影子价格），则原问题的列生成算法子问题即为：

　　若子问题的最优值非正，则 和 为可行的对偶解，从而根据对偶理论，当前所得解即为原问题的最优解；否则将子问题所获得的解 加入到主问题中，重新求解主问题。照此循环直至获得原问题的最优解。

　　其中，由于松弛主问题规模可控，因此可以用单纯形法求解。而由于该子问题是NP-难的[5]，无法在多项式时间内最优求解，因此本文设计了一个能够快速求解子问题的贪婪启发式算法。

　　3.2 求解子问题的贪婪启发式

　　该启发式的总体思想是从空的供应集 开始，根据最大边际效益逐渐向其中加入航线。

　　首先需将子问题（9）改写成另外一个等价形式。为此引入0-1变量 ，若当前供应集 中包含航线 ，则 ；否则 。用0-1变量 替换集合变量 ，可将子问题（9）等价地改写为下列形式：

　　（10）

　　贪婪启发式如下：

　　（i）计算所有航线 对应的 ，若 ，则令 ；

　　（ii）令 表示还未赋值的 所对应的航线的集合；

　　（iii）计算 。并令 ， ；

　　（iv）计算 ，若 ，则将 加入到 中，同时从 移除。重复此步骤，直至 不再被修正；

　　（v）若 ，则令 ；否则，令 。

　　四、数据测试

　　为了验证算法的有效性，利用Liu[6]中一个含7个航段共22条航线的航空网络和随机生成的客流数据进行测试。各航段的初始运力如表1所示，客流组别的相关参数以及航线的参数分别如表2和表3所示。

　　测试结果如表4所示。针对不同的负荷因子取值，所求结果与Liu[6]中所给上界相比最大间隙仅为0.50%，同时求解时间有所减少。结果表明所设计的列生成算法能够在短时间内获得较高质量的解。

　　表1 航段初始运力

　　表2 客流组别相关参数

　　表3 航线相关参数

　　表4 测试结果

　　五、结论

　　本文考虑了一个以航线设计为背景的网络收益管理问题，由于问题规模随着航线数量的增加成指数级增长，是一个大规模的线性规划问题，为此采用列生成算法进行求解，同时针对其子问题是NP-难的，设计了一个贪婪启发式算法进行求解。利用随机生成数据的实验结果表明本模型及列生成算法的逻辑正确性，也验证了本模型的列生成算法可以求解大规模的航线设计优化问题，可以在短时间内获得令人满意的高质量的解。

　　参考文献：

　　[1] Talluri K, Van Ryzin G. The theory and practice of revenue management [J]. Operations Research Letters, 2005, 33(2):312-318.

　　[2] Daniel Adelman. Dynamic bid price in revenue management [J]. Operations Research, 2007, 55(4):647-661.

　　[3] Talluri K. Revenue management under a general discrete choice model of consumer behavior [J]. Management Science, 2004, 50(2): 15-33.

　　[4] Palmgren M. A column generation algorithm for the log truck scheduling [J]. European Journal of Operational Research, 2004, 101(2): 220-228.

　　[5] Gustavo Vulcano. A column generation algorithm for network revenue management [J]. Theory and applications to travel demand, 2007, 36(5):35-54.

　　[6] Zhang D. Revenue management for parallel flights with customer-choice behavior [J]. Operations Research, 2005, 53(5):514-531.