第 ! 卷" 第 ! 期
#$$! 年 %# 月
交 通 运 输 工 程 学 报
&’()*+, ’- .)+--/0 +*1 .)+*23’)4+4/’* 5*6/*77)/*6
8’,9 !" :’9 !
;70< #$$!
收稿日期：#$$!=$%=%$
作者简介：卜" 雷（%>?@=），女，山东蓬莱人，同济大学讲师，博士，从事智能运输系统研究<
文章编号：%A?%=%AB?（#$$!）$!=$$C!=$!
优化普零货物拼箱配装的遗传算法
卜" 雷%，尹传忠#，蒲" 云B
（%9 同济大学 运输管理工程系，上海" #$$$>#；#9 西南交通大学 交通运输学院，
四川 成都" A%$$B%；B9 西南交通大学 研究生院，四川 成都" A%$$B%）
摘" 要：应用遗传算法，考虑货物装载重量、装载容积、优先装箱及非同时配装等约束条件，采用适
当的个体编码方法，并构造合理的适应值函数，优化铁路集装箱运输中的普零货物拼箱配装。结果
发现以 !# 件货物装入 %$ 4箱，利用遗传算法得到的集装箱装载重量利用率为 CB9 CD，优化了装载
结果，达到了装载要求，这说明该方法是可行的。
关键词：物流工程；装箱；遗传算法；优化
中图分类号：E%A>" " " 文献标识码：F
!"#"$%& ’()*+%$,- .*+ */$%-’( ’++’#)"-"#$ *. )"#"+’( /%"&" )**01
GE H7/%，IJ: KL(+*=ML’*6#，NE I(*B
（%9 ;73+)4O7*4 ’- .)+*23’)4+4/’* +*1 P+*+67O7*4 5*6/*77)/*6，.’*6Q/ E*/R7)2/4S，TL+*6L+/ #$$$>#，KL/*+；
#9 T0L’’, ’- .)+--/0 +*1 .)+*23’)4+4/’* 5*6/*77)/*6，T’(4LU724 &/+’4’*6 E*/R7)2/4S，KL7*61( A%$$B%，KL/*+；
B9 T0L’’, ’- V)+1(+47，T’(4LU724 &/+’4’*6 E*/R7)2/4S，KL7*61( A%$$B%，KL/*+）
231$+’&$：J* ’)17) 4’ O+W7 6’’1 (27 ’- 0’*4+/*7)X2 ,’+1/*6 U7/6L4 ’- R’,(O7 /* )+/,U+S 4)+*23’)4+4/’*，
4L/2 3+37) 0’*24)(0471 )7+2’*+Y,7 0’1/*6 +*1 -/4*722 -(*04/’* YS /O3)’R71 67*74/0 +,6’)/4LO，+00’)1/*6 4’
,’+1/*6 U7/6L4，R’,(O7 +*1 3)/’)/4S< J4 U+2 -’(*1 4L+4 !# 3/7072 ’- 6’’12 +)7 ,’+171 /*4’ + %$ 4
0’*4+/*7)，4L7 0’*4+/*7) (2+67 )+4/’ ’- ,’+1/*6 U7/6L4 /2 CB9 CD < F33,/71 )72(,4 2L’U2 4L+4 4L7 +,6’)/4LO
/2 -7+2/Y,7< # 4+Y2，% -/6，> )7-2<
4"5 6*+01：,’6/24/02 7*6/*77)/*6；,’+1/*6 /* 0’*4+/*7)；67*74/0 +,6’)/4LO；’34/O/M+4/’*
27$,*+ +"17-"：GE H7/（%>?@=），-7O+,7，NL;，CA=#%=@%$B$##>，,7/Y(B$@Z 2/*+< 0’O<
89 引9 言
在铁路集装箱运输中，对于货物批量不能装满
一个集装箱的零星小批量普通普零货物，可以进行
拼箱配装，这类合理配装的装箱判定问题属于
:NK［%，#］，对于这类问题的求解方法通常采用动态规
划方法和 $=% 规划算法［B］。但是随着配装问题规模
的不断增大，其计算时间会以指数规模不断地增加，
甚至达到无法忍受的程度，这就要求寻求一种适合
于求解大规模普零货物配装问题的有效方法。而遗
传算法（简称 VF）作为一种基于生物遗传和进化机
制的自适应概率优化技术［%］，同传统的优化方法相
比，具有运算简单，搜索过程灵活，搜索效率高以及
隐含并行性等特点，是一类可用于复杂系统优化计
算的鲁棒搜索算法，能够很好地解决普零货物集装
箱配装问题求解过程中的时间维数灾难问题，有利
于促进铁路集装箱运输中充分利用集装箱载重或容
积，提高集装箱使用效率［! [ >］。
:9 拼箱配装优化数学模型
为使问题简化，约定：每一批货物为一张货票；
货票中货物的外径体积［#］是由于待装货物外形及
万方数据
包装条件等因素影响，在装运堆码时产生的体积；指
令性优先配装货票集中的任意两票货物不受混装限
制。各变量的表示意义：! 为待配装货物集｛" ! "，
#，⋯，#｝；$" 为第 "票货物的质量（ $）；%" 为第 " 票货
物的外径体积（%&）；&%’(为待装集装箱的载重（ $）；’
为待装集装箱的容积（%&）；&%)*为待装集装箱最小
货物装载质量（ $）；’%)*为装箱货物最小总外径体积
（%&）；#为货票总数（张）；(+ 为指令性优先装箱货
票集；,(" ,为 (" 中的货票总数（张）；(" 为在混装限
制条件下与货票 " 不能同时装配的货票集；)" 为货
票 "的配装状态。则基于文献［&］的数学模型对普
零货物拼箱配装优化模型描述如下
%’(- *（)）+ %
"&!
［!%" ,（" - !）$"］)"
./ $/
!’%)* )%
"&!
%")" ) ’%’(
（" - !）&%)* )%
"&!
$")" ) &%’(
)" + "- - - - - - - （ "& (+）
)" ,
"
. (" .%/&("
)/ ) "-（ "& !
）
)" !
" （当货票 "货物配装时）
+ （当货票 "货物不配装时{ ）
! !
" （当追求目标为集装箱容积利用率最大时）
+ （当追求目标为集装箱载重利用率最大时{ ）
模型中第 " 项为配装货票货物总外径体积约
束；第 # 项为配装货票货物总质量约束；第 & 项为优
先装箱约束；第 0 项为非同时配装约束。
!" 求解拼箱配装优化问题的遗传算法
为增强简单遗传算法的搜索效果和搜索效率，
较好地发挥其优越性，本文构造了改进的遗传算法。
同时考虑到在铁路普零货物拼箱配装过程中，有时
会要求某些货物为指令性优先装箱货物，因此在算
法构造过程中分存在指令性优先装箱货票集和不存
在指令性优先装箱货票集。
!# $" 不存在指令性优先装箱货票集
#1 "1 "- 拼箱配装编码
由于拼箱配装是将同一到站不同收货人的货物
混装在 " 个集装箱内，因此编码时不必考虑货物的
装箱顺序，采用常规二进制编码，即 +、" 字符串。以
货票 "中普零货物的配装状态作为染色体中的第 "
位遗传基因，每条染色体上有 #个遗传基因，即染色
体的编码形式为（)"，)#，⋯，)"，⋯，)#），每个基因的
取值为 )" ! + 或 "（ " ! "，#，⋯，#）。若第 " 张货票中
的普零货物不配装则 )" 取值为 +，否则 )" 取值为 "。
每种编码方式表示普零货物在集装箱中的一种配装
方法，如（"，+，"，+，+，"，+，⋯，+）表示该装载方案
为：货票 " ! "，&，2 的货物配装，货票 " ! #，0，3，4，
⋯，#的货物不配装。
#1 "1 #- 适应函数值计算
对于算法迭代过程中每代个体的优劣程度通过
个体适应函数值进行评价。在求解适应函数值的过
程中，采用罚函数法对违反约束条件的个体给予相
应的惩罚，以确保那些符合约束条件而较优的个体
有较大的生存机会。传统罚函数法需要罚因子无限
增大，而有可能使得问题的求解过程过早地收敛于
非极值点，为解决这种病态现象，本文采用退火精确
罚函数法［&］，基于模拟退火思想来选择惩罚因子，
使得惩罚因子随着进化的不断进行而逐渐增大，从
而使解群逐渐趋于可行解，最终收敛到全局最优解。
第 0代个体 )的适应函数值 1)0 计算方法为
1)0 + *（)）- 20%
3
" + "
%’(［+，3"（){ }）］
- - %
/&4
［!’%’( ,（" - !）&%’(］
3"（)）+ %
"&!
%")" - ’%’(
3#（)）+ !’%)* -%
"&!
%")"
3&（)）+（" - !）&%)* -%
"&!
$")"
30（)）+ %
"&!
$")" - &%’(
33（)）+ )" , %
/&("
)( )/ . (" . - "
- - 计算方法为
20 + " 5 6
6 + "6
"&［+，"］
式中：3"（ )）、3#（ )）为配装货物总外径体积惩罚；
3&（)）、30（)）为配装货物总质量惩罚；33（)）为混装
惩罚；20 为惩罚因子。
#1 "1 &- 遗传操作过程
在算法中，对个体实行的遗传操作过程包括复
制过程、交叉过程及变异过程。在复制过程中，实施
最优保留策略。将第 0代个体按照适应函数值大小
进行降序排列，首位个体即为最优个体，将其直接保
留至第 0 5 " 代作为第 " 个个体，而第 0 代中其余个
体以复制概率 &)0 进行复制至第 0 5 " 代。复制概率
36第 0 期- - - - - - - - - - 卜- 雷，等：优化普零货物拼箱配装的遗传算法
万方数据
!"# 计算方法为
!"# $（%
"
# & %!"#）%
’!$%
" $ &
（%"# & %!"#）
%!"# $ !"#%
"
#
’ ’ 在交叉过程中，依概率 !( 执行交叉操作，采取
三交配位法：在［&，)］间随机产生 ( 个整数 *&、*)、
*(（*& * *) * *(）分别作为父个体 +和 ,的交叉位
+ $（&，+，+，- &，&，+，- +，+，&，- &，+，&）
, $（+，&，+，- +，&，&，- +，+，+，- +，&，+）
’ ’ 首位基因至交配位 *& 间的基因不变，交配位 *&
至交配位 *) 间的基因相互交换，交配位 *) 至交配
位 *( 间的基因不变，交配位 *( 至末位基因间的基
因相互交换，形成 ) 个子个体
+ $（&，+，+，- +，&，&，- +，+，&，- +，&，+）
, $（+，&，+，- &，&，+，- +，+，+，- &，+，&）
’ ’ 在变异过程中，在［&，)］间随机产生 ) 个整数
.& 与 .)，作为变异基因位，并互换 ) 个位置的基因
值。
!" !# 存在指令性优先装箱货票集
在普零货物配装过程中，若存在指令性优先装
箱货票集 /+，且其货票数为 0，为了保证指令性优先
装箱货票在编码及遗传操作过程中的有效性，编码
时 "1 , &（ 1 , &，)，⋯，0），"1 , & 或 +（ 1 , 0 - &，0 - )，
⋯，)）。复制、交叉及适应函数值计算均同前述方
法相同，而变异操作有所不同。在［0 - &，)］间随机
产生 & 个整数 .& 作为变异基因位，改变该基因位的
基因取值。
!" $# 算法的实现过程
’ ’ ./01+ ’ 编码预处理。根据问题的具体约束条
件与要求进行有效的染色体编码，排除那些一定不
是可行解的编码方式。
2/01&’ 参数初始化。令迭代次数 # , +，确定算
法的最大迭代代数 2、初始群体规模 ’+、种群规模
’!$%、交叉概率 !( 和变异概率 !3 的值。
’ ’ 2/01)’ 产生初始种群。由 2/01+ 的染色体编码
随机产生规模为 ’+ 的初始群体，计算群体中所有个
体适应函数值 %"#，并将其按照 %
"
# 值降序排列，然后
由第 & 条染色体依次选取 ’!$%条不同染色体作为初
始种群。
2/01(’ 判断是否满足停止准则。若 # , 2，则转
2/013，否则进行 2/014。
2/014’ 实施最优保留策略。将最优个体直接
保留至下一代。
2/015’ 进行遗传操作。按照概率 !"#、!( 和 !3
分别选择个体执行复制、交叉和变异等遗传操作。
2/016’ 判断子代个体数目。若满足个体数目
4 , ’!$%，则计算子代个体的适应函数值 %
"
#，置 # ,
# - &，转 2/01(，否则转 2/015。
2/013’ 输出最优结果。适应函数值 %"# 最大的个
体为算法的最优个体，解码得到问题的最优配装方案。
$# 实例分析
利用 789&+型集装箱配装 4) 张货票的普零货
物，各货票的货物质量和外径体积见表 &，货票 & 的
货物必须优先装箱，且各货票中的货物性质与包装
不发生相互抵触，确定载重利用率最大的配装方案。
表 %# 各货票货物质量及外径体积
&’() %# *++,- ./’0123 ’4, 5+0/67
货票编号 *1 5 / 61 5 !( 货票编号 *1 5 / 61 5 !( 货票编号 *1 5 / 61 5 !(
& &: ))& &: +5 &5 &: +4+ ): 6+ ); &: &+) ): 46
) &: &56 &: ;< &6 +: <+5 &: )( (+ ): +4& ): )+
( +: 3++ ): ++ &3 &: ))+ +: 65 (& &: ;++ ): <+
4 &: )4( (: &4 &< &: +++ ): 4+ () ): 4++ (: )+
5 &: 6++ ): <6 &; &: 3<) +: <3 (( &: +); (: ++
6 &: 6&) ): &3 )+ &: &++ &: 54 (4 (: +++ &: )+
3 ): (++ 4: <+ )& &: +(+ 5: 6+ (5 &: <4+ &: )+
< &: ;(+ 5: )+ )) +: 3(+ 4: 4+ (6 &: 3;6 (: <;
; &: <5+ ): (+ )( &: +(+ &: <+ (3 ): 65+ &: +&
&+ &: ;++ (: <+ )4 ): 4(+ (: <+ (< &: ;35 &: )(
&& &: &)+ ): ++ )5 &: 5)+ 4: ++ (; +: <++ &: ++
&) &: 4(& 4: +) )6 &: <;+ 5: 46 4+ &: &++ (: )+
&( +: 6++ ): 3< )3 &: ()+ (: 54 4& &: )++ +: <+
&4 +: (+6 (: )) )< &: &5+ &: 6+ 4) ): +++ &: &+
6< 交’ 通’ 运’ 输’ 工’ 程’ 学’ 报’ ’ ’ ’ ’ ’ ’ ’ ’ ’ ’ )++4 年
万方数据
! ! 为了客观地评价本文提出遗传算法的可行性与
有效性，基于 "语言编程并在同一台计算机上运行，
分别应用动态规划方法、#!$ 规划算法和遗传算法对
该实例求解，每个算法独立地运行 %#次，各项参数取
值为："&’( )$*+ ,$ &
%，#&’( ),+ %,- .，#&/0 )1+ $2$ .，初
始群体规模 $# ) -##，种群规模 $&’( ) 3#，#% ) #+ 23，
#& )#+ #$，’ )$3#，( )3#，! )#+ ,4。遗传算法中每代
群体中个体平均适应函数值与进化代数之间的变化
关系见图 $，算法迭代了 $3# 次，但是在迭代到 ,% 次
时便收敛到全局最优点，最优配装方案见表 -。
表 !" 配装结果
#$%& !" ’()*+, -. /--0) $11$2/(3(2,
货票编号 $ - % 1 3 * 4 , 2 $# $$ $- $% $1
配装结果 $ # # # # # # # $ # # # # #
货票编号 $3 $* $4 $, $2 -# -$ -- -% -1 -3 -* -4 -,
配装结果 # # # $ # # # # $ # # # # $
货票编号 -2 %# %$ %- %% %1 %3 %* %4 %, %2 1# 1$ 1-
配装结果 # # # # $ # # # # # # $ # #
目标函数值 ,+ %,#
图 $! 适应函数值与进化代数之间的关系
5/67 $! 89:’./;0 ;< ’=9>’69 =’:?9 ;< </.09@@ <?0A./;0
’0B 9=;:?./;0’: 6909>’./;0
4" 结" 语
本文结合铁路普零货物运输的特点，提出应用
改进的遗传算法求解普零货物多车拼箱配装优化问
题，实例计算表明该算法编码简单、运算方便，尤其
在货票量多，配装规模大时，该算法在求得与传统优
化计算方法相同最优解的同时能够大大缩短计算时
间。但同时也应该看到，各项初始参数的适当选取
均会影响算法的收敛性、收敛速度和计算时间，这就
要求在实际问题的计算中通过大量的数值模拟计
算，从中选择比较理想的参数搭配，使得该算法更好
地发挥优越性。
参考文献：
’(.(1(25() ：
［$］! 周 ! 明，孙树栋7 遗传算法原理及应用［C］7 北京：国防出版
社，-###7
［-］! 康立山，谢! 云7 非数值并行算法（!）［C］7 北京：科学出版
社，$22,7
［%］! 李致中7铁道运输管理的数学模型及算法［C］7 武汉：华中理
工
大学出版社，$2237
［1］! 卜! 雷7 遗传算法确定零担货物的选择装箱方式［ D］7 交通运
输工程学报，-##-，-（%）：2%—2*7
EF G9/7 H9A/B/06 .; @9:9A. ’0B :;’B I/9A9 6;;B@ /0 A;0.’/09> JK
6909./A ’:6;>/.L&［ D］7 D;?>0’: ;< M>’<</A ’0B M>’0@I;>.’./;0
N06/099>/06，-##-，-（%）：2%—2*7（ /0 "L/09@9）
［3］! 卜! 雷7 零担货物序贯装箱优化问题的遗传模拟退火算法
［D］7西南交通大学学报，-##-，%4（3）：3%$—3%37
EF G9/7 O 6909./A ’0B @/&?:’.9B ’009’:/06 ’:6;>/.L& <;> ;I./&’:
@9P?90./’: A’@/06 ;< :9@@’0QA’>:;’B <>9/6L.@［ D］7 D;?>0’: ;<
R;?.LS9@. D/’;.;06 F0/=9>@/.K，-##-，%4（ 3）：3%$—3%37（ /0
"L/09@9）
［*］! 吴志远7基于遗传算法的退火精确罚函数非线性约束优化方
法［D］7控制与决策，$22,，$%（-）：$%*—$1#7
TF UL/QK?’07 O009’:/06 ’AA?>’AK I90’:.K <?0A./;0 J’@9B ;0
0;0:/09’> A;0@.>’/ ;I./&/V’./;0 &;B S/.L 6909./A ’:6;>/.L&@
［D］7 ";0.>;: ’0B H9A/@/;0，$22,，$%（-）：$%*—$1#7（ /0 "L/09@9）
［4］! 卜! 雷7 集装箱中零担货物合理混载的遗传退火进化算法
［D］7世界科技研究与发展，-##-，-1（*）：,,—2$7
EF G9/7 W909./A ’009’:/06 9=;:?./;0’>K ’:6;>/.L&@ ’II:/9B .; .L9
I/9A9 6;;BX@ >9’@;0’J:9 &/(9B :;’B/06 /0 A;0.’/09>［ D］7 T;>:B
RA/90A9QM9AL0;:;6K 89@9’>AL ’0B H9=9:;I&90.，-##-，-1（ *）：
,,—2$7（ /0 "L/09@9）
［,］! 8?J90@.9/0QC;0.’0; E，O0’0B’:/06’& W，U’0B/ Y7 O 6909./A
’:6;>/.L& ’II>;’AL .; I;:/AK B9@/60 <;> A;0@9P?90A9 &/0/&/V’./;0
［D］7 N?>;I9’0 D;?>0’: ;< ZI9>’./;0’: 89@9’>AL，-###，$-1（$）：
1%—317
［2］! MO[ \;06Q]/，UN[W \/，"OZ T9/7 89@;:=/06 >9@.>/A. [G^
I>;J:9& JK &/(9B 6909./A ’:6;>/.L&@［ D］7 D;?>0’: ;< 5?B’0
F0/=9>@/.K，-###，%2（3）：1*4—14#7（ /0 "L/09@9）
4,第 1 期! ! ! ! ! ! ! ! ! ! 卜! 雷，等：优化普零货物拼箱配装的遗传算法
万方数据
