货物配装问题两种算法的比较研究

杨 辉

摘要:货物配装问题是NP—难问题,对这类问题如何求解,学术界提出了多种算法,这些算法可归结为2大类:精确算法和启发式算法。通过对这2类算法中最具代表性的几种算法的分析、比较和总结,指出了各种算法的优缺点、适用范围和场合、存在的问题以及改进的方案,为货物配装问题求解过程中算法的选择提供了依据和参考。

关键词:货物配装;精确算法;启发式算法

中图分类号:U294文献标识码:A

Abstract: Loading of goods problem is an NP—hard problem, how to resolve this problem, academia have put forward many algorithms. These algorithms can be clarified as accurate algorithm and heuristic algorithm. By analyzing, comparing, summarizing some representative algorithms, points out advantages, dis—advantages, application scope and situation, problems, as well as improving project, this paper provides the reference for selecting algorithm when resolving loading of goods problem.

Key words: loading of goods; accurate algorithm; heuristic algorithm

1货物配装问题概述

货物配装问题的研究始于国外,自1939年(Kantorovich)、1940年(Brook等)以来,由于行业的需要,国外开始出现相关问题的研究。货物配装问题是指在配送中心,有若干需要送给不同客户且有不同装载要求的货物,有若干台车辆,要求合理安排货物的装车顺序、合理安排货物在车辆空间的装载位置,从而在给定的约束条件下(如车辆的容积、车辆的载重等限制下),研究如何把所需配送的货物合理装入车辆中,并使目标函数取得优化(如使用车辆少、车辆载重和容积的利用率高等)的方法。

配装问题在学术上属于相当复杂约束条件的组合优化问题,属于NP—难问题。国内外许多学者对此进行了研究,研究的内容主要从车辆和货物两方面考虑,大致分为四种配装情形,相同体积货物与不同体积货物的配装、单车型和多车型的配装。在有的货物配装问题中,还要考虑到客户对货物需求的优先等级或货物的不相容(某两种货物不能在统一辆车内配装)问题,这需要在原模型中增加新的约束条件。对于考虑客户需求优先级的问题,按客户需求的急迫程度给定相应货物一个优先等级,然后按优先等级装配;对于货物不相容问题,则利用二部分图的最大匹配问题思想来寻找能够混装的最大货物子集。

另外,按货物在装载空间的装载维数考虑,货物配装问题有二维货物配装问题(即因货物为密度很大的重质货物或易碎怕压货物,在车辆内只能单层装载)和三维货物配装问题(货物在车辆内可以多层装载)之分。

一般情况下,货物配装问题可以这样描述:设配送中心有m辆可选车辆(车辆编号为j,j=1,2,3,…,m)对n件货物(货物编号为i,i=1,2,3,…,n)实施装载配送,每辆车的容积限制为V ,载质量限制为G ,每件货物的体积为v ,质量为g ;x 为货物i和车辆j的关系变量,如果货物i装入货车j中,x 为1,否则x 为0;y 为货车j的状态变量,如果货车j被选中用于货物装载,y 为1,否则y 为0。

根据货物和车辆的数量,装载问题可以分为两大类。一是待装的货物相对有限,要求使用的车辆数目最少。其数学模型如下:

minZ= y (1)

s.t.x ≤1 (2)

g x ≤G y (3)

v x ≤V y (4)

二是装载车辆相对有限,要求充分利用现有车辆的容积和载质量,尽可能多载货物,使车辆的利用率最高。在这种情况下,由于所有的车辆都被选中用于货物装载,因此y 为1。决策目标为:使得所有车辆装载货物的总体积Z 和总质量Z 最大。建立该类问题的数学模型如下:

maxZ =g x (5)

maxZ =v x (6)

s.t.x ≤1 (7)

g x ≤G (8)

v x ≤V (9)

上述模型中,目标函数(1)为使使用的车辆数达到最少,目标函数(5)和(6)为使所有车辆的载重和体积利用率达到最高;(2)式和(7)式保证了每件货物只装一辆车的约束;(3)式和(4)式分别实现了配装货物的总质量和总体积不超过选择配装的车辆的质量和体积限制;(8)式为每辆车的装载重量约束,(9)式为每辆车的装载体积约束。

2货物配装问题的求解算法

由于求解货物配装问题的方法很多,而且根据优化目标的不同可选择的算法也有区别,但究其实质,可以分为精确算法和启发式算法两大类。

2.1精确算法

精确算法是指可求出其最优解的算法,主要有:分枝定界法、割平面法、动态规划法等。

(1)分支定界法。分枝定界法是以广度优先遍历或以最小耗费(最大效益)优先的方式搜索问题的解空间树。在分枝定界法中,当搜索到一个结点时,如果该结点可以继续搜索下去,则称其为活结点,并加入到活结点队列中。利用不同的分枝定界法在活结点队列中选择结点成为下一层搜索的扩展结点,通过该扩展结点搜索其产生的所有子结点,将能继续搜索的子结点加入下一层搜索的货结点队列中,重复上述结点扩展过程,这个过程一直持续到找到问题的最优解。由于其计算量关于货物数增长较快,所以这种方法只适于求解货物数不多的货物配装问题。

(2)割平面法。割平面法求解货物配装问题(A)的基本思想是,在求解相应的不含整数约束的货物配装问题(B)上,增加线性约束条件(几何术语称为割平面),以将B的可行域切割掉一部分,使其切割掉的部分只包含非整数解,没有切割掉任何整数可行解,直到切割后得到的可行域有一个整数坐标的极点恰好是A的最优解为止。由于割平面法求解时间过长,故也不适用于大规模问题。

(3)动态规划法。动态规划法常常用来求解带客户需求优先级的货物配装问题。动态规划法求解货物配装问题的基本思路是,将货物配装问题视为一个n阶段的决策问题,进而将其转化为依次求解n个具有递推关系的单阶段的决策问题,从而简化计算过程。用这种方法可求得货物配装的最优解,但仅适用于较小规模的寻优问题。

2.2启发式算法

由于精确算法的计算量一般随问题规模的增大呈指数增长,在实际中其应用范围很有限。因此,专家研究出一些更实用、易操作的启发式算法。启发式算法又分为传统启发式算法和现代启发式算法。

2.2.1传统启发式算法

传统启发式算法采用逐步构解策略,算法拟从以下几个方面来考察装配结果。①着眼于提高装载单元的载重力利用率,每次挑选重量最大的物品装入装载单元;②着眼于节省装载单元的空间容积,每次挑选所占空间最小的物品装入;③着眼于充分利用装载单元的容积利用率,每次挑选所占空间最大的物品装入;④着眼于优先运送轻浮货物,每次选取单位比容最大的物品进行配装;⑤着眼于优先运送重质货物,每次选取单位比容最小的物品进行配装。

Bhatta-charya等提出的深度优先搜索算法[1],在求解的过程中,优先考虑问题的一个维度。该方法对求解小规模货物装载问题相当有效,但是由于该算法的计算量随装入货物数目的增加呈指数式增长,不太适合大规模货物的装载。

Scheithauer等在Smith四分区算法和Bischff五分区算法基础上,将该方法扩展到大批量单一品种物品的摆放问题[2],但分区算法需对大量的可能模式进行检验,尤其是对剩余空间和载质量难以妥善处理。

Berghammer等对装载问题采用线性逐渐逼近的方法进行优化,不过该方法对逼近的收敛条件较难确定[3]。

孙焰为单车装载和多车装载分别设计了A 算法和First Fit算法。A 算法考虑每个至多有K个元素的子集S,若 g ≤G,及 v ≤V,则从余下来体积以非递增次序排列的货物列中逐个取出货物加入车箱中直至装满,该算法被证明是多项式算法具有可行性。同时装配m辆车的First Fit算法对于各车箱已装载的货物集合s ,s ,…,s ,每次为剩余容积最大或剩余载重力最大的车箱寻找一批最合适的货物装车,直至所有车箱装满为止[4]。

高红建等的实用启发式算法给出了货物合理比容的数值定义为“装载单元的实际比容”(“合理比容”是指装载单元内部的几何容积与其载重力之比),算法着眼于提高装载单元的装载能力利用率,每次选取松弛比容的偏差量最小的物品配装构成了货物合理配装的最优策略,实现了货物配装时的巧装满载[5]。

刘小群等对First Fit算法进行优化,在以容重比为基准对多品种的货物进行配装的基础上,将问题进一步深化到各种不同类型的货物[6]。根据货物相对货车轻重属性的不同,同类型的货物,将货物划分为不同的类型,采取不同的标杆,构建基于标杆的启发式算法。算法通过将货物的容重比值与装载单位的容重比值比较分类出轻质货物、重质货物和匀质货物。对于轻质货物,相比而言,货物的体积较大,因此在算法设计中,应该以货车的载质量为标杆,在保证货车容积能充分利用的前提下,尽可能地提高货车的载质量利用率。对于重质货物而言,则以货车的容积为标杆,在充分利用货车载质量的前提下,尽可能地提高货车的容积利用率。对于匀质货物,由于货物的体积和质量相对货车都比较均衡,则应以货车的体积质量比为标杆,对货车的容积和载质量利用率同时优化。

2.2.2现代启发式算法

20世纪90年代以来,由于人工智能方法在解决组合优化问题中的强大功能,不少学者开始将人工智能引入货物配装问题的求解中,并构造了基于人工智能的启发式算法(现代启发式算法),现代启发式算法包括:

(1)遗传算法。遗传算法是进行局部搜索改进的一类算法。遗传算法求解货物配装问题时,主要利用生物进化世代性与最优货物配装方案的迭代共性,在全局范围内搜索货物配装方案的最优解。如遇同一级配送结点分支对优化目标的相同利用率情况,则均予以考虑,分别参与下一步骤迭代,并由后续步骤逐渐淘汰,最终确定最优货物配装方案;如遇同一级配送结点分支的对优化目标不同利用率情况,则“适者幸存”,由耗费少的配送分支获得继续迭代的权利,但并不能确定其最优资格,必须参与后续淘汰步骤,直至迭代结束,得到最优货物配装方案。卜雷等对零担货物的装箱方式采用遗传算法进行了模拟[7],结果表明遗传算法具有良好的鲁棒性、灵活性、通用性,特别适合于大规模货物配装问题的求解。但由于算法本身还存在的一些缺陷,如易出现早熟收敛,局部搜索能力差,因此,不能保证最大概率收敛到全局最优解。并且当配装货物的配装号较多,配装关系十分复杂时,交叉和变异操作会以一个较大概率产生违背配装约束的子代染色体, 如果加入惩罚因子则在进化过程中会使不符合配装约束的染色体逐渐增多,从而出现提前成熟的现象,找不到最优解。如果改变交叉和变异规则, 调整子代染色体代表的配装方案,使之满足配装约束,则父代染色体的大多属性会丢失,子代失去父代大多数遗传信息,遗传算法变得不可靠。张丽萍等人于2002年通过引入新颖交叉算子,构造了一种改进遗传算法。此算法摆脱了对群体多样性的要求,不存在传统遗传算法常见的“早熟收敛”问题,可以有效求得货物配装问题的优化解。

(2)蚁群算法。蚁群算法是Dorigo提出的一种基于群体仿生的智能优化算法。该算法的基本原理是模拟蚁群搜索食物的行为:蚂蚁群找到食物时,它们总能找到一条从食物到巢穴之间的最优路径。这是因为蚂蚁在寻找路径时,会在路径上释放出一种特殊的信息素。当它们碰到一个还没有走过的路口时,就随机地挑选一条路径前行,并释放出与路径长度有关的信息素。路径越长,释放的激素浓度越低,当后来的蚂蚁再次碰到这个路口的时候,选择激素浓度较高路径概率就会相对较大。这样就形成了一个正反馈,最优路径上的激素浓度越来越大,而其他的路径上激素浓度却会随着时间的流逝而消减,最终整个蚁群会找出最优路径。曹宏美等结合具体问题,充分利用蚁群算法可以有效解决无法用数学表达式描述问题的优势,构造了多约束条件下多品种货物配装问题的蚂蚁算法[8]。该算法在求解货物配装问题方面有良好效果,但存在如计算时间较长、容易陷入局部最优等问题。

(3)模拟退火算法。模拟退火法是由Metropolis于1953年提出的,是一种基于热力学原理的随机搜索算法。贺国先等对货物配装问题的模拟退火算法进行了研究,提出模拟退火方法适合于解决危险货物配装问题[9]。用模拟退火法求解货物装配问题时,把物理退火中原子获得能量相当于将货物配装到装载单元中,将原子振动模拟为装载方案寻优空间的随机搜索。搜索过程由执行分配的成对交换完成,搜索初始解为转载单元的容积或载重量的利用率。对现有配装情况用任意成对交换产生新的分配,从而对配装方案不断进行改进,直至找到最优货物配装案。模拟退火算法适合大规模的考虑配装约束时的货物配装问题。从理论上讲,用这种方法求解货物配装问题,可以求得全局最优解,但在实际应用中,由于受计算时间的限制,往往只能给出一个近似的最优解。为了使模拟退火算法求出的近似解更准确,一般重复执行模拟退火法多次,从中选取最好的解作为最终的近似最优解。

另外,在做配装方案时,若待配装货物的种类比较多,且配装号也较多时,配装关系十分复杂,此时可以先将货物依据配装号分类,之后将具有同一配装号的货物视为一批(或一件)货物,按照配装号的顺序进行解的编码,这样编码长度最多为所有货物包含的配装号的数量,节省计算机存储空间,大大降低计算复杂度,提高计算效率;但是在进行单车配载时该编码方法产生的最优解不利于充分利用货车载重量。在确定请求车时,需要多次使用该算法,直到确定的配装方案中的货物总重量和总体积小于装载单位的标记载重为止。

3结束语

货物配装问题是NP—难问题,如果用精确算法来求解,只能解决规模较小的问题,而且求解过程需要的运行时间较长。因此,目前启发式算法,特别是智能化启发式算法,仍是求解货物配装问题的主要方法。需要说明的是,启发式算法虽然能够比较快地解决有关问题,但算法的各项初始参数的适当选取均会影响算法的收敛性、收敛速度和计算时间,因此启发式算法的优劣往往取决于算法设计者的实际经验以及处理的样本空间的大小。在求解过程中,应根据各类算法的适用范围,并针对配装优化问题的具体情况,寻找最适合的求解方法,搜索最优配装方案。对于货物号比较多的配装优化问题、多约束的复杂货物配装问题或者是多优化目标的货物配装优化问题,可以考虑利用多种算法相结合的办法来解决。

参考文献:

[1]Bhattacharya S, Roy R. An exact depth-first algorithm for the pallet loading problem[J]. European Journal of Opera-tional Research, 1998,110(3):610-625.

[2]Scheithauer G, Sommerweib U. 4-block heuristic for the rec-tangle packing problem[J]. European Journal of OperationalResearch, 1998,108(3):509-526.

[3]Berghammer R, Reuter F. A linear approximation algorithmfor bin packing with absolute approximation factor[J]. Sci-ence of Computer Programming, 2003,48(1):67-80.

[4] 孙焰,李致中. 求双目标配装方案的多项式近似算法[J]. 长沙铁道学院学报,1997,15(2):33-39.

[5] 高红建,等. 货物合理配装的实用启发式算法[J]. 交通科学与经济,2004(1):59-61.

[6] 刘小群,马士华. 基于标杆的多车多品种货物装载优化算法[J]. 交通运输工程学报,2007,7(1):99-105.

[7] 卜雷,等. 遗传算法确定零担货物的选择装箱方式[J]. 交通运输工程学报,2002,2(3):93-96.

[8] 曹宏美,等. 优化多品种货物配装的蚂蚁算法[J]. 交通与计算机,2008,26(2):11-15.

[9] 贺国先,刘凯. 模拟退火算法在铁路货运站危险货物配装中的应用[J]. 铁道学报,2003,25(1):9-14.

[10] 王玲玲,等. 单车多品种货物配装问题模型与算法研究[J]. 物流科技,2007(8):118-122.

[11] 孙黎宏,许恒勤. 多包装形式下货物配装问题的研究[J]. 森林工程,2006,22(5):69-70.

[12] 王玲玲,等. 多车多品种货物配装问题模型与算法研究[J]. 物流科技,2007,26(7):58-60.

[13] 曹明兰,等. 考虑客户需求优先级的货物配装问题的模型与算法研究[J]. 物流科技,2007,29(10):69-72.

[14] 史亚贝,等. 零担货物配装问题的算法和系统设计[J]. 工艺与装备,2008(3):86-90.

[15] 吴颖,程赐胜. 基于分枝定界法的车辆配载问题[J]. 长沙理工大学学报,2008,5(4):23-27.

注:本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文