物流车队调度优化算法的研究与应用

遗传算法在物流系统优化中的应用研究

【摘要】：物流已被认为是继降低原材料消耗和提高劳动生产率之后的“第三利润源”。通过优化物流系统,可以降低物流成本,从而增强企业的市场竞争能力。因此,研究物流系统中的优化问题,具有十分重要的意义,是国内外研究的一个热点。库存成本与配送成本是物流系统的核心成本,在物流总成本中占据了很大的比例。如果能降低库存成本与配送成本,就能有效地降低物流成本。遗传算法是一种应用很广泛的智能优化算法,本文对遗传算法进行了分析研究,针对遗传算法的一些缺陷提出了相应的改进方法。在上述研究基础上,本文基于遗传算法,研究了物流系统中的库存优化问题及车辆路径问题。本文将库存仿真优化问题与车辆路径问题都看作是组合优化问题,并应用遗传算法进行求解。本文的主要研究工作及贡献可归纳如下:(1)对随机库存系统建立了基于离散事件系统的计算机仿真模型。用系统仿真方法求解最优库存策略时,其难点之一在于仿真的优化。为此,本文将计算机仿真技术和遗传算法相结合,应用遗传算法来优化模型的控制参数,即获得最优的库存控制策略。针对随机系统的特点,设计了候选解收集器,它能够收集在仿真优化过程中产生的Pareto解;提出了M精英选择算子,用于保护潜在的最优个体,使它们在交叉、变异算子中不被破坏。针对两种常用的库存控制策略进行了仿真优化的实验,结果表明本文提出的仿真优化方法是有效的。(2)旅行商问题(TSP)是车辆路径问题的子问题。为了求解TSP问题,研究了常用于TSP问题的三种交

叉算子的优化效果,提出了一种求解TSP问题的高效混合遗传算法HGA-TSP。在该算法中以变形的OX算子作为交叉算子,以2-opt算法作为遗传算法的变异算子;提出了K近邻点集的概念以缩减搜索空间并提高算法的时间效率。(3)将单配送中心,多辆运输车且无约束的车辆路径问题建模成具有总路径长度最短、子路径长度均衡性好这两个目标的双目标多旅行商问题(MTSP),并基于HGA-TSP算法,研究了三种求解上述问题的解决方案。(4)对于带能力约束的车辆路径问题(CVRP),提出了一种新的双层染色体编码方案和一种子路径交换算法。双层染色体编码方案不需要预先知道最优解所需要的车辆数,并能确保染色体不违反能力约束,这更适合求解实际物流配送系统中的车辆路径问题。此外,相对于常用的单层染色体编码方案,该编码方案还能降低搜索空间的大小,从而提高搜索效率并降低计算时间。子路径交换算法可以有效提高遗传算法的求解精度。基于上述双层染色体编码方案和子路径交换算法,设计了两种求解CVRP问题的混合遗传算法,分别是HGA-CVRP算法和HGA-SE-CVRP算法。(5)对于带时间窗约束的车辆路径问题(VRPTW,首先改进了双层染色体编码方案,以便在编程实现时更方便地进行子路径的处理。然后研究了遗传算法与邻域搜索算法的结合方式,在遗传算法中引入了带克隆操作的邻域搜索算子。最后提出了一种求解VRPTW问题的新型混合遗传算法HGA-VRPTW。(6)综合应用了面向对象分析与设计、多线程、UML等先进的软件开发方法与技术,设计并开发了VRP仿真实验室,这是一个用于研究车辆路径问题的软件包,具有使用简便、界面美观的特

物流科技２００８年第１１期　Ｌｏｇｉｓｔｉｃｓ　Ｓｅｉ—Ｔｅｃｈ　Ｎｏ．１　１，２００８　

。仓储运输・　

Ａｐｐｌｉｃａｔｉｏｎ　ｏｆ　Ｉｍｍｕｎｅ　Ａｌｇｏｒｉｔｈｍ　ｉｎ　Ｅｍｅｒｇｅｎｃｙ　Ｌｏｇｉｓｔｉｃｓ　Ｄｉｓｔｒｉｂｕｔｉｏｎ　ＶＲＰ　

古火焰　（长沙理工大学，湖南长沙４１００７６）　

ＧＵ　Ｈｕｏ—ｙａｈ（Ｃｈａｎｇｓｈａ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｓｃｉｅｎｃｅ＆Ｔｅｃｈｎｏｌｏｇｙ，Ｃｈａｎｇｓｈａ　４１００７６，Ｃｈｉｎａ）　

摘　要：应急物流是处理各类突发事件对物资、人员的需求进行紧急保障的一种特殊物流活动　文章根据应急物流的特点，　

将免疫算法用于应急物流车辆调度研究中，同时通过算例．证明用免疫算法优化车辆行驶路径的有效性和可行性　

关键词：应急物流：免疫算法：车辆优化调度　中图分类号：Ｆ２２４　文献标识码：Ａ　文章编号：１００２—３１００　ｆ２００８１　１１—００２４—０４　

Ａｂｓｔｒａｃｔ：Ｅｍｅｒｇｅｎｃｙ　ｌｏｇｉｓｔｉｃｓ　ｉｓ　ａ　ｋｉｎｄ　ｏｆ　ｓｐｅｃｉａｌ　ｌｏｇｉｓｔｉｃａｌ　ａｃｔｉｖｉｔｙ　ｓｏｌｖｉｎｇ　ａｌｌ　ｋｉｎｄｓ　ｏｆ　ｕｎｅｘｐｅｃｔｅｄ　ｅｖｅｎｔｓ　ｗｈｉｃｈ　ａｒｅ　ｄｅｍａｎｄｅｄ　

ｓｅｒｉｏｕｓｌｙ　ｔｏ　ｔｈｅ　ｇｏｏｄｓ　ａｎｄ　ｍａｎｐｏｗｅｒ．Ａｃｃｏｒｄｉｎｇ　ｔｏ　ｔｈｅ　ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ　ｏｆ　ｔｈｅ　ｅｍｅｒｇｅｎｃｙ　ｌｏｇｉｓｔｉｃｓ，ｔｈｉｓ　ｔｅｘｔ　ａｐｐｌｉｅｓ　ｔｈｅ　ｉｍｍｕｎｅ　ａｌ—　ｇｏｒｉｔｈｍ　ｉｎ　ｔｈｅ　ｅｍｅｒｇｅｎｃｙ　ｌｏｇｉｓｔｉｃｓ　ｄｉｓｔｒｉｂｕｔｉｏｎ　ＶＲＰ．Ａｔ　ｔｈｅ　ｓａｍｅ　ｔｉｍｅ，ａｎ　ｅｘａｍｐｌｅ　ｉｓ　ｇｉｖｅｎ　ｔｏ　ｐｒｏｖｅ　ｔｈｅ　ｅｆｆｉｃｉｅｎｃｙ　ａｎｄ　ｕｓａｂｉｌｉｔｙ　

ｉｎ　ｔｈｅ　ｖｅｈｉｃｌｅ　ｒｏｏｔｉｎｇ　ｐｒｏｂｌｅｍ．　

第３２卷第１期　２００８年２月２０日　水电自动化与大坝监测　Ｈｙｄｒｏｐｏｗｅｒ　Ａｕｔｏｍａｔｉｏｎ　ａｎｄ　Ｄａｍ　Ｍｏｎｉｔｏｒｉｎｇ　Ｖｏ１．３２　ＮＯ．１　Ｆｅｂ．２０，２００８　

遗传算法在水库【群）优化调度研究中的应用综述　

涂启玉，梅亚东　

（武汉大学水资源与水电工程国家重点实验室，湖北省武汉市４３００７２）　

摘要：介绍了遗传算法在水库（群）优化调度中的应用背景及算法的收敛性，讨论了水库（群）优化　

调度中遗传算法的基本应用步骤以及存在的问题，给出了算法的各种改进方法，并对遗传算法的应　

用前景进行了展望。　

关键词：遗传算法；水库（群）优化调度；收敛性；算法改进　

中图分类号：ＴＶ６９７．１　

Ｏ　引言　

遗传算法口］（ＧＡ）在优化计算时从多个初始点　

开始寻优，对所求问题没有太多的数学约束，而且优　

化求解过程与梯度信息无关。它不要求目标函数连　

续、可导，也不要求约束域为凸集，因而在非线性约　

束优化问题的求解中显出了独特的优势。在水库优　

化调度中，文献［２］使用基于二进制编码的遗传算法　

对水库优化调度进行了研究。文献［－３－］将ＧＡ用于　

４座水库优化调度中，并与传统方法进行比较，发现　

ＧＡ鲁棒性强，很容易用于复杂系统，有潜力取代随　

机动态规划，同时实数编码快于二进制码，结果更　

优。文献［４］采用ＧＡ对水库运行进行寻优，并与模　

拟退火算法对比，ＧＡ得出了更好的结果。目前，　

ＧＡ在水库（群）优化调度中的应用越来越广，随着　

研究的深入，对ＧＡ的认识越来越深，也随之产生了　

许多问题。本文针对ＧＡ在水库（群）优化调度中的　

应用进行探讨。　

１　应用背景　

ＧＡ与其他算法相比具有以下特点：①从一群　

初始点而非单一的初始点开始，所以能有效跳出局　

部极值点；②使用目标函数的评价信息而非传统目　

标函数的求导，对目标函数的性态没有要求，因而有　

良好的适应性和可规模化；③搜索效率高，每代处理　

规模为　的个体，实际上处理了ｏ（　。）个模式，具有　

龙源期刊网

物流配送车辆调度路径优化问题算法研究

作者：浮萍萍 叶春明 李佳桐

来源：《物流科技》2015年第03期

摘 ;要：近年来，我国物流运行总体平稳，物流需求规模保持较高增幅，物流业增加值平稳增长，但经济运行中的物流成本与其他发达国家相比依然较高。车辆调度配送路径优化问题同时涉及能源消耗和废物的排放问题，随着人们对环境问题给予越来越多的关注，因而其一直是国内外研究的热点。同时物流配送车辆调度问题在企业运营中起着重要的作用。文章首先简介了车辆调度问题，然后从研究的精确算法和启发式算法两方面较为详细地论述了国内外有关车辆调度问题的研究现状，总结了研究中存在的问题，并对物流算法的发展进行了展望。

关键词：车辆调度;路径优化;启发式算法

;中图分类号：F253 ; ;文献标识码：A

Abstract： In recent years， domestic logistics is developing steady in a whole， the demand of

logistics is also in a high amplification. The logistics industry is in a stable increase while the

operating cost is still higher than that of developed countries. For that vehicle routing problem both

relates to energy consumption and wastage emission， VRP is a research hotspot at home and abroad

under the case that more and more attention are paid to environment protection. Vehicle scheduling