协同舱位配置模型分析

4.3.4　协同舱位配置模型分析

本章构建的MSSASC、MSSASCC、MSSASE、MSSAJF等协同舱位配置模型均属多目标整数规划模型MOILP。这几个模型涉及的变量、参数规模很大。对于这些大规模整型变量多目标优化问题，由于变量又主要为整型决策变量，且规模庞大，这给问题的求解带来了很大困难，且在多目标规划中，极少存在绝对最优解。这是因为在优化过程中，多个目标往往难以同时达到最优。因此，在决策优化过程中，我们应当避免最差的结果，寻找其Pareto最优解（有效解）或弱有效解^［33］。

在处理多目标规划问题时，常根据多目标问题实际通过评价函数映射转换成单目标问题，再用解单目标问题的方法求解。评价函数主要构建方法有理想点法、乘除法、线性加权和法等^［33］。近年来，作为进化算法的一个重要分支的遗传算法已经作为一种有效的多目标优化方法而被广泛应用。它的优点在于可较高效处理搜索空间、在单轮优化期间产生多个最优解或有效解^［32］，但操作复杂，计算量大，不太适合成千上万个变量的大规模规划问题。

本书处理大规模多目标整数规划以Zadeh^［128］线性加权和作为多目标优化问题的评价函数，多目标优化问题则可转化为单目标优化问题。该算法的主要优点是思想简单、可行以及时间复杂度低，且有利于决策人员找到他们所需的偏好解，对大规模问题便捷高效。已有定理证明^{［33，128］}，给多目标规划问题的目标函数赋予相应的权重w_i，只要其中各w_i＞0，则对应的单目标规划问题的最优解必然是原多目标规划问题的Pareto最优解。

对于多目标规划问题，人们通常可能不满足于求出其随意的一个Pareto最优解或弱有效解，而是设法求得一个决策者满意的Pareto最优解。此时给多目标所赋予的权重就显得重要。结合协同舱位配置模型实际，可根据层次分析法来赋予权重或者根据联营方的共享舱位量来决定权重。如图4－2所示。

图4－2　大规模多目标规划模型求解步骤

通过线性加权和处理后，得到单目标大规模整数规划的协同舱位配置模型，得到的这些纯整数规划模型在优化计算上也具有极高的复杂度^［32］，求解也比较困难^[1]。导致这些整数规划问题难于求解的原因是由于对问题变量的取值方式的限制，且规模过大。在此不加证明地给出有关纯整数规划复杂性的定理，具体定理证明，可参考相关文献^{［31，32］}。

Cook^［129］给出并证明了有一类问题具有下述性质：①这类问题中任何一个问题至今未找到多项式时间算法；②如果这类问题的一个问题存在有多项式时间算法，那么这类问题都有多项式时间的算法，这类问题中的每一个问题成为非确定多项式NP（nondeterministic polynomial）问题，这个问题的集合简记NPC。

邢文训和谢金星^［31］给出NPC定义。如果判定问题A满足A∈NP，且NP中的任何一个问题都可以在多项式时间内规约为A，则A称为NP完全。若NP中的任何一个问题都可以在多项式时间内规约为判定问题A，则称A为NP难。简记NP难问题的集合为NPH，于是显然有NPC≤NPH。NP完全和NP难问题的区别是NP难问题无须判断A是否属于NP。由此可推出：

定理4－1^{［31，32］}所有NP类问题都可以多项式规约到任一NP困难的问题。若问题为NP困难的，则除非P＝NP，问题不可能在多项式时间内求解。

整数规划问题是实际遇到的离散最优化问题最主要组成部分^［32］。现有的NP完全（困难）问题中有一大部分可直接表述为某一整数或组合最优化问题。根据著名的割平面算法，从理论上讲，整数规划的求解可转化为线性规划的求解。对于纯整数规划则更为复杂，其与0—1规划有以下关系：

定理4－2^{［31，32］}纯整数规划问题的任一例子可以在多项式时间内转化为某一0—1规划问题的例子。

由定理4－2，可以得出：

推论4－1^{［31，32］}纯整数规划问题有多项式时间算法当且仅当存在求解0—1规划问题的多项式时间算法。

但遗憾的是，对纯整数规划和0—1规划问题，很少可能有多项式时间算法。因为已有证明，以下结论定理和推论成立：

定理4－3^{［31，32］}0—1规划的判定问题是NP完全的。

推论4－2^{［31，32］}0—1规划问题、整数规划问题均是NP完全的。

基于上述结论和NP完全理论，要想给出求解整数规划问题精确而有效的方法，如多项式时间算法，几乎不可能。也正是如此，对于此类整数规划问题，需要采用完全不同于连续优化的方法来求解。所以各种启发式和近似算法是解决整数规划问题的主要方法。

相关近似算法主要有局部搜索法、贪婪算法等^{［31，32］}。局部搜索法先得到一个初始可行解，以此初始起点出发进行局部邻域搜索迭代，然后选取最好的结果。这就要求设置一个好的邻域十分关键，一个较大的邻域可能会提供更好的局部最优解，但需要更长的时间去搜索，所以存在大小邻域的权衡问题，有时可能往往凭经验和直觉来设计有效的局部搜索法，这在大规模变量优化问题上显然不够科学。贪婪算法的具体迭代格式对问题的具体性态依赖性很大，受数据规模的影响极大，适用于小规模问题，当随着数据集规模的增大计算时间迅速增加。

目前关于此类整数规划启发式方法，主要有基于数学规划的启发式方法。随着计算机技术发展，模拟退火算法、遗传算法等现代智能优化启发式算法也逐渐应用到各领域。模拟退火算法^［130］是一种现代启发式算法，实际上是局部搜索法的推广。它克服了局部搜索法局部最优的缺点，但它也同样面临解的表示和邻域结构设计的问题。另外，模拟退火算法过分依赖其冷却进度表参数的选取，通用性差。遗传算法是Holland教授20世纪70年代首先提出的，源于模拟达尔文的进化论遗传算法类似于自然进化，通过作用于染色体上的基因寻找好的染色体来寻求解问题^［131］。理论上，遗传算法可以收敛到全局最优解，但在实际应用中也存在着种群早熟、收敛速度较慢、可能收敛于局部最优解等问题。因此，编码方式、初始种群的产生、适应度函数的选取、遗传算子和遗传算法的参数值的选择对问题的最终结果影响十分关键^［132］。遗传算法从若干解出发，通过对其邻域的不断搜索和当前解的替换来改进解的质量，可以取得较好的解，但操作复杂，计算量大，还不太适合求解大规模问题^［31］。近年来，蚁群优化算法、粒子群优化算法等新的智能优化算法开始兴起，取得一定成果，但在大规模系统优化领域应用更为少见^［31］。

目前来说，解决整数规划的较成熟的启发式算法主要依赖于分支定界算法、割平面算法以及拉格朗日松弛算法等基于数学规划的启发式算法^{［31，32］}。其中分支定界算法和割平面算法应用最为广泛，并开发出了相应的商业优化软件。例如LINGO和CPLEX等商业软件，均已开发出了以分支定界方法来进行大规模整数规划的程序模块。本研究将采用LINGO11.0优化平台，自编程序，应用其分支定界算法，以基于共同派船的协同舱位配置模型为例，进行大规模实证算例研究。

本研究所构建的联营模式下的协同舱位配置模型为大规模多目标整数规划模型，属纯整数多目标规划问题。求解思路是首先将模型多目标规划转换为确定性单目标混合整数规划，仍属NP完全（难）复杂规划问题。通过分支定界启发式算法，应用LINGO平台，编制程序加以求解。本章下一小节，将以共同派船模式为例，进行实证算例分析。通过线性加权多目标共同派船模式整数优化模型，得到改进的基于共同派船的协同舱位配置模型（Modifⁱed Model of Synergy Slot Allocation with Joint Fleets，MMSSAJF），模型如下：