基于改进自适应遗传算法的物流配送路径优化研究

吴 聪，陈侃松，姚 静

(湖北大学 计算机与信息工程学院物联网工程研究所， 武汉 430062)

0 引言

车辆的路径问题是物流配送中的核心问题，合理地规划物流运输过程中的车辆路径能为企业降低生产成本，提高企业市场竞争力。带软时间窗的车辆路径问题(vehicle routing problem with soft time windows，VRPSTW)，是指在满足车辆容量不超过核载容量和规定时间范围等约束条件的前提下，合理规划车辆运输路径，使物流配送过程中产生的费用最低。

遗传算法是一种智能进化算法，它具有全局搜索能力强，算法灵活，计算速度快等优势[1]，被广泛应用于求解物流配送路径优化问题[2]，但其存在初始种群的随机性强，个体分布比较分散，同时局部搜索能力差，搜索到全局最优解附近时收敛速度变慢，容易出现未成熟收敛，陷入局部最优[3]等缺点，为克服这些缺陷sriniva[4]等人提出了自适应遗传算法，搜索过程中交叉概率和变异概率根据进化的情况进行自适应调整[5]。任子武[6]等人对传统的自适应遗传算法进行改进，遗传参数随适应度的大小自适应调整，算法的收敛速度和收敛精度得到了一定的提高，但该方法对适应值小于平均适应值的劣质个体的处理方式单一，算法进化到晚期还是存在种群中个体多样性降低，收敛速度变慢的缺点，针对这些问题本文提出新的改进自适应遗传算法，对遗传参数的自适应调整方案进行改进，并利用该方法来求解VRPSTW问题。

1 数学模型的建立

VRPSTW问题的优化目标是在满足车辆容量不超过核载容量和规定时间范围等约束条件的前提下，优化车辆运输路径，使物流配送过程中产生的费用最低，费用函数可表示如下：

Z=P+P(t)+P(q)

(1)

其中:P为车辆配送过程中产生的费用，P(t)表示配送车辆超出时间窗范围产生的惩罚费用，P(q)表示超过车辆的核载容量产生的惩罚费用。车辆在运输过程中必须满足以下约束条件：

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

t0≥e0

(10)

(11)

其中:N为客户编号，K为车辆数，Qk为每辆车的限制容量，e0为每辆车开始工作的时间，I0为每辆车最晚回到配送中心的时间，tij为从客户i到客户j的时间，si表示在客户i的服务时间，wi表示在客户i的等待时间。

式(2)～ 式(3)表示车辆服务的规则；式(4)～式(11)是VRPSTW的约束条件。式(4)表示K辆车生成K条配送路线，并且是从配送中心出发，最终回到配送中心，式(5)表示每辆车只给一个客户i配送一次货物，式(6)～(7)表示的是每辆车只能从一个边进一个边出，式(8)表示每辆车每条路径上送货的总重量不超过最大容量，式(9)表示每辆车的行驶的总时间不超过最终回配送中心的限制时间，式(10)表示车辆要在开始工作时间之后出发晚，式(11)表示每个客户规定的服务时间窗。

为了保证遗传操作生成的染色体是有效的，需要将相应的约束条件设计成惩罚函数[7]，如果配送车辆超出时间窗范围或者超过车辆的核载容量，就会进行相应的惩罚[8]。

1) 时间惩罚函数：

(12)

c1，c2为早到和晚到的时间惩罚系数，ei为客户要求的最早服务时间，ti为车辆到达客户i的时间，li为客户i要求的最晚服务时间。

2) 容量惩罚函数：

P(q)=c0max(0,(qiyik-Q))

(13)

c0为超过核载容量的惩罚系数,qi表示客户i的货物需求量Q表示车辆的限制容量。

由此，得到物流路径优化问题的目标函数如下：

{c1max[0,(ei-ti)]+c2max[0,(ti-li)]}

(14)

其中:p0为车辆发车所需要的费用，p为单位里程所产生的费用，dij为车辆从客户i到客户j的路程。

配送路径方案的优劣是由适应度来评价的[9]，适应度值越大方案越优，目标函数值越小，这里选择目标函数的倒数作为适应度函数，如下：

f=1/Z

(15)

2 自适应遗传算法的改进

2.1 基本自适应遗传算法

自适应遗传算法在进行搜索的过程中交叉概率和变异概率会根据进化的情况进行自适应调整[10]。传统的自适应遗传算法(AdaptiveGeneticAlgorithm，AGA)是由sriniva等人提出的。其中交叉概率和变异概率的自适应调整公式如下：

(16)

(17)

其中:fmax为所有个体适应值中最大的适应值，favg为所有个体的平均适应值f为要变异个体的适应值f’为准备交叉的两个个体中较大的适应值，系数k1，k2，k3，k4取(0,1)区间的值。

由式中可以看出,fmax—favg越大，即种群中个体适应度比较分散时，则pc、pm比较小；如果fmax—favg越小，即种群中的个体适应度比较集中时，则pc、pm越大，pc和pm会根据个体的适应度值自适应调整。

但是AGA也存在缺点：一方面由于传统的自适应交叉和变异概率主要取决于取值为(0,1)的随机系数k1，k2，k3，k4，随机性比较大，影响了遗传算法的种群个体质量，可能会导致遗传算法陷入局部最优；另一方面，f’=fmax或者f=fmax时，即交叉和变异的个体适应度达到最高适应度时，交叉概率和变异概率为0，种群个体会处于停滞不前的状态。

针对AGA的缺点，任子武等人提出了改进自适应遗传算法，公式如下：

(18)

(19)

式中,fmax为所有个体适应度值中最大的适应值，favg为所有个体的平均适应值，f为要变异个体的适应值，f’为要交叉的个体中比较大的适应度,pc1>pc2,pm1>pm2, 取(0,1)区间的值，可在优化过程中调整。

以上改进后pc和pm不仅可以随适应度的大小自适应调整，而且，若f’=fmax，则pc=pc2，若f=fmax，则pm=pm2，不存在最大适应度个体的pc和pm为0的情况。

但该算法还有如下缺点：

1) 该算法没有对劣质个体进行处理，当个体的适应度小于平均适应度时，pc和pm为设定的固定值。

2) 随着算法进化到晚期，虽然个体的适应度都比较高，但是个体之间趋于相似，种群中个体多样性降低，收敛速度慢，进行交叉操作已经没有意义。

2.2 自适应遗传算法的改进

下文针对传统自适应遗传算法和经典的改进自适应遗传算法的缺点提出了新的自适应遗传算法(new improved adaptive genetic algorithm，NIAGA)如下：

2.2.1 选择算子的改进

首先，将种群中所有个体的适应度按从大到小的顺序进行排列，新种群中有1/2的个体直接复制初始种群中适应度最高的个体而产生，剩下的个体采用轮盘赌的方式进行选择；然后，将选择的个体组合成新的种群，并将新种群中所有个体的适应度按从大到小的顺序排列，选择出适应度最高的个体保存下来；最后完成遗传算法的所有操作，生成新的种群，如果新种群中适应度最高的个体适应度值比旧种群中保存的适应度值低，那么就用旧种群中适应度值最高的个体替代新种群中适应度最低的个体。

按以上改进方法进行选择操作，不仅在种群个体的总数目没有改变的前提下增加了适应高的个体比率，保持了种群中个体的多样性；还在一定程度上解决了轮盘赌选择法种群单一随机化和容易陷入局部最优的缺陷。

2.2.2 交叉算子和变异算子的改进

由于交叉概率和变异概率是进行交叉和变异操作的重要参数，对遗传算法的搜索能力有很大影响，而基本遗传算法的交叉概率和变异概率是设定的固定值，缺乏理论依据。本文提出了新的自适应遗传算法，它的交叉概率和变异概率会根据适应度，进化代数和进化过程中最优解没有改变的个体数目的变化而自适应调整。不仅可以增加算法的收敛速度，还突出个体之间的差异以增加个体之间的竞争力。

根据传统和改进自适应遗传算法存在的问题，本文提出了交叉概率和变异概率根据适应度、进化代数和进化过程中个体未改变数目自适应调整的改进方法，交叉概率和变异概率变化公式如下：

(20)

(21)

进化初期，种群中的个体之间差异比较大，fmax—favg的值也比较大，此时进化代数t和进化过程中个体未改变数目S比较小，所以交叉概率pc比较大，种群收敛速度较快。进化后期，由于种群中个体之间的差异变小，个体之间相似度变高，收敛速度变慢，有陷入局部最优的趋势，fmax—favg的值变小，进化代数t和进化过程中个体未改变数目S变大，为了提高收敛效率，交叉概率pc变小，变异概率pm增加，提高了种群个体的多样性，充分显示了变异算子的局部搜索能力。经过改进的遗传算法在进化的过程中根据适应度大小、进化代数t和进化过程中个体未改变数目S自适应调整交叉和变异概率，不仅能保证交叉操作的全局搜索能力，并且能充分发挥变异操作的局部搜索能力。

3 改进自适应遗传算法在VRPSTW中的应用

改进遗传算法求解VRPSTW问题主要包括编码，种群初始化，求解适应度，选择，交叉，变异，终止条件判定等步骤。

3.1 参数设定

首先对实验参数设定如下：

种群规模：M=50

交叉概率：pc=0.6,pc1=0.6,pc2=0.3

变异概率：pm=0.01，pm1=0.01，pm2=0.002

终止代数：T=200

每辆车最大容量：Q=6000

发车成本：p0=100

考虑到司马相如写关中上林苑，未必也像左思写《三都赋》那样“稽之地图”“验之方志”，个别地方含糊带过也许只是文人寻常虚饰，那也还并不是特别值得批驳。但我们注意到，在关于上林苑的方位、界限这些基本的宏观地理指称多用含混虚夸之辞。

单位运输成本：p=10

车辆行驶速度：v=5

超载惩罚系数：c0= [0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10]

早到惩罚系数：c1= [0 5.0 6.0 14.0 5.0 4.0 4.0 8.0 5.0 3.0 6.0 15.0 8.0 7.0 15.0 5.0 4.0 6.0]

迟到惩罚系数：c2=[0 150 300 210 160 180 320 210 2700 220 180 210 2500 310 210 100 1500 180]

3.2 遗传操作

3.2.1 选择

采用精英保留策略和轮盘赌方法分别选择个体(路径)组成新的种群，该种群一共包含50条城市路径(即50条染色体)，首先对所有个体的适应度按从大到小的顺序进行排列，选择部分适应度最高的个体(所用费用最少的路径)，剩下的个体通过轮盘赌选择法选择，然后组合成的规模为50的新种群，将这50个个体按照适应度从大到小的顺序进行排列，将适应度最高的个体保存，然后进行交叉和变异操作，生成新的种群，如果新的种群中最高适应度小于旧种群中最高适应度，则用旧种群中适应度最高的个体代替新种群中适应度最低的个体。

3.2.2 交叉

本文采用两点交叉的方式进行交叉操作，首先随机选取两个交叉位点，对交叉点中间的基因模块进行交叉路径,比如：

交叉前

父代1：1 5 6 | 4 1 3 1 2 | 8 7 9 1

父代2：1 5 4 | 1 8 6 2 1 | 3 9 7 1

交叉后

子代1： 1 5 6 | 1 8 6 2 1 | 8 7 9 1

子代2： 1 5 4 | 1 8 6 2 1 | 3 9 7 1

3.2.3 变异

本文在用遗传算法求解VRPSTW问题的过程中，采用的是随机选择基因位点(城市编号)进行变异操作的，首先根据变异概率选中进行变异的个体(路径)，然后在该个体上随机选择两个基因位，最后将这两个基因位上的基因相互交换，形成新的个体。

变异前

父代： 1 5 6 | 4 1 3 1 2 | 8 7 9 1

变异后

子代： 1 5 6 | 8 1 3 1 2 | 4 7 9 1

4 仿真实验及结果分析

应用提出的算法解决如下物流路径问题：6辆车从1个配送中心出发，为17个客户提供配送服务。配送中心(城市编号为1)和17个客户所在城市坐标，每个客户的服务时间窗和货物需求量信息如表1所示。

根据配送过程中产生的费用和车辆行驶的路径来衡量NIAGA求解VRPSTW问题的优化效果。对比的算法是任子武等人提出了改进自适应遗传算法(improved adaptive genetic algorithm，简称IAGA)。设定进化代数为500，一共进行了5次实验，呈现的结果是求取5次实验结果的平均值。将IAGA和NIAGA求得的VRPSTW问题的实验结果进行对比，如表2所示。

表2 IAGA和NIAGA求解VRPSTW问题实验结果对比

从表中可以看出，NIAGA在求解VRPSTW问题的过程中所产生的费用比IAGA低很多，最短路径也小很多，更进一步验证了本文提出的改进遗传算法在求解VRPSTW问题中有明显优势。

为了更直观地对IAGA和NIAGA求解VRPSTW问题进行观察，取其中一次的IAGA和NIAGA求解VRPSTW问题的路径仿真图，并对其详细参数进行对比。如下：

图1 IAGA在VRPTW中应用的路径图

注：三角形表示的是配送中心，数字表示的是城市编号，小圆圈表示客户所在城市。
图2 NIAGA在VRPTW问题中应用的路径图

从图中可以看出，NIAGA的路径图比IAGA的路径图简单一些。其具体参数如表3所示。

表3 IAGA和NIAGA求解VRPSTW问题的最优解对比

从表中可以看出，NIAGA在求解VRPSTW问题与IAGA相比，求得的最优成本和行驶里程都比较小。其中，NIAGA求解最优路径中，每辆车的行驶路径及货物容量如表4所示。

表4 每辆车的行驶路径及货物容量

每辆车的核载总容量是6 000，由上表可以看出，本次NIAGA求解最优路径中，每辆车的载货容量都没有超过核载总容量。

由每个城市的坐标可以得出每两个城市之间的距离，根据车辆的行驶速度，可以得出每辆车在每两个城市之间的行驶时间，从而计算出车辆到达目的地的时间。与表4.1给出的时间窗进行对比，判断车辆是否满足约束条件。每辆车的具体路径长度及到达目的地的时间如表5 ～ 表10所示。

表5 车辆1的具体路径长度及到达目的地时间

表6 车辆2的具体路径长度及到达目的地时间

表7 车辆3的具体路径长度及到达目的地时间

表8 车辆4的具体路径长度及到达目的地时间

表9 车辆5的具体路径长度及到达目的地时间

表10 车辆6的具体路径长度及到达目的地时间

从表5 ～ 表10可以得出车辆1到达9号城市的时间是8.8548，但是9号城市的规定的服务时间窗是[7,8]；车辆6到达17号城市的时间是9.0424，而17号城市规定的服务时间窗是[7,9]。所以车辆1和车辆6到达时间都比规定时间晚，应该受到相应的惩罚。

从以上数据可以得出，NIAGA求解VRPSTW问题过程中，能够求出最优解，并且产生的费用和行驶路径距离都比IAGA小很多；同时车辆载重没有超过车辆容量的限制，但是还是有两辆车超过出时间窗的范围，产生了相应的惩罚费用，不过超出时间窗的值比较小，对求解最优解影响不是很大，可见NIAGA在求解VRPSTW问题上有很大的优势。

5 结语

本文提出一种改进的自适应遗传算法，对遗传参数的自适应调整方案进行改进，进化过程中交叉概率和变异概率根据适应度、进化代数和进化过程中个体未改变数目个数来自适应变化。将该算法应用于求解带软时间窗的物流运输车辆路径优化问题，结果与先前的改进自适应遗传算法进行比较，分析表明该算法能有效抑制遗传算法的“早熟”，优化精度更高，得到的优化结果更靠近全局最优。

[1] Holland J H. Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence [M]. MIT Press, 1992.

[2] Vehicle routing: problems, methods and applications[M]. Society for Industrial and Applied Mathematics, 2014.

[3] 葛继科,邱玉辉,吴春明, 等. 遗传算法研究综述[J]. 计算机应用研究, 2008, 25(10): 2911-2916.

[4] Holland J H. Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence[M]. MIT Press, 1992.

[5] 朱鳌鑫.遗传算法的适应度函数研究[J]. 系统工程与电子技术, 1998, 20(11): 58-62.

[6] 任子武,伞 冶.自适应遗传算法的改进及在系统辨识中应用研究[J].系统仿真学报, 2006, 18(1): 41-43,66.

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

[8] Solomon M M. Algorithms for the vehicle routing and scheduling problems with time window constraints[J]. Operations Research,1987，35(2)：254-265.

[9] Holland J L. Making vocational choices: A theory of vocational personalities and work environments [M]. Psychological Assessment Resources, 1997.