基于离散教与学算法求解车辆路径问题 A Discrete Teaching-Learning-Based Optimization Algorithm for the Capacitated Vehicle Routing Problem

doi:10.12677/OJTT.2014.31004

设为首页加入收藏期刊导航网站地图

期刊菜单

文章导航

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

for the Capacitated Vehicle Routing Problem

Xiucheng Liu*, Qiong Liu

State Key Laboratory of Digital Manufacturing Equipment & Technology, Huazhong University of Science and Technology, Wuhan

Email: *gdutliuch@163.com

Received: Dec. 5th, 2013; revised: Dec. 27th, 2013; accepted: Jan. 12th, 2014

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 Copy-

Abstract: Teaching-learning-based optimization (TLBO) is a recently proposed population based algorithm which si-

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 solutions 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 optimization. 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

基于离散教与学算法求解车辆路径问题

1. 引言

车辆路径问题在物流配送中起着重要的作用，良

好的车辆路径安排能有效降低物流费用，提高企业的

运营效率和服务水平。车辆路径问题的主要目标是在

满足一定约束的条件下，对车辆的运输路径进行安排

使得车辆的运输距离或者使用的车辆数最少，从而达

到降低物流成本的作用。由于车辆路径问题是 NP 难

问题，精确算法无法在有限的时间内获得最优解，因

此研究者们提出了许多启发式算法进行求解，如遗传

算法、禁忌搜索、蚁群算法和粒子群算法等[1]。教与

学算法是由 Rao等[2]于2011年提出来的一种新型的群

体智能算法，该算法通过模拟班级授课的教学过程来

实现对问题的优化。与上述启发式算法不同的是，教

与学算法具有参数少、收敛速度快的特点[3]。虽然教

与学算法已在机械参数设计[2]、连续函数优化[4]、和

平面钢框架设计[5]等方面取得巨大的成功，但还没有

见到在车辆路径问题的应用。由于教与学算法是针对

连续优化模型提出来的，为了求解车辆路径问题，提

出一种离散教与学算法进行求解，通过对基准实例的

测试，验证了所提算法的可行性和有效性。

2. 车辆路径问题模型

车辆路径问题可描述为：在满足一定约束的条件

下，尽可能以最少的车辆数或者使车辆行驶最短的距

离来完成对分布在不同地方的顾客配送货物的任务。

本文所考虑的约束主要有：

1) 每辆车从停车场出发，并最终返回停车场；

2) 每个顾客有且只能被访问一次；

3) 每辆车所配送的货物都不超过车辆本身的容

量。

假设停车场用 0表示，车辆数为

，顾客数为

，

每个顾客的需求为

，顾客

和

之间的距离为 Cij，

则最小化车辆的总距离为

10 0

min

KNN kk

ij ij

ki j

= ==

∑∑∑

(1)

S.t.

ki j

X

=



如果车辆从顾客行驶到顾客

其他

(2)

1,1, 2,,,

KN k

Xj N

= =

∑∑



(3)

1,1, 2,,,

KN k

Xi N

= =

∑∑



(4)

0,1,2, ,;1,2, ,,

it tj

XX kKtN

= =

−== =

∑∑



(5)

,1, 2,,,

jij k

DX QkK

= =



≤=





∑∑ 

(6)

1,1, 2,,,

Nkj

Xk K

≤=

∑



(7)

1,1, 2,,,

Xk K

≤=

∑

(8)

{ }

0,1,,0,1,2,, ;1,2,, ,

XijNk K∈= =

(9)

约束(3)和(4)保证每个顾客有且只能被访问一次；

约束(5)保证到达顾客的车辆数等于离开顾客的车辆

数；约束 (6)保证每条车辆路径上所配送的货物都不超

过车辆本身的容量；约束(7)和(8)保证每辆车的使用不

超过一次；约束(9)满足决策变量约束。

3. 教与学算法简介

教与学算法主要模拟班级中课程学习的两种基

本模式：1) 教师教学阶段：学生通过教师授课进行学

习；2) 学生互学阶段：学生之间相互学习，共同提高。

教与学算法中的所有学生相当于一个种群，学生所要

学习的课程相当于所要优化问题的决策变量，学生的

总成绩相当于所要优化问题的目标值，所有学生中总

成绩最好的学生作为教师。该算法主要分为两个过程：

教师教学阶段和学生互学阶段。

3.1. 教师教学阶段

在这个阶段，教师通过授课的方式来提高整个班

级的平均成绩。假设有 n门课程，m个学生，在迭代

次数 t时，所有学生的课程 j的平均成绩为 Mjt，所有

学生中总成绩最好的个体为Xbest,t，选取该个体作为教

师，则教师与学生在课程j上的成绩差值用公式(10)

计算。

是[0, 1]范围内的随机数，

是教学因子，取

1或者 2，由随机数控制，采用公式(11)计算。为了将

学生的成绩向教师移动，采用公式(12)对所有学生个

体进行更新。如果更新后的个体

jkt

X′

对应的目标值更

好，则接受该更新个体，否则保持原来的个体

jkt

。

( )

,best,jttjtFjt

DMrXT M= −

(10)

OPEN ACCESS 17

基于离散教与学算法求解车辆路径问题

( )

round 1rand0,1

T= +

(11)

jkt jktjt

XX DM

′= +

(12)

3.2. 学生互学阶段

在此阶段，学生通过相互学习来提高各自的成绩。

对于一个给定的学生 P来说，随机选取与该同学成绩

不相等的学生Q，通过比较这两个学生的成绩来决定

如何更新学生 P，具体的更新策略如公式(13)所示，

()

,,jPt

′

表示学生 P的成绩，

()

,,jQt

′

表示学生 Q

的成绩。如果更新后的个体

,,jPt

X′′

对应的目标值更好，

则接受该更新个体。

() () ()

()() ()

,,,, ,,,,,,

,if

jPt

jPt tjPtjQtjPtjQt

jPt tjQtjPtjPtjQt

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

基于离散教与学算法求解车辆路径问题

所获得的序列就表示车辆访问顾客的顺序。例如，假

设要配送货物的顾客数为 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

ii j

PCC CC

=−−

∑

(14)

4.2.2. 迭代变换法变异

当采用轮盘赌策略从种群中选出m个个体后，由

于选出来的个体可能重复，因此采用迭代变换法对选

出来的个体进行一次随机变异。迭代变换法的具体步

骤如下所示：

步骤 1：从个体P中随机选择两个位置i和j，如

图3所示，i = 3，j = 6；

步骤 2：交换i和j两个位置处的实数形成一个新

的解 C1；

步骤 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

Figure 3. Iterated swap procedure

图3. 迭代变换法

OPEN ACCESS 19

基于离散教与学算法求解车辆路径问题

解C2、C3、C4、C5；

步骤 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+1

j+1

i+1

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

’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

24581736

解码

变异

变异前

变异后

Figure 6. Duplicate solution modified by mutation

图6. 重复个体变异

OPEN ACCESS

基于离散教与学算法求解车辆路径问题

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. European 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 optimization. Engineering Structures, 34, 225-

232.

[6] Lin, S. (1965) Co mpute r solu tions o f the tr aveling sal esman prob-

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 Appli-

cations of Artificial Intelligence, 21, 548-557.

[8] Augerat, P., Belenguer, J.M., Benavent, E., et al. (1995) Com-

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 Engi-

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