管理论文物流配送路径优化问题的模型及改进混合算法.doc

《管理论文物流配送路径优化问题的模型及改进混合算法.doc》由会员分享，可在线阅读，更多相关《管理论文物流配送路径优化问题的模型及改进混合算法.doc（4页珍藏版）》请在三一办公上搜索。

1、物流配送路径优化问题的模型及改进混合算法 物流配送路径优化问题的模型及改进混合算法是小柯论文网通过网络搜集，并由本站工作人员整理后发布的，物流配送路径优化问题的模型及改进混合算法是篇质量较高的学术论文，供本站访问者学习和学术交流参考之用，不可用于其他商业目的，物流配送路径优化问题的模型及改进混合算法的论文版权归原作者所有，因网络整理，有些文章作者不详，敬请谅解，如需转摘，请注明出处小柯论文网，如果此论文无法满足您的论文要求，您可以申请本站帮您代写论文，以下是正文。 摘要：在建立带有时间窗的物流配送路径优化问题数学模型的基础上，构造了求解该问题的遗传模拟退火混合算法。该混合算法利用了遗传算法较强

2、的全局搜索能力和模拟退火算法较好的局部搜索能力，克服了两种算法各自在寻优方面的不足，使其在全局最优搜索和计算速度方面都有了很大的提高。最后经仿真试验证实了混合算法解决物流配送路径优化问题的优越性。关键词：物流配送；数学模型；遗传算法；模拟退火算法；时间窗中图分类号：F224文献标识码：A文章编号：1002-3100(2008)04-0026-05Abstract: The thesis constructs the mathematical model of optimizing distribution routing problem with time window, and design

3、s 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

4、 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 window0引言物流配送是指按用户的订货要求，在配送中心进行分货、配货，并将配好的货物及时、经济、有效地送给收货人。配送路径的选择是否合理对加快配送速度、提高服务质量、降低

5、配送成本有很大的影响。物流配送路径的优化问题是一个典型的NP完全问题，很难用全局搜索算法求出最优解，因此寻求一种有效的算法求出其接近最优解或满意解有重要的理论和实践意义。遗传算法（Genetic Algorithm，GA）和模拟退火算法（Simulated Annealing Algorithm，SA）在解决复杂优化问题时显示出良好的特性。GA有较强的全局搜索能力，但实际应用中容易出现早熟收敛（premature convergence）现象，且在进化后期搜索效率较低。SA具有很好的局部搜索能力，但对参数的依赖性较强。因此考虑到两种算法在实际应用中的特点，本文在对GA改进的基础上，采用与SA算

6、法相结合的混合算法，最后的仿真试验说明了混合算法解决物流配送优化问题的优越性。1物流配送路径优化问题的数学模型物流配送问题的描述：从配送中心将一定的货物用一定的货车向多个需求点运送，每个需求点的位置和需求量确定，安排合理的货车运输路径使运距最短（即表示目标函数运价最低），并且满足：（1）每条路线所运送货物总和不能超过货车载重量；（2）每辆货车都要在规定的时间内准时送达货物；（3）每辆货车从配送中心出发，在规定时间内最后返回配送中心。其中（1）是目标函数，方程（2）规定了路径数限制，（3）确保货车的出发地和返回地都是物流中心，（4）和（5）确保每个需求点只被一辆货车送货一次，（6）表示每条路线所

7、运送的货物总和不能超过货车载重量，（7）货车运输的时间约束，（8）（10）定义了车流路径的时间窗。2SA算法及其实现模拟退火算法是用于解决组合优化问题的，是基于物理中固态物质的退火过程与一般组合优化问题之间的相似性，通过设定初温和初态，伴随温度的不断下降，结合概率突跳特性在解空间中通过邻域函数进行随机搜索，最终得到全局最优。模拟退火算法可以分解为解空间、目标函数和初始解三部分。模拟退火算法实现步骤如下：（1）初始化：初始温度T，初始解状态S，每个T值的迭代次数为L；（2）对k=1,2,L，做第（3）至第6步；（3）对当前状态S随机扰动产生一个新解S；（4）计算增量t=CS-CS，其中CS为评价

8、函数；（5）若t0，则接受S作为新的当前解，否则以概率exp-tT接受S作为新的当前解；（6）如果满足终止条件则输出当前解作为最优解，结束程序。终止条件通常取为连续若干个新解都没有被接受时终止；（7）T逐渐减少，且T0，然后转到第（2）步。以上步骤称为Metropolis过程4，按照一定的退火方案逐步降低温度，重复Metropolis过程，就构成了SA优化算法。当系统温度足够低时，就认为达到了全局最优状态。SA在解决组合优化问题中取得很好的效果，能解决传统的优化方法难于解决的某些问题。3GA算法及其实现遗传算法是美国Michigan大学John Holland教授根据生物进化论和遗传学的思想提

9、出的一种全局启发式优化算法，它利用遗传算子（选择、交叉和变异）促进解集合类似生物种群在自然界中自然选择、优胜劣汰、不断进化，最终收敛于最优状态。遗传算法的实现步骤为：（1）对求解空间进行编码、初始化；（4）应用遗传算子产生新一代群体popi+1；（5）判断终止条件，不满足返回（3）。GA通过选择复制和遗传因子的作用，使优化群体不断进化，最终收敛于最优状态。选择复制适应度函数值大的个体有较大的复制概率，它能加快算法的收敛速度。交叉算子通过对两个父代进行基因交换而搜索出更优的个体。变异操使进化群体产生多样性，避免算法陷入局部最优。然而实践证明，遗传算法往往会表现出早熟现象、局部寻优能力较差等不足，

10、将遗传算法与其它算法相结合有助于弥补它的不足之处，并能够加快寻优速度。4GA和SA混合算法及其实现4.1算法分析遗传算法较适合于传统搜索方法所不能解决的复杂问题和非线性问题。然而，实际应用中遗传算法存在编码、迭代次数、种群规模的限制，造成种群多样性和选择性压力的调和冲突，即强选择性压力导致遗传搜索过早收敛，强种群多样性导致遗传搜索效率低下，遗传算法的改进应考虑到：（1）为了保证算法能全局收敛，必须保证种群的多样性；（2）为了加快算法的收敛，必须使种群中个体尽快向最优解聚集。理论上分析，GA和SA算法均属于基于概率分布机制的优化算法。将两种算法进行结合，有利于丰富优化过程中的搜索行为，增强全局和

11、局部意义下的搜索能力和效率。4.2算法步骤GA和SA混合算法的基本思想：从通过PFIH方法6产生的初始种群中开始全局最优解的搜索过程，先通过选择、交叉、变异等遗传操作来产生一组新的个体，然后再独立地对种群中的个体进行模拟退火过程，以其结果作为下一代种群中的个体。经过反复的迭代直到满足某个终止条件为止。算法实现的步骤如下：其他参考文献Baker, Sheridan. The Practical Stylist. 6th ed. New York: Harper & Row, 1985.Flesch, Rudolf. The Art of Plain Talk. New York: Harper

12、& Brothers, 1946.Gowers, Ernest. The Complete Plain Words. London: Penguin Books, 1987.Snell-Hornby, Mary. Translation Studies: An Integrated Approach. Amsterdam: John Benjamins, 1987.Hu, Zhuanglin. 胡壮麟, 语言学教程 M. 北京: 北京大学出版社, 2006.Jespersen, Otto. The Philosophy of Grammar. London: Routledge, 1951.L

13、eech, Geoffrey, and Jan Svartvik. A Communicative Grammar of English. London: Longman, 1974.Li, Qingxue, and Peng Jianwu. 李庆学、彭建武, 英汉翻译理论与技巧 M. 北京: 北京航空航天大学出版社, 2009.Lian, Shuneng. 连淑能, 英汉对比研究 M. 北京: 高等教育出版社, 1993.Ma, Huijuan, and Miao Ju. 马会娟、苗菊, 当代西方翻译理论选读 M. 北京: 外语教学与研究出版社, 2009.Newmark, Peter. A

14、pproaches to Translation. London: Pergmon P, 1981.Quirk, Randolph, et al. A Grammar of Contemporary English. London: Longman, 1973.Wang, Li. 王力, 中国语法理论 M. 济南: 山东教育出版社, 1984.Xu, Jianping. 许建平, 英汉互译实践与技巧 M. 北京: 清华大学出版社, 2003.Yan, Qigang. 严启刚, 英语翻译教程 M. 天津: 南开大学出版社, 2001.Zandvoort, R. W. A Handbook of English Grammar. London: Longmans, 1957.Zhong, Shukong. 钟述孔, 英汉翻译手册 M. 北京: 商务印书馆, 1983.Zhou, Zhipei. 周志培, 汉英对比与翻译中的转换 M. 上海: 华东理工大学出版社, 2003.