设为首页
加入收藏
期刊导航
网站地图
首页
期刊
数学与物理
地球与环境
信息通讯
经济与管理
生命科学
工程技术
医药卫生
人文社科
化学与材料
会议
合作
新闻
我们
招聘
千人智库
我要投搞
办刊
期刊菜单
●领域
●编委
●投稿须知
●最新文章
●检索
●投稿
文章导航
●Abstract
●Full-Text PDF
●Full-Text HTML
●Full-Text ePUB
●Linked References
●How to Cite this Article
Open Journal of Transportation Technologies
交通技术
, 2014, 3,
16-21
http://dx.doi.org/10.12677/ojtt.2014.31004
Published Online
January
2014 (http://www.hanspub.org/journal/ojtt
.html
)
A
Discr ete Teaching
-Learning-
Based Optimization Algorithm
f
or
the Capacitated Vehicle Routing Problem
Xiucheng
L
iu
*
, Qiong
L
iu
State Key Laboratory of Digital Manufacturing Equipment & Technology, Huazhong University of Scie
nce and Technology, Wuhan
Email:
*
gdutliuch@163.com
Received: Dec. 5
th
, 2013; revised: Dec. 27
th
, 2013;
accepted: Jan. 12
th
, 2014
Copyright ©
201
4
Xiucheng Liu
,
Qiong Liu
. This is an o pen access article distributed u nder the Creative Commons Attribution License, which per-
mits unrestricted use, distributio n, and reproduction in any mediu m, provided the original work is p roperly cited. In accordance of the Creative Com-
mons Attribution License all C op y ri gh ts © 2 01
4
are reserved f o r Hans and the own er of th e in tellectual p rop ert y Xiuch eng Liu
,
Qiong Liu
. All Cop
y-
right © 201
4 are guarded by law and by Hans as a guardian.
Abstract:
Teaching
-l
earning
-
based optimization
(TLBO) is a recently proposed population based algorithm which s
i-
mulates the teaching
-
learning process of the class room. In order to solve the capacitated vehicle routing problem, a
discrete teaching
-
learning
-
based optimization
algorithm
(DTLBO) is proposed with a new solution representation and
decoding method in this paper. An elitist strateg y is introduced in the TLBO algorithm to preserve the be st individuals
from generation to generation. At the same time, duplicate solution
s are modified by mutation on randomly selected
dimensions of the duplicate solutions to keep the diversity of the population. Then the 2
-
OPT local search is combined
to improve the local search ability of the hybrid discrete teaching
-
learning
-
based optimi
zation. Tested on the several
benchmarking capacitated vehicle routing problems, the hybrid discrete teaching
-learning-
based optimization can
achieve the optimal solutions of all selected instances
.
Keywords:
Teaching
-
Learni ng
-
Based Optimization
Algorithm; Vehicle Routing Problem; Solution Decoding Method;
Elitist Strategy
基于离散教与学算法求解车辆路径问题
刘秀城
*
,刘
琼
华中科技大学,数字制造装备与技术国家重点实验室,
武汉
Email:
*
gdutliuch@163.com
收稿日期:
2013
年
12
月
5
日;修回日期:
2013
年
12
月
27
日;录用日期:
2014
年
1
月
12
日
摘
要:
教与学算法是一种通过模拟班级授课的“教”与“学”过程来实现对连续优化模型进行优化的群体智
能算法。为了求解车辆路径问题,提出一种离散的教与学算法,设计了一种新的个体解码方法对教与学算法的
实数个体进行解码。为了尽可能不丢失迭代中的最优解,在离散教与学算法中引入精英策略,同时通过随机变
异的方法对重复的个体进行变异以保持种群个体的多样性。最后将
2-
OPT
局部搜索与所提的离散教与学算法混
合以提高算法的局部搜索能力。对车辆路径问题的基准实例测试表明,所提的离散教与学算法可以获得基准实
例的当前最优解。
关键词:
教与学算法;车辆路径问题;个体解码方法;精英策略
*
通讯作者。
OPEN ACCESS
16
基于离散教与学算法求解车辆路径问题
1.
引言
车辆路径问题在物流配送中起着重要的作用,良
好的车辆路径安排能有效降低物流费用,提高企业的
运营效率和服务水平。车辆路径问题的主要目标是在
满足一定约束的条件下,对车辆的运输路径进行安排
使得车辆的运输距离或者使用的车辆数最少,从而达
到降低物流成本的作用。由于车辆路径问题是
NP
难
问题,精确算法无法在有限的时间内获得最优解,因
此研究者们提出了许多启发式算法进行求解,如遗传
算法、禁忌搜索、蚁群算法和粒子群算法等
[1]
。教与
学算法是由
Rao
等
[2]
于
2011
年提出来的一种新型的群
体智能算法,该算法通过模拟班级授课的教学过程来
实现对问题的优化。与上述启发式算法不同的是,教
与学算法具有参数少、收敛速度快的特点
[3]
。虽然教
与学算法已在机械参数设计
[2]
、连续函数优化
[4]
、和
平面钢框架设计
[5]
等方面取得巨大的成功,但还没有
见到在车辆路径问题的应用。由于教与学算法是针对
连续优化模型提出来的,为了求解车辆路径问题,提
出一种离散教与学算法进行求解,通过对基准实例的
测试,验证了所提算法的可行性和有效性。
2.
车辆路径问题模型
车辆路径问题可描述为:在满足一定约束的条件
下,尽可能以最少的车辆数或者使车辆行驶最短的距
离来完成对分布在不同地方的顾客配送货物的任务。
本文所考虑的约束主要有:
1)
每辆车从停车场出发,并最终返回停车场;
2)
每个顾客有且只能被访问一次;
3)
每辆车所配送的货物都不超过车辆本身的容
量。
假设停车场用
0
表示,车辆数为
K
,顾客数为
N
,
每个顾客的需求为
i
D
,顾客
i
和
j
之间的距离为
C
ij
,
则最小化车辆的总距离为
10 0
min
KNN
kk
ij ij
ki j
CX
= ==
∑∑∑
(1)
S.t.
1
0
k
ij
ki j
X
=
如果车辆 从
顾客 行驶到顾客
其他
(2)
10
1,1, 2,,,
KN
k
ij
ki
Xj N
= =
= =
∑∑
(3)
10
1,1, 2,,,
KN
k
ij
kj
Xi N
= =
= =
∑∑
(4)
00
0,1,2, ,;1,2, ,,
NN
kk
it tj
ij
XX kKtN
= =
−== =
∑∑
(5)
00
,1, 2,,,
NN
k
jij k
ji
DX QkK
= =
≤=
∑∑
(6)
0
1
1,1, 2,,,
N
k
j
j
Xk K
=
≤=
∑
(7)
0
1
1,1, 2,,,
N
k
i
i
Xk K
=
≤=
∑
(8)
{ }
0,1,,0,1,2,, ;1,2,, ,
k
ij
XijNk K
∈= =
(9)
约束
(3)
和
(4)
保证每个顾客有且只能被访问一次;
约束
(5)
保证到达顾客的车辆数等于离开顾客的车辆
数 ;约 束
(6)
保证每条车辆路径上所配送的货物都不超
过车辆本身的容量;约束
(7)
和
(8)
保证每辆车的使用不
超过一次;约束
(9)
满足决策变量约束。
3.
教与学算法简介
教与学算法主要模拟班级中课程学习的两种基
本模式:
1)
教师教学阶段:学生通过教师授课进行学
习;
2)
学生互学阶段:学生之间相互学习,共同提高。
教与学算法中的所有学生相当于一个种群,学生所要
学习的课程相当于所要优化问题的决策变量,学生的
总成绩相当于所要优化问题的目标值,所有学生中总
成绩最好的学生作为教师。该算法主要分为两个过程:
教师教学阶段和学生互学阶段。
3.1.
教师教学阶段
在这个阶段,教师通过授课的方式来提高整个班
级的平均成绩。假设有
n
门课程,
m
个学生,在迭代
次数
t
时,所有学生的课程
j
的平均成绩为
M
jt
,所 有
学生中总成绩最好的个体为
X
best,
t
,选取该个体作为教
师,则教师与学生在课程
j
上的成绩差值用公式
(
10
)
计算。
t
r
是
[0,
1]
范围内的随机数,
F
T
是教学因子,取
1
或者
2
,由随机数控制,采用公式
(
11
)
计算。为了将
学生的成绩向教师移动,采用公式
(
12
)
对所有学生个
体进行更新。如果更新后的个体
jkt
X
′
对应的目标值更
好,则接受该更新个体,否则保持原来的个体
jkt
X
。
( )
,best,
jttjtFjt
DMrXT M
= −
(10)
OPEN ACCESS
17
基于离散教与学算法求解车辆路径问题
( )
( )
round 1rand0,1
F
T
= +
(11)
jkt jktjt
XX DM
′
= +
(12)
3.2.
学生互学阶段
在此阶段,学生通过相互学习来提高各自的成绩。
对于一个给定的学生
P
来说,随机选取与该同学成绩
不相等的学生
Q
,通过比较这两个学生的成绩来决定
如何更新学生
P
,具体的更新策略如公式
(
13
)
所示,
(
)
,,
jPt
fX
′
表示学生
P
的成绩,
(
)
,,
jQt
fX
′
表示学生
Q
的成绩。如果更新后的个体
,,
jPt
X
′′
对应的目标值更好,
则接受该更新个体。
()
() ()
()() ()
,,
,,,, ,,,,,,
,,,, ,,,,,,
,if
,if
jPt
jPt tjPtjQtjPtjQt
jPt tjQtjPtjPtjQt
X
X rXXfXfX
X rXXfXfX
′′
=
′ ′′′′
+−>
′ ′′′′
+− <
(13)
4.
离散教与学算法求解车辆路径问题
由于教与学算法是针对连续优化模型提出来的,
为了求解带有离散变量的组合优化问题如车辆路径
问题,首先要将教与学算法的实数编码解码成离散的
车辆路径,然后计算路径的目标值。为了保证在算法
的迭代过程中尽可能不丢失所搜索到的迭代最优解,
在教与学算法中引入精英策略,每次迭代结束后,将
上一次迭代产生的
e
个最优解替换本次迭代中的
e
个
最差解。同时,为了提高算法的局部搜索能力,将教
与学算法与
2-
OPT
[6]
局部搜索混合求解车辆路径问题,
为了加快算法的收敛速度并增强算法的全局搜索能
力,先采用轮盘赌策略随机选择
m
个体进行变异,再
进行
2-
OPT
局部搜索。由于引入了精英策略,为了防
止由于精英个体替换导致产生重复解而使算法过早
的陷入局部最优的情况,精英个体替换之后,对整个
种群进行重复值检验并对重复值进行随机变异产生
新的个体,以扩大种群的多样性。离散教与学算法求
解车辆路径问题的流程图如图
1
所示。
4.1.
个体解码及目标值计算
由于教与学算法采用实数对个体进行编码,为了
求解车辆路径问题,必须对个体的实数编码进行解码。
本文提出的个体解码方法为:将教与学算法的个体实
数编码按从小到大的顺序进行排序,把最小的实数赋
给最小的顾客编号
1
,第二小的实数赋给顾客编号
2
,
以此类推,直到最大的实数赋给最大的顾客编号
n
,
设置参数,如学生数
m
,精英个体数
e
,最大迭代次数
ITR
随机初始化
m
个实数编码,解码并计算目标值
保存种群中最优的
e
个精英个体
教与学算法过程
轮盘赌选择
m
个个体变异后进行
2-OPT
局部搜索
用保存的
e
个精英个体替换种群中的最差个体
去重检验并进行随机变异
达到算法的最大迭代次数
结束
开始
否
是
Figure 1. Flow chart of the discrete teaching-learning-based optimization
algorithm for capacitated vehicle routing problem
图
1.
离散教与学算法求解车辆路径问题的流程图
OPEN ACCESS
18
基于离散教与学算法求解车辆路径问题
所获得的序列就表示车辆访问顾客的顺序。例如,假
设要配送货物的顾客数为
n
= 8
,教与学算法的个体实
数编码如图
2
所示,则由于
0.15
是最小的实数,将
1
替换
0.15
所在的位置,以此类推,获得的车辆路径如
图
2
所示。
为了计算解码后的车辆路径的目标值,对该车辆
路径从左到右进行扫描,将顾客分配给第一辆车进行
运输,当超出车辆的容量约束时,则插入停车场编号
0
,将接下来的顾客分配给下一辆车,最终解码获得
的完整车辆路径如图
2
所示。然后计算该车辆路径的
运输距离。
4.2.
局部搜索
为了提高教与学算法的局部搜索能力并加快其
收敛速度,我们将
2-
OPT
局部搜索与教与学算法混合
求解车辆路径问题。为了增强算法的随机性从而提高
算法的全局搜索能力,采用轮盘赌策略从种群中选取
m
个个体进行变异,然后再进行
2-
OPT
搜索,变异的
方法采用迭代变换法
[7]
(
Iterated Swap Procedure
,
ISP
)
。
4
.2.1
.
轮盘赌方法选择个体
轮盘赌方法可以保证适应度值较大的个体被选
中的概率较大,为了更好的区分种群中的较好个体和
较差个体,本文采用的轮盘赌方法为:先将所有个体
中距离的最大值减去每个个体的距离,再将所得差值
进行概率选择,如公式
(
14
)
所示。
( )
( )
max max
1
m
ii j
j
PCC CC
=
=−−
∑
(14)
4
.2.2
.
迭代变换法变异
当采用轮盘赌策略从种群中选出
m
个个体后,由
于选出来的个体可能重复,因此采用迭代变换法对选
出来的个体进行一次随机变异。迭代变换法的具体步
骤如下所示:
步骤
1
:从个体
P
中随机选择两个位置
i
和
j
,如
图
3
所示,
i
= 3
,
j
= 6
;
步骤
2
:交 换
i
和
j
两个位置处的实数形成一个新
的解
C
1
;
步骤
3
:交 换
i
和
j
前后位置的实数形成
4
个邻域
0.
24 0.58 0.37 0.92 0.15 0.83 0.46 0.74
25381746
02538017
064
个体实
数编码
解码过程
顾客分配过程
最终的车
辆路径
目标值计算
Figure 2. Solution decoding method and objective value calculation
图
2.
个体解码和目标值计算的示意图
0.24 0.58
0.37
0.92 0.15
0.83
0.46 0.74
0.24 0.58
0.83
0.92 0.15
0.37
0.46 0.74
0.24 0.58
0.83
0.92
0.37
0.15 0.46 0.74
0.24 0.58
0.83
0.92 0.15 0.46
0.37
0.74
0.24
0.83
0.58 0.92 0.15
0.37
0.46 0.74
0.24 0.58 0.92
0.83
0.15
0.37
0.46 0.74
C
1
C
2
C
3
C
4
C
5
P
Figure 3. Iterated swap procedure
图
3.
迭代变换法
OPEN ACCESS
19
基于离散教与学算法求解车辆路径问题
解
C
2
、
C
3
、
C
4
、
C
5
;
步骤
4
:计算步骤
2
和
3
产生的
5
个解的目标值
并求出其中的最好解;
步骤
5
:如果上述
5
个解中的最好解比原来个体
的目标值更好,则替换原来的个体,否则不交换。
4
.2.3
. 2-OPT
局部搜索
对于一条完整的车辆路径,
2-
OPT
局部搜索通过
删除路径中的两条边,再增加另外的两条边的方法来
对路径进行寻优并保证路径的完整性。如果交换后路
径的目标值更好,则进行交换,否则不交换。其原理
如图
4
所示
,以
图
3
中的个体
C4
为例,假设
图
4
中
的
i
= 2
,
j
= 6
,则进行一次迭代过程如图
5
所示。对
选出来的个体进行上述的迭代过程,直到不能通过上
述迭代过程提高个体的目标值为止。
4.3.
精英策略和去重检验
为了保存迭代最优解,对个体进行
2-
OPT
局部搜
索后,将上次迭代中的
e
个最好解替换本次迭代中的
e
个最差解。由于精英替换可能使种群中产生重复个
体,为了保持种群个体的多样性,每次迭代精英替换
之后立即进行重复值检验,并对重复值进行随机变异
以产生新的个体。由于所有个体编码的实数范围在
0
和
1
之间,因此随机变异的方法为用在
0
和
1
之间产
生的随机数替换重复个体中的任一值,以个体
P
为例,
用随机产生的实数
0.66
替换个体
P
中的实数
0.37
,具
体的变异过程如图
6
所示。
i
i+1
j
j+1
i
i+1
j
j+1
Figure 4. 2-
OPT
图
4. 2-
OPT
示意图
i j
0.24
0.83
0.58 0.92 0.15
0.37
0.46 0.74
0.24
0.83 0.37
0.15 0.92 0.58 0.46 0.74
C
’
4
C
4
i+1 j+1
Figure 5. 2-OPT iteration
图
5. 2-
OPT
迭代过程
5.
实验结果
为了验证所提离散教与学算法求解车辆路径问
题的有效性,将该算法用于求解
Augerat
等
[8]
提出的
车辆路径问题基准实例
(
http://www.branchandcut.org/VRP/data/
)
,并 与
Ai
等
[9]
提出的两种采用不同解码规则的粒子群算法
SR1
和
SR2
进行比较。本算法采用
matlab 7.0
编程实现,算
法的具体参数通过多次试验确定,最终的算法参数设
置如下:学生数
m
=
40
,迭代次数
ITR =
200
,精英
个体数
e
= 4
。将该算法运行
10
次,所得到的最好值、
最差值、平均值和标准差列于表
1
中。
从表
1
中可以看到,本文所提出的离散教与学算
法可以求得上述基准实例中的所有最好值,而
Ai
等
[9,
10]
所提的
SR1
粒子群算法可以获得上述
10
个基准实
例中的
7
个最好值,所提的
SR2
粒子群算法可以获得
上述
10
个基准实例中的
9
个最好值。因此,从最好
值的角度来看,本文所提的教与学算法优于
Ai
等
[9,10]
所提出的粒子群算法。由于
Ai
等
[9,10]
没有给出最差值、
平均值和标准差的结果,因此其他结果无法比较。限
于篇幅所限,本文只给出实例
An46k7
的最优解收敛
曲线,如图
7
所示
。从
图
7
中可以看到,离散教与学
算法求解车辆路径问题的收敛速度非常快。从以上结
果和分析可知,本文所提的教与学算法是一种求解车
辆路径问题的较好算法。
6.
结语
教与学算法是一种求解连续优化模型的较好算
法,它没有自己的算法参数,只需设置一般启发式算
法所共有的参数如种群数和迭代次数等,所以算法的
参数设置较简单,同时教与学算法还具有收敛速度较
0.24 0.58
0.37
0.92 0.15 0.83 0.46 0.74
0.24 0.58
0.66
0.92 0.15 0.83 0.46 0.74
25381746
P
24581736
解码
解码
变异
变异前
变异后
Figure 6. Duplicate solution modified by mutation
图
6.
重复个体变异
OPEN ACCESS
20
基于离散教与学算法求解车辆路径问题
Table 1. Comparison results of benchmarking problems
表
1.
基准实例测试结果比较
编号
基准实例
最优解
SR
-1
[9,
10]
SR
-2
[9,
10]
离散教与学算法
最好值
最好值
最好值
最差值
平均值
标准差
1
An33k5
661
661
661
661
670
663.8
3.46
2
An33k6
742
742
742
742
745
742.7
0.95
3
An34k5
778
778
778
778
792
782.4
5.06
4
An36k5
799
799
799
799
835
811.3
11.78
5
An37k5
669
670
669
669
687
674
5.98
6
An37k6
949
949
949
949
997
969
13.68
7
An38k5
730
730
730
730
761
737.2
9.86
8
An39k5
822
825
822
822
836
827.8
3.82
9
An44k6
937
940
940
937
960
946.7
6.25
10
An46k7
914
914
914
914
944
922.3
11.14
Figure 7. Convergence of the best solution for instance An46k7
图
7.
实例
An46k7
的最优解收敛曲线
快的特点。为了求解车辆路径问题,本文提出了一种
混合
2-
OPT
局部搜索和 带有 精英 策略 的离散教 与学
算法。对基准实例的测试表明所提的离散教与学算法
是一种求解车辆路径问题的较好可行算法。由于本文
只考虑了带有车辆容量约束的车辆路径问题,将所提
出的离散教与学算法应用在带有其他约束如时间窗
和多停车场的车辆路径问题中将是本文的下一个研
究方向。
参考文献
(References)
[1]
Laporte
,
G.
(
1992
)
The vehicle routing problem: An overview of
exact and approximate algorithms
.
Europe
an Journal of Opera-
tional Research
,
59
,
345
-
358.
[2]
Rao, R.V.
, Savsani
, V.J
. and
Vakharia, D.
P.
(
2011
)
Teaching-
learning
-
based optimization: A novel method for constrained
me-
chanical design opti mization proble ms
.
Computer-
Aided Design
,
43
,
303
-
315.
[3]
Waghmare
, G. (
2013
)
Comments on
“a
note on teaching
-learn-
ing
-
based optimization algorithm
”.
Information Sciences
,
22 9
,
159
-
169.
[4]
Rao, R.V.
, Savsani
, V.J. and Balic,
J.
(
2012
)
Teaching-learning-
based optimization algorithm for unconstrained and constrained
real-parameter optimization problems.
Engineering Optimization
,
44
,
1447
-
1462.
[5]
Toğan
,
V.
(
2012
)
Design of planar steel frames using
teaching-
learning
based optimizati
on
.
Engineering Structures
,
34
,
225
-
232.
[6]
Lin
,
S.
(
1965) Co mpute r solu tions o f the tr aveling sal esman
pro
b-
lem.
Bell System Technical Journal
,
44
,
2245
-
2269.
[7]
Ho, W.
, Ho
, G.T.
, Ji
, P.
, et al.
(
2008
)
A hybrid genetic a lgorithm
for the multi
-
depot vehicle routing problem
.
Engineering Appl
i-
cations of Artificial Intelligence
,
21
,
548
-
557.
[8]
Augerat, P.
, Belenguer
, J.M.
, Benavent
, E.
, et al.
(
1995
)
Co
m-
putational results with a br anch and cut code for the ca pacitated
vehicle routing problem. Rapport De Recherché-
IMAG
.
[9]
Ai, T.J
. and
Kachitvichyanukul,
V.
(
2009
)
Particle
swarm opti-
mization and two solution representations for solving the capa-
citated vehicle routing problem
.
Computers & Industrial Eng
i-
neering
,
56
,
380
-
387.
[10]
Moghaddam
, B.F.
, Ru iz
, R
. and
Sadjadi
, S.
J.
(
2012
)
Vehicle
routing
problem with uncertain demands: An
advanced particle swarm
algorithm.
Computers & Indus trial Engineering
,
62
,
306
-
317
.
OPEN ACCESS
21