基于改进遗传算法的库存与配送系统联合优化研究

邵伟杰

摘 要：库存与配送联合优化可以提高物流运作效率，有效降低成本，本文基于供应商管理库存构建了一个但供应商对多零售商配送模型，并结合C-W算法，对遗传算法进行改进运用于构建的模型求解，实例验证说明了改进算法对库存-配送问题求解的有效性。

关键词：库存配送系统；联合优化；遗传算法；C-W算法

一、库存与配送系统联合优化研究分类

1.联合优化思路。在库存与配送联合优化研究提出之前，大多学者都是单独对企业库存与配送进行研究的，比如考虑输入输出对动态库存进行研究，单独进行配送线路规划，动态库存管理研究中输入输出是已知的，没有考虑输入输出受企业采购过程中供应商配送的影响，而单独的运输线路规划问题则没有考虑库存内部动态管理，因此，对库存与配送系统联合优化研究很有必要，目前该类研究大致可以分为以下类型：

一类研究基于供应链整体成本，构建模型求得整体的订货量与配送策略。此类研究综合考虑了供应链各节点企业的三大成本“库存、采购与运输”，基于各方需求统一确定，互相了解需求，并且不允许缺货情况的发生，运输服务统一由第三方提供，构建的目标优化模型以生产商的生产成本、零售商的采购、库存成本，以及运输服务提供方的运输成本，以此求得最优解。但是该类研究没有考虑供应链参与各方的合作情况，各方对于利益的分配、成本的分摊机制没有考虑，容易造成分配不均而产生摩擦。

另外一类研究则是是由供应商主导库存配送，考虑一个供应商对多个零售商的库存-配送进行管理，构建模型对各独立零售商的库存进行管理，基于各地库存对时间、数量的需求，以自身成本最小为目标，进行路线规划，及时给零售商补货。供应商管理库存与前一类研究不同，两类研究均从总体成本最优角度出发，但是前一类研究没有厘清供应链中各企业角色，及相应的职责，此类研究确定了供应商管理库存，则明确了研究的类型，对于成本分配问题有了较好的解决。通过建立合理的数学算法可以对基于库存考虑的线路规划问题求得最优解，通过供应链各节点的协同配合促进运作效率，各方均获得最大收益，为实际供应链运作提供参考。

2.算法研究分类。库存-配送系统可以视为库存-路径问题的升级版，但是本质考虑的重点仍然是供应链各方库存保有量、采购量、采购周期，与运输路径选择之间的合理调节。对于库存-路径问题的算法研究较多，我们可以借鉴其相关算法应用于库存-配送系统研究。

（1）启发式算法。运用启发式算法对库存-路径问题进行求解的研究比较普遍，如蚁群算法、邻域搜索算法、禁忌搜索算法、模拟退火算法、遗传算法及人工神经网络等智能算法都或多或少有应用于库存-路径研究领域，其中遗传算法有较好的收敛性，能较快地达到全局最优解，并且有优胜劣汰的算法规则，最多地被运用或改进后运用于库存-路径求解。

（2）C-W节约算法。C-W算法是解决旅行商提出的，基于节约的理念，适用于物流单元间流量较为稳定，变化不大的问题，是一种较为简洁实用的算法。由供应商主导库存，为多个零售商供货可以解决信息不对称造成的库存过度配置，配送次数多配送量过大的情形，可以达到配送次数最少，配送量最经济（供应商、零售商采用最佳采购量）的效果，此时配送路线上配送较为稳定，配送变化不会太大，不会因为市场需求变动过大而引起配送问题，因为供应商对零售商的库存需求情况十分了解。因此C-W算法比较适合研究库存-路径问题，多数学者采用遗传算法或其他优化算法是都会结合C-W算法特点进行研究。

（3）其他算法。除运筹学领域优化算法、智能算法与C-W算法这几类典型的库存-路径求解算法之外，一些学者还采用概率论领域的马尔科夫决策过程研究随机需求下的库存-路径算法，也有学者采用分散决策算法（DDA decentralized decision algorithm）以求解分散决策情形下的库存与运输问题）。

二、库存与配送系统联合优化模型构建

库存与配送系统联合优化是促进供应链一体化的有效手段，本文基于供应商统一管理库存构建一个供应商对多个零售商配送的简单两级供应链模型。

1.模型假设。（1）各零售商需求确定，且均与供应商形成直接连接网络；（2）零售商不允许缺货，不考虑提前期；（3）运输费用与距离成正比；（4）一个运输车辆一天只做一次配送，在不超过运输车辆的满载负荷前提下可以为多个零售商配送；（5）多个零售商的不同货物可以拼车运货，这一点由供应商统一管理库存，统一配送可以比较好地解决。

2.符号表示。本文考虑的是由供应商管理库存，由单供应商与多个零售商构成的一对多的简单二级供应链，用数字序号下标表示供应商与零售商，i∈（0，1，2，...，N），0表示供应商，1至N表示零售商。货物由供应商负责配送，共有M辆运输车，每辆车的载重相等为Q，供应商的补货周期为T，eij表示供应商及各零售商之间的距离，di表示零售商的需求率，A0，Ai表示供应商与零售商的补货成本，h0与hi表示供应商与零售商的库存成本，C表示车辆的运输成本，在供应商的补货周期内，ni表示零售商的订货次数，ti表示零售商的订货周期，则T=niti，令Xijkt表示车辆k在时间t从点i开往j进行配送，是则值为1，否则为0，令Qjkr表示车辆k在时间r为点j配送的货物量。

3.数学模型。本文将采用遗传算法，较好地控制库存，并利用C-W算法来寻找车辆调度，路径选择方案，通过这些手段要达到一个统一的目的，那就是我们所要设定的目标函数，本文以成本最小为目标，更细化为单位时间的供应商库存、运输成本，零售商的库存成本，同时还需要获得供应商与零售的采购周期，配送路径方案作为输出，以（T，ti，ni，Xijkt）为决策变量构建如下目标函数：

（1）

其中大括号内为整个供应商补货周期配送系统总成本，

包括车辆运输成本，供应商库存成本，补货固定成本，零售商库存成本。

（2）

上式表示零售商不能缺货，是缺货限制条件，如果供应商配送与供应链中任何一个零售的需求之差小于零，则会造成缺货，缺货会带来缺货成本对供应商与零售商双方都有不利因素，因此制定此约束条件做缺货限制。

（3）

本条件是一个基础条件，运输车辆不能超负荷作业，任何两点之间单趟运输量都不能超过运输车辆的运输上限。

（4）

此项条件为避免回路，一个车辆对零售商进行配送后必须前往下一个零售商，即必须要有下一个不同的出口，或者配送完毕直接返回供应商点，而不能原路返回上一个零售商处。

（5）

此项约束条件规定一天内配送车辆数不能超过总车辆数。

以上为库存-配送系统数学模型，是库存管理与运输路径规划模型的结合，对此类问题的求解必须采用启发式算法，逐步求得最优解。

三、基于改进遗传算法的求解算法设计

从前述章节对库存-配送系统问题的求解算法介绍中我们可以了解到遗传算法具有较好的全局搜索能力，其优胜劣汰法则适用于库存控制，而C-W算法适用于路径求解，将两种方法结合，对遗传算法进行改造可以获得一个更优的求解算法。本文以单位时间总成本最小为目标，以零售商的采购周期的倍数对问题进行分区，提高求解速率，缩短运行时间。算法分为主算法、遗传函数、适应度函数与C-W算法三部分，循环嵌套，具体如下：

1.主算法。（1）令T'为供应商补货的最长期限，将T'平均分割成S个部分（S为T'的约数），那么整个补货周期可以分别表示为[1，T'/S]，[T'/S+1，2T'/S]，……，[（S-1）T'/S+1，T']。

（2）设定S+1个处理单元，对于处理单元i，对T∈[（I-1）T'/S+1，iT'/S]进行遍历搜索，调用遗传算法函数Gen（T）对目标函数进行求解，获得单位时间成本最小时供应商与零售商的采购周期，运输路径。

（3）输出最小成本值及供应商、零售商的采购周期，配送路径。

2.遗传算法Gen（T）函数。（1）首先需要选取初始化种群，取T的S个约数，随机选取其中约数作为染色体基因，由此生成长度n的染色体，多次操作获得初始种群规模为U，代数上限为G。

（2）求解种群中各染色体的适应度值，适应度值通过适应度函数f（·）求解。

（3）根据个体的适应度值进行排序，选择其中前h个个体。

（4）将被选择的个体以某一特定概率进行随机交叉操作，以获得新个体。

（5）再以一定概率对选中个体进行基因变异操作。

（6）重复以上操作，到达最大代数为止，输出结果。

3.遗传算法适应度函数。（1）令ghj表示第h代中的第j个个体，初始化mit=0，（i=1，...，N，t=0，...，T）。

（2）令配送量设为d，则d=lQ+qi，mit=l+1，l∈{0，1，...，M}。

（3）当mit>1时，先给零售商派送mit-1个车辆进行配送，满足需求中的车载Q 的整数部分，赋值X0ikl与Xi0kl均为1，令qt，h=qi，代数h增加1；若mit=1，qt，h=d。

（4）使用C-W算法cw（qth[]）计算Xijkt与Qikt，将两值代入目标函数ts，f（·）=1/ts。

4.C-W算法cw（q[]）

（1）令q[]表示需求点集，即零售商集合，分别将需求点集中点与供应商（以0表示）连接，令Sij=e0，q[i]+e0，q[j]-eq[i]，q[j]。

（2）将Sij进行降序排序，若Sij=0，则结束算法，将所有无回路路径连接至供应商点，对运输整数倍车辆负荷之外的车辆Xijkt进行赋值，输出路径。否则满足q[i]与q[j]都在同一路径或两分别在两条路径的头和尾则进入下一步。

（3）若在q[i]与q[j]之后的路径货运总量q小于车载Q则连接两点。

（4）初始化Sij=0，重复操作，直到输出所有路径。

四、算例

1.实例运行。令零售商个数为15，需求率分别为（17，5，7，5，5，7，3，

4，3，2，5，2，8，14，4），单次补货成本分别为（100000，50，…，50），第一项为供应商采购成本，后面为零售商成本，车载负荷为40，车辆单位行驶距离成本为90，供应商补货最大周期为80，需要遍历6组（有6个处理单元进行处理计算）。遗传算法初始种群规模50，最大代数5000，交叉与变异概率分别为0.8与0.2，距离矩阵在此不做列示，可以得到如下结果：

2.结果分析。对运行结果进行分析，可以看出：一方面，供应商与零售商的单位库存成本的上升必然导致总成本的上升，这是合乎常理的；另一方面，随着单位库存成本的上升，系统为了获得低成本降低了采购周期，包括供应商与零售商采购周期均缩短，增加采购次数，以保持较低库存水平，虽然运输成本和订货费用会有所增加，但会大大减少库存成本，可以将由库存成本增加带来的影响降低。因此，运用改进遗传算法计算获得的最优采购周期具有较强的实践意义，算法具有具备有效性。

五、结语

库存-配送系统问题的研究是物流领域的一个重点研究问题，对于物流成本的控制有重要作用。在此类问题求解中，一般采用启发式算法，存在一定的求解时间复杂度问题，当问题的求解复杂度增加时，启发式算法的求解时间复杂度将呈指数增长，因此借鉴部分学者对C-W算法的研究，本文融合C-W算法对遗传算法进行改进，使用改进的算法对库存-配送问题进行求解，求解精度较好，对实际应用有一定的参考价值。

参考文献：

[1]李仲兴， 朱向顺， 李锦飞.供应链中配送系统联合优化的数学模型及求解的混合算法[J]. 物流技术， 2005， （9）： 92-94.

[2]曾文飞， 颜玲， 雷军程.启发式库存-路径问题求解算法[J].计算机应用与软件， 2013， 30（7）：157-159.