第28卷 第5期中南林业科技大学学报V o l.28 N o.5 2008年10月Journal of Central South U niversity of Fo restry&T echno logy O ct.2008 文章编号:1673-923X(2008)05-0113-06
程赐胜，蒲云虎，吴 颖
(长沙理工大学交通运输学院，湖南长沙410076)
摘 要: 选址2路径问题(L ocati on2Routing P roblem,L R P)是物流系统中的一个组合优化问题.一般采用“两阶段法”将其分解为选址分派和车辆路径问题来求解.这种两阶段法未能考虑到问题的内在联系，因而往往不能得到满意的解.本研究把L R P问题的解看作是一个整体，采用遗传算法求解该问题；对遗传算法的编码进行重新设计，对交叉和变异操作做了改进，因而能够更容易得到问题的最优解.最后通过算例分析，验证了本算法的可行性. 关键词: 物流系统；选址2路径问题(L R P)；优化模型；遗传算法
中图分类号: F252;F253 文献标志码: A
Si ngle-stage A lgor ithm of L oca tion-Routi ng Problem Opti m iza tion
M odel for I n tegra ted L og istics
CH EN G C i2sheng,PU Yun2hu,W U Y ing
(T raffic and T ranspo rtati on Co llege,Changsha U niversity of Science and T echno logy,Changsha410076,H unan,Ch ina)
Abstract:L ocati on2routing p roblem(L R P)in a logistics system is a p roblem of com binati onal op ti m izati on.A usual so luti on to L R P can be obtained by dividing the p roblem into locati on assignm ent and veh icle routing w ith a two2phase m ethod but th is m ethod often does no t lead to a satisfacto ry result fo r its igno ring the inherent relati on betw een the two sides.T h is paper,using a genetic algo rithm to so lve the p roblem,regards its so luti on as a w ho le and thus easily obtains the op ti m al so luti on by designing the algo rithm coding and
i m p roving the cro ssover and m utati on.T he feasibility of th is algo rithm has been verified th rough examp les.
Key words:logistics system;locati on2routing p roblem(L R P);op ti m izati on model;genetic algo rithm
选址2路径问题(L ocati on2Rou ting P rob lem,L R P)是物流规划中选址定位问题和车辆路径问题的集成，是物流系统优化的难题.多年来，国内外许多学者对L R P的求解算法进行了大量研究[1].Jacob sen和M adsen在对报纸配送系统研究时，引入了三种启发式算法去解决三层系统的L R P问题[2];Perl和D ask in提出了一种解决复杂L R P的三阶段算法;L in et al.在研究香港某通讯公司帐单递送问题时，提出了将L R P转化为选址2路径安排2配载三个阶段交替求解的优化过程，使用阈值接受(TA)和模拟退火(SA)的启发式方法[3]；张潜对L R P 做了系统的研究，并采用聚类—混沌搜索和模糊优化遗传算法来解决此类问题[4].
L R P常规的解决方法均倾向于把选址定位和车辆路径作为独立的问题进行两阶段求解，但是第一阶段的求解结果往往会极大影响到第二阶段的求解结果，即使第一阶段求得很好的结果，也无法保证最终会得到较好的解.这种方法没有考虑选址定位和车辆路径两个问题之间相互影响和制约的关系，往往得不到满意的解答.本研究采用遗传算法对该问题进行求解，将L R P的解看作一个整体，通过对L R P的解的结构进行分析，重新进行设计和改进遗传算法中的编码、交叉、变异各种算子，利用遗传算法体搜索的特点，减少了求解结果停滞于局部最优的概率，提高了解空间分布式搜索的效率[5～7].
Ξ收稿日期:2008210212
作者简介：程赐胜(1953—)男，广东中山人.长沙理工大学交通运输学院教授，研究生导师，研究方向：物流工程、交通运输规划与管理.
1 选址2
路径问题的模型
图1 L R P 概念模型示意图
F ig .1 L ocation -Routi ng proble m m odel
1.1 L R P 的表述
L R P 可以描述为：给定与实际问题相符合的一系列
潜在的备选物流节点，在这些潜在的节点中选择并确定出若干物流节点，同时需要制定出一套从各个物流节点到各个客户点的运输路线，确定的依据是满足问题的目标(通常是总的费用或者时间最小)，其中客户点的位置和客户的需求量是已知的和可估算的，一系列潜在备选物流节点的位置也是已知的.概念模型如图1所示.1.2 L R P 的数学模型 选址2路径问题(L ocati on 2Rou ting P rob lem ,L R P )数学模型如下:
dc-dc变换器目标函数: M in F =2i ∈S 2j ∈S 2k ∈V
复合硅微粉
C ij X ijk q j d ij +2i ∈G
(F r +W r )Z r .
(1)约束条件: 2k ∈V 2i ∈S
X
ijk
=1,Π给定j ∈H ,(2) 2j ∈S q j 2i ∈S X
ijk
≤Q k ,
Πk ∈V ,(3) 2i ∈S
X
ip k
-2i ∈S
X
p jk
≥0,
Πk ∈V ,p ∈S ,(4) 2r ∈G 2j ∈H X
rjk
≤1,Πk ∈V ,(5) 2k ∈V X
r m k
+Z r +Z m ≤2,
Πr ,m ∈G ,(6) 2k ∈V 2j ∈H
X
rjk
-Z r ≥0,
Πr ∈G ,(7) 2j ∈H X
rjk
-Z r ≤0,
Πk ∈V ,r ∈G ,
(8) 2r ∈G 2i ∈H X
rjk
+2j ∈H 2m ∈G
X jm k
≤1,Πk ∈V ,(9) X
ijk
=0或1,
Πi ,j ∈S ,k ∈V ,(10)
Z r =0或1,
Πr ∈G .
(11)式(1)～(11)中:G ={r r =1,…,R }为潜在的物流节点的集合;H ={i i =R +1,…,R +N }为需要物流服务的客户点;S ={G }∪{H }为潜在的物流节点和客户点的总和;V ={v k =v 1,v 2,…,v K }为K 个车辆可以到达物流
节点的运输路线;C ij 为从客户i 点到客户点j 的平均单位运输成本;d ij 为从客户点i 到客户点j 的距离;q j 为客户点j 的物流需求量;Q K 为车辆K 的容量;F r 为在r (r =1,…,R )处建立物流节点的成本;W r 为在r (r =1,…,R )处运作物流节点的成本.决策变量为:X ijk (i ∈S ,j ∈S ,k ∈V ,i ≠j )表示车辆K 是否从点i 到点j ;Z r (Πr ∈G )表示是否在r 处建立物流节点.
对以上各式简要说明：目标函数式(1)表示对总成本求极小值，其中第一项是运输成本，第二项是建设和运作物流节点所需的成本；约束条件式(2)表示每个客户节点仅由一辆车提供服务；式(3)表示每辆车装载的货物不超过其装载能力；式(4)保证运输路线具有空间连续性；式(5)表示每条运输路线最多从一个物流节点开始；式(6)表示物流节点之间没有连接；式(7)保证每辆车的运输路线源自于物流节点；式
(8)保证每辆车的运输路线只能有一个物流节点作为起点；式(9)保证任何两个物流节点不会在一条运输路线上；式(10)和式(11)保证了决策变量取整数.
2 选址2路径问题的遗传算法设计
风力摆
遗传算法(Genetic A lgo rithm ,GA )是20世纪60～70年代由美国M ich igan 大学的Ho lland 教授及其学生模拟生物进化机制发展起来的优化搜索算法，该算法将操作对象看作是一个生物体，按照自然选择、适者生存的进化理论进行多代繁殖，经过淘汰后选择出优秀个体，作为系统的最优解.在遗传算法中，体由一组染
411中 南 林 业 科 技 大 学 学 报第28卷
体组成，每个染体就是一个问题的解，组成染体的基因就是问题的决策变量.遗传算法所涉及的5大要素为：编码、设定初始体、适应度函数、遗传操作(选择、交叉、变异)和参数值的设定.遗传算法要素设计如下.2.1 编码
分析选址2路径问题的解的结构，可以看出问题的解必须包含以下4个方面的内容：选址、分派、车辆安排、路径选择.由于遗传算法运算的是解集的编码，而非解集本身，因此对问题的解的编码必须能够反映出这4个内容，以实现对选址2路径问题的解的描述.
一个染体代表一组问题的可行解，本研究采用基于序数的非定长实数编码来表述染体.首先，对待选的物流节点和客户点编号，利用所编的序号进行编码；然后根据解的特点确定染体的构成，染体的长度可以不相等，但是每个染体必须由若干个子串组成，每个子串的第一个数字表示已选择的物流节点的序号，其余的数字表示一条车辆子路径上访问客户点的先后顺序.每个子串表示一个车辆安排，每个子串顺序就是一条行车路径，子串的含义为：车辆从物流节点出发，按照一定的行车路径(顺序)访问客户点并回到原物流节点的过程.表达
形式如下：染体V k ={C 1k ,C 2k ,…,C w k ,…,C 5k }，其中1≤w ≤s ,1≤s ≤t (t 为客户点数目),k =1,2,3…,m (m 为染体的数目)；子串C w k ={l w 0,l w 1,l w 2,…,l w d },l w 0表示物流节点的序号,l w 1,l w 2,…,l w d 表示客户点的序号
.例如，有5个备选的物流节点和15个客户点，对它们编序号:1,2,3,…14,15是客户点的序号,16,17,18,19,20是待选的物流节点的序号.某一条染体V k ={1613162451867818101214199111315}，该染
体中有5个子串:C 1k =(1613);C 2k =(1624);C 3k =(18678);C 4k =(18101214);C 5k =(199111315)；在这
5个子串中，备选的物流节点的序号只出现了16、18、19，即编号为16、18、19的节点被选择为物流ei硅钢片
节点；而且客
户点1,3,2,4,5被分派给物流节点16，客户点6,7,8,10,12,14被分派给物流节点18，客户点9,11,13,15被分
派给物流节点19；其中子串C 5
k =(199111315)表示车辆从编号为19的物流节点出发，经过编号为9,11,13,15的客户点最后返回原物流节点的过程，即:19→9→11→13→15→19.2.2 随机产生初始种
产生含有m 条染体的种的伪代码如下:begin
fo r k =1to m
产生m 条染体 从R 个待选的节点中随机选择个作为物流节点
fo r i =1to n 对n 个物流节点进行分派高炉喷煤
分别计算R i 和r ip R i 表示物流节点i 与其它物流节点最短距离的一半,
r ip 表示物流节点i 与任意客户点p 的距离
if r ip <R i then 将客户点p 分派给物流节点i ; nex t i ;
if 客户点p 没有被分派then 将客户点p 分派给最近的物流节点i ; fo r i =1to n
物流节点i 从分派的客户点集中随机选一个节点相连产生一条新路线; w h ile (该物流节点所分派的客户点集不为空)do 从客户点集中随机选择一个客户点插入路线；累加整条路线的总需求量;
w h ile (该条路线的运载量不超限)do
从客户点集中删除已经加入路线的客户点;
else
物流节点与随机选择的客户点直接相连产生另外一条路线; end do
if (该物流节点所分派的客户点集为空)then 跳出此循环; end do nex t i
5
11第5期程赐胜等：集成化物流选址2路径问题优化模型的算法研究
nex t k end
2.3 计算适应度值
适应度函数反映了每一个染体适应环境的能力，通过计算染体的适应度，决定该染体是否保留，适应度值域在[0,1]之间.本研究对染体进行评估的适应度函数为:
f k =1
i ∈S j ∈S k ∈V
C ij X ijk q j d ij +2r ∈G
(F r +W r )Z r
.
(12)2.4 选择
(1)对种中所有染体的适应度值求和
F =2m
k =1
f k .
(13)
(2)对各个染体V k 计算选择概率P k
P k =
f k
F
, k =1,2,3…,m .(14)
(3)对各个染体计算累积概率
q k =2k
j =1
p j , k =1,2,3…,m .
(15)
(4)在[0,1]之间产生均匀分布的伪随机数r k
(5)若r k ≤q 1，选择第一个染体V 1；若q k -1<r k ≤q k ,2<k ≤m ，则选择染体V k .2.5 交叉操作
本文中，采用部分匹配交叉(Partially M atched C ro ssover ,PM X )的方法进行杂交，即先随机从染体中挑选欲进行交叉的两父代染体，再随机产生交叉点，定义交叉点邻近的区域为匹配区域，并使用位置交换操作交换两个父代的匹配区域产生子代.染体交叉步骤如下.
(1)选择参数P c 作为交叉操作的概率，在[0,1]之间产生均匀分布的伪随机数r k (k =1,2,…,m )，如果r k <P c ，则选择V k 作为一个父代，然后对选择出的父代随机配对(V i ,V j )，其中(1≤i <j ≤m ).
(2)父代V i ,V j 均由不同长度和数量的子串组成，随机选择V i 的第C w 1i 条子串和V j 的第C w 2
j
条子串进行交叉，首先使用位置交换操作将第C w 1i 条子串交叉至V j 的末端，同时将V j 中与C w 1
i 中重复的位置消去，得到V j 的子代V ′j ；然后将第C w 2j 条子串交叉至V i 的末端，同时将V i 中与C w 2j 中重复的位置消去，得到V i 的子代V ′i
.(3)如果产生的子代中因为合并路线而使子串的车辆运载量超标，则将超过的部分形成一个新的子串；如果交叉后的子串中只有物流节点，而没有客户点，则将该物流节点消去
.
图2 交叉过程示意图
F ig .2 The sche matic di agram of crossover process
以上例进行说明，按照交叉操作的概率选择若干对父代染体，其中一对父代染体为:V 1={16131624
51867818101214199111315},V 2={1621371668194512209101520131114}.随机选择子串
C 41=(18101214)和C 4
2=(2091015)作为匹配区域进
行交叉，交叉示意图如图2所示.2.6 变异操作
从初始种中按照变异概率选择进行变异的染
体，分别对染体子串中的路径和物流节点进行变异操
作，分两步变异的方法如下.
(1)物流节点变异：在父代染体V k 中，随机选择S 条子串C 1k ,C 2
k ,…,C s k ,1≤s ≤t (t 为客户点数目)，其中子串C w k ={l w 0,l w 1,l w 2,…,l w d },1≤w ≤s ,d 为子串中客户点的数目
.对这S 条子串序列的第一位l w 0，即物流节点进行变异，即对于每一个l w 0，从物流节点R 中随机选择一个物流节点来代替，记作l ′
w 0，则得到经过物流节点变异
后的新子串为C w ′k ={l ′
w 0,l w 1,l w 2,…,l w d }
.对这S 条子串按照同样的方法进行变异操作，得到经过变异后的子代染体V ′
k .
611中 南 林 业 科 技 大 学 学 报第28卷
(2)路径变异：在父代染体V k 中，随机选择S 条子串C 1k ,C 2k ,…,C s k ,1≤s ≤t (t 为客户点数目)，其中子串C w
k
={l w 0,l w 1,l w 2,…,l w d },1≤w ≤s ,d 为子串中客户点的数目.对子串中除过第一位外的序列进行随机排列:l w 1,
l w 2,…,l w d ]l ′
w 1,l ′
w 2,…,l ′
w d ，则得到经过路径变异后的新子串为C w ′
k ={l w 0,l ′w 1,l ′w 2,…,l ′
w d }，对这对这S 条子串按
照同样的方法进行变异操作，得到子代染体V ′
k
.
图3 变异过程示意图
F ig .3 The sche matic di agram of m ut ation process
对上例中的染体V 1执行变异操作进行说明.选取
V 1的子串C 41=(18101214)和=C 5
1(199111315)分别
进行物流节点和路径的变异，变异操作如图3所示.2.7 参数值设定
在遗传算法的运行过程中，存在着对其性能产生重大影响的一组参数.这组参数在初始阶段或体进化过程中需要合理的选择和控制，使GA 以最佳的搜索轨迹
达到最优解.主要参数包括体规模n ，交叉概率P c 以及
变异概率P m .许多学者进行了大量实验研究，给出了最
优参数建议.一般取n =20～200,P c =0.60～1.00,P m =0.005～0.01.
3 算例分析
沿用上面提到的例子，采用同种型号的车辆从5个潜在的备选物流节点给15个客户点提供物流服务.假设
车辆的单位平均运输成本C ij 为2元
(t ・km )；车辆的容量为8t ；按照上面的方法对物流节点和客户点编序号，物流节点和客户点之间的最短距离、客户点之间的最短距离、物流节点的建设和运营费用如表1所示.
表1 选址2路径问题(L R P )基本参数表
(单位:d ij km ;q j t ;F r ,W r
万元)Table 1 The essen ti al param eter of lacation -routi ng proble m
d ij
123456789101112131415F r
W
r
10
2622524262729892120841667615211220网邻
4826688858928611470150501268630
74204062767098581349811811840
5854326660884413248928450
20425650786212410611811860
22363058589410211411470
34285636928010210280
424470801147611690
28646411460100100
924613660100110
84925623120
1002828130
7636140
4015
0q j
2.31.7
3.521.232.121.5132.62.61.6
4.516703892369410668102961248011612884880251780625836381843024524088849696158501814413812211210282806852527212921656752019140114156112154152130154138138941067478781204020
194
168
188
166
174
154
92
140
90
90
58
75
68
80
69
65
18
其计算步骤为:
Step 1 设定遗传算法的参数值n =20,P c =0.7,P m =0.005，进化代数200；并初始化种;Step 2 计算种中每个染体的适应度值;
Step 3 遗传操作(选择适应度值大的个体保留，按照一定概率进行交叉和变异操作)
Step 4 判断体性能是否满足某一指标，或者己完成预定迭代次数，满足则以进化过程中所得到的具有最大适应度的个体作为最优解输出，终止计算；不满足则返回步骤(2).
7
11第5期程赐胜等：集成化物流选址2路径问题优化模型的算法研究
