论文部分内容阅读
摘要：文章在建立配送车辆路径优化问题数学模型的基础上，构造了遗传算法来求解该问题，并在算法中引入了自然选择、交叉操作、变异操作等思想。实验结果表明，此算法可以有效求得车辆路径问题的优化解或近似优化解，是求解车辆路径问题的一个较好的方案。
关键词：配送；路径优化；遗传算法
中图分类号：F252文献标识码：A文章编号：1002-3100(2007)10-0033-04
Abstract: On the basis of the mathematic model for logistics distribution VRP, this paper presents Genetic Algorithm（GA）to solving this problem, and has led into idea such as natural selection, interlace operation, dissociation operation in the algorithm. This algorithm can find the optimal or nearly optimal solution to the vehicle routing problem effectively, which is proved by the number experiment provided by this paper.
Key words: distribution; routing optimizing; Genetic Algorithm
0引言
物流配送路径优化问题，即所谓的车辆路径问题（Vehicle Routing Problem，VRP）最早是由Dantzig和Ramser于1959年提出的，属于典型的复杂组合优化问题。其研究的问题可以描述为：有n个商品需求点（可以称之为顾客），各个顾客之间的距离以及商品需求量事先已知，要求从中心仓库（或称为配送中心）最多用k辆车来运输商品，每辆车载重量一定，使得运输路程最短并满足所有顾客的需求。车辆路径问题的研究具有应用的广泛性和经济上的重大价值，受到国内外学者的广泛关注。
由于车辆路径问题是NP完全问题，随着顾客数量的增加，其解呈指数级增长，用精确算法很难求得最优解。因此, 用启发式算法求解该问题就成为人们研究的一个重要方向，遗传算法（Genetic Algorithm，GA）是由J.H.Holland等于20世纪70年代发展起来的。它抽象于生物体的进化过程，是一种以自然选择和遗传理论为基础，将生物进化过程中适者生存规则与同一群染色体的随机信息变换机制相结合的搜索算法。其通过给解向量编码、形成初始种群，然后用变异、交叉重组、自然选择等算子，进行并行迭代，求得优化解。由于它采用随机选择，对搜索空间无特殊要求，无需求导，具有运算简单、收敛速度快等优点，尤其适用于处理传统搜索方法难于解决的复杂和非线性的问题，目前已广泛应用于组合优化、机器学习、自适应控制等领域。为此，本文研究运用GA编码构造求解车辆路径问题的算法，并对其运算过程和结果进行分析。实验数据表明本算法行之有效，不失为一种求解车辆路径问题的性能优越的启发式算法。
1VRP优化问题的数学模型
VRP可以描述为：有多个商品需求点（可以称之为顾客），各个顾客之间的距离以及商品需求量事先已知，要求从中心仓库（或称为配送中心）最多用k辆车来运输商品，每辆车载重量一定，要求合理安排车辆配送路线，使目标函数得到优化，并满足以下条件：（1）每条配送路径上各客户的需求量之和不超过配送车辆的载重量；（2）每条配送路径的长度不超过配送车辆一次配送的最大行驶距离；（3）每个客户的需求必须满足，且只能由一台配送车辆送货。
2VRP优化问题的遗传算法
2.1遗传算法的基本原理
在自然进化中，每一物种越来越适应环境；物种的个体的基本特征被其后代所继承，但后代又不完全同于自己的父代；个体的性质是由染色体决定的，染色体是由基因有序排列组成的；由染色体决定的个体对环境有不同的适应性，通过基因杂交和基因突变产生适应性强的个体；在世代进化中，“适者生存”的自然选择的强制作用，使得更能适应环境的个体的特征（对应适应值高的基因结构）被保存下来。GA正是基于自然选择和自然遗传这种生物进化机制的搜索算法，把优化问题的解的搜索空间映射为遗传空间，把每一可能的解编码为一个称为染色体的二进制串（也有其它编码方法），染色体的每一位称为基因。每个染色体（对应一个个体）代表一个解，一定数量的个体组成群体。GA首先随机地产生一些个体组成初始群体（即问题的一群候选解），按预先根据目标函数确定的适应度函数计算各个体的对问题环境的适应度，再根据个体适应度对个体对应的染色体进行选择，抑制适应度低的染色体，弘扬适应度高的染色体，然后进行交叉、变异等遗传操作产生进化了的一代群体。如此反复操作，一代一代不断向更优解方向进化，最后得到满足某种收敛条件的最适应问题环境的群体，从而获得问题的最优解。
如图1是一个使用选择（再生）、交换和突变三种遗传操作的GA。
选择：其过程为，基于个体对环境的适应度（由f∑f决定，其中f是对象函数值，∑f是群体里所有对象函数值的和），决定哪个个体被复制。选择意味着较高对象函数值的个体，有较大的概率在下一代提供一个或多个后代。
为了能使算法收敛到全局最优，遗传群体应具有一定规模，但为了保证计算效率，群体规模也不能太大。在初始化染色体时，先生成k個分仓库的一个全排列，再将m+1个0随机插入排列中。需要注意的是，必须要有两个0被安排在排列的头部和尾部，并且在排列中不能有连续的两个0。这样就构成一条满足问题需要的染色体，重复这一过程，直至生成满足群体规模数的染色体。
2.2.2计算适应度函数
对于某个个体所对应的配送路径方案，要判定其优劣，一是要看其是否满足配送的约束条件；二是要计算其目标函数值（即各条配送路径的长度之和）。根据配送路径优化问题的特点所确定的编码方法，隐含能够满足每个需求点都得到配送服务及每个需求点仅由一辆汽车配送的约束条件，但不能保证满足每条路径上各需求点需求量之和不超过汽车载重量及每条配送路线的长度不超过汽车一次配送的最大行驶距离的约束条件。
为此，对每个个体所对应的配送路径方案，要对各条路径逐一进行判断，看其是否满足上述两个约束条件，若不满足，则将该条路径定为不可行路径，最后计算其目标函数值。对于某个个体j，设其对应的配送路径方案的不可行路径数为Mj（Mj=0表示该个体对应一个可行解），其目标函数值为Zj，则该个体的适应度Fj可用下式表示
Fj=1Zj+MjG（9）
式中，G为对每条不可行路径的惩罚权重, 可根据目标函数的取值范围取一个相对较大的正数。
2.2.3自然选择
根据计算父代和子代的适应度，并将每代群体中的N个个体按适应度由大到小排列，排在第一位的个体性能最优，将它复制一个直接进入下一代，并排在第一位。下一代群体的另N-1个个体需要根据前代群体的N个个体的适应度，采用轮盘赌选择法产生。
2.2.4交叉操作实现
（1）随机在父代个体中选择一个交配区域，如两父代个体及交配区域选定为：A=47|8563|921，B=83|4691|257；
（2）将B的交配区域加到A的前面，A的交配区域加到B的前面，得：A'=4691|478563921，B'=8563|834691257；
（3）在A'、B'中自交配区域后依次删除与交配区相同的自然数，得到最终的两个体为：A"=469178532，B"=856349127。
与其他交叉方法相比，这种方法在两父代个体相同的情况下仍能产生一定的变异效果，这对维持群体的多样性有一定的作用。
2.2.5变异操作实现
2.2.6结束条件
当算法的当前进化代数小于预先设定的N时，返回3.2.2计算适应度函数部分，算法继续。
3实例计算及结果分析
3.1实例计算
3.2实例计算结果分析
从表中数据可以看出，应用遗传算法求解VRP时，得到最终的配送路径方案为：路径1：0-4-7-6-0；路径2：0-2-8-5-3-1-0，而且第4次还得到了该问题的最优解67.5 km。然而用节约法再对其进行求解，得到的最终配送路径方案为：路径1：0→6→5→7→3→0，路径2：0→4→8→2→1→0，并且得到相应运输距离为79.5km。
由表中数據可见，应用遗传算法得到的10次运行结果均优于节约法所得的结果79.5 km。所以说，应用遗传算法进行配送路径优化的方案，既能满足车辆容量约束又满足了各客户的货物需求，是上述车辆路径问题的一个可行解，而且利用遗传算法可以方便有效地求得VRP的最优解或近似最优解（满意解）。
4结论
在物流配送系统中，合理选择配送路径是提高服务质量、降低配送成本、提高经济效益的重要手段。但是由于VRP本身的NP完全性质，要精确求解非常困难，因此，研究启发式算法不失为一种可行的研究方向。
本文在建立VRP数学模型的基础上，通过对VRP优化问题的分析，提出了构造求解VRP的遗传算法，在算法中设计的个体编码方法、个体适应度计算方法及选择、交叉、变异算子，对解决类似的组合优化问题具有一定的参考价值。实验计算结果表明本算法是一种性能较好的启发式搜索方法, 利用该方法可以较快地找到问题的优化解或近似优化解，是求解车辆路径问题的一个较好的方案。
参考文献：
[1] 李军，郭耀煌. 物流配送车辆优化调度理论与方法[M]. 北京：中国物资出版社，2001.
[2] 李军，谢秉磊，郭强. 非满载车辆调度问题的遗传算法[J]. 系统工程理论方法应用，2000(3):235-239.
[3] 李敏强，寇纪淞,等. 遗传算法的基本理论与应用[M]. 北京：科学出版社，2003.
[4] 姜大立，杨西龙，杜文,等. 车辆路径问题的遗传算法研究[J]. 系统工程理论与实践，1999,19(6):40-45.
[5] 郎茂祥. 基于遗传算法的物流配送路径优化问题研究[J]. 中国公路学报，2002,15(3):76-79.
[6] 李向阳. 遗传算法求解VRP问题[J]. 计算机工程与设计，2004,25(2):271-276.
[7] 唐坤. 车辆路径问题中的遗传算法设计[J]. 东华大学学报：自然科学版，2002,28(1):66-70.
注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”
关键词：配送；路径优化；遗传算法
中图分类号：F252文献标识码：A文章编号：1002-3100(2007)10-0033-04
Abstract: On the basis of the mathematic model for logistics distribution VRP, this paper presents Genetic Algorithm（GA）to solving this problem, and has led into idea such as natural selection, interlace operation, dissociation operation in the algorithm. This algorithm can find the optimal or nearly optimal solution to the vehicle routing problem effectively, which is proved by the number experiment provided by this paper.
Key words: distribution; routing optimizing; Genetic Algorithm
0引言
物流配送路径优化问题，即所谓的车辆路径问题（Vehicle Routing Problem，VRP）最早是由Dantzig和Ramser于1959年提出的，属于典型的复杂组合优化问题。其研究的问题可以描述为：有n个商品需求点（可以称之为顾客），各个顾客之间的距离以及商品需求量事先已知，要求从中心仓库（或称为配送中心）最多用k辆车来运输商品，每辆车载重量一定，使得运输路程最短并满足所有顾客的需求。车辆路径问题的研究具有应用的广泛性和经济上的重大价值，受到国内外学者的广泛关注。
由于车辆路径问题是NP完全问题，随着顾客数量的增加，其解呈指数级增长，用精确算法很难求得最优解。因此, 用启发式算法求解该问题就成为人们研究的一个重要方向，遗传算法（Genetic Algorithm，GA）是由J.H.Holland等于20世纪70年代发展起来的。它抽象于生物体的进化过程，是一种以自然选择和遗传理论为基础，将生物进化过程中适者生存规则与同一群染色体的随机信息变换机制相结合的搜索算法。其通过给解向量编码、形成初始种群，然后用变异、交叉重组、自然选择等算子，进行并行迭代，求得优化解。由于它采用随机选择，对搜索空间无特殊要求，无需求导，具有运算简单、收敛速度快等优点，尤其适用于处理传统搜索方法难于解决的复杂和非线性的问题，目前已广泛应用于组合优化、机器学习、自适应控制等领域。为此，本文研究运用GA编码构造求解车辆路径问题的算法，并对其运算过程和结果进行分析。实验数据表明本算法行之有效，不失为一种求解车辆路径问题的性能优越的启发式算法。
1VRP优化问题的数学模型
VRP可以描述为：有多个商品需求点（可以称之为顾客），各个顾客之间的距离以及商品需求量事先已知，要求从中心仓库（或称为配送中心）最多用k辆车来运输商品，每辆车载重量一定，要求合理安排车辆配送路线，使目标函数得到优化，并满足以下条件：（1）每条配送路径上各客户的需求量之和不超过配送车辆的载重量；（2）每条配送路径的长度不超过配送车辆一次配送的最大行驶距离；（3）每个客户的需求必须满足，且只能由一台配送车辆送货。
2VRP优化问题的遗传算法
2.1遗传算法的基本原理
在自然进化中，每一物种越来越适应环境；物种的个体的基本特征被其后代所继承，但后代又不完全同于自己的父代；个体的性质是由染色体决定的，染色体是由基因有序排列组成的；由染色体决定的个体对环境有不同的适应性，通过基因杂交和基因突变产生适应性强的个体；在世代进化中，“适者生存”的自然选择的强制作用，使得更能适应环境的个体的特征（对应适应值高的基因结构）被保存下来。GA正是基于自然选择和自然遗传这种生物进化机制的搜索算法，把优化问题的解的搜索空间映射为遗传空间，把每一可能的解编码为一个称为染色体的二进制串（也有其它编码方法），染色体的每一位称为基因。每个染色体（对应一个个体）代表一个解，一定数量的个体组成群体。GA首先随机地产生一些个体组成初始群体（即问题的一群候选解），按预先根据目标函数确定的适应度函数计算各个体的对问题环境的适应度，再根据个体适应度对个体对应的染色体进行选择，抑制适应度低的染色体，弘扬适应度高的染色体，然后进行交叉、变异等遗传操作产生进化了的一代群体。如此反复操作，一代一代不断向更优解方向进化，最后得到满足某种收敛条件的最适应问题环境的群体，从而获得问题的最优解。
如图1是一个使用选择（再生）、交换和突变三种遗传操作的GA。
选择：其过程为，基于个体对环境的适应度（由f∑f决定，其中f是对象函数值，∑f是群体里所有对象函数值的和），决定哪个个体被复制。选择意味着较高对象函数值的个体，有较大的概率在下一代提供一个或多个后代。
为了能使算法收敛到全局最优，遗传群体应具有一定规模，但为了保证计算效率，群体规模也不能太大。在初始化染色体时，先生成k個分仓库的一个全排列，再将m+1个0随机插入排列中。需要注意的是，必须要有两个0被安排在排列的头部和尾部，并且在排列中不能有连续的两个0。这样就构成一条满足问题需要的染色体，重复这一过程，直至生成满足群体规模数的染色体。
2.2.2计算适应度函数
对于某个个体所对应的配送路径方案，要判定其优劣，一是要看其是否满足配送的约束条件；二是要计算其目标函数值（即各条配送路径的长度之和）。根据配送路径优化问题的特点所确定的编码方法，隐含能够满足每个需求点都得到配送服务及每个需求点仅由一辆汽车配送的约束条件，但不能保证满足每条路径上各需求点需求量之和不超过汽车载重量及每条配送路线的长度不超过汽车一次配送的最大行驶距离的约束条件。
为此，对每个个体所对应的配送路径方案，要对各条路径逐一进行判断，看其是否满足上述两个约束条件，若不满足，则将该条路径定为不可行路径，最后计算其目标函数值。对于某个个体j，设其对应的配送路径方案的不可行路径数为Mj（Mj=0表示该个体对应一个可行解），其目标函数值为Zj，则该个体的适应度Fj可用下式表示
Fj=1Zj+MjG（9）
式中，G为对每条不可行路径的惩罚权重, 可根据目标函数的取值范围取一个相对较大的正数。
2.2.3自然选择
根据计算父代和子代的适应度，并将每代群体中的N个个体按适应度由大到小排列，排在第一位的个体性能最优，将它复制一个直接进入下一代，并排在第一位。下一代群体的另N-1个个体需要根据前代群体的N个个体的适应度，采用轮盘赌选择法产生。
2.2.4交叉操作实现
（1）随机在父代个体中选择一个交配区域，如两父代个体及交配区域选定为：A=47|8563|921，B=83|4691|257；
（2）将B的交配区域加到A的前面，A的交配区域加到B的前面，得：A'=4691|478563921，B'=8563|834691257；
（3）在A'、B'中自交配区域后依次删除与交配区相同的自然数，得到最终的两个体为：A"=469178532，B"=856349127。
与其他交叉方法相比，这种方法在两父代个体相同的情况下仍能产生一定的变异效果，这对维持群体的多样性有一定的作用。
2.2.5变异操作实现
2.2.6结束条件
当算法的当前进化代数小于预先设定的N时，返回3.2.2计算适应度函数部分，算法继续。
3实例计算及结果分析
3.1实例计算
3.2实例计算结果分析
从表中数据可以看出，应用遗传算法求解VRP时，得到最终的配送路径方案为：路径1：0-4-7-6-0；路径2：0-2-8-5-3-1-0，而且第4次还得到了该问题的最优解67.5 km。然而用节约法再对其进行求解，得到的最终配送路径方案为：路径1：0→6→5→7→3→0，路径2：0→4→8→2→1→0，并且得到相应运输距离为79.5km。
由表中数據可见，应用遗传算法得到的10次运行结果均优于节约法所得的结果79.5 km。所以说，应用遗传算法进行配送路径优化的方案，既能满足车辆容量约束又满足了各客户的货物需求，是上述车辆路径问题的一个可行解，而且利用遗传算法可以方便有效地求得VRP的最优解或近似最优解（满意解）。
4结论
在物流配送系统中，合理选择配送路径是提高服务质量、降低配送成本、提高经济效益的重要手段。但是由于VRP本身的NP完全性质，要精确求解非常困难，因此，研究启发式算法不失为一种可行的研究方向。
本文在建立VRP数学模型的基础上，通过对VRP优化问题的分析，提出了构造求解VRP的遗传算法，在算法中设计的个体编码方法、个体适应度计算方法及选择、交叉、变异算子，对解决类似的组合优化问题具有一定的参考价值。实验计算结果表明本算法是一种性能较好的启发式搜索方法, 利用该方法可以较快地找到问题的优化解或近似优化解，是求解车辆路径问题的一个较好的方案。
参考文献：
[1] 李军，郭耀煌. 物流配送车辆优化调度理论与方法[M]. 北京：中国物资出版社，2001.
[2] 李军，谢秉磊，郭强. 非满载车辆调度问题的遗传算法[J]. 系统工程理论方法应用，2000(3):235-239.
[3] 李敏强，寇纪淞,等. 遗传算法的基本理论与应用[M]. 北京：科学出版社，2003.
[4] 姜大立，杨西龙，杜文,等. 车辆路径问题的遗传算法研究[J]. 系统工程理论与实践，1999,19(6):40-45.
[5] 郎茂祥. 基于遗传算法的物流配送路径优化问题研究[J]. 中国公路学报，2002,15(3):76-79.
[6] 李向阳. 遗传算法求解VRP问题[J]. 计算机工程与设计，2004,25(2):271-276.
[7] 唐坤. 车辆路径问题中的遗传算法设计[J]. 东华大学学报：自然科学版，2002,28(1):66-70.
注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”