人工智能算法论文：基于客户选择的网络收益管理问题的列生成算法

人工智能算法论文：基于客户选择的网络收益管理问题的列生成算法

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

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

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

1  问题描述

考虑一个航线网络设计问题，假设有段航段，可以组合成条航线。航线的集合记为，各航段的初始运力记为，定义覆盖矩阵，当航线包含航段时，有，否则。该网络问题的状态设为各航段的剩余运力，记为。航线设计的有效时长被分为若干个阶段。假设每个时间段内最多只有一个顾客到达（设到达率为），且对某条航线的需求为一个单位。将顾客需求分为个组别，每个组别分别对应于一个需求集，且不同组别的需求集可以重叠。每个顾客属于组别的概率为，显然。

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

2  数学模型

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

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

3  问题求解

虽然上一节所建模型为一个线性规划，但是注意到当有条航线时，变量的数量为，这表明问题的规模随着航线数量的增加成指数级增长，容易使得问题的求解陷入维数灾，而列生成算法即是一个有效算法。 

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

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

    若子问题的最优值非正，则和为可行的对偶解，从而根据对偶理论，当前所得解即为原问题的最优解；否则将子问题所获得的解加入到主问题中，重新求解主问题。照此循环直至获得原问题的最优解。其中，由于松弛主问题规模可控，因此可以用单纯形法求解。

4、数据测试

为了验证算法的有效性，利用Liu[4]中一个含7个航段共22条航线的航空网络和随机生成的客流数据进行测试。测试结果如表1所示。针对不同的负荷因子取值，所求结果与Liu[6]中所给上界相比最大间隙仅为0.50%，同时求解时间有所减少。结果表明所设计的列生成算法能够在短时间内获得较高质量的解。

表1 测试结果

5、结论

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