遗传算法在ＶＲＰ问题中的应用

张国英　林贤茂

摘要：配送是物流系统中一个直接与消费者相连的重要环节，对配送系统进行优化，可以提高物流经济效益、实现物流科学化，因此配送系统的优化问题显得尤为重要。进行配送系统优化，主要是配送车辆调度的优化。文章在全面分析研究物流配送业务特点的基础上，针对配送中的核心问题——车辆调度优化问题进行了深入的研究，建立了单源点物流配送车辆调度优化问题的数学模型，并运用遗传算法对其进行求解，仿真实例证明了该方法的有效性。

关键词：物流配送；车辆调度；遗传算法

中图分类号：U116.2文献标识码：A

Abstract: Distribution is an important link in logistics, which is joined to consumers directly. Vehicle Routing Problem（VRP）is the main part of optimizing the distribution system. It can advance the economic benefits and make logistics scientific. Firstly, the paper analyzes VRP, and sorts it according to given conditions. Secondly, it chooses a typical one to analyze. It sets a model of the problem, and settles it with a genetic algorithm that is fast and accurate. Lastly, the paper illustrates the process of using the method referred in the paper by an example.

Key words: distribution; VRP; genetic algorithm

0引言

物流配送车辆优化调度问题于1959年由Dantzig和Ramser提出，国外一般称之为Vehicle Routing Problem（VRP）[1]。车辆调度问题是指为服务于已知的一组顾客的一个车队，设计一组开始和结束于一个中心出发点的最小费用路径。每个顾客只能被服务一次，而且一个车辆服务的顾客数不能超过它的能力。VRP已被证明是一个NP问题。

VRP问题的研究起步较早，求解方法也非常丰富，基本上可以分为精确算法和启发式算法两大类[2]。由于VRP问题是强NP难题，高效的精确算法存在的可能性不大，所以寻找近似算法是必要和现实的，本论文在建设物流配送体系、改进遗传算法的应用等方面进行了新的探索与尝试，主要工作在于：

（1）将改进遗传算法应用于物流配送优化中实际问题的求解，并采用计算机语言完成对其算法的实现；

（2）通过实证分析，改进遗传算法用于物流配送优化的效果。

1问题描述

典型的VRP问题可以描述为：从某物流中心用多台配送车辆向多个客户送货，每个客户的位置和货物需求量一定，每辆配送车辆的载重量一定，其一次配送的最大行驶距离一定，要求合理安排车辆配送路线，使目标函数得到优化。

2扫描法和遗传算法介绍

制定从一个物流中心向多个用户运送货物的配送计划时，必须考虑每辆车的运载能力和行驶距离及时间等的限制。扫描法是一种能较好地解决配送路线问题的方法。

遗传算法最早由美国密切根大学（Michigan）的Holland教授提出，主要特点是群体搜索策略和群体（population）中个体（individual）之间的信息交换。它实际上是模拟由个体组成的群体的整体学习过程，其中每个个体对应研究问题的一个解。

鉴于以上算法的特点，本文将扫描法和遗传算法结合以来，将VRP问题转换为TSP问题求解，并且对传统的遗传算法进行改进。

3算法的设计

{输入车辆调度问题的己知条件：

输入运行参数，如群体规模N，终止进化代数T和最优染色体保留代数N，交叉概率pc，变异概率pm，执行变异操作时的基因换位次数J，对不可行路径的惩罚权重Pw等；

采用扫描法进行配送线路分区，确定每个客户点属于哪辆车，车辆编号为1-m；

Whilei≤mdo

随机产生初始化群体P0，当前进化代数t=0；

计算P0中每个个体的适应度；

whilet<指定进化终止代数Tdo

{将本代中适应度最高的个体复制一个，直接进入到新群体Pt+1中；

根据本代个体的适应度，计算群体内每个个体的选择概率pi；然后根据轮盘赌方式选择染色体复制到新群体Pt+1，使新群体的规模为N；

根据选择概率pc，从Pt+1中随机生成两条染色体作父代，交叉操作生成两条新染色体，计算四条染色体适应度，保留两条最优染色体在Pt+1中；

根据选择概率pm，从Pt+1中随机生成一条染色体作父代，变异操作生成新染色体，计算父代和子代染色体适应度，保留最优染色体在Pt+1中；

计算Pt+1中每个个体的适应度和成本；

t=t+1；

}

输出最优染色体的编码和染色体的成本；

i=i+1；

计算并输出各辆车最优染色体的成本和。

}

4仿真实验

实验：现假设有n个货物需求点和一个为这些需求点提供货物的配送中心，配送中心有m辆汽车用于各需求点的货物配送，每辆车的载重量皆为定值，假设车辆的容量为10 000，每个客户的需求为0~10 000/7的一个随机数。

通过实验遗传算法和节约型算法的比较（如表1所示），可知：

（1）采用首先扫描后遗传算法进行配送路径优化，随客户点的增加，计算时间有所增加，但是时间变化近似线性变化，而节约型的算法，随客户点的增加，计算时间呈几何级增长，当客户点在一千个左右的时候，运行时间超过半个小时；

（2）通过试验可以得出这样的结论：若车的容量一定，使每辆车配送的客户点一定，增加客户点的个数对程序运行时间影响不是很大。但是若每辆车的配送点增加，这样程序的运行时间会显著增加，当每辆车的客户点超过500时，程序在十分钟内运行不出结果。对于单车来讲，采用此算法最适合的配送点在10, 200区间；

（3）采用不同的交叉和变异对于程序的收敛速度以及程序的准确性有很大的影响；对于不同规模的线路优化问题，应当选取不同的参数值。

5结论

遗传算法与传统的算法相比的优越性有：（1）遗传算法能以很大的概率找到问题的最有解，遗传算法具有并行性，能有效地处理大规模的优化问题。（2）遗传算法的结构是开放式的，与问题本身无关，所以容易和其他的算法相结合，共同得到性能更好的混合算法。

参考文献：

[1] Dantzig G., Ramser J. The Truck Dispatching Problem[J]. Management Sci, 1959(6):80-91.

[2] 李军. 物流配送车辆优化调度理论与方法[M]. 北京：中国物资出版社，2001.

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文