混合超启发式法求解大规模VRP的优化研究

杜玲玲

（华东交通大学信息工程学院，江西南昌 330013）

车辆路径问题（vehicle routing problem，VRP）是一个涉及运筹学、管理学、交通运输、计算机科学等领域的著名NP难题。由于它在许多行业（如公共汽车线路制定、垃圾回收、邮件传递、银行系统货币收集、航空铁路时间安排表等）的物流分配系统规划中起着至关重要的作用，因而是一个具有重要理论意义和实际应用价值的研究课题。

车辆路径问题可简单描述为对一系列客户组织适当的行车路线，使车辆有序地通过，在满足一定的约束条件下（如货物的需求量、发货量、交货时间、车辆的容量限制、行驶里程限制、时间限制等），且在客户可以接受的演算时间内，给出尽可能优化的路线规划方案，最大限度地降低客户的运营成本。

对VRP的求解，传统的精确算法只适合求解小规模问题，随着实际问题规模的扩大，求解时间呈几何级数上升，人们逐渐倾向于采用元启发式算法。目前，国内外研究VRP的文献也主要把精力放在构造高质量的启发式算法上。目前已成功用于求解VRP的启发式算法有模拟退火算法、遗传算法、禁忌搜索算法和蚁群优化等。关于这些算法的描述，可以查阅以下研究论文：Brandao等[1]的文献，刘志硕等[2-3]的文献，Tar⁃antilis[4]的文献，Baldacci等[5]的文献，Laporte[6]的文献。近年来，混合不同元启发式算法的搜索策略和优化技术的混合启发式算法成为了一个新研究热点，并取得了一定的研究成果。如在求解大规模的带时间窗的车辆路径问题上，Battarra[7]等结合导向性局部搜索和演化策略的优点，设计了一种主动引导演化策略。Homberger和Gehring[8]提出了一种两阶段（即初始阶段和优化阶段）混合元启发式算法，分别使用演化策略和禁忌搜索来优化使用车辆数最少和旅行时间最短两个目标，已被证明能成功地解决超过1 000个客户的大规模问题。

1 问题描述

带容量约束的车辆路径问题（capacitated vehicle routing problem，CVRP）是VRP的基本类型。在CVRP中，客户的需求是事先已知的，并且不可分裂。给定的K辆车辆具有相同车型，开始时都位于配送中心，受车辆容量约束（有时还有车辆最大旅行时间限制），其目标是如何安排这K辆车的服务对象和路线，使得车辆总的运输成本最小。

近年来，研究者采用结合局部最近邻搜索法（nearest neighbor search，NNS）的混合启发式算法设计了一些求解CVRP的方法。如Crispim等[9]提出了一种混合遗传算法；Tang Montane等[10]提出一种两个种群的混合遗传算法；Chen和Wu[11]提出了一种基于“记录”和“禁忌表”的混合启发式算法，Bianchessi和Righini[12]提出了构造性混合算法，Zachariadis等[13]提出了基于模拟退火和禁忌搜索（tabu search，TS）[14]的混合启发式算法。

上述算法对初始解和邻域的依赖较大，求解后容易陷入局部最优，且一旦陷入几乎没有机会跳出。为进一步扩大对解空间的搜索，以取得更好质量的解。本文提出一种将NNS和TS结合的混合超启发式算法。

2 数学模型

在CVRP中，其总体目标是在满足容量约束条件下尽量减少总运输成本。一般情况下，运输成本与车辆行驶路径成正比，行驶路径越短，车辆的耗油量越少，司机的工作时间越少，总的运输费用也就越少。

这里，我们定义以下符号来进行描述：

A为弧线集；

n为节点总数；

N为节点-弧线关联矩阵；

V为节点集；

T为路线；

3 求解大规模VRP的混合超启发算法

在实际物流配送中，类似于烟草公司这样需要为城市某个范围内的上百个甚至几百个零售商送货，单个零售商送货量又不大的CVRP大量存在，因此，求解这类规模的CVRP需要解决的是如何安排最优线路，使整个网络的总运输费用最小。

3.1 初始解的构造

由于NNS算法操作简单，容易较快得到初始解。所以，首先利用该算法构建初步路线。其算法思想是以配送中心为起始点，搜索距中心最近的、未访问的节点作为下一个节点，在不超出容量限制的情况下重复步骤，达到容量限制后结束该条线路，继续寻找其他新的线路，直到将所有的节点都访问过。

令V*表示车辆尚没有访问过的客户点的集合。从仓库（即调度中心，用节点0表示）开始，构造一条由节点0，i1，…，ij组成的线路，其中

当u≥di1+di2+...+dij，对于任何其它节点s∈V*都有u＜di1+di2+...+dij+ds。重复这个过程直到所有客户点都被访问到。

由于每个客户都可作为车辆路线的第一个客户，这样有n个客户就可形成n种路线安排，选择其中最好的路线安排（即目标值最小）作为算法的初始解。

3.2 禁忌搜索算法的优化设计

由于采用NNS求解后容易陷入局部最优，且一旦陷入几乎没有机会跳出。而TS算法具有收敛速度快，能在第30代左右就能跳出局部最优并达到全局最优点。因此，再利用它来对线路进行优化。

在TS中有多种邻域操作方法，这里，我们采用内部交换和交叉交换法相混合来构造一个求解CVRP的新禁忌搜索算法。

在两条路线之间交换客户，给定由线路集所表示的问题的一个解，其中ri是对应的1条车辆路径：

在交叉交换过程中，首先从第1条线路中删除两条边（i-1，i）和（k，k+1），同时从第2条线路中删除两条边（j-1，j）和（l，l+1）；然后通过引入新的四条边（i-1，j），（l，k+1），（j-1，i）和（k，l+1）实现线段i-1和j-1的互换，其中，线段i-k和j-1中可能包含任意数量的客户。

结点交换后，为优化一些单独的线路，可将交叉邻域法的范畴进行扩大，包含仅用于单一线路的线内交换。从一条给定的线路中删除两条边，且将这两条边之间的线段移动到同一条线路内的另一位置。

4 实验仿真

我们采用基于标准的基准数据集，即Homberger 400 customer Rc2-410和湖北随州市6 772名真实烟草商数据集为实验数据。

4.1 基于标准的基准数据集

标准基准数据集Rc2-410是一个随机集群客户的组合，包含了400个客户。分别利用最近邻搜索（NNS）、内部交换（NNS+intra-exchange）、交叉交换（NNS+cross-exchange）和混合交换法（NNS+intra-&cross-exchange）四种方法在matlab上仿真其路线结构。

实验结果表明，采用混合交换法后，线路密度降低了，这就意味着所构建线路的总路程减少了。因此，该算法能够比其它算法构建出更好的路线。

在表1中列出了这四种算法的详细比较。它们具有相同的路径数，但其消耗的总路程明显不同。可以看出，NNS+intra-&cross-exchange法与NNS法相比，极大地减少了总路程。

表1 算法比较Tab.1 Algorithm comparasion

4.2 基于真实数据集

我们以湖北随州市中心和郊区的6 772位烟草客户为应用数据，根据实际需要，将这些客户划分为5个区域，如图1所示。图中每个点代表了一个客户的位置，如：点（37.1232，113.3423）代表纬度37.1232，经度113.3423。

图2-6分别是采用混合交叉法NNS+intra-&cross-exchange法为这5个区域所构建的路线图，每个区域都使用了多条线路来进行应用验证。图中，直线表示的是某条线路上第1个客户点和最后1个客户点，和车场之间的连接；曲线则表示这条线路上的其他点，按照其实际行走的线路连接起来（实际也是用直线连的，只是点多，形成了多段折线）。这里的x和y也是表示客户点的经纬度。

从这些区域线路图可以看出，新方法在实际应用中可以取得良好的效果，大大减少了线路的总路程，因而能降低运输成本，提高烟草运输的效率。

5 结束语

本文研究了启发式算法及其在车辆路径问题中的应用，重点解决带容量约束的大规模车辆路径问题，将最近邻搜索法和禁忌搜索法的优势相结合，提出结构简单、求解精度高、时间代价小、扩展性好的混合超启发式算法，形成两阶段求解法。第1阶段利用最近邻搜索法构建初步路线，第2阶段再利用禁忌搜索法对内部线路和互跨线路进行优化。

实验结果表明：采用新算法在线路优化上具有显著地改善效果，为大规模CVRP的求解提供了新的求解思路。

[1]BRANDAO J.A deterministic tabo search algorithm for the fleet siza and mix vehicle routing problem[J].European Journal of Operational Resrach，2009，195（3）：716-728.

[2]刘志硕，申金升.蚁群算法及其在有硬时间窗的车辆路径问题中的应用[J].计算机继承制造系统，2006，12（4）：596-602.

[3]刘志硕，申金升.一种求解车辆路径问题的混合多蚁算法[J].系统仿真学报，2007，19（15）：3513-3520.

[4]TARANTILIS C D，IOANNOU G，KIRANOUDIS C T，et al.Solving the open vehicle routing problem via a single parameter metaheuristic algorithm[J].Journal of the Operational Research Society，2005，56（5）：588-596.

[5]BALDACCI R，CHRISTOFIDES N，MINGOZZI A.An exact al-gorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts[J].Mathematical Programming，2008，115（2）：351-385.

[6]LAPORTE G.Fifty years of vehicle routing[J].Transportation Science，2009，43（4）：408-416.

[7]BATTARRA M，GOLDEN B，VIGO D.Tuning a parametric Clarke-Wright heuristic via a genetic algorithm[J].Journal of the Operational Research Society，2008，59（11）：1568-1572.

[8]HOMBERGER JORG，HERMANN GEHRING.A two-phase hybrid metaheuristic for the vehicle routing problem with time windows[J].European Journal of Operational Research，2005，162（1）：220-238.

[9]CRISPIM J，BRANDAO J.Metaheuristics applied to mixed and simultaneous extensions of vehicle routing problems with backhauls[J].Journal of the Operational Reseach Socitey，2005，56（11）：1296-1302.

[10]TANG MONTANC F，GALVAO R.A tabu search algorithm for the vechicle routing problem with simultancous pick-up and delivery service[J].Comuputers and Operations Research，2006，33（3）：595-619.

[11]CHEN J，WU T.Vechicle routing problem with simultancous deliverics and pick-ups[J].Journal of the Operations Research Socitey，2006，57（5）：579-587.

[12]BIANCHESSI N，RIGHINI G.Heuristic algorithm for the cechicle routing problem with simultaneous pick-up and delivery[J].Comuputers and Operations Research，2007，34（2）：578-594.

[13]ZACHARIADIS E E，TARANTILIS C D，KIRANOUDIS C T.Ahybrid metaheuristic algorithm for the vehicle routing problem with simultaneous delivery and pick-up service[J].Expert Systems with Applications，2009，36（2）：1070-1081.

[14]LAI MINGYONG，CAO ERBAO.An improved differential evolution algorithm for vehicle routing problem with simultaneous pickups and deliveries and time windows[J].EngineeringApplications ofArtificial Intelligence，2010，23（2）：188-195.