需求量变动引言物流配送过程经常受到某些不确(4)
2013-07-02 01:03
导读：模型的求解算法的选择本文构建的物流配送干扰管理模型，考虑了干扰管理过程对物流配送系统多方参与者的扰动因素，必须优化多个目标，求解过程很复
模型的求解算法的选择本文构建的物流配送干扰管理模型，考虑了干扰管理过程对物流配送系统多方参与者的扰动因素，必须优化多个目标，求解过程很复杂，采用精确算法无法获得解；而一些求解问题的传统启发式算法，如交换算法，插入算法等，由于其邻域函数单一，获得较好解的能力差；而在元启发式算法中，遗传算法与蚁群算法等一些相对高级的算法的编码过程复杂，算法设计需要很高的技巧，算法运行结果的好坏很大程度上依赖于编码者。鉴于上述这些问题，本文采用禁忌搜索算法（Tabu Search Algorithm）[20]对模型进行求解。禁忌搜索是对局部邻域搜索扩展后的一种全局逐步寻优算法，该算法的搜索速度快、效率高，适用于大规模的优化计算，随着VRP 复杂性的提高和问题领域的延伸，该算法近些年来备受研究者的青睐[21]。该算法的邻域结构可以融合多种插入、交换等邻域函数，加上算法本身的记忆功能，获得较好解的能力强，并且算法的设计技巧性不强，不依赖于编码者，实用性更强。
算法的设计本文设计算法求解多目标规划模型时，引入目标逐级优化的思想，即：算法完整迭代运行三轮，每轮的优化目标分别是式（4）定义的三个目标。第一轮迭代以优化P1 定义的目标为目标，当迭代结束后，得到P1 目标的最优值，设为S1，将该值作为约束条件加入到算法的第二轮迭代中，即，第二轮迭代时，可行解必须满足P1 目标的值不大于S1，设第二轮迭代结束得到P2 目标的最优值为S2，则第三轮迭代的可行解必须同时满足P1 目标的值不大于并且P2 目标的值不大于S2 两个约束。
禁忌搜索算法的主要模块和参数有：初始解、邻域结构、候选解集合、禁忌表、藐视准则、终止准则。下文结合模型重点讨论这几大模块与参数的设计。
（科教作文网http://zw.NSEaC.com编辑发布） （1）初始解该文研究的问题是干扰事件发生后对现有配送计划的调整，因此初始解即为干扰事件发生时刻的当前配送状态，设计算法时不需要初始解的产生模块，只需要设计读入当前配送计划的模块即可，因此初始解与该算法是相互独立的，这同时克服了禁忌搜索算法对初始解的依赖的缺陷。
（2）邻域结构设计邻域结构采用VRP 问题禁忌搜索算法中常用的两种邻域函数：λ -interchange 和2-opt，前者用于对点的操作，后者用于对边的操作，由约束条件(10)~(15)负责验证邻域解是否可行。
邻域函数的详细介绍可参考文献[22]，此处不再赘述。
（3）候选解集合候选解的集合是发挥禁忌搜索算法记忆功能的重要参数。候选解的评价依赖于模型的目标函数，按照评价值由小到大排序。邻域函数运行一次时，新解的评价值如果小于候选解集合中的评价值最大的解时，则用新解更新该候选解，并对候选解集合中的解重新排序。候选解的评价函数为式(6)、(7)和式(3)，分别对应于算法的第一到第三轮迭代。
（4）禁忌表设计禁忌表也是体现禁忌搜索算法记忆功能的参数之一，本文将客户在某条路线中的某个位置作为禁忌对象，记作：tabu(i, r, p)=l，即，当邻域函数运行时，将客户点i 从路线r 中的位置p 移出后，在规定的l 次搜索内，不允许邻域函数执行使该客户点返回该位置的操作，是禁忌表的长度。依据常用的固定禁忌长度的设定方法，考虑数据集合中总客户数m，本文将禁忌表的长度设定为：l=2 m。
（5）藐视准则藐视准则基于解的评价值来设定，即，如果某个解的评价值小于以往最优解的评价值，则此解不受禁忌表的限制，被设定为当前解。
（6）终止准则终止准则是当迭代达到预先给定的最大步数时，算法终止。三轮迭代的步数设定相同。
（科教范文网 fw.nseac.com编辑发布） 算例验证与结果分析由于干扰管理问题尚未有标准的测试数据集，因此，本文首先设计了一个车辆路径问题的算例，以配送成本最低为目标，通过遗传算法得到最优配送方案，之后将此方案作为物流配送系统需求量变动的干扰管理问题的背景，运用本文建立的模型和求解算法对该问题进行干扰管理，通过与传统全局重调度的结果对比，验证模型的有效性和可行性。
