题 目 启发式与贪心思想融合的装箱问题求解
摘 要：
随着中国快递市场的迅猛发展，2022 年中国快递包裹数量已超过 1000 亿件，占据
全球快递事务量一半以上。然而，在庞大且复杂的快递物流体系中，包裹打包环节至关
重要。选取合适的包装耗材，特别是纸箱，对整个物流效率和成本控制具有重大意义。
因此，本文旨在建立一个有效的数学模型，解决快递包裹装箱优化问题，提高装箱效率
和经济效益。
本文简单分析了一种袋装类型耗材的简化近似，将复杂的形变问题转为简单的长方
体，同时还保留了一定的近似度。对于问题一及其后续处理的基础，本文提出了一种基
于贪心思想的先打分-后放置算法，并设计了一种简化物品放置的方法——凹角法，使
之能够清晰简洁地处理物品的放置问题，将复杂多变的放置位选择问题简化为仅需对三
个凹角的选择。先打分-后放置算法依赖于打分的权重系数，经验调整使人力不从心，
于是结合启发式算法——差分进化来调整权重系数，取得了一定进步。对于第二问，我
们对 9 种耗材的尺寸属性建模，先后用了粒子群优化和差分进化方法，求解出了一组尺
寸属性。对于第三问，我们假设在装载时，物品与耗材总是处在最大形变状态，然后进
行求解。
本文也存在许多有待进一步研究的不足，比如袋装类型耗材的简化近似模型在使用
时并不能发挥出很好的效果，需要进一步理解柔性材料的放置操作，又比如打分的 7 个
权重设置可能还可以再添加一些新的权重类型，提高放置的收益度。
关键词：贪心算法；装箱优化；差分进化；粒子群优化；多面体膨胀问题
2023 年第三届长三角高校数学建模竞赛
参赛编号:YRDMCM202300475
选题: _A_ (A 或 B 或 C) 参赛赛道: _研究生_（本科生、专科生或研究生）
目录
目录
一、 问题重述 ................................................................................................................................................1
1.1 问题的背景 ......................................................................................................................................1
1.2 问题的提出 ......................................................................................................................................1
二、 基本假设及符号说明 ............................................................................................................................2
2.1 基本假设 ...........................................................................................................................................2
2.2 符号说明 ...........................................................................................................................................2
三、 总体技术路线图 ....................................................................................................................................2
四、 数据预处理 ............................................................................................................................................3
4.1 格式简化与数据剔除 .......................................................................................................................3
4.2 可视化直观分析与数据排序 ..........................................................................................................4
五、 问题一的求解 ........................................................................................................................................5
5.1 进一步假设与符号说明 ...................................................................................................................5
5.2 模型建立 ...........................................................................................................................................6
5.3 模型求解 ...........................................................................................................................................6
六、 问题二的求解 ........................................................................................................................................9
6.1 模型建立 ...........................................................................................................................................9
6.2 求解思路 ...........................................................................................................................................9
6.3 粒子群优化 .......................................................................................................................................9
6.4 求解结果 .........................................................................................................................................10
七、 问题三的求解 ......................................................................................................................................10
7.1 问题分析 .........................................................................................................................................10
7.2 求解思路 .........................................................................................................................................10
八、 模型评价与展望 ..................................................................................................................................12
1
一、问题重述
1.1 问题的背景
2022 年，中国一年的快递包裹数量已经超过了 1000 亿件，占据了全球快递事务量
的一半以上。令人惊讶的是，近几年来，中国每年新增的包裹数量已经相当于美国整个
国家一年的包裹数量。而仅仅十年前，中国还是全球物流成本最高的国家。
在这个庞大且复杂的快递物流体系中，包裹打包环节是非常重要的一环。选取合适
的包装耗材，尤其是合适的纸箱，对于整个物流效率和成本控制具有重要意义。考虑到
中国的包裹基数之大，即使每个包裹的耗材成本只能略微降低，也可能带来极大的经济
效益。
然而，如何有效地选取和使用纸箱，以实现包裹装箱的优化，如何根据包裹的大小
和形状，以及可能的堆叠方式，选择最合适的纸箱，是一个值得深入研究的问题。这个
问题也涉及到三维空间的装箱问题，需要考虑如何将各个包裹最优地放入一个给定的空
间，以实现空间的最大化利用。
因此，对于中国这样一个全球最大的快递市场来说，研究和解决快递包裹装箱优化
问题具有极其重要的实际意义和经济价值。本文的目标就是建立一个有效的数学模型，
来解决这个实际问题，并尽可能提高包裹装箱的效率和经济效益。
1.2 问题的提出
问题一:订单装箱优化
对于附件 1 中给出的订单数据和耗材数据，我们需要设计出一个有效的装载方案，
使得每个订单都可以被适当地装入箱子或袋子中。设计方案的目标是使得使用的耗材数
量最少，如果耗材数量相同，那么应优先选择总体积更小的耗材。我们需要提供每种耗
材的使用总数以及总体积。
问题二:耗材尺寸优化
在问题一的基础上，我们现在需要针对附件 1 的数据，对耗材的尺寸进行优化。优
化的目标是在保持耗材种类数量不变的情况下，通过改变耗材的尺寸，尽可能减少问题
一中成功装载的物品所使用的箱子或袋子的数量。注意，优化后的耗材总体积不能超过
原方案的总体积。如果耗材数量相同，那么应优先选择总体积更小的耗材。我们需要提
供优化后的每种耗材的具体尺寸、使用总数以及总体积。
问题三:考虑柔性的装箱与尺寸优化
在问题一和问题二的基础上，我们需要考虑货物和耗材的物理性质。假设货物和耗
材不再是完全刚性的，而是存在一定的柔性或者可以被轻微挤压。在这种情况下，我们
需要重新完成问题一和问题二。在考虑耗材伸展时，我们假设长、宽、高的变化幅度都
不会超过原尺寸的 5%。
提示点:
装载方案：我们需要为每个订单考虑三种装载方案——箱装（只使用箱子作为耗
材）、袋装（只使用袋子作为耗材）以及混合装（同时使用箱子和袋子作为耗材）。
物品尺寸：物品的长、宽、高可以任意互换。
袋子装载标准：当使用袋子装载物品时，袋子需要满足以下两个条件才能装下物品：
袋子的长度+高度≥物品的长度+高度；袋子的宽度+高度≥物品的宽度+高度。
订单分类：具有相同序号的 case 视为同一订单。同一订单的物品可以装在同一箱
（袋）子里，而不同订单的物品必须装在不同的箱（袋）子里。
物品装载：如果耗材无法装下，则可以不考虑该物品。
2
3
二、基本假设及符号说明
2.1 基本假设
统一单位假设：附件中所有长度单位均为㎝。
严格旋转假设：在装箱过程中，如果物品需要旋转，则必须保证物品旋转后其六面
依旧平行于容器的六面。
无厚度假设：任何耗材本身都视为无厚度，即其体积等于其容积。
无重叠假设：任何两个物品或物品耗材之间都不能有重叠，即物品必须完全被耗材
包含，不能超出容器的边界。
无间隙假设：物品与耗材之间，以及物品与物品之间在装载时没有任何间隙，即物
品的边长完全可加，即如果两个物品在某一维度（如高度、长度或宽度）紧密堆叠，那
么这两个物品的总边长等于各自边长的和，没有任何误差。
无运动假设：物品在装箱完成后就保持固定，不再改变自身位置。
无分割假设：物品不能被分割，每个物品必须作为一个整体装载。
2.2 符号说明
符号
意义
𝐵
,
𝐵
𝑚
,
𝐵
𝑘
,
𝑖
𝑚
,
容器,耗材
𝐼,
𝐼
𝑠
,
𝐼
𝑖,𝑗
𝑠,𝑘
物品,商品,产品
𝑋
[
𝑎
],
𝑋
[
𝑏
],
𝑋
[
𝑐
]
,𝑋
[
𝑣],𝑋
=
𝐼,
𝐵
耗材或物品的最长边,次长边,最短边,体积
𝑂
𝑘
,
𝛺
订单与订单集合
𝛹
容器集合
𝛷
𝑢
=
{
𝜑
𝑘
}
放置方案的集合与放置方案
𝐵
𝑚
=
(
𝑏
𝑚,𝑙
,
𝑏
𝑚,ℎ
,
𝑏
𝑚,𝑤
)
耗材的尺寸规格
三、总体技术路线图
数据预处理
问题一:订单装箱优化
问题二:耗材尺寸优化
机理分析
装箱函数设计与优化
算法优选
粒子群优化
贪心算法
差分进化
问题三:加入柔性考虑
差分进化
简化假设
