物流配送途径优化问题研讨

1.前言

1.1问题描述与研究意义

物流配送运输指的是短途运输，适合多客户、小批量的货物运输。虽然配送路线比较固定，但由于同一路线往返次数较多，即使一次节约的费用不多，但由于运输次数多，总费用也能降低很多，所以合理的规划配送路线对运输成本的影响较大。在物流配送中存在多种优化策略，但是车辆配送路径优化问题是其中较关键的一个，选择合理有效的车辆路径方案，尽量减少车辆的配送里程数，有利于节约时间和运输成本。

1.2本文主要工作

物流配送的一个重要方面是，力争实现车辆行驶里程最短、运输总费用最低等目标。针对车辆路径优化这一典型的NP难题，本文运用遗传算法来求解该问题的最优解。本文使用图和边来表示路径问题，任意边的权重为两个端点的欧几里得距离。图中的结点代表城市，用数字1到n编号，d(Ci,Ci+1)表示城市Ci到城市Ci+1的距离，其中Ci、Ci+1坐标分别为(xi,yi)，(xi+1,yi+1)。另外数字0代表配送中心的出发点C。物流配送的路径问题就是搜索整数子集x={0,1,2,3,…,n}的一个排列{C,C1,C2,C3,…,Cn}，需要使目标函数总路径距离dis（C）取最小值。其中，dis（C）=d(C,Ci)+∑i=1n-1d(Ci,Ci+1)+d(C,Cn)d(Ci,Ci+1)=(xi-xi+1)2-(yi-yi+1)2。

2.遗传算法基本原理概述

遗传算法（GA—GeneticAlgorithm）是模拟生物自然选择和遗传学机理的生物进化过程的计算模型，按照“优胜劣汰，适者生存”的原则对目标函数进行优化。经过多次迭代计算，得到最优结果。它最初由美国Michigan大学J.Holland教授于1975年提出来。GA涉及到五大要素：编码、初始种群的设定、适应度函数的设计、遗传操作的设计和控制参数的设计。五大要素中最重要的是参数编码和遗传操作的设计。参数编码决定了算法的计算效率，遗传操作决定了算法的优化成功与否。遗传操作主要由三部分组成：选择(selection)、交叉(crossover)和变异(mutation)。

2.1编码

经典GA编码多采用二进制表示形式。另外，在实际应用中还有多种编码形式：动态参数编码、实数编码、整数和字母排列编码等。

2.2初始种群的设定

初始种群的设定是由于GA的群体型操作需要。为遗传操作准备一个由若干初始解组成的初始群体。通常初始种群采用随机生成的形式，数量一般要根据染色体的长度而定。

2.3适应度函数的设计

GA在搜索进化过程中用评估函数值来评估个体或解的优劣，并作为以后遗传操作的依据。评估函数值又称为适应度(fitness)。因此，适应度函数就是我们要优化的指标函数。

2.4遗传操作的设计

①选择选择提供了GA的驱动力。主要的选择方式有：适应值比例选择、联赛选择、精英选择等。适应值比例选择是最基本的选择方法，其中每个个体被选择的期望数量与其适应值和群体平均适应值的比例有关，通常采用赌的方式实现。这种方式首先计算每个个体的适应值，然后计算出此适应值在群体适应值总和中所占的比例，表示该个体在选择过程中的概率。②交叉操作交叉操作是GA具备的原始性的独有特征，是模仿自然界有性繁殖的基因重组过程，其作用在于将原有的优良基因模式遗传给下一代个体，并生成包含更复杂基因结构的新个体。③变异操作变异操作模拟自然界生物进化中染色体上某一位基因发生的突变现象，从而改变了染色体的结构和物理性状。在GA中，变异算子通过按变异概率，随机反转某一位等位基因的二进制字符值来实现。

2.5控制参数的设计

①交叉概率一般在0.7～0.85之间，通常用Pc表示。主要的交叉方法有：单点交叉、多点交叉、均匀交叉、洗牌交叉等。单点交叉的染色体长n时，可能有n-1个不同的交叉。交叉的过程分为两步：随机产生交叉点；对匹配的位串进行交叉繁殖，产生新位串。②变异概率一般在0.001～0.1之间，通常用Pm表示。变异是防止因过渡成熟而丢失重要信息的保险策略，可起到恢复位串字符多样性的作用，并可以适当提高GA的搜索效率。

2.6GA的运行过程

GA的运行过程是一个迭代过程，其必须完成的工作内容的基本步骤如下：

(1)选择编码策略；

(2)定义适应度函数f(x)；

(3)参数初始化，包括选择群体大小，迭代次数，确定选择、交叉、变异方法，以及确定交叉概率Pc、变异概率Pm等遗传参数；

(4)随机初始化生成群体P；

(5)计算群体中个体解码后的适应度f(x)；

(6)按照遗传策略，运用选择、交叉和变异算子作用于群体，形成下一代，保留最好解；

(7)迭代，判断群体性能是否满足指标或达到迭代次数，不满足则返回(6)；满足则转到(8)；

(8)获得最优解，计算结束。

3.GA在物流配送路径问题中的应用

3.1编码策略

用GA求解物流配送的路径问题，编码的方式很重要。这里采用自然数编码的方法，即直接采用城市在路径中的位置来表示，例如有六个城市，配送顺序为：0-2-4-5-6-1-3-0，编码表示成()，其表示的一条配送路线，是从配送中心出发，依次经过城市2、4、5、6、1、3，最后回到配送中心。这种编码方法自然、直观，路径表示易于加入启发式信息，便于遗传交叉操作。在保证较好性能的同时，还可以简化找出最优染色体后解码的过程，减小计算量。

3.2确定适应度函数

为了将解物流配送的路径问题空间转到GA空间中，首先要确定适应度函数，将一个合法的城市序列S=（C,C1,C2,C3,…,Cn,C）作为一个个体。这个序列中相邻两城之间的距离的总和的倒数就可作为相应个体S的适应度，适应度函数为f(S)=1dis(C)。

3.3选择算子

使用赌选择法，定义某一染色体被选中的概率Pc（选择概率）为Pc=f(xi)/∑f(xi)。式中xi为种群中第i个染色体对应的数字串，f(xi)是第i个染色体的适应度值，∑f(xi)是种群中所有染色体的适应度值之和。在GA中，整个群体被各个个体所分割，各个个体的适应度占全部个体的适应度值总和的比例大小不一，以比例分配整个赌盘盘面，盘面大小代表个体下一代群体遗传上一代各个个体的概率。在赌选择方法中，个体适应度高低按比例转化为选中概率，适应度低的个体就可能被淘汰，而适应度高的个体被选中的几率就大。

3.4交叉策略

本文使用单点交叉操作。例如：设城市数目为5，设种群里的其中两个个体：P1=0123450，P2=0152430，如图1所示（两点间的数值为距离）。它们产生的子代分别是C1和C2。首先随机选择一个交叉位，接着父代各自保留左边的部分，右边的部分交换，则产生了两个子代。若有重复的基因（最后一位除外），那么要进行修正。例如选择第四位，C1''''=0123430，C2''''=0152450，修正后分别为C1=0125430，C2=0132450。3.5变异策略这里采用换位变异操作，随机选择两个城市（配送中心除外），然后把这两个城市进行换位。例如：对于个体(0123450)，若随机选择城市1和城市4，则换位后的新个体为（0423150）。3.6初始化设种群大小N=50，交叉概率Pc=0.9，变异概率Pm=0.1，迭代次数T=100。3.7算法的步骤step1：读入城市的坐标数据以及控制参数种群规模N和终止的迭代次数T；step2：计算城市间的距离，形成一个城市距离二维矩阵dn×n；step3：随机生成初始种群，N个个体分别为：S1{C,C1'''',C2'''',C3'''',…,Cn'''',C}，S2{C,C1'''''''',C2'''''''',C3'''''''',…,Cn'''''''',C}，S3{C,C1'''''''''''',C2'''''''''''',C3'''''''''''',…,Cn'''''''''''',C}……计算各个体的适应度，f(Si)=1dis(Ci)（i=1,2,3,…,N），将个体按照适应度降序排列。初始化终止进化代数计数器t=0；step4：根据交叉概率Pc，选择父代进行交叉操作以及按变异概率Pm，随机抽取个体进行变异操作，产生下一代种群，并计算出其个体的适应度，保留当前代最好解；step5：终止进化代数计数器t加1；如果t小于T，转step4；如果t大于T，停止迭代，转step6；step6：在当前种群中获得该问题的最优解，计算结束。

4.数据实验

4.1实验环境

CPU：IntelCoreT64002.0G；内存：2G；操作系统：WindowsXPSP3；编译工具：MicrosoftVisualC++6.0。

4.2实验数据该实验中，各控制参数分别为：种群大小N=50，交叉概率Pc=0.9，变异概率Pm=0.1，迭代次数T=100。上面的实验截图，表示从第1至第100代的运行结果，每一代中的50个个体的行车路线以及各自的总路径距离。

4.3实验分析经过多次实验发现，本文的实验数据再迭代40次左右，结果就趋于稳定，达到最优解。

5.结束语

本文运用了遗传算法来求解物流配送路径优化问题，进行了遗传算法的设计、编程和数据仿真研究等，经多次实验测试，计算得出了实际问题的最优解，且效率比较高，说明遗传算法是求解路径优化问题的一种有效方法。