基于蚁群算法的车辆路径问题求解.pdf

基于蚁群算法的车辆路径问题求解

(信息工程学院, 电子系,电子信息工程专业张玮谊)
(学号:1999132246)

内容提要:蚁群算法是一种基于群体合作的求分布式启发算法,它主要用于解决离散组
合优化中的问题。本文结合蚁群算法和单亲遗传算法解带有能力约束的车辆路径问题。关键
是设计单亲遗传算法中的交叉算子。运用蚁群算法找出问题的较好解,再通过交叉操作得到
新的个体,从而发掘更优解。实验结果表明,同时该算法尚需解决的问题及今后的研究和方
向。
关键词:蚁群算法遗传算法交叉
教师点评:论文通过分析蚁群算法和单亲遗传算法在解决带有能力约束的车辆路径问题
上的优缺点,并将两者有机结合,提出解决带有能力约束的车辆路径问题,并获得较好的实
验效果。

1 引言
车辆路径问题,即 Vehicle Routing Problem 是供应链研究的一项重要内容。车辆路径问
题是由 G..Dantzig 首先提出的[1]。至今对于车辆路径问题的研究已有 40 年的历史。
目前为止,解决和优化 VRP 问题的方法很多,其中有禁忌搜索法[2],3-opt[3],遗传算
法[4] ,蚁群算法[5,6]等等。本文主要研究 VRP 问题的一种较简化的模型,较典型的有“有
能力限制的车辆路径问题”,即 Capacitated-VRP(CVRP)。它是最基本的 VRP 问题。本文
提出的算法有机地结合了蚁群算法和遗传算法来解决此类问题,并有效地克服了两种算法的
不足之处。
2 车辆路径问题的数学模型
车辆路径问题的描述
所考虑的 VRP 可以概述如下:假设有 n 个城市,每个城市的位置坐标和货物需求已知,
车辆的负载能力一定,但车辆数目未给定,VRP 是对车辆(每辆车一条路径,开始和终止
都在起始点(depot))所要访问的客户进行排序,使所有客户都满足要求,且总旅行成本最
小。假设每个客户被分配到某一辆车,访问一个客户的车辆也必须离开那个客户,每辆车所
访问的城市的需求总和不能超过车辆的能力。
数学模型[2]
为了方便描述,引入下面符号:
客户集合 V={i},当 i=0, 指仓库;车辆集合,M={k}, k=1,⋯⋯,公式, 且 m 是一个待定的
∈=
决策变量。是客户 i 的需求量, i V(i=0 时,qo 0 ); cij -客户 i 到客户 j 的距离; Qk
= ∈≥∈
是车辆 k 的载重量(能力) Qk Q ,其中 k M ; ;Q max{ qi ,i V }
令
1,如果车辆k在访问客户i之后立即访问客户j
=
xijk 
0,其它
1
1,如果车辆k访问客户j
=
yik 
0,其它

可建立 VRP 的数学模型,如下:
min m
(1)
min ∑cij ∑ xijk
i, j k
(2)
n
∑ qi
=
其中最少车辆数由下面公式决定: m = i 1
Q
(3)
其中,目标(1)保证车辆数最少。在本算法中,车辆数由公式(3)决定。目标(2)是目
标函数,即使最小化旅行距离。对于 CVRP 问题,要保证满足以下的约束条