基于混合遗传算法的物流路径优化方法研究

申艳光，张玲玉，刘永红

(1.河北工程大学 信息与电气工程学院，河北 邯郸 056038；2.中电建建筑集团有限公司，北京 100000)

0 引 言

随着社会经济的不断发展，现代物流企业在物流配送中如何合理调度运输车辆，优化运输线路，减少运输距离，已经成为物流管理的一个关键问题，直接影响和决定着物流企业在社会中的竞争。目前国内各地物流企业在选择物流配送路线时，主要依据经验选择配送路线，往往达不到行驶距离最短，调用车辆次数最少的效果。因此如何选择最优物流配送车辆路径，及时将货物送到客户手中，成为物流研究领域中的热点问题[1]。

通过研究物流配送路径优化问题，发现车辆路径问题是一个NP(non-deterministic polynomial，非确定性多项式)完全问题。在20世纪60年代初，车辆路径问题一直是配送和物流领域的一个重要问题[2]。现在关于车辆路径问题的算法有很多种，主要包括人工蜂群算法[3-6]、禁忌搜索法[7]、遗传算法[8-10]、启发式算法、蚁群算法[11]等。其中遗传算法是求解此类NP完全问题的一种有效的全局搜索算法,但在求解车辆路径问题时存在早熟和局部搜索能力不足的问题。因此寻求合理的方法，提高算法的效率，增强算法对配送车辆调度的优化性能，成为相关学者分析的重点[12]。

遗传算法(genetic algorithm，GA)是模拟生物在自然环境中的遗传和进化过程而形成的一种全局优化搜索算法[13]。为了提高遗传算法的局部搜索能力和早熟现象，以往的算法忽略了在物流配送途中可能存在的一些客观因素，比如车辆行驶路线、在配送过程中给车辆加油或修车额外行驶距离和使用车辆数量等。因此，针对物流配送路径中存在的问题，文中提出一种结合K-means算法与改进遗传算法的混合遗传算法。首先，通过K-means算法对客户的位置坐标进行聚类分析，得到局部配送中心及其配送范围内的客户点，然后利用改进遗传算法使目标函数最小，优化配送路线。

1 物流配送路径优化数学模型

1.1 问题描述

物流配送车辆的调度问题描述如下：已知每个客户的位置坐标和需求量，车辆的最大行驶距离，在满足目标函数最小和多个约束条件的前提下，要求每辆车从配送中心出发，用k(1≤k≤K，K为最大允许的车辆数)辆车分别走不同的配送路线，把货物送到客户指定的送货地点，使得每个客户有且仅有一辆车进行一次配送，完成配送任务后返回配送中心。所以物流配送路径问题的关键是如何优化配送路线和分配车辆的行驶路线，使得总运输距离最短。

1.2 模型假设和模型符号

在对物流配送路径优化问题进行建模时，需要遵循以下假设条件：

(1)每辆车都要从配送中心出发进行货物运输，完成任务后返回配送中心；

(2)每辆车只能分配一条运输路线，而且每个客户只能被访问一次；

(3)已知每个客户配送地址的坐标；

(4)已知每个客户点的需求量；

(5)每辆车的行驶距离不得超过其规定的最大行驶距离；

(6)必须满足每个客户的配送需求。

基于以上假设，建立物流配送路径优化模型，与之相关的数学模型符号的含义如下：

K：表示配送中心的总车辆数(k=1,2,…,K)；

Pi：表示每个客户(k=1,2,…,K)；

N：表示这一区域内需要服务的客户数量；

Xij：表示决策变量，表示从客户i到客户j的次数；

dij：表示客户i与客户j之间的距离；

d1o：表示车辆从配送中心到第1个客户点的距离；

So：表示车辆在行驶过程中额外行走的路程(例如配送过程中加油、修车行驶路程)；

dno：表示车辆送货完毕返回配送中心的距离；

Xik：表示车辆从客户i行驶到客户k；

L：表示可以行驶的最大距离；

Xko：表示k点到原点的距离；

Q：表示每台车的最大载重量；

qi：表示每个客户的需求量。

1.3 建立模型

由以上问题描述和假设条件，建立了物流配送路径优化数学模型。模型以最少运输距离为目标函数，确定最优的车辆配送路线来求解数学模型，其目标函数和约束条件如下所示：

目标函数：

(1)

(2)

(3)

(4)

(5)

(6)

约束条件：

目标函数(1)：表示计算可行驶最短路径的目标函数；

约束条件(2)：表示计算预留车辆数量；

约束条件(3-4)：表示每个客户被访问有且仅有一次；

约束条件(5)：表示车辆在配送过程中行驶一次的距离不能超过其规定的行驶距离L；

约束条件(6)：xij是模型的决策变量。

2 优化物流配送路径的混合遗传算法

由于传统遗传算法存在局部搜索能力不足和早熟的缺点，于是首先通过K-means算法对客户的位置坐标进行聚类分析，得到局部配送中心及其配送范围内的客户点，然后利用改进遗传算法的选择、交叉、变异操作对物流路径进行优化。

2.1 K-means算法

K-means算法以k为参数，把n个对象分成k个簇，以使簇内具有较高的相似度，而簇间具有较低的相似度，相似度根据一个簇中对象的平均值来计算。定义准则如下：

(7)

其中，E为所有对象的误差平方和；x为给定的对象属于Ci的平均值。

该准则函数试图使生成的结果簇尽可能地紧凑和独立。

计算步骤如下：

(1)任意选择k对象，然后将每个数据对象作为聚类中心；

(2)将剩下的数据对象划分到和各个数据对象本身距离最近的聚类中心，根据式(8)：

DS(Ca,Cb)=min{d(x,y)|x∈Ca,y∈Cb}

(8)

其中，Ca和Cb是两个簇，它们分别包含m和h个元素。设元素x∈Ca，y∈Cb，这两个元素间的距离用簇间距离表示，记为D(Ca,Cb)。

(3)重新计算每个聚类中心中数据对象的均值，得到新的聚类中心，均值计算公式为：

(9)

其中，Ci为一个聚类，x为Ci内的一个数据对象，即x∈Ci；nk为第k个聚类中的数据对象。

(4)重复步骤(2)到(3)，直到每个聚类中的数据对象不再发生变化或者目标函数收敛时结束。

2.2 改进遗传算法

2.2.1 编码设计

这里采用序号编码的方式。假设随机产生一个序列(1，2，3，4，7，6，5，9，8)，设生成的断点矩阵为(2，5，7)，则首先在序列的第2、第5及第7位加“0”，序列变为(1，2，0，3，4，7，0，6，5，0，9，8)，再在新序列的首末位加“0”，则染色体为(0，1，2，0，3，4，7，0，6，5，0，9，8，0)。其中，0表示配送中心，序号表示客户编号，此序列表示配送方案由4条路线组成。车辆1的路线为(0，1，2，0)，经过客户后回到配送中心，为子路径1；同理，车辆2的路线为(0，3，4，7，0)，为子路径2；车辆3的路线为(0，6，5，0)，为子路径3；车辆4的路线为(0，9，8，0)，为子路径4，如图1所示。图1很直观地给出了子路径及客户顺序。此染色体结构能够很清晰地表

图1 染色体结构

达车辆路径问题的解空间[14]。

通过编码重复染色体生成的过程，一直达到种群规模M，即初始种群。

2.2.2 适应度函数设计

通过适应度函数选择优秀的染色体，因此设计的适应度函数为：

(10)

其中，fitness(xi)为第i个个体的适应度；x0为初始种群中最优染色体的运输距离；xi为当前染色体所对应的运输距离。

然后利用适应度函数计算适应度值，按从小到大进行排序，最后进入选择操作。

2.2.3 选择操作

采用精英保留模型的锦标赛选择策略，产生一个新的染色体。锦标赛选择策略是一种基于适应度的选择方法，随机从染色体中选择一组个体(n个)称为比赛集。这里设置的大小为4，选择一个随机数r(介于0和1之间)。当r小于0.8时，在比赛集中设置个体的优胜劣汰，然后选择一个用于复制。否则，任何染色体选择从比赛集复制，被精英保留模型选中，以确保最好的个体进入下一代。

2.2.4 交叉操作

选择操作产生的新种群，除第一条染色体外，另外N-1条染色体要根据交叉概率pc(pc取值在0～1之间)进行交叉配对[15]。这里采用双切点交叉遗传，在传统遗传算法中多采用单点交叉遗传，单点交叉遗传使得父代双方很多染色体发生交换，在交换过程中有时会破坏种群中优秀的染色体；而双切点交叉遗传与单点交叉遗传相比，父代双方很少有染色体发生交换，有利于保留优秀的染色体。例如对下面两个个体使用双切点交叉的方法，切点分别在第2个位置和第5个位置：

↓切点1 ↓切点2

染色体1：1 0 7 6 9 8 3 2

染色体2：0 1 9 8 7 4 2 3

则通过多点交叉之后，两个染色体个体分别变为：

染色体1：1 0 9 6 7 8 3 2

染色体2：0 1 7 8 9 4 2 3

即只交换了两个切点之间的部分。

2.2.5 变异操作

采用k-交换变异操作，通过对初始可行路线交换k条边/弧，对初始可行解进行逐步改进，直到不能改进为止。一般2-交换和3-交换技术运用较多，即在每代种群中随机地以变异概率pm选择染色体上的两个点或三个点，并执行2-交换和3-交换变异操作。

3 实验结果与分析

3.1 实验数据

实验数据来源于《中国所有城市坐标表》，以河北省15个城市坐标作为测试数据，为了使描述简单准确，进行了相应的原始数据处理，见表1。

表1 各个客户之间的位置坐标和需求量

3.2 参数设定

根据K-means算法与改进遗传算法二者结合的混合遗传算法、改进遗传算法和传统遗传算法利用Matlab对表1的实验数据进行编程得出实验结果。

实验中算法的初始参数设置为：初始配送中心编号为0，首先根据K-means算法，设k=3计算出聚类中心点，即局部配送中心以及客户的分配范围，然后利用改进遗传算法优化配送路线；设车辆的数量由式(2)计算，得出K=4，车辆的载量Q=20 m3，每次配送车辆最大行驶距离L=100 km,额外行驶路程So=80 km，种群大小M=100,交叉概率pc=0.7，变异概率pm=0.05。

3.3 实验结果

图2和图3为传统遗传算法和改进遗传算法的配送路径。

图2 传统遗传算法配送路径

图3 改进遗传算法配送路径

从图2可以看出，传统遗传算法在物流配送路径中配送路线有若干条交叉线，可以判断这不是一个最优解。图3中改进的遗传算法在物流配送路径中配送路线相比图2交叉线明显减少。而图4比图2、图3更能达到目标函数的最少运输距离。

图4 混合遗传算法配送路径

从表2可以看出每台车辆分别在传统遗传算法和改进遗传算法、K-means算法与改进遗传算法相结合的混合遗传算法下物流配送路径的路线及运输距离，说明混合遗传算法所求得的最优配送路线使目标函数值达到最小并解决了早熟现象。基于表2中的最优配送路线，相对应的货物配送量见表3。

表2 传统遗传算法、改进遗传算法和混合遗传算法配送路线比较

续表2

表3 最优车辆调度状态下的需求分配

注：q表示对对应节点客户的需求进行配送，后面的数字均表示相应的配送量。

4 结束语

考虑到实际车辆在配送过程中的应用，文中建立了减少运输距离的物流配送路径最优化的数学模型，提出了一种K-means算法与改进遗传算法相结合的混合遗传算法，并通过仿真实验对其进行了验证。实验结果表明，与传统遗传算法和改进遗传算法相比，该算法解决了早熟现象，优化了物流配送路径，从而加快了配送速度，提高了服务质量，缩短了配送距离。在未来的工作中，力图将该算法推广到更复杂的物流配送当中，通过仿真实验进一步优化该算法的性能。

[1] 吴洁明.物流配送车辆路径优化问题的仿真研究[J].计算机仿真,2011,28(7):357-360.

[2] BELL J E,MCMULLEN P R.Ant colony optimization techniques for the vehicle routing problem[J].Advanced Engineering Informatics,2004,18(1):41-48.

[3] AKAY B,KARABOGA D.A modified artificial bee colony algorithm imization[J].Information Sciences,2012,192(1):120-142.

[4] IRANI R,NASIMI R.Application of artificial bee colony-based neural network int bottom hole pressure prediction in underbalanced drilling[J].Journal of Petroleum Science and Engineering,2011,78(1):6-12.

[5] KARABOGA D,QZTRUK C.A novel clusteringapproach:artificial bee colony (ABC) algorithm[J].Applied Soft Computing,2011,11(1):652-657.

[6] MANDAL S K,CHAN F T,TIWARL M.Leak detection of pipeline:an integrated approach of rough set theory and artificial bee colony trained SVM[J].Expert Systems with Applications,2012,39(3):3071-3080.

[7] 巩 固,胡晓婷,卫开夏,等.物流配送车辆路径问题的优化研究[J].计算机工程与科学,2011,33(5):106-111.

[8] 雷建平,沈成武,闻骥骏.货郎担问题与单亲遗传算法[J].武汉理工大学学报,2003,25(6):80-83.

[9] 周春光,周国芹,程彦峰,等.一种克服遗传算法收敛于局部极小的方法[J].小型微型计算机系统,1997,18(3):46-49.

[10] 李向阳.遗传算法求解VRP问题[J].计算机工程与设计,2004,25(2):271-273.

[11] 陈卫东,王 佳.基于混合蚁群算法的物流配送路径优化[J].计算机工程与设计,2009,30(14):3383-3385.

[12] 彭其华.一种车辆路径优化调度算法的研究与仿真[J].计算机仿真,2014,31(5):143-146.

[13] HOLLAND J H.Adaptation in natural and artificial systems[M]//Adaptation in natural and artificial systems.Cambridge,MA,USA:MIT Press,1975.

[14] 葛显龙,辜羽洁,谭柏川.基于第三方带软时间窗约束的车辆路径问题研究[J].计算机应用研究,2015,32(3):689-693.

[15] 易荣贵,罗大庸.基于遗传算法的物流配送路径优化问题研究[J].计算机技术与发展,2008,18(6):13-15.