基于改进遗传算法在货运物流中的应用研究

摘 要：物流企业中车辆路径选择规划问题（VRP）是一个典型的NP难问题。为了解决这类问题，启发式算法被提出。现代启发式优化算法中的遗传算法是解决货运物流运输车辆问题的有效算法。本文详细研究了遗传算法在货运物流中的应用，结合实际建立了合适的VRP数学模型，提出了解决该问题的改进遗传算法，并对该算法进行了详细的讨论。

关键词：物流；VRP；遗传算法

中图分类号：TP18

随着电子商务时代的来临，消费者的消费习惯产生了巨大的变化，同时也给货运物流行业带来了全新的发展。货运配送业务量也在逐年增长，如何加快物流配送的速度，进一步达到快速、及时、节约的物流配送目的就成了时下亟待解决的问题。本文中我们对车辆物流配送建立了数学模型，然后利用遗传算法对该模型进行求解，并结合实际情况将该模型予以改进。最后将其应用到实践之中。

1 货运物流管理

1.1 物流的概念和发展

物流的概念最早在形成于美国，起初被称为Physical Distribution（PD），即实体分配或配送。到了1963年，物流的概念被引入日本，进一步解释为“利用现代信息技术和设备，将物品从供应地向接收地准确的、及时的、安全的、保质保量的、门到门的合理化服务模式和先进的服务流程。

“物流”自上个世纪70年代末引进我国以来，经历了近20年的研讨酝酿、启蒙尝试，到90年代后半期，在改革开放和现代化建设的强有力推动下，伴随着信息技术的迅猛发展和跨国公司的大举进入引起了社会各界广泛关注。现代物流就不单纯考虑了货物配送的问题，而且还要考虑从供应商到制造商的原材料采购，以及制造商在产品生产制造过程中的运输、仓储、装卸、配送和信息等各个方面，如何全面地、综合性地提高经济效益和效率的问题。

1.2 国内货运物流的现状

随着我国正式加入世界贸易组织，国内的运输业和物流业正面临着前所未有的挑战和机遇。随着UPS、Fedex等物流巨头的进入，无论从资金、管理、技术和能力上，我国的物流业都毫无优势可言。

在新的经济形势下，客户对车辆运输提出了更高的要求。不仅要加快运输速度，保证货物运达的成功率和效率，减少转运周期，减少流动资金占用，还要利用自身的物流信息为客户提供物流管理，从而为客户和运输企业本身创造更多的价值。因为运输成本是物流成本中仅次于仓储成本的第二大成本，而利用车辆货运又在全国货运总量中占有很大的比例，因此车辆运输成本的节约将给运输企业以及客户带来巨大的经济效益。

2 遗传算法

2.1 遗传算法的概念和基本流程

遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。它是由美国的J.Holland教授1975年在他的专著《自然和人工系统的适应性》首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术之一。

遗传算法（Genetic Algorithm）是一类借鉴生物界自然选择和自然遗传机制的随机搜索算法。其主要特点是群体搜索策略和种群中个体之间的信息交换、搜索不依赖于梯度信息。它尤其适用于处理传统搜索方法难以解决的复杂和非线性问题。

遗传算法效仿基于自然选择的生物进化，是一种模仿生物进化过程的随机方法，下面先介绍几个生物学的基本概念和术语，这对于理解遗传算法是非常重要的。

定义1.染色体（Chromosome）。生物细胞中含有的一种微小的丝状化合物。它是遗传物质的主要载体，由多个遗传因子—基因组成。

定义2.个体（Individual）。指染色体带有特征的实体。

定义3.种群（Population）。带有特征个体的染色体集合称为种群。该集合内个体的总数称为群体的大小。有时个体的集合也称为个体群。

定义4.适应度（Fitness）。在研究自然界，卜生物遗传和进化现象时，生物学家使用适应度这个术语度量某个物种对于生存环境的适应程度。对生存环境适应度高的物种获得更多的繁殖机会，而生存环境适应度低的物种，其繁殖机会就会相对较少，甚至逐渐灭绝。

定义5.选择（selection）。指决定以一定的概率从种群中选择若干个体的操作。一般而言，选择的过程是种基于适应度的优胜劣汰的过程。

定义6.复制（Reproduction）。细胞在分裂时，遗传物质DNA通过复制而转移到新产生的细胞中，新的细胞就继承了旧细胞的基因。

定义7.交叉（Crossover）。有性生殖生物在繁殖下一代时两个同源染色体之间通过交叉而重组，亦即在两个染色体的某一个相同位置处DNA被切断，其前后两串分别交叉组合形成两个新的染色体。这个过程又称为基因重组，俗称“杂交”。

定义8.变异（Mutation）。在细胞进行复制时可能以很小的概率产生某些复制差错，从而使DNA发生某种变异，产生出新的染色体，这些新的染色体表现出新的性状。

我们习惯上把Holland1975年提出的GA称为传统的GA。它的主要步骤如下：编码：GA在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据，这些串结构数据的不同组合便构成了不同的点。初始群体的生成：随机产生N个初始串结构数据，每个串结构数据称为一个个体，N个个体构成了一个群体。GA以这N个串结构数据作为初始点开始迭代。适应性值评估检测：适应性函数表明个体或解的优劣性。不同的问题，适应性函数的定义方式也不同。选择：选择的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代为下一代繁殖子孙。遗传算法通过选择过程体现这一思想，进行选择的原则是适应性强的个体为下一代贡献一个或多个后代的概率大。选择实现了达尔文的适者生存原则。交换：交换操作是遗传算法中最主要的遗传操作。通过交换操作可以得到新一代个体，新个体组合了其父辈个体的特性。交换体现了信息交换的思想。变异：变异首先在群体中随机选择一个个体，对于选中的个体以一定的概率随机地改变串结构数据中某个串的值。同生物界一样，GA中变异发生的概率很低，通常取值在0.001～0.01之间。变异为新个体的产生提供了机会。遗传算法的基本处理流程如图1所示。

2.2 遗传算法与物流配送的关系

车辆路径问题是一个NP完全问题，只有当其规模较小时才有可能寻求其精确解。因此，如何针对车辆路径问题的特点，构造运算简单、性能优异的启发式算法，对物流系统以及许多可以转化为车辆路径问题的组合优化问题都有十分重要的意义。在求此类问题时，若不能利用问题的固有知识来缩小搜索空间，很容易产生搜索的组合爆炸，因此研究在搜索过程中自适应地完成搜索过程，从而得到最优解或次优解的通用的搜索算法一直是令人瞩目的课题。遗传算法就是这种特别有效的算法。它的主要特点是简单、通用、鲁棒性强，适应于并行分布处理，应用范围广。目前，遗传算法已经在求解车辆路径问题方面取得了成功的应用。但传统标准遗传算法（GA）易陷入局部极值解，出现“早熟收敛”现象。为此，本文针对遗传算法在求解车辆路径问题中存在的“早熟收敛”、易陷入局部极值点、寻优效率不够理想等问题，研究出了新的改进遗传算法，以消除传统遗传算法中的不足，提高算法寻优效率。它无法用常规的最优算法求得精确的最优解，为此，人们使用各种启发式算法来解决它。在启发式算法中，现代优化算法是近年来发展起来的一类启发式算法，其中的遗传算法更以其独特的思想方法受到人们的重视。

3 遗传算法在货运物流中的应用

3.1 货运物流配送的数学模型

车辆货运物流运输路径问题（VRP）可描述为：从配送中心用多辆汽车向多个需求点送货，每个需求点的位置和需求量一定，每辆汽车的载重辆一定，要求合理安排汽车路线，使总运距最短，并满足以下条件：

（1）每条配送路径的长度不超过汽车一次配送的最大行驶距离；

（2）每条配送路径上各需求点的需求量之和不超过汽车载重量；

（3）每个需求点的需求必须满足，且只能由一辆汽车送货；设配送中心有K辆汽车，每辆汽车的载重量为Qk（1，2，…K），其一次配送的最大行驶距离为Dh，需要向L个需求点送货，每个需求点的需求量为qi（i=1，2，…L），需求点i到j的运距为Dij，配送中心到各需求点的距离为doj（i，j=1，2，…L）。再设nk为第k辆汽车配送的需求点数（nk=0表示未使用第k辆汽车）用集合Rk表示第k条路径，其中的元素rki表示需求点rki在路径k中的顺序为i（不包括配送中心），令rk0=0表示配送中心，则可建立如下物流配送路径优化问题的数学模型的目标函数：

3.2 改进的交叉算子

遗传算法的车辆路径规划方法中，不管是在已知的环境或者未知环境，遗传算法的交叉概率都给出一个值。虽然这并不影响对遗传算法的平稳运行，但很容易在在交叉过程当中丢失最优解。这主要是因为用于个体的交叉都是随机选择的，适应值大的个体与适应值小的个体有相同的交叉概率，也就有同样的被交叉机会，而适应值大的个体进行交叉后，有可能会降低平均适应度，损失最优解。

本文在遗传算法的改进方法中，提出了一种自适应交叉概率的方法，交叉概率的方法，该方法令大适应值个体具有小交叉概率，小适应值个体具有大交叉概率，这样就保证了最优个体在交叉操作中能够保存下来。该方法的表达式为：Pc=K1×（fmax-f`）/（fmax-fmin）+K2

其中，fmax、fmin。和f`，分别为种群的最大适应度数值、最小适应函数值和相交叉的两个个体中的较大适应值k1、k2分别为算法的收敛系数，且k1+k2=1。这种自适应交叉概率的方法，保证了具有大适应值的个体保留下来，选择适应值小的个体进行交叉。

3.3 求解问题的混合遗传算法HGA-VRP

为了提高优化的效果和算法的时间效率，本文提出了一种求解VRP问题的混合遗传算法HGA-VRP（Hybrid Genetic Algorithm for Vehicle routing Problem）。HGA-VRP将2-opt算法作为变异算子，以改进的自适应交叉概率方法获取交叉算子以提高优化的效果。

HGA-VRP的编码方案采用常用的路径标示基因编码方案。个体的适应度由个体所代表的适应值函数来决定，适应值函数越小则个体的适应度越高。HGA-VRP算法在交叉算子方面，采用改进的自适应交叉算子，采用2-opt算法作为遗传算法的变异算子。

HGA-VRP算法的计算步骤如下：

（1）初始化：根据多个货物配送点建立坐标空间模型。并对坐标进行基因编码。

（2）生成初始种群：把产生一系列可行路径顺序排列作为染色体的编码方法，在程序中染色体用数组存储，生成初始种群M。

（3）遗传代数计数器初始化，options=0。

（4）循环处理步骤4a至步骤4d，直到设定的最大进化代数。

a.以路径长度的倒数作“适应值函数”，具体表达如下：

对种群中的个体计算适应值的长度，并对个体按适应值从小到大排序。

b.选择算子：按照赌的方法选出新的种群。

c.交叉操作：交叉操作是在选出的部分子种群中进行的，其结果关系到算法的收敛速度，所以是遗传算法中比较重要的一个算子。根据低适应值函数个体具有高交叉率，高适应值函数个体具有低交叉率的原则，引入如下自适应产生交叉概率方法：Pc=K1×（fmax-f`）/（fmax-fmin）+K2

d.变异算子：选择种群中M*Pm的个体，Pm是变异概率。采用2-opt邻域搜索优化算法对所选个体进行优化。

4 结论

本文介绍了货运物流管理的概况，以及国内货运物流的现状，指出了货运物流管理信息化的意义，详细研究了遗传算法在货运物流配送问题中的应用，在VRP模型的基础上，结合实际地建立了合适的数学模型，设计实现了解决该问题的改进混合遗传算法，采用了自适应交叉操作和2-opt邻域搜索优化算法来优化变异操作，对遗传算法中的各个步骤进行了研究，实现了完整的遗传算法。本文所提出的改进遗传算法的是一种较为合理、相对完善的车辆货运物流运输路径问题解决方案，具有一定的理论和现实意义。

参考文献：

[1]宋华，胡左浩.现代物流与供应链管理[M].经济管理出版社，2000.

[2]李军，郭耀煌.物流配送车辆优化调度理论与方法[M].中国物资出版社，2001，6.

[3]张文修.遗传算法的数学基础[M].西安交通大学出版社，2000.

[4]阎庆，鲍远律.新型遗传模拟退火算法求解物流配送路径问题[J].计算机应用，2004，6：261-263.

[5]Ellehi Taniguehi， Russell G.Thompson， Tadashi Yamada， Ron Van Duin. City Logistics： Network Modeling and Intelligent Transport Systems.PERGMAON.2001：2-3.

作者简介：张彦（1982.7.10-），女，浙江杭州人，助理工程师，学士学位，研究方向：计算机应用。

作者单位：杭州萧山国际机场，杭州 311209