基于量子粒子群算法求解供应链集成计划问题

李 敏 （上海理工大学 管理学院，上海 200093）

随着科学技术的发展，经济一体化趋势越来越明显，产品生命周期越来越短，对订单的响应速度越来越快，客户对产品和服务的交付时间和质量期望越来越高。企业无法凭借自身力量在激烈的竞争中取得优势，这使得他们不得不抛弃以前的单打独斗的竞争思想，开始考虑企业内部业务流程重组或者是与上下游企业之间的业务集成，与不同的企业为了共同的市场利益而结成战略联盟。

PSO（Particle Swarm Optimization）粒子群算法[1]是继遗传算法、蚁群算法等进化算法之后出现的一种新的智能优化算法，它具有控制参数少，编码简单、计算速度快、容易实现等特点。目前量子优化算法在求解经典组合优化问题上的应用较为广泛，如TSP问题[2-4]，0/1背包问题[5]，单目标和多目标流水车间调度问题[6]等。同时在解决现实生活中的各种问题，如路由问题[7]，投资组合优化[8]，图像分割[9]，易逝品多目标定价问题[10]等也表现出良好的性能。

1 模型描述

为了比较分散决策和集成决策之间的成本费用上的差异，将生产、采购集成模型分解成独立的多时间段的资源受限的生产计划决策模型和考虑价格折扣和运输成本的采购计划决策模型。

其中，每个时间段生产计划的批量决策问题只需要考虑计划周期内每个时间段外部需求和自身能力资源限制即可，见下公式 （1）。采购计划模型是在已求出的优化生产计划批量Qmt的前提下，考虑价格折扣和库存成本以及运输成本，在最小化这些成本的基础上来制定相应的原材料采购批量计划，见下公式 （9）。

1.1 模型建立。首先根据要求先定义模型中的变量，如表1所示。

表1 符号的定义

约束式 （2）和 （10）表示工厂产品和原材料采购、生产、需求及库存的动态平衡方程。约束式 （3）表示工厂生产的最大能力资源限制。约束式 （4）表示原材料的采购数量大于0时，即决定采购时，才存在相应的订货调整费用。约束式 （5）和（13）表示Xmt、Ymt是0或1的调整变量。约束式 （6）和 （7）表示原材料的生产数量、采购数量都是非负的。约束式 （8）和（16）表示产品和原材料在计划周期的开始时间段和结束时间段的库存水平是0。约束式 （11）表示当生产数量大于0时，即发生生产时，才存在相应的生产调整费用。约束式 （12）表示根据采购批量的不同，享受不同的价格折扣下的采购成本计算公式。约束式 （14）、 （15）表示产品的生产数量和库存水平都是非负的。

1.2 模型求解。基于量子粒子群算法求解生产、采购集成决策计划问题的具体流程如下：

（1）初始化量子粒子群算法的参数，包括确定种群的规模N，惯性权重w，加速系数c1和c2，初始速度v［N］，进化代数k。

（2）量子染色体的初始化，设置初始角度θ，一般设置为45°。

（3）随机观察产生求解问题的一个解，根据角度，产生Qk，Qk表示第k代粒子群量子比特对应的概率矩阵。Qk通过随机观察生成Pk，具体操作过程如下：随机产生一个［0,1 ］之间的随机数，若它大于Qk，则对应的Pk粒子的量子比特位取值为1，否则取值为0。

（4）计算每个粒子的适应值，根据生成的Pk产生n个粒子，并计算出该状态下各个粒子的适应值。

（5）量子进化

（6）循环迭代，直到满足终止条件。

1.3 仿真实验。仿真实验求解结果如表2所示，可以看出集成决策生产、采购计划能够有效降低供应链的总成本。最优解的迭代曲线如图1所示。

表2 集成决策和分散决策求解结果比较

2 小 结

本章构建了多周期、多产品、单工厂的生产和采购集成计划模型，将原材料的采购成本和运输成本考虑到优化的模型中去，以生产商为中心，统一制定采购计划和生产计划，并设计了用于求解该问题的量子粒子群算法方案。分别建立了分散决策下的生产计划模型和原材料采购计划模型，并对模型进行求解，得到独立计划时各个时间段生产批量和原材料的采购批量。仿真实验的结果表明：量子粒子群算法在求解供应链集成计划上的有效性，集成化决策比分散决策能够有效地降低供应链的总费用。

[1] Kennedy J,Eberhart RC.Particle a warm optimization[J].Proceedings of IEEE International Conference on Neural Networks,1995(17):1942-1948.

[2] 王宇平，李英华.求解TSP的量子遗传算法[J].计算机学报，2007,30(5):748-755.

[3] 武妍，包建军.一种新的求解TSP的混合量子进化算法[J].计算机应用，2006,26(10):2433-2436.

[4] 杨丽，李平，秦亚玲.改进的量子进化算法及其在TSP问题中的应用[J].信息与电子工程，2006,4(6):412-416.

[5] 钟艳花，余超凡.0/1背包问题的量子算法[J].计算机信息，2006,22(12-13):176,273-274.

[6] Wang L,Wu H,Tang F,et al.A hybrid quantum-inspired genetic algorithm for flow shop scheduling[J].Lecture Notes in Computer Science,2005(1):636-644.

[7] 秦洁，须文波.基于QPSO的QoS组播路由算法[J].计算机应用，2007,27(2):285-288.

[8] 须文波，江家宝，孙俊.基于QPSO算法的多阶段投资组合优化[J].计算机应用，2006,26(7):1682-1685.

[9] 龙海侠，须文波，孙俊.基于量子行为的微粒群优化算法的图像分割[J].计算机工程与应用，2006,28:54-55.

[10] 陆海燕，须文波.量子粒子群算法在易逝品多目标定价中的应用[J].计算机工程与应用，2007,43(19):237-239.