新型遗传算法求解车辆路径问题研究

张瑞锋，汪同三

(中国社会科学院数量经济与技术经济研究所，北京 100732)

0 引言

车辆路径问题[1](Vehide routing problem,VRP)是物流配送优化中关键的一环，也是电子商务活动中不可缺少的内容.自1959年Dantzing和Ramser首次提出VRP以来，很快引起运筹学、应用数学、网络分析、图论及计算机应用等学科的专家与运输计划制定者和管理者的极大重视.历经多年的研究发展，衍生出多种不同类型的问题.VRP一般定义为：对一系列发货点和/或收货点，组织适当的行车路线，使车辆有序地通过它们，在满足一定的约束条件(如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制及时间限制)下，达到一定的目标(如路程最短、费用最小、时间尽量少及使用车辆尽量少).由于VRP已被证明是一个NP难题[2]，求解该问题高效的精确算法存在的可能性不大，为此专家们主要将精力用于构造高质量的启发式算法上.比知一些学者尝试了用一般启发式算法、神经网络、遗传算法、禁忌搜索及模拟退火等智能化启发式算法，均取得了较好的结果[3-4].但是，这些算法在求解问题时都存在“早熟收敛”、搜索效率低和求解速度慢的问题.针对遗传算法的不足，本文中通过将模拟退火的思想引入遗传算法，并对交叉和变异后的个体实施接收策略，不但能有效地缓解遗传算法的选择压力，并且能增强遗传算法的全局收敛性，克服其易限于局部最优的缺陷.实验结果表明该算法具有较强的寻优性能和较快的收敛速度，得到的优化结果也更接近最优解.

1 问题的描述及数学模型

车辆路径问题的一般描述为：有一个中心仓库，拥有K辆车，容量为q，有L个客户点，其需求为gi(i=1，2，…，L)，且gi≤q，顶点集为V={1，2，…，L}，求满足货运需求的总最短行车路线.

根据不同的约束，VRP有多种不同类型，从上述描述中可知，该问题是车辆数固定的单车场单车型非满载车辆路径问题.用cij表示从点i到点j的运输成本，其含义可以是距离、费用及时间等，设配送中心编码为0，客户编码为1，2，…，L，定义变量

(i)xijk=1,表示车辆k由客户i行驶到客户j，xijk=0表示否定；

(ii)yik=1,表示客户i的任务由车辆k完成，yik=0表示否定.

建立数学模型

(1)

(2)

(3)

(4)

(5)

xijk=0或1，i，j=1，2，…L，k=1，2，…，K

(6)

yik=0或1，i=1，2，…，L，k=1，2，…，K

(7)

其中，目标式(1)保证总成本Z最小；式(2)为车辆的容量约束，式(3)保证每个客户点的运输任务仅由一辆车来完成，而所有的运输任务则由K辆车共同完成,式(4)和式(5)保证每个客户能且只能被一辆车服务一次.

2 求解问题的遗传模拟退火算法

遗传模拟退火算法(genetic simulated annealing algorithm， GSAG)是遗传算法和模拟退火算法相结合的一种优化方法.它既具有遗传算法的全局性和并行性，又具有模拟退火算法的局部搜索能力和退火特征，将这两种算法结合起来所构成的遗传模拟退火算法使得遗传算法的搜索性能得到极大改进.具体分为5个步骤.

步骤1:给定种群规模pop_size，k=0；初始温度tk=t0，为了算法的效率t0=(最大成本-最小成本)/(pop_size/2)，产生初始种群pop(k)；对初始种群计算目标值，找出函数值最小的染色体i和这个函数值f，记min=i,s*=f.

步骤2:若满足结束条件则停止计算，输出最优染色体min和最优解s*；否则，在染色体i的邻域N(i)中随机选取一个状态，按模拟退火中的接受概率接受或拒绝j，共迭代pop_size次选出新种群pop1.

步骤3:在pop1(k+1)中计算适应度函数fitness(tk)=1/fi(tk)，然后采用改进的比例选择策略进行染色体的选择.将在pop1(k+1)中的染色体按fitness(tk)值排序，将值最大的染色体复制一个直接进入下一代，下一代种群中剩下的pop-1个染色体用轮盘选择法产生.这样首先可以保证最优个体可以生存到下一代，既给了适应度较大的个体以较大的机会进入下一代，又避免了个体间因适应值不同而被选入下一代的机会悬殊.最后形成种群pop2.

步骤4:对pop2进行交叉和变异操作.

步骤5:计算种群pop2中个体的目标函数值，找出函数值最小的染色体i和这个函数值f，如果f

2.1染色体结构出于表示简单，计算机处理方便的目的，本文中拟采用自然编码.问题的解向量可编成一条长度为N的染色体(c1，c2，…，cN)，其中基因ci为[1，N]之间的一个互不重复的自然数.随机产生一组互不相同的pop_size个染色体作为第一代种群.

2.2可行化过程将染色体的编码向量映射为满足全部约束条件的可行解的过程，称可行化过程.具体过程：

(1)优先关系指的是客户被服务的先后次序.它可以根据起点到各分店的距离确定，也可以根据每个分店的时间窗来确定，还可以通过加权因子由二者共同来确定.在满足车容量和时间窗的约束前提下，我们有理由访问与起点0 距离成本较小的客户.为此，构造下面的评价函数

式中，ω1，ω2,ω3为权重系数，满足0 ≤ω1，ω2，ω3≤1，且ω1+ω2+ω3=1；式中前两项分别为：从起点0访问客户j的时间窗口左右边界的绝对差与整个时间窗口宽度的比值，第三项为距离因素，把客户按照其评价值从小到大的顺序进行排列，就得到一个各分店被服务的优先关系.

(2)在一个染色体中，按照从左到右的顺序，满足优先关系的基因段确定一个车辆路径，例如8个顾客的优先关系为1 2 3 4 5 6 7 8，则s：3 1 4 7 2 8 5 6这个染色体，共有4个基因段满足优先关系，它们分别是：(3)，(1 4 7)，(2 8)和(5 6).因此s表示使用的车辆数为4.其中ω1=0.4，ω2=0.4，ω3=0.2，优先关系为3-8-1-7-5-4-6-2.

(3)对照优先关系确定的各个基因段，检查是否车辆容量约束和各个顾客的时间窗口约束，若满足，则该染色体对应问题的一个可行解，否则，该染色体对应不可行解.

2.3个体的评价对种群中每一个染色体Gh(h=1，2，…，pop_size)，可行化后求得对应的可行解，根据式(1)求得这一可行解对应的目标函数值Zh，若染色体对应不可行解，赋予Zh一个很大的正整数M.令其适应度函数为fh=1/Zh，则fh越大，表明Gh性能越好，对应的解越接近最优解.

2.4染色体的交叉在每代种群中，以一定的交叉概率对染色体进行交叉操作，在此引入一种新颖的交叉算子，这种交叉算子的最大特点是当两父代相同时，仍能产生新的个体，这就减弱了对种群多样性的要求，能够有效地避免传统遗传算法“早熟收敛”的缺点，这是以往交叉算子所不具备的.举例说明其操作：随机在父代个体中选择一个交配区域，如两父代个体及交配区域选定为：A=51|2438|679，B=96|1243|578；将B的交配区域加到A的前面，A的交配区域加到B的前面，得：A′=1243|512438679，B′=2438|961243578；在A′B′中自交配区域后依次删除与交配区相同的自然数，得到最终的两个体为124358679，243896157.与其他交叉方法相比，这种方法在两父代个体相同的情况下仍能产生一定的变异效果，这对维持种群的多样性有一定的作用.

2.5染色体变异物种变异的可能性较小，所以在遗传算法中变异操作只起辅助作用，对每代种群以一定概率变异.变异的策略是随机产生两变异点，将变异段逆转得新个体.

2.6邻域结构每个染色体的邻域包括随机使用两点交换、2-op交换和3-opt交换.

3 算例比较

本文中讨论的问题中有8个顾客和1个服务中心，各顾客的需求量、服务时间、各顾客要求的服务时间范围由表1给出，服务中心与各分店间的距离由表2给出.这些顾客由容量为8吨的车辆完成服务，要求合理安排车辆的行驶路线，使总的运距最短.在计算过程中，设置GSAG算法的进化代数为300，每组计算次数为50，并同文献[5]中的分派启发式算法的结果进行了比较.具体结果见表3.

表1 任务的特征及需求

表3 不同算法的优化结果比较

表2分店及分店与配送中心的距离

距离0123456780040607590200100160801400654010050751101002606507510010075757537540750100509090150490100100100010075751005200501005010007090756100757590757007010071601107590759070010088010075150100751001000

通过表3可以得出，提出的遗传模拟退火算法在求解VRPTW问题时，求得的最优解行驶成本比文献[5]中的分派式启发式算法少13.7%，这说明本文中的算法求解质量较高；通过表4可以得出，算法在群体规模为80时得到最优解的概率在78%以上，这可以说明本文中算法具有较强的克服陷入局部最优的能力.通过表5可以得出，算法在群体规模为120时得到最优解的概率为94%以上，并且在交叉概率为0.8，变异概率为0.2时，得到最优解的概率为100%.通过表3和表4的平均搜索时间，还可以得出算法的收敛速度较快.

表4 本文中算法在群体规模为80的计算结果

表5本文中算法在群体规模为120的计算结果

变异概率交叉概率0.60.70.8平均搜索时间/s0.1049/049/045/00.1549/048/050/02.900.2048/047/050/0

4 结论

在建立带时间窗车辆路径问题的数学模型基础上，针对遗传算法因局部搜索能力不强造成寻优效果较差的缺陷，将局部搜索能力很强的模拟退火算法与之结合，从而构造了求解带时间窗车辆路径问题的混合遗传算法.实验计算结果表明，用混合算法求解带时间窗的车辆路径问题，可以在一定程度上克服遗传算法在局部搜索能力方面的不足和模拟退火算法在全局搜索能力方面的不足，从而得到较好的计算结果，同时混合遗传算法还具有计算效率较高，计算结果较稳定和鲁棒性强的特点，充分显示了其良好的寻优性能.

[1] 李军，郭耀煌.物流配送——车辆优化调度理论与方法[M].北京:中国物资出版社，2001.

[2] Laporte G.The vehicle routing problem:an overview of exact and approximation algorithms[J].European Journal of Operational Research， 1992，5 (9):345-358.

[3] 赵燕伟，吴斌，蒋丽，等.车辆路径问题的双种群遗传算法求解方法[J].计算机集成制造系统，2004，10(3):303-306.

[4] 肖健梅，李军军，王锡淮.求解车辆路径问题的改进微粒群优化算法[J].计算机集成制造系统，2005，11 (4):577-581.

[5] 邹彤，李宁，孙德宝.不确定车辆数的有时间窗车辆路径问题的遗传算法[J].系统工程理论与实践，2004，24(6):134-138.