一、引言
物流配送是物流管理中直接与顾客相连的重
要环节,是货物从物流点送达收货人的过程, 其运
营成本占整个物流成本的大部分。车辆路径问题
(VRP)是以中心仓库为起点和终点,求解服务于
一组顾客的车辆配送路线的优化集合。解决VRP
问题是物流管理中的关键,也是电子商务中的重
要环节。对配送车辆的路线方案进行优化,可以
降低企业物流的运营成本,提高物流工作效率。
否则,顾客就不能在适当的地点和适当的时间得
到订购的商品。
车辆路径问题(VRP)是由Dantzig和Ramser
于1959年首次提出[ 1 ] 。该问题含有几类约束条
件,比如车辆的容量限制、顾客的服务时间窗、路
线的长度限制等。由于VRP是一个NP - 难的组
合优化问题并具有重要的经济应用价值,此问题
自提出以来得到了广泛注意,已涌现出许多精确
型和启发式算法。人们相继提出了基于问题的特
定方法[ 2 ]以及诸如禁忌搜索[ 3 ] 、模拟退火、遗传算
法和神经网络等元启发方法。
应用蚁群优化(ACO)求解VRP是近年来研
究的新方向。在本文中,我们提出一种基于ACO
的混合方法来解决VRP。首先提出一种ACO 算
法,然后加入局部搜索机制并使用基于问题的特
定启发信息———节约量来改进算法。
二、蚁群优化
蚁群优化是群体智能研究领域的一部分。在
群体智能领域,科学家们研究蜜蜂、白蚁、蚂蚁和
其他社会昆虫的行为模式以模拟其过程。昆虫群
体在自然界中解决复杂生存任务的能力吸引了科
学家们设计相应的计算机算法来解决相似的复杂
问题。对于蚁群行为的研究产生了一个崭新的研
究领域,现在通称为蚁群优化(ACO) 。
ACO是新近出现的一种源于自然的解决问题
的启发式算法,这类算法还包括神经网络、模拟退
火和进化算法等。Marco Dorigo在1992年的论文
中首次提出蚂蚁系统(AS) [ 4 ] , 并应用到旅行商问
题(TSP) 。AS是ACO方法的最早版本。AS算法基本上是一个多agent系统,系统中单个agent (即
人工蚂蚁)之间低层次的交互形成蚁群整体的复
杂行为。
ACO算法是受到自然界中真实蚂蚁觅食行为
的启发,即蚂蚁能够迅速找到从蚁巢到食物源的
最短路径。众所周知,个体蚂蚁之间是通过信息
素(pheromone)来传达路径信息的。蚂蚁开始时
是以一种随机方式搜索蚁巢周围的区域,当一个
蚂蚁在随机的游荡中找到食物源时,会在地上释
放出一定量的信息素。位于邻近区域的其他随机
移动的蚂蚁会察觉到这些信息素,接着会以很高
的概率沿着这条路径搜索,同时在行进的过程中
释放自己的信息素,从而增强了这条路径上信息
素的浓度。越来越多的蚂蚁会沿着信息素浓度高
的路径行进,这条路径上信息素浓度的进一步升
高又使得其他蚂蚁沿这条路径行进的概率进一步
提高。正是这种具有正反馈机制的自动催化过程
帮助蚂蚁快速找到最短路线。
在ACO 算法中,首先设置参数值,并给出每
条路径上信息素的初始值,然后蚁群按照状态转
移规则构造解,在每个循环中应用信息素更新规
则,这个过程一直到满足终止条件才结束。ACO
算法的步骤可简要地表述如下[ 5 ] :
步骤1:设置所有参数,初始化信息素
步骤2: Loop
Sub - loop
按照状态转移规则构造解
应用局部信息素更新规则(可选)
直到生成所有的蚂蚁
应用局部搜索(可选)
评价所有的解,并记录最好的解
应用全局信息素更新规则
直到满足终止条件
实际上,ACO方法在目前已成功地应用到不
同的连续和组合优化问题,比如旅行商问题( Trav2
eling Salesman Problem, TSP ) 、二次分配问题
(Quadratic assignment p roblem, QAP) 、图着色问题
(Graph Coloring Problem, GCP) 、调度问题( Schedu2
ling Problem, SP)等。
三、求解VRP的ACO算法
这里我们考虑只有一个中心仓库和相同车辆
的VRP问题。该问题可以形式化定义为一个完全
图G = (V, E) ,其中V = { 0, ⋯⋯, n} 为顶点集, E
为各顶点相互连接组成的弧集。顶点0表示仓库,
而其他顶点表示顾客。顶点i和j之间的旅行成本
用dij表示,代表距离或旅行时间。我们假设成本是
对称的(即dij = dji ) , 相同的车辆数没有限制, 每
辆车的容量Q > 0并已知。每个顾客i的需求量为
qi ,并且满足0 < qi ≤Q。每个顾客只能由一辆车
提供服务,每辆车的载重量不能超过它的容量。
求解的问题是找到一个最小成本的车辆路线集
合,其中每辆车都是从仓库出发,最终又回到仓
库。
在选择车辆路线的过程中,对于决定每辆车
的配送路线而言,选择顾客的组合是任意的。因
此,车辆路径问题是一个组合优化问题,该问题的
可行解的数目随着顾客数目的增加呈指数性增
长。由于没有已知的多项式算法可以找到每个实
例的最优解,车辆路径问题因而被认为是NP - 难
的。对于这样的问题,使用启发式算法不失为一
种寻求解的合理方法, 我们这里使用蚁群优化
(ACO)方法来求解VRP。
求解VRP的ACO算法的步骤如下所示:
步骤1:初始化
设置最大迭代次数Imax、当前迭代次数I = 0
和蚂蚁数m。设置每条弧上的信息素τ( i, j) =τ0 。
步骤2:将m 只蚂蚁都置于起点v0。
步骤3:构造路线
用蚂蚁来模拟车辆, 其构造路线的过程是通
过一步步地选择顾客直到所有的顾客都被访问。
第一只蚂蚁构造一个完整的线路后, 第二只蚂蚁
才开始它的旅行。这样的过程一直继续, 直到预定
的m 只蚂蚁都各自创建了一条可行路线。每只蚂
蚁构造解的过程是从决定第一辆车的路线开始。
蚂蚁从可行的位置列表中选择下一个顾客访问,
车辆的存储容量在再次选择顾客之前进行更新。
如果再次选择顾客会超过车辆容量而导致不可行
解,那么该蚂蚁就回到起点仓库。然后,继续决定
其他车辆的路线直到完成解的构造。
每只蚂蚁通过重复地应用状态转移规则来构
造旅行路线(即VRP的可行解) 。假设蚂蚁k在位
置i, Fk ( i) ,是待访问的可行位置集合,蚂蚁k将按
照(1) 式中给出的状态转移规则选择移动到位置
j。
j =
arg max
u∈Fk ( i) [τ( i, u) ]·[η( i, u) ]β
如果q ≤ q0 　(利用)
J 否则　上式中η( i, u) 是用于评价蚂蚁从位置向位置移
动的启发函数, 其值定义为弧( i, u) 的长度的倒
数,即η( i, u) =
1
diu
。参数β(β > 0) 决定信息素对
于距离的相对重要性。q是在[0, 1 ]上均匀分布的
随机数。参数q0 (0 ≤ q0 ≤1) 决定利用和开发的相
对重要性,利用是指选择最好的路, 开发是指按概
率高的原则选择路。q0 越小,蚂蚁进行随机选择的
概率就越高。J 是一个随机变量, 按照(2) 式中给
出的分布选择。(2) 式给出了蚂蚁在位置i选择向
位置j移动的概率。简言之,当q ≤ q0 时,按照(1)
式选择最好的弧,否则,按照(2) 式选择新的弧。
pk ( i, j) =
[τ( i, j) ]·[η( i, j) ]β
Σu∈Fk ( i) [τ( i, j) ]·[η( i, j) ]β
如果j ∈ Fk ( i)
0 否则
(2)
步骤4:局部信息素更新
在构造解时,蚂蚁对其访问过的每条弧应用
(3) 式中给出的局部信息素更新规则来改变信息
素值。
τ( i, j) = (1 - ρ) ·τ( i, j) +ρ·τ0 (3)
式中ρ(0 ≤ρ≤ 1) 是信息素挥发参数。
步骤5:如果所有的蚂蚁都构造完解,则转向
下一步骤;否则转向步骤3。
步骤6:用2 - op t进行局部改进
为了改进元启发方法的性能,通常加入局部
搜索步骤。因此,我们使用启发式局部优化算法
来改进每代中获得的最好解。这里,我们使用求
解TSP常用的2 - op t交换策略,即对已得的回路
解,通过每次交换2条边来进行改进,从而缩短人
工蚂蚁产生的每辆车的行走路线长度。
步骤7:全局信息素更新
应用下列的全局信息素更新规则来改变最短
路线上的所有弧( i, j) 相关联的信息素值。
τ( i, j) = (1 - α) ·τ( i, j) +α·△τ( i, j) (4)
式α(0 ≤α ≤ 1) 中是信息素挥发参数。
△τ( i, j) =
1
Lgb
如果弧( i, j) 属于全局最短路线
0　　否则
(5)
上式中Lgb 是目前得到的全局最优解的路线长度。
全局信息素更新的目的是在最短路线上加入
更多的信息素,这是一个正反馈的过程。
步骤8:终止
如果终止条件满足,则结束;否则I = I + 1,转
向步骤2进行下一代进化。终止条件是迭代次数
满足I = Imax。
四、基于问题特定的改进
在VRP中,车辆路线的长度不仅决定于任意
两个顾客之间的相对位置,还决定于每个顾客与
仓库v0之间的相对位置。节约算法是工业应用中
解决VRP问题的商品化软件工具的基础[ 6 ] 。该
算法在初始化时,分别向每个顾客配送货物。然
后,按照下列公式计算由于连接顾客和而得到的
节约量。
s ( i, j) = d ( i, 0) + d (0, j) - d ( i, j) (6)
式中d ( i, j) 表示位置i和j之间的距离,符号0表示
仓库。因此,值s ( i, j) 表示由原来的向顾客i和j分
别配送货物改变为将顾客i和j置于同一条回路而
得到的节约量。
如果节约量s ( i, j) 得到高的值, 则表示在访
问顾客i之后访问顾客j是一个好的选择。如果节
约量越高,选择概率就越高, 则引入节约量可以改