基于改进遗传算法的带时间窗VRP问题研究

摘要：带时间窗约束的VRP问题（VRPTW）属于NP-hard问题，采用改进遗传算法探索最优方案。首先分析了带时间窗VRP问题的一般数学模型，并采用罚函数的方法对时间窗约束进行处理；设计了带权重的适应度函数，并采用了基于基因库的跨世代精英选择算子、PMX交叉算子和局部爬山变异算子；最后通过仿真实验与传统遗传算法和自适应遗传算法进行了对比研究，仿真结果表明改进遗传算法在解决带时间窗VRP问题中具有较高收敛速度和全局搜索能力。

关键词：遗传算法；时间窗；车辆路径问题；基因库

中图分类号：TP202+.7文献标识码：A文章编号：1009-3044(2011)10-2411-03

Research on VRPTW Problem Based on Improved Genetic Algorithm

FAN Yue-lin, ZHOU Su-ping

(Economy Management College, Nanjing University of Information Science & Technology, Nanjing 210044, China)

Abstract: The Vehicle Routing Problem with Time Windows (VRPTW) is NP-hard, this paper explored the optimal solution by improved Genetic Algorithm, and firstly analyzed the general mathematical model of the Vehicle Routing Problem with Time Window, and dealt with Time Window through penalty function. Then designed a fitness function with weight in-built, then adopted the elite selection operator based on gene pool ,PMX crossover operator and local_climbing mutation operator. Finally compared the algorithm with simple genetic algorithm and adaptive genetic algorithm by simulation. The results indicate that the improved genetic algorithm has higher convergent speed and global searching capability.

Key words: genetic algorithm; time window; VRP; gene pool

车辆路径问题（Vehicle Routing Problem-VRP）是物流配送中的关键问题之一，最早由Dantzing和Ramser于1959年提出[1]，是典型的NP-hard问题。而有时间窗约束的车辆路径问题（Vehicle Routing Problem with Time Window-VRPTW ）则是VRP的一个特例，它考虑了需求在时间上的约束，即要求车辆尽可能在时间窗以内到达客户点，现实意义更强。众所周知，对于NP-hard问题，采用精确式算法得出确定的最优解往往是不可行或不经济的，而更为有效的方法则是通过某种启发式算法找到问题的近优解。其中遗传算法以其独特的算法形式和运行机理在复杂问题的求解中有着比较明显的优势。为此，本文采用改进的遗传算法对有时间窗约束的车辆路径问题进行了探讨研究，以寻找最优解为目标，在构造出VRPTW的一般模型后，着重阐述了改进遗传算法的设计，最后通过仿真计算取得了良好的效果。

1 VRPTW模型

给定一个配送中心，拥有若干载重相同的配送车辆。在配送中心周围分布有若干客户，每个客户有不同的货物需求。配送车辆装载一定数量的货物，按照预先分配好的线路行驶，在各个客户要求的服务时间窗内将货物送达。通过合理安排配送线路和次序，使得配送过程的总成本最小（见图1）。

为方便表示，建立如下符号体系：Z表示配送总成本；m为所需的配送车辆数；n代表需要服务的客户数量；Di,j表示从客户i到客户j的距离（i,j的取值从0到n）；c表示单位距离运输成本；gi表示客户i的需求量；q表示配送车辆的最大载重；[eti,lti]是客户i要求的服务时间窗；ti是配送车辆到达客户i的时间（t0是车辆从配送中心的出发时间），time是对每个客户的服务停留时间，speed是配送车辆的平均行驶速度。另外定义变量如：

本文采用罚函数的方法来处理时间窗约束，并设a、b分别为配送车辆提前和滞后到达客户的时间窗惩罚因子，则客户i处的时间窗成本为：

有了以上的符号体系，可以得到如下成本表示[3]：

距离运输成本：

(1)

超重成本：

(2)

时间窗成本：

(3)

其中DistanceCost计算的是各条线路的距离成本；CapacityCost计算的是各配送车辆由于超载所产生的成本，在现实生活中如果严防超载，可以将M系数设置成非常大（一般为1000000）即可；TWCost反应了配送车辆违背时间窗的惩罚成本。三种成本按照用户设定的权重值(W1,W2,W3)加权计算，就得到了配送总成本的表达形式：

(4)

2 改进的遗传算法

2.1 算法原理

遗传算法最初是由J.H.Holland等在70年代提出[2]，以自然选择和遗传理论为基础，模仿自然界优胜劣汰的进化机制，通过不断迭代最终得出最优解。本文对传统遗传算法的选择和变异操作进行改进，算法流程图见图2。

2.2 算法设计

2.2.1 编码

本文将按照配送车辆到达客户的先后顺序进行编码。假设有九个客户需要配送货物，分别命名为1,2，…9，配送中心为0，随机产生一个序列作为一条染色体如3 5 6 9 2 1 4 8 7 ，表示配送车辆到达的次序是客户3,客户5，…，最后到达客户7。现实应用中往往需同时派出多辆配送车运送货物，每辆配送车负责一条线路，对以上的染色体进行可行化处理――线路划分，这样每辆配送车能在不超载的情况下完成各自的配送任务，这样就很好的解决了车辆载重约束。线路划分算法如图3。

假设经过线路划分的染色体编码形式变为：

解码后：

2.2.2 适应度函数

适应度函数是衡量染色体接近最优解的程度，能有效地反映每一条染色体与问题最优解染色体的差距。由于我们在编码阶段已经通过线路划分完全消除了车辆超载的可能，因此我们在适应度的计算中只需考虑距离运输成本和时间窗成本。我们采用如下设计：

第w条染色体的适应度函数为fw

(5)

其中w1,w3分别为距离运输成本和时间窗成本的权重值，且0≤w1,w3≤1 , w1+w3=1.

2.2.3 遗传操作的改进

遗传操作包括选择、交叉和变异三个过程。在选择算子中本文在roulette wheel选择法的基础上进行改进，建立了世代基因库，用于存储进化过程中适应度很高的精英染色体。基因库中染色体按适应度大小排序且库大小设置为20，每次更新基因库时将新染色体按适应度大小插入，将适应度最小者剔除以保证基因库中的平均适应度不断提高（见图4） 。在选择染色体时将基因库中的染色体混入一般染色体中用于进一步进化。

交叉算子模拟的是自然界中的基因重组过程，本文采用部分匹配交叉（partially matched crossover , PMX）,在交叉过程中将隔离基因预先剔除，交叉完成后重新进行线路划分，以杜绝不可行解的出现。

变异过程是对染色体上一个或几个基因位进行随机替换。本文将传统多点变异改进成局部爬山变异，即变异有若干个候选变异方向，算子将按照其中最好的方向实施变异，以达到局部最优。设计如下：在染色体编码序列中随机产生三个位置（非隔离基因0）pos1, pos2, pos3作为变异点如：

pos1, pos2, pos3三个位置的编码值任意交换位置产生A33=6种组合，分别计算这六种组合所对应的编码序列的适应度函数，将适应度最高的染色体保留下来作为变异的结果。如此使得变异算子具有局部爬山能力，可使染色体只向有利的方向变异，提高收敛速度。

3 仿真实验及分析

3.1 仿真条件及参数设置

本文在Java Eclipse Galileo环境下进行了仿真，主机配置为Intel 双核处理器，CPU主频1.8GHZ，内存2.0GB，采用Java和SQL Sever2000编程实现。仿真数据如下：O是配送中心，坐标为[200,200]，配送车辆出发时间是8:00，A～J分别代表十个有配送需求的客户，客户信息见表1。算法参数为：种群大小=50，交叉概率=0.80，变异概率=0.01，终止代数=500，车辆最大载重=8.0，早于时间窗惩罚因子=10.0，晚于时间窗惩罚因子=10.0。

表1 客户信息表

3.2 仿真结果及分析

采用以上参数设置时经过687ms的计算取得了较为满意的计算结果见图6。结果显示，当种群进化到113代以后，配送车辆的规划路径已经不在发生变化（---OGFO---OAJHIO----OEDCBO----），并且总成本也趋于稳定直至254代以后完全固定在2244.098为止。图5则给出了最佳配送方案的直观展示，十个客户按照配送顺序被划分到①②③三个区域，分别由三辆配送车进行配送。

为验证本文改进遗传算法的可行性和有效性，分别采用传统遗传算法（SGA）、自适应遗传算法（ASA）和本文改进的遗传算法（IGA）对带时间窗VRP问题在相同实验环境和仿真数据下进行了100次对比仿真实验，结果如表2。

表2表明：对于本文的带时间窗VRP问题，改进遗传算法的选择和变异操作中要比另外两种算法复杂，但局部的复杂却提高了算法全局的进化效率，收敛时间大为缩短。而且当问题规模较小时，三种方法虽都能得出最优解，但改进算法的最优解收敛次数却提高了13.64%以上。可见改进的遗传算法运算效率得到了提升而且全局搜索能力大大增强。

4 结束语

采用遗传算法处理带时间窗约束的车辆路径问题，其实质就是将约束条件转化到遗传算子的设计中，在成功处理了约束条件后，问题就简化为简单的TSP问题[6]，目前，具有较强实际意义的约束条件有载重约束、时间窗约束、路径长度约束、取货送货约束、回程约束和司机工作时间约束等等。随着约束条件的增加，遗传算法的设计难度也越大。因此，如何恰当的将各种约束条件进行转化成为解决车辆路径问题的关键，也是当前的研究热点。笔者希望通过本文的探讨研究能为VRP问题的研究者提供参考。

参考文献：

[1] CORDEAU J F,LAPORTE G.A unified tabu search heuristic for vehicle routing problems with time window[J].Journal of the Operational Research Society,2001,52(8):928-936.

[2] Holland J H.Adaptation in Natural and Artificial System[M].Mit Press,Cambridge,Mass,1975.

[3] 陈湘州,杨勇,王俊年.一种改进的自然数编码遗传算法在非满载时间窗车辆优化调度问题中的应用[J].长沙电力学院学报:自然科学版,2004,19(2):56-59.

[4] 孙曦,蔡临宁.带时间窗的车辆路由问题的改进遗传算法[J].工业工程与管理,2007(3):16-20.

[5] 孙辉.遗传算法在物流企业配送业务中的应用[D].吉林大学数学所,2005.

[6] 李大卫,王莉,王梦光.遗传算法在有时间窗车辆路径问题上的应用[J].系统工程理论与实践,1999,19(8):65-69.

[7] 乔彦平,张骏.基于一种改进遗传模拟退火算法的TSP求解[J].计算机仿真,2009,26(5):205-208.

[8] 韦雪洁,黎明,刘高航,田贵超.基于知识库求解TSP问题的改进遗传算法[J].计算机仿真,2006,23(8):161-163.