基于遗传算法的物流配送路径优化问题研究
郎茂祥
（北方交通大学 交通运输学院，北京 100044）
摘 要：论文在建立物流配送路径优化问题的数学模型的基础上，构造了求解该问题的
遗传算法，并进行了实验计算。计算结果表明，用遗传算法进行物流配送路径优化，可以方
便有效地求得问题的最优解或近似最优解。
关键词：物流配送；遗传算法；优化
2 物流配送路径优化问题的数学模型
物流配送路径优化问题可以描述为：从配送中心（或称物流据点）用多辆汽车向多个需
求点（或称顾客）送货，每个需求点的位置和需求量一定，每辆汽车的载重量一定，要求合
理安排汽车路线，使总运距最短，并满足以下条件：（1）每条配送路径上各需求点的需求
量之和不超过汽车载重量；（2）每条配送路径的长度不超过汽车一次配送的最大行驶距离；
（3）每个需求点的需求必须满足，且只能由一辆汽车送货。本文借鉴文献[3]建立的车辆路
径问题的数学模型，并通过考虑上述物流配路径优化问题的约束条件和优化目标，建立了物
流配送路径优化问题的数学模型。
设配送中心有 K 辆汽车，每辆汽车的载重量为 Qk（k=1，2，···，K），其一次配送的最
大行驶距离为 Dk，需要向 L 个需求点送货，每个需求点的需求量为 qi（i=1，2，···，L），
需求点 i 到 j 的运距为 dij，配送中心到各需求点的距离为 d0j（i、j=1，2，···，L），再设 nk
为第 k 辆汽车配送的需求点数（nk=0 表示未使用第 k 辆汽车），用集合 Rk 表示第 k 条路径，
其中的元素 rki 表示需求点 rki 在路径 k 中的顺序为 i（不包括配送中心），令 rk0=0 表示配送
中心，则可建立如下物流配送路径优化问题的数学模型：
（1）
.
K
k i
krrrr
n
nsignddZ
k
kkknkiik
1 1
)]([min
0)1(
n
Qq
k
ki
i
kr
1
（2）
（3）
（4）
（5）
（6）
（7）
（8）
上述模型中，（1）式为目标函数；（2）式保证每条路径上各需求点的需求量之和不超
过汽车的载重量；（3）式保证每条配送路径的长度不超过汽车一次配送的最大行驶距离；
（4）式表明每条路径上的需求点数不超过总需求点数；（5）式表明每个需求点都得到配送
服务；（6）式表示每条路径的需求点的组成；（7）式限制每个需求点仅能由一辆汽车送货；
（8）式表示当第 k 辆汽车服务的客户数≥1 时，说明该辆汽车参加了配送，则取 sign(nk)=1，
当第 k 辆汽车服务的客户数<1 时，表示未使用该辆汽车，因此取 sign(nk)=0。
k
i
krrrr D
n
nsigndd
k
kkknkiik
)(
1
0)1(
Lnk 0
Ln
K
k
k
1
},...,2,1,,...,2,1|{ kkikik niLrrR
21 kk
RR 21 kk
其他0
11
)( kk
n
nsign
3 物流配送路径优化问题的遗传算法
遗传算法的基本要素
遗传算法是一种“生成+检测”的迭代搜索算法。该算法以群体中的所有个体为操作对象，
每个个体对应研究问题的一个解。选择、交叉和变异是遗传算法的三个主要操作算子。该算
法包括以下 6 个基本要素：
（1）编码。由于遗传算法不能直接处理解空间的数据，因此，必须通过编码将它们表
示成遗传空间的基因型串结构数据。
（2）初始群体生成。由于遗传算法是一种群体型搜索方法，所以必须为遗传操作准备
一个由若干个体组成的初始群体，每个个体都应通过随机方法产生，并分别对应研究问题的
一个解。
（3）适应度评估。遗传算法在搜索过程中一般不需要其他外部信息，仅用适应度来评
估个体的优劣，并以其作为遗传操作的依据。
（4）选择。选择操作是为了从当前群体中选出优良的个体，使它们有机会作为父代为
下一代繁殖子孙，个体的适应度越高，其被选择的机会就越大。
（5）交叉。它是遗传算法中最主要的操作，一般分两步进行，一是对群体中的个体进
行随机配对；二是在配对个体中，随机设定交叉处，使配对个体彼此交换部分信息。
（6）变异。即按一定的概率改变个体的基因链。变异操作同样是随机进行的，其目的
是挖掘群体中个体的多样性，克服遗传操作可能限于局部解的弊端。
物流配送路径优化问题的遗传算法的构造
针对物流配送路径优化问题的特点，作者构造了求解该问题的遗传算法。
（1）编码方法的确定。根据物流配送路径优化问题的特点，作者采用了简单直观的自然
数编码方法，用 0 表示配送中心，用 1、2、···、L 表示各需求点。由于在配送中心有 K 辆
汽车，则最多存在 K 条配送路径，每条配送路径都始于配送中心，也终于配送中心，为了
在编码中反映车辆配送的路径，作者巧妙地采用了增加 K-1 个虚拟配送中心的方法，分别
用 L+1、L+2、···、L+K-1 表示。这样，1、2、···、L+K-1 这 L+K-1 个互不重复的自然数的
随机排列就构成一个个体，并对应一种配送路径方案。例如，对于一个有 7 个需求点，用 3
辆汽车完成配送任务的问题，则可用 1、2、···、9（8、9 表示配送中心）这 9 个自然数的随
机排列，表示物流配送路径方案。如个体 129638547 表示的的配送路径方案为：路径 1：
0-1-2-9（0），路径 2：9（0）-6-3-8（0），路径 3：8（0）-5-4-7-0，共有 3 条配送路径；个
体 573894216 表示的配送路径方案为：路径 1：0-5-7-3-8（0），路径 2：9（0）-4-2-1-6-0，
共有 2 条配送路径。
（2）初始群体的确定。随机产生一种 1~L+K-1 这 L+K-1 个互不重复的自然数的排列，
即形成一个个体。设群体规模为 N，则通过随机产生 N 个这样的个体，即形成初始群体。
（3）适应度评估。对于某个个体所对应的配送路径方案，要判定其优劣，一是要看其
是否满足配送的约束条件；二是要计算其目标函数值（即各条配送路径的长度之和）。本文
根据配送路径优化问题的特点所确定的编码方法，隐含能够满足每个需求点都得到配送服务
及每个需求点仅由一辆汽车配送的约束条件，但不能保证满足每条路径上各需求点需求量之
和不超过汽车载重量及每条配送路线的长度不超过汽车一次配送的最大行驶距离的约束条
件。为此，对每个个体所对应的配送路径方案，要对各条路径逐一进行判断，看其是否满足
上述两个约束条件，若不满足，则将该条路径定为不可行路径，最后计算其目标函数值。对
于某个个体 j，设其对应的配送路径方案的不可行路径数为 Mj（Mj=0 表示该个体对应一个
可行解），其目标函数值为 Zj，则该个体的适应度 Fj 可用下式表示：
Fj=1/（Zj+Mj×G） （9）
式中，G 为对每条不可行路径的惩罚权重，可根据目标函数的取值范围取一个相对较大的正
数。
（4）选择操作。将每代群体中的 N 个个体按适应度由大到小排列，排在第一位的个体
性能最优，将它复制一个直接进入下一代，并排在第一位。下一代群体的另 N-1 个个体需
要根据前代群体的 N 个个体的适应度，采用赌轮选择法[4]产生。具体地说，就是首先计算上
代群体中所有个体适应度的总和（ΣFj），再计算每个个体的适应度所占的比例（Fj/ΣFj），以
此作为其被选择的概率。这样选择方法既可保证最优个体生存至下一代，又能保证适应度较
大的个体以较大的机会进入下一代。
（5）交叉操作。对通过选择操作产生的新群体，除排在第一位的最优个体外，另 N-1
个个体要按交叉概率 Pc 进行配对交叉重组。本文采用了一种类似 OX 法[2]的交叉方法，现举
例说明之：①随机在父代个体中选择一个交配区域，如两父代个体及交配区域选定为：
A=47|8563|921，B=83|4691|257；①将 B 的交配区域加到 A 的前面，A 的交配区域加到 B 的
前面，得：A’=4691|478563921，B’=8563|834691257；①在 A’、B’中自交配区域后依次删除
与交配区相同的自然数，得到最终的两个体为：A”=469178532，B”=856349127。与其他交
叉方法相比，这种方法在两父代个体相同的情况下仍能产生一定程度的变异效果，这对维持
群体的多样化特性有一定的作用。
（6）变异操作。由于在选择机制中采用了保留最佳样本的方式，为保持群体内个体的
多样化，本文采用了连续多次对换的变异技术，使个体在排列顺序上的有较大变化。变异操
作是以概率 Pm 发生的，一旦变异操作发生，则用随机方法产生交换次数 J，对所需变异操
作的个体的基因进行 J 次对换（对换基因的位置也是随机产生的）。
4 实验计算与结果分析
作者根据上述遗传算法编制了 C 语言程序，并对文献[3]列出的一个某配送中心使用 2
辆汽车对 8 个需求点进行送货的物流配送路径优化问题实例进行了实验计算。设汽车的载重
量为 8t，每次配送的最大行驶距离为 40km，配送中心与各需求点之间、各需求点相互之间
的距离及各需求点的需求量见表 1。
表 1 配送中心与需求点之间的距离及各需求点的需求量表
dij (km)
j
i
0 1 2 3 4 5 6 7 8
0 0 4 6 9 20 10 16 8
1 4 0 4 10 5 11 10
2 6 0 10 10
3 4 0 10 5 9 9 15
4 9 10 10 10 0 10 10
5 20 5 10 5 10 0 7 9
6 10 9 7 0 7 10
7 16 11 9 9 7 0 10
8 8 10 15 10 10 10 0
qj (t) -- 1 2 1 2 1 4 2 2
根据上述实例的特点，作者在实验计算中采用了以下参数：群体规模取 20，交叉概率
和变异概率分别取 和 ，进化代数取 50，变异时基因换位次数取 5，对不可行路径
的惩罚权重取 100km。对上述问题，利用计算机随机求解 10 次，得到的计算结果见表 2。
表 2 物流配送路径优化问题的遗传算法计算结果
计算次序 1 2 3 4 5 6 7 8 9 10
配送总距离 Z /km 72 72 70 70 75 69
从表中数据可以看出，10 次运行得到的结果均优于节约法所得的结果 。而且第
5 次还得到了该问题的最优解 ，其对应的配送路径方案为：路径 1：0-4-7-6-0；路径
2：0-2-8-5-3-1-0。可见，利用遗传算法可以方便有效地求得物流配送路径优化问题的最优解
或近似最优解（或称满意解）。
5 结论
（1）在物流配送业务中，合理确定配送路径是提高服务质量、降低配送成本、增加经
济效益的重要手段。由于物流配送路径优化问题是一个 NP 难题，因此，采用启发式算法求
解是一个重要的研究方向。
（2）本文在建立物流配送路径优化问题的数学模型的基础上，构造了求解物流配送路
径优化问题的遗传算法。实验计算结果表明，遗传算法是一种性能优良的启发式搜索方法，
利用该方法可以方便有效地求得物流配送路径优化问题的最优解或满意解。
（3）本文所构造的进行物流配送路径优化的遗传算法，包括巧妙设计的个体编码方法、
个体适应值的计算方法以及选择、交叉和变异算子，对解决类似的组合优化问题具有一定的
参考价值。
