龙源期刊网 http://www.qikan.com.cn
物流配送路径优化问题的模型及改进混合算法
作者：刘 勇 崔炳谋 王小东 来源：《物流科技》2008年第04期
摘要：在建立带有时间窗的物流配送路径优化问题数学模型的基础上，构造了求解该问题的遗传模拟退火混合算法。该混合算法利用了遗传算法较强的全局搜索能力和模拟退火算法较好的局部搜索能力，克服了两种算法各自在寻优方面的不足，使其在全局最优搜索和计算速度方面都有了很大的提高。最后经仿真试验证实了混合算法解决物流配送路径优化问题的优越性。
关键词：物流配送；数学模型；遗传算法；模拟退火算法；时间窗 中图分类号：F224文献标识码：A 文章编号：1002-3100(2008)04-0026-05
Abstract: The thesis constructs the mathematical model of optimizing distribution routing problem with time window, and designs the hybrid algorithm of Genetic and Simulated Annealing Algorithm. The hybrid algorithm, which overcomes the disadvantages of the two algorithms in global search, adopts the advantages of both algorithms to solve the combinatorial and optimizing problem. The hybrid algorithm improves the GB search and computation speed greatly. Finally, simulated test proves the superiority of the hybrid algorithm.
Key words: logistics distribution; mathematical model; genetic algorithm; simulated annealing algorithm; time window 0引言
物流配送是指按用户的订货要求，在配送中心进行分货、配货，并将配好的货物及时、经济、有效地送给收货人。配送路径的选择是否合理对加快配送速度、提高服务质量、降低配送成本有很大的影响。物流配送路径的优化问题是一个典型的NP完全问题，很难用全局搜索算
龙源期刊网 http://www.qikan.com.cn
法求出最优解，因此寻求一种有效的算法求出其接近最优解或满意解有重要的理论和实践意义。
遗传算法（Genetic Algorithm，GA）和模拟退火算法（Simulated Annealing Algorithm，SA）在解决复杂优化问题时显示出良好的特性。GA有较强的全局搜索能力，但实际应用中容易出现早熟收敛（premature convergence）现象，且在进化后期搜索效率较低。SA具有很好的局部搜索能力，但对参数的依赖性较强。因此考虑到两种算法在实际应用中的特点，本文在对GA改进的基础上，采用与SA算法相结合的混合算法，最后的仿真试验说明了混合算法解决物流配送优化问题的优越性。
1物流配送路径优化问题的数学模型
物流配送问题的描述：从配送中心将一定的货物用一定的货车向多个需求点运送，每个需求点的位置和需求量确定，安排合理的货车运输路径使运距最短（即表示目标函数运价最低），并且满足：（1）每条路线所运送货物总和不能超过货车载重量；（2）每辆货车都要在规定的时间内准时送达货物；（3）每辆货车从配送中心出发，在规定时间内最后返回配送中心。
其中（1）是目标函数，方程（2）规定了路径数，（3）确保货车的出发地和返回地都是物流中心，（4）和（5）确保每个需求点只被一辆货车送货一次，（6）表示每条路线所运送的货物总和不能超过货车载重量，（7）货车运输的时间约束，（8）—（10）定义了车流路径的时间窗。
2SA算法及其实现
模拟退火算法是用于解决组合优化问题的，是基于物理中固态物质的退火过程与一般组合优化问题之间的相似性，通过设定初温和初态，伴随温度的不断下降，结合概率突跳特性在解空间中通过邻域函数进行随机搜索，最终得到全局最优。模拟退火算法可以分解为解空间、目标函数和初始解三部分。模拟退火算法实现步骤如下：
（1）初始化：初始温度T，初始解状态S，每个T值的迭代次数为L；
龙源期刊网 http://www.qikan.com.cn
（2）对k=1,2,…L，做第（3）至第6步； （3）对当前状态S随机扰动产生一个新解S'； （4）计算增量Δt=CS'-CS，其中CS为评价函数； （5）若Δt
（6）如果满足终止条件则输出当前解作为最优解，结束程序。终止条件通常取为连续若干个新解都没有被接受时终止；
（7）T逐渐减少，且T→0，然后转到第（2）步。
以上步骤称为Metropolis过程[4]，按照一定的退火方案逐步降低温度，重复Metropolis过程，就构成了SA优化算法。当系统温度足够低时，就认为达到了全局最优状态。SA在解决组合优化问题中取得很好的效果，能解决传统的优化方法难于解决的某些问题。
3GA算法及其实现
遗传算法是美国Michigan大学John Holland教授根据生物进化论和遗传学的思想提出的一种全局启发式优化算法，它利用遗传算子（选择、交叉和变异）促进解集合类似生物种群在自然界中自然选择、优胜劣汰、不断进化，最终收敛于最优状态。遗传算法的实现步骤为： （1）对求解空间进行编码、初始化；
（4）应用遗传算子产生新一代群体popi+1； （5）判断终止条件，不满足返回（3）。
GA通过选择复制和遗传因子的作用，使优化群体不断进化，最终收敛于最优状态。选择复制适应度函数值大的个体有较大的复制概率，它能加快算法的收敛速度。交叉算子通过对两个父代进行基因交换而搜索出更优的个体。变异操使进化群体产生多样性，避免算法陷入局部最优。然而实践证明，遗传算法往往会表现出早熟现象、局部寻优能力较差等不足，将遗传算法与其它算法相结合有助于弥补它的不足之处，并能够加快寻优速度。
龙源期刊网 http://www.qikan.com.cn
4GA和SA混合算法及其实现
4.1算法分析
遗传算法较适合于传统搜索方法所不能解决的复杂问题和非线性问题。然而，实际应用中遗传算法存在编码、迭代次数、种群规模的，造成种群多样性和选择性压力的调和冲突，即强选择性压力导致遗传搜索过早收敛，强种群多样性导致遗传搜索效率低下，遗传算法的改进应考虑到：（1）为了保证算法能全局收敛，必须保证种群的多样性；（2）为了加快算法的收敛，必须使种群中个体尽快向最优解聚集。理论上分析，GA和SA算法均属于基于概率分布机制的优化算法。将两种算法进行结合，有利于丰富优化过程中的搜索行为，增强全局和局部意义下的搜索能力和效率。 4.2算法步骤
GA和SA混合算法的基本思想：从通过PFIH方法[6]产生的初始种群中开始全局最优解的搜索过程，先通过选择、交叉、变异等遗传操作来产生一组新的个体，然后再地对种群中的个体进行模拟退火过程，以其结果作为下一代种群中的个体。经过反复的迭代直到满足某个终止条件为止。算法实现的步骤如下：
Step8：判断S'是否小于S，如果是，令S=S'，p=0，否则p=p+1；
Step9：判断p是否大于或等于q，如果是，则以S作为最终解输出，并停止计算。否则返回第（3）步。 4.3算法描述 （1）染色体的编码
采用人工染色体字符串实体表示种群成员，解表示长度为N的定长整型字符串，N为网络中的需求点数，染色体中的一个数字表示一个需求点，染色体基因的顺序表示货车行使的路径和方向。例如含有8个需求点的配送网络其编码可以表示为47628531，表示的路径为：路径1，0→4→7→6→0；路径2，0→2→8→5→3→1→0，其中，路径k的最后一个需求点与路径k+1的第一个需求点相连。解码时将基因按顺序插入新的路径当中，一般认为路径数最小化即是费用最小化，即在约束条件下最大限度的利用每条路径货车的载重量。
龙源期刊网 http://www.qikan.com.cn
（2）初始种群的产生 （4）适应度函数 （5）选择算子 （6）交叉和变异算子
由于传统的单点或双点交叉操作只适用于无序的染色体基因序列或变长的染色体基因序列，而物流配送路径问题的染色体编码是定长有序的，且每条染色体中的整数基因只出现一次，为了避免经交叉操作后出现不合格后代（即染色体中出现重复的整数基因），本文采用PMX[7]（Permutation Crossover）交叉方法，即在染色体编码中随机选择两个交叉点，然后交换两点之间的染色体基因，例如：若父代基因序列为： Parent1 h k c e f d b l a i g j Parent2 a b c d e f g h I j k l 交叉后的后代基因序列为： Offspring1 i g c d e f b l a j k h Offspring2 l k c e f d g h I a b j
变异操作是交叉操作的重要补充，变异操作使父代种群产生随机的、无关联的性状，是维持种群多样性的重要手段。考虑到本算法编码的特点，本文采用INV[3]作为变异算子，这有利于算法的小范围迁移，并可以在染色体中引入小幅度变化，增加了种群的多样性。变异概率的选择是变异算子的关键，概率太大使算法收敛过快，陷入局部最优；而概率太小使算法收敛过慢，影响计算速度。本文采用一种独特的适应性变异概率计算方法，即：s =。
（7）新个体的复制策略及终止规则
根据本文的混合算法及以上参数设定编制了各个算法的计算机程序，GA算法求得的解分布较为均匀，而改进的遗传模拟退火算法在模拟中都找到了最优解，SA算法的运行时间较长，但求得的最优解强于GA算法最优解，而GA算法求得的解的变化幅度较小，各种算法性能比较如表3所示。说明SA算法在局部搜索的能力较GA算法强，而GA算法全局搜索能力较SA算法强。改进的遗传模拟退火算法保持了很高的性能，获得了明显优于其它两种方法的解，算法求得的最优路径如表4所示，说明混合算法较快的收敛并得到比较满意的解。
龙源期刊网 http://www.qikan.com.cn
6结束语
算法中，当货车数过小时，找不到可行解，当货车数过大时，得到的方案不经济，通过适当的调整货车数使方案达到满意的结果。混合算法结合了遗传算法和模拟退火算法各自优点，即利用了GA的全局搜索能力和SA的局部搜索能力，使混合算法在全局寻优和计算效率方面都有了很大的提高。经试验证明，混合算法在解决带有时间窗的物流配送路径优化问题上保持了良好的性能，当需求点较少时得到了最优解，当需求点较多时得到了满意解。
参考文献：
[1] 郎茂祥. 基于遗传算法的物流配送路径优化问题的研究[J]. 中国公路学报，2002(3):76-79.
[2] 赵瑛琪. 一种求解车辆路径问题的双目标遗传算法[J]. 湖南工程学院学报，2006,16(2):49-51.
[3] 刘怀春，刘怀亮，李秀焕,等. 改进的遗传模拟退火算法及其在组合优化中的应用研究[J]. 现代计算机，2004(1):14-16,41.
[4] 王素云，李军. 基于遗传算法的物流配送车辆优化调度[J]. 商场现代化，2006(28):119-120.
[5]K. C. Tan, L. H. Lee, Q. L. Zhu, K. Qu. Heuristic Methods for Vehicle Routing Problem with Time Window[J]. Artificial Intelligence in Engineering, 2000(12):15.
[6]Solomon MM. Algorithms for Vehicle Routing and Scheduling Problem with Time Window constraints[J]. Oper Res, 1987,35(2):54-66.
[7]Oliver IM, Smith DJ, Holland JRC. A study of permutation crossover operations on the traveling salesman problem[C] // In: Proceedings of the fourth International Conference on Genetic Algorithm, 1991.
注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。
