探究遗传算法应用于物流的配送运输

摘要：随着社会经济和网络技术的不断发展，社会物流业也呈快速发展的趋势。在物流业中，物流配送是很重要的环节之一。本文以临沂地区的物流业为背景，为了更好地解决物流配送路径优化问题，建立了一种遗传算法模型。实验计算表明，通过用遗传算法进行物流配送路径优化，可以方便有效地得到问题的最优解或者近似最优解。

关键词：遗传算法 物流配送 优化 临沂地区

1.引言

市场经济的改革以及跨地区贸易的发展共同促进了物流业的快速发展。物流配送是指将客户所购的货物及时的送交客户的过程，物流配送不仅是物流业最重要的环节之一，同时物流配送的效率也直接影响着整个工作流程的效率，因此，需要不断地改进、优化物流配送路径。本文的研究背景是山东的临沂地区，临沂市被确定为省级物流节点城市，将利用商贸市场集聚的优势，以建设大物流促进商贸流通发展为目标，建立连接江苏、辐射长江三角洲，连通日照、连云港的商贸物流基地，服务于省内外商贸流通和经济建设。那么在这样一个重要的物流节点城市，合理地选择配送路径具有重要的意义，不仅能偶缩短配送时间，也能降低配送成本，在提高服务质量和提高经济效益方面都有较大贡献。

优化配送路径是一个NP-Hard问题，为了解决这一问题，近年来提出了不少算法，比如节约法、扫描法等，本文通过一系列的研究，将遗传算法应用于物流配送的决策分析中。遗传算法（Genetic　Algorithms，GA）最早是由John.H.Holland于1975年提出的，它是一种结合了生物自然选择和基因遗传学的优化搜索方法。它的优点非常多，比如鲁棒性强、速度快、搜索范围广等而广泛应用于各个领域。本文针对物流配送路径优化问题，首先分析了其数学模型，然后引入了遗传算法来优化，最后进行了实验计算，研究表明，将遗传算法应用于物流配送路径优化问题是行之有效的方法，取得较好的结果。

2.优化物流配送路径的数学模型

物流配送的优化可以描述为：配送中心用多辆汽车向多个客户送货，其中汽车的载量确定，客户的位置和需求量确定，通过优化，使得汽车所行驶的总路程最短，并且满足以下条件：

（1）各路径上的客户的总需求量小于等于汽车载量；

（2）各路径总长度小于等于汽车配送一次可行驶的最大长度；

（3）一条路径由一辆汽车进行配送，且必须满足个客户需求。

通过对以上条件的分析，建立物流配送路径的数学模型。首先规定以下公式中各字母的意义：K为配送中心拥有的汽车总量；[Qk]（k=1，2，…，K）为各汽车的载量；[Dh]为汽车进行一次配送所行驶的最大长度；L为客户总数；[qi]为客户i的需求量；[d0j]为客户与配送中心的长度；[dij]为客户i和客户j之间的长度；[nk]为第k辆汽车负责的配送的客户数，若此值为0，则表示此汽车未使用；[Rk]为集合，表示第k条路径，其中[rki]表示客户[rki]在路径k中的顺序为i，令[rk0]=0表示配送中心。经过分析，建立如下数学模型：

3.优化物流配送路径的遗传算法

3.1遗传算法的基本思想

遗传算法是一种很好的搜索优化方法，它的操作对象为种群的所有个体，个体与问题的解是一一对应的，其中选择、交叉和变异是最主要的操作。它的流程图如下：

图1 遗传算法流程图

这种算法主要包括6个基本要素：

（1）编码：通过编码将空间的数据转变为基因型串数据，在编码前先进行量化。

（2）生成种群：通过随机方法产生初始种群，每个个体对应问题的一个解。

（3）评估适应度：用来评估个体的优劣，评估结果作为遗传操作的依据。

（4）选择：通过“适者生存”的选择方法，从当前种群中选取适应度高的个体组成新的种群，适应度越高，被选择几率越大，但不能保证一定被选择。

（5）交叉：将选出的个体存入配对库，进行随机配对，产生新的个体。

（6）变异：引入变异是为了解决在交叉过程中引起的信息遗失现象，按概率改变染色体基因位。

3.2优化配送路径的遗传算法构造

（1）编码方法。在本文中，配送中心用0表示，客户用1表示（L个1表示有L个不同客户）。每条配送路径的起点和终点都是配送中心，配送路径的最大值由配送中心的汽车总数K决定，这样，L个1或者K—1个0随机排列成一条染色体，则对应一种配送路径方案。

（2）初始种群的产生。由1和0构成的序列称为一条染色体，那么由多条不同的染色体构成初始种群。

（3）适应度评估。在评价一种配送方案的优劣时，既要判断是否能够满足约束条件，又要计算它的目标函数值。因此，在进行评估时，首先判断各配送路径方案是否满足约束条件，如果不满足，则该路径为不可行的路径，然后计算目标函数值。适应度[Fi]的计算公式如下所示：

[Fi=1Zi+MiG]

其中，[Zi]为目标函数值，[Mi]为染色体i所对应的不可行路径数，G为权重因子，为值较大的正数。

（4）选择操作。在本文中，综合使用最优个体保留策略和赌法，首先，将所有染色体按照适应度小进行排序，对于适应度最高的染色体，则直接进行复制；然后采用赌法，使剩余的染色体产生下一代的N-1条染色体。每条染色体被选中的概率为它本身的适应度与种群中所有染色体的适应度之和的比值。

（5）交叉操作。交叉操作主要是按照交叉概率将除了第一条染色体外的其他染色体进行交叉配对，本文采用两点交叉法。

（6）变异操作。本文所采用的变异操作是为了保证一旦某基因片段需要发生变异，那么另一片段也要发生变异，这个片段是随机产生的。

4.实验与计算

在本实验中，采用C语言编程，以2辆汽车为5个客户配送为例，其中汽车载量为8000千克，一次配送最大行驶长度为40千米，配送中心与客户以及客户与客户之间的长度由下表表示（单位千米）：

5.小结

通过本文的理论分析与实验证明，将遗传算法应用于物流配送路径优化方案中是可行的。本文首先分析了物流配送路径的数学模型，然后简介了遗传算法的原理，并进一步将遗传算法应用于物流配送路径中，最后通过实验计算，证明用遗传算法能够得到快速的得到物流配送路径的最优解，是提高配送效率有效的方法。

参考文献：

[1]王辉.基于改进遗传算法的物流配送路径优化研究[D].山东科技大学，2010，5

[2]黄晓滨，邹书蓉，张洪伟.改进的遗传算法及在物流配送路径优化中的应用[J].西南民族大学学报（自然科学版）.2008（4）

[3]易荣贵，罗大庸.基于遗传算法的物流配送路径优化问题研究[J].计算机技术与发展.2008（6）

[4]郭淑红，杨晓慧.遗传算法在物流配送路径优化问题中的应用[J].硅谷.2009（1）

作者简介：

殷俊峰（1978- ），男，山东费县人，汉，临沂大学讲师，山东大学硕士研究生，主要研究方向：统计学，运筹学，计量经济学的应用问题、时间序列分析等。