二维货物配装的整数规划模型与算法

The Integer Programming Model and Algorithm for the Two-Dimensional Loading of Goods

摘要: 本文研究了物流二维货物配装问题。基于客户优先级等因素，建立了一个二维货物配装的整数线性规划模型，并设计了相应算法，给出了货物配装的优化策略。数值算例验证了算法的有效性。

Abstract: In this paper, we study on the logistics two-dimensional loading of goods. Based on customer priority and other factors, we establish an integer programming model for two-dimensional loading of goods, and the corresponding algorithm is designed. Furthermore, the optimization strategy of goods loading is also given. Numerical examples demonstrate the effectiveness of the proposed algorithm.

1. 引言

货物配装问题关系到车辆空间、载重的利用率，影响企业物流成本和效益，合理配装是现代物流的一个关键性技术，是企业追求的目标之一。近年来，货物配装优化问题，无论是在实际应用还是在学术研究，已成为现代物流研究的一个热点，引起了国内外众多学者浓厚的研究兴趣( [1] [2] [3] )。随着国际物流产业的发展，货物的规模、种类和数量出现了大幅度增加，货物配装的目标更多、限制条件更多成为发展的必然趋势，这就导致货物配装问题模型的目标函数和约束条件变得更加复杂。对此，国内学者也做了大量的研究，基本的思路是基于遗传算法和背包问题进行模型建立和算法改进。史亚贝等( [4] )利用动态规划方法，基于对车厢的容积和载重量利用率的考虑，给出了求解该问题的算法，但由于考虑的约束条件过少，在实际的车厢配装过程中，对数量多、种类杂的货物配装效果不明显。明立立( [5] )在装载空间、载重量、容积、容重比的四大约束条件下，又增加了层级约束，建立了无层级约束和有层级约束的单车三维货物配装问题，应用遗传算法进行了求解。符丽锦( [6] )基于改进的量子遗传算法QGA的理论，给出新的动态调整量子旋转角方案，在货物配装的全局搜索货物、寻优货物等选择货物的环节里，加快了收敛速度，缩短了迭代次数。同时，再加上采用整车合并思想，该方法能够有效地减少配装车辆的数量，减少货物配装环节的成本。张卉( [7] )阐述了单车二维货物配装问题、单车三维货物配装问题和多车三维货物配装问题，并建立了相应的遗传算法。本文，基于客户优先级等因素，建立了一个单车二维货物配装的整数线性规划模型，并设计了相应算法，给出了货物配装的优化策略。数值算例验证了算法的有效性。

2. 模型建立与算法设计

2.1. 单车二维配装模型建立

按照客户优先级和最优路径，不仿假设配送中心个客户的货物为需要配送，用表示货物集合，每个客户有种货物(客户的货物少于时，那么用0补齐)，表示第个客户的种不同货物，表示第个客户的不同货物的集合；表示装第个客户的第种货物，表示不装第个客户的第种货物；分别表示第个客户的第种货物的质量、体积、容重比(货物的体积和质量的比)。有一订单(已知客户需求的货物、运达时间、配送路径)，现用一辆货车配送这些货物。这里，基于客户优先级和最优路径两个因素探讨货物的配装优先级及确定方法，制定一套合理的配装方案，使货车的车厢利用率更加合理。

基于以上问题，建立如下的整数线性规划模型：

(1)

其中表示货车车厢规定的载重量，表示货车车厢规定的额定容积；(1)式中的第一式和第二式分别表示装载货物的总质量、总体积不能超过货车车厢的载重量、容积；(1)式中的第三式和第四式分别表示第个客户的装载货物的总质量、总体积不超过车厢的剩余载重量、剩余容积。其中，为装第个客户货物之前已装载货物的总质量，为装第个客户货物之前已装载货物的总体积。

2.2. 算法设计

基于以上建立的模型，给出下面的求解算法。

Step 1. 计算货车车厢的容积与载重量之比，记为货车的容重比。根据不同客户的货物配送的时间需求，按递增顺序排列，作成。

Step 2. 规定的值，如果规定，若，则，其中。即是说配装这些货物，把这些放在一起，作成集合。此时如果有，，则记，表示剩余货物的集合。

Step 3. 计算出剩余货物集合中每一个货物的容重比，表示第个客户的第种货物的容重比。并对这些剩余货物的容重比同样按递增顺序排列，作成集合。

Step 4. 计算出已配装货物的总容重比，计算和，并求出。

如果，则从剩余货物中找出一个货物，满足条件：

；‚；ƒ

如果，则从剩余货物中找出一个货物，满足条件：

；‚；ƒ

Step 5. 若上面的不存在，则去掉条件，寻找满足‚、ƒ的放入集合中，即是说该满足。然后继续进入Step 4，重复Step 4~Step 5，直到或或条件不再满足。如果仍然寻不到这样的，则该货车的配装环节完毕，进入Step 6。

Step 6. 输出已经进行配装的货物集合，结束。

3. 举例说明

某配送中心负责给周边市场的商贩配送货物，现有一批货物需要给3家客户配送，9种货物已经采用集装箱包装，已知客户的需求时间排列顺序见表1。目前该配送中心有一辆载重量13 t，容积18 m³的货车，请制定合理的配送方案，在完成客户满意度的前提下，使得单车配送的利用率最大。

根据以上所提算法求解如下。

Step 1. 首先求出货车车厢的容重比；

Step 2. 规定。此时A和B客户的货物必须进行配装，则有

，

令集合为已装货物集合，集合为剩余货物的集合；

Step 3. 求出每个剩余货物的容重比：，所以；

Step 4. 求出已装货物的总容重比，可以得到，所以从剩余货物中找出一个货物，满足条件：；‚；ƒ可以得到满足条件；

Table 1. Demand time order, quality and volume of goods for customer

表1. 客户需求时间排列顺序、货物质量和体积

表中的A, B, C表示客户；M_i (i = 1, 2, 3)表示客户A, B, C的需求时间；g₁₁, g₁₂, g₁₃表示客户A的货物；g₂₁, g₂₂表示客户B的货物；g₃₁, g₃₂, g₃₃, g₃₄表示客户C的货物

Step 5. 重复上一个步骤，由上述算法可以计算出参与配装的货物有，，，，，，。

基金项目

中国物流学会与中国物流与采购联合会计划项目(2015CSLKT3-199)；山东省科技计划项目(2013GGA 13034)；全国高校物流教研课题(JZW2014048, JZW2014049)和国家级大学生创新创业训练计划项目(2016)。