2023年第三届长三角高校数学建模竞赛】A 题 快递包裹装箱优化问题 详细数学建模过程

简介: 本文详细介绍了2023年第三届长三角高校数学建模竞赛A题的详细数学建模过程,探讨了快递包裹装箱优化问题,提出了三维装箱算法、目标规划和优化策略,旨在减少耗材使用量和优化耗材总体积,同时考虑了货物和耗材的柔性属性。

在这里插入图片描述

相关链接

【2023年第三届长三角高校数学建模竞赛】A 题 快递包裹装箱优化问题 20页完整论文及代码

1 题目

2022 年,中国一年的包裹已经超过 1000 亿件,占据了全球快递事务量的一半以上。近几年,中国每年新增包裹数量相当于美国整个国家一年的包裹数量, 十年前中国还是物流成本最昂贵的国家,当前中国已经建立起全世界最强大、最先进的快递物流体系。在包裹的打包环节,选取合适的包装耗材非常重要。由于包裹的基数大,因此每个包裹耗材成本的略微降低,也能带来极大的经济效益。图 1 是一些纸箱实物样式,图 2 是某种三维装箱示意图。

在这里插入图片描述

图1 纸箱样式图2 三维装箱示意图

附件 1 的装箱数据中给出了订单数据和耗材数据。根据以上背景,请你们的团队完成以下问题:

问题1: 针对附件1装箱数据中给出的订单数据和耗材数据,对每个订单,分别用箱子或袋子去装,请设计出合适的装载方案,要求使用耗材数量越少越好, 在耗材数量相同时,耗材总体积越小越好。给出每种耗材的使用总数和耗材总体积。

问题2: 针对附件1的数据,现在需要优化耗材的尺寸,请给出耗材尺寸的优化方案。要求优化后耗材的种数不变,只是改变耗材尺寸;对问题1中成功装载的物品,优化后的方案使用的箱子或袋子数尽量减少;总体积不能超过原方案的总体积;在耗材数量相同时,耗材总体积越小越好。给出优化后的每种耗材的具体尺寸、使用总数和耗材总体积。

问题 3: 以上两个问题假设货物与耗材都为刚性的,若货物与耗材存在柔性或者可轻微挤压的属性时,请重新完成问题 1、2。根据实际情况,这里考虑耗材伸展时,长、宽、高都不超过原尺寸的 5%。

提示:

1、需要分别给出箱装(全使用箱子作为耗材)、袋装(全使用袋子作为耗材) 以及两种耗材同时使用的方案。
2、物品长宽高可以任意互换,如case1中第一种物品可看成长170、宽110、高27,也可看成长110、宽170、高27。
3、用袋子装物品时,能够装下的判定标准为同时满足如下两个条件: 袋子长+袋子高≥物品长+物品高;袋子宽+袋子高≥物品宽+物品高。
4、在附件1装箱数据中,case序号相同的看作同一订单,同一订单的物品可以装在同一箱(袋)子里,不同订单的物品一定装在不同箱(袋)子里。
5、对附件1装箱数据中的某订单物品,若耗材无论如何不能装下,则不需要考虑该物品。
6、耗材的重量暂不考虑。
7、表1是订单表示例,表2是耗材信息表,更详细的数据见附件1。

表1 部分订单表(示例)

case L(长) W(宽) H(高) num
1 170 110 27 7
1 210 200 30 1
2 105 105 100 2
2 135 110 110 5
3 208 140 18 5
3 90 90 75 1
4 115 65 35 1
5 250 190 53 3
6 140 140 48 2
6 225 80 35 2
7 292 166 87 1
7 320 240 70 1
8 228 148 26 2

表 2 耗材信息表

耗材名称 耗材类型 重量
普通1号袋 250 190 1 10
普通2号袋 300 250 1 8
普通3号袋 400 330 1 15
普通4号袋 450 420 1 23
普通1号自营纸箱 165 120 55 45
普通2号自营纸箱 200 140 70 67
普通3号自营纸箱 200 150 150 103
普通4号自营纸箱 270 200 90 132
普通5号自营纸箱 300 200 170 179

2 思路

2.1 问题一

这个一个目标规划中的三维装箱算法问题。根据附件1.csv文件中的订单数据,可以得到以下信息:

  • 每个订单有多个产品,每个产品的长、宽、高和数量都不同。
  • 每个订单都需要使用一定数量的耗材。
  • 每个耗材包括多种不同的规格和重量。

为了更高效地计算每个订单所需的装箱量,可以使用三维建模软件来模拟不同尺寸和形状的箱子和袋子的使用情况,大概的建模过程如下:

  1. 首先需要将所有的产品按照其长、宽、高进行归一化,使得所有产品的尺寸单位都相同。例如,可以将所有产品的长、宽、高除以一个标准长度(比如170mm),得到归一化后的尺寸。
  2. 然后需要确定每个产品最适合使用的尺寸和形状的箱子或袋子,以及需要使用的数量。这个过程可以根据实际情况进行优化算法,可以考虑以下因素:
  • 箱子或袋子的尺寸是否能够容纳产品?
  • 箱子或袋子的形状是否能够适应产品的形状?
  • 使用单个箱子或袋子时是否能够满足耗材数量要求?
  • 如果使用多个箱子或袋子,则它们的尺寸和形状是否能够最大化地利用空间?
  • 如果使用多个箱子或袋子,则它们之间是否存在重叠部分,导致浪费空间?
  1. 对于每个订单,需要计算出它需要使用的箱子或袋子的总数量和总体积。具体的计算方法取决于选择的优化策略。一般来说,可以考虑以下两种策略:
    • 贪心算法:每次选择能够使耗材数量最少的产品组合,并尝试使用最合适的箱子或袋子来装载它们。如果当前的组合无法满足耗材数量要求,则继续选择其他产品组合,直到找到合适的组合或者已经没有更多的可选项为止。这种策略的优点是速度较快,但可能会出现无法满足耗材数量要求的组合。
    • 动态规划算法:预先计算出所有可能的组合的耗材数量和体积,然后根据实际需求逐步选择合适的组合和箱子或袋子。这种策略的优点是能够确保满足所有的耗材数量要求,但计算量较大。

2.2 问题二

我将附件1拆分为两个csv文件,方面后续的讲解,订单数据.csv和全部耗材数据.csv数据,可以采用以下优化方案来改变耗材尺寸,同时尽量减少使用箱子或袋子的数量,并且总体积不能超过原方案的总体积。对于这个题的建模过程如下。

  1. 确定优化方案的目标和约束条件:减少使用箱子或袋子数、总体积不能超过原方案的总体积、耗材总体积越小越好。
  2. 建立数学模型:定义一个函数$f(d_2)$,表示将所有产品放入尺寸为$d_2$的箱子或袋子中所需的最小空间。
  3. 设计算法:根据上述数学模型,设计算法来计算最优的$d_2$​尺寸。具体来说,可以采用贪心算法或者动态规划算法等方法进行计算。
  4. 实现算法:将设计的算法实现到程序中,并调用该程序来计算最优的$d_2$​尺寸。
  5. 分析算法性能:对算法进行性能分析,包括时间复杂度、空间复杂度等方面的评估,以确定算法是否满足要求。
  6. 不断优化算法:如果算法性能不够理想,可以对算法进行优化,以提高其效率和准确性。

2.3 问题三

(1)问题一改进

在贪心算法或者动态规划算法的基础上,考虑耗材的柔性属性,将每个产品的尺寸进行归一化后,计算出产品在不同尺寸下能够放入箱子或袋子中的最小体积。如果产品的形状存在柔性或可轻微挤压的属性,那么产品放入尺寸为k的箱子或袋子中时,长、宽、高都不超过 0.5×k的限制。

(2)问题二改进

在原有模型的基础上,考虑货物与耗材的柔性属性,即当货物或耗材具有柔性或可轻微挤压的属性时,在计算占用空间时应将长、宽、高都限制在原尺寸的5%以内。对于每个产品,将其长、宽、高分别除以$d_2$​,得到三个比例系数r1​,r2​,r3​,然后将它们相乘即可得到占用的空间。

3 建模方案

3.1 问题一

以下是针对每个订单使用贪心算法的三维装箱算法,以减少耗材数量和优化耗材总体积为目标:

  1. 首先,需要将所有产品按照尺寸进行归一化,使得所有产品的尺寸单位都相同。例如,对于长、宽、高分别为170mm、110mm、27mm的产品,可以将其归一化为170mm×110mm×27mm的尺寸。

  2. 然后,需要计算出每个订单需要使用的箱子或袋子的总数量和总体积。具体的计算方法取决于选择的优化策略。

  3. 对于每个订单,可以使用三维贪心算法来进行装箱。具体步骤如下:

。。。略,请下载完整文档
下面是具体的数学公式说明:

设dp[i][j][k] 表示在前 i个产品中选择尺寸为 j的产品放入尺寸为k 的箱子或袋子的最优解,其中dp[i][j][k] 的定义如下:

。。。略,请下载完整文档

3.2 问题二

针对装箱数据中给出的订单部分数据附件1.csv和全部耗材数据附件2.csv数据,可以使用数学模型来优化耗材尺寸,以达到减少使用箱子或袋子数、总体积不能超过原方案的总体积、耗材总体积越小越好的目标。
假设原方案中每种耗材的尺寸为d1​,数量为n1​,总体积为V1​;优化后方案中每种耗材的尺寸为$d_2$​,数量仍为n2​,总体积为V2​。需要求解以下问题:

。。。略,请下载完整文档
在满足上述条件之一之后,就可以确定最优的

3.3 问题三

(1)改进问题一思路

在贪心算法的基础上,考虑耗材的柔性属性,将每个产品的尺寸进行归一化后,计算出产品在不同尺寸下能够放入箱子或袋子中的最小体积。如果产品的形状存在柔性或可轻微挤压的属性,那么产品放入尺寸为k的箱子或袋子中时,长、宽、高都不超过 0.5×k的限制。

具体数学模型如下:

。。。略,请下载完整文档

(2)问题二改进思路

  1. 在原有模型的基础上,考虑货物与耗材的柔性属性,即当货物或耗材具有柔性或可轻微挤压的属性时,在计算占用空间时应将长、宽、高都限制在原尺寸的5%以内。

  2. 对于每个产品,将其长、宽、高分别除以$d_2$​,得到三个比例系数r1​,r2​,r3​,然后将它们相乘即可得到占用的空间。具体数学模型如下:
    。。。略,请下载完整文档

4 完整文档获取方式

看我知乎文章的最底部。

zhuanlan.zhihu.com/p/628512849

目录
相关文章
|
机器学习/深度学习 算法 决策智能
智能解决装箱问题:使用优化算法实现高效包装
装箱问题(Bin Packing Problem)是组合优化领域中的一个经典问题,主要涉及如何将一系列对象高效地装入有限数量的容器(或“箱”)中,同时满足特定的约束条件。这个问题的目标是最小化所需使用的箱子数量或者最大化箱子的装载效率,以减少空间或资源的浪费。
|
6月前
|
机器学习/深度学习 存储 算法
【LeetCode 热题100】347:前 K 个高频元素(详细解析)(Go语言版)
这篇文章详细解析了力扣热题 347——前 K 个高频元素的三种解法:哈希表+小顶堆、哈希表+快速排序和哈希表+桶排序。每种方法都附有清晰的思路讲解和 Go 语言代码实现。小顶堆方法时间复杂度为 O(n log k),适合处理大规模数据;快速排序方法时间复杂度为 O(n log n),适用于数据量较小的场景;桶排序方法在特定条件下能达到线性时间复杂度 O(n)。文章通过对比分析,帮助读者根据实际需求选择最优解法,并提供了完整的代码示例,是一篇非常实用的算法学习资料。
400 90
|
存储 监控 安全
服务器维护是确保服务器稳定运行、数据安全和性能优化的重要过程
【10月更文挑战第4天】服务器维护是确保服务器稳定运行、数据安全和性能优化的重要过程
315 65
|
人工智能 算法 物联网
求解三维装箱问题的启发式深度优先搜索算法(python)
求解三维装箱问题的启发式深度优先搜索算法(python)
365 0
|
算法 Python 容器
基于最低水平面的三维装箱问题的启发式算法
基于最低水平面的三维装箱问题的启发式算法
265 0
|
数据采集 存储 移动开发
【2023五一杯数学建模】 B题 快递需求分析问题 建模方案及MATLAB实现代码
本文介绍了2023年五一杯数学建模竞赛B题的解题方法,详细阐述了如何通过数学建模和MATLAB编程来分析快递需求、预测运输数量、优化运输成本,并估计固定和非固定需求,提供了完整的建模方案和代码实现。
538 0
【2023五一杯数学建模】 B题 快递需求分析问题 建模方案及MATLAB实现代码
|
数据采集 传感器 XML
LabVIEW和MES系统的智能化车间数据对接
LabVIEW和MES系统的智能化车间数据对接
272 4
|
算法 计算机视觉
数字图像处理OpenCV——实验三 图像分割实验
实验三 图像分割实验 实验项目名称:图像分割实验 (1) 进一步理解图像的阈值分割方法和边缘检测方法的原理。 (2) 掌握图像基本全局阈值方法和最大类间方差法(otsu法)的原理并编程实现。 (3) 编程实现图像的边缘检测。 编程实现图像阈值分割(基本全局阈值方法和otsu法)和边缘检测。 图像的二值化处理图像分割中的一个主要内容,就是将图像上的点的灰度置为0或255,也就是讲整个图像呈现出明显的黑白效果。用I表示原图,R表示二值化后的图,则二值化的过程可以用以下公式表示: thr表示选取的阈值。二值化的过
583 0
数字图像处理OpenCV——实验三 图像分割实验
|
机器学习/深度学习 传感器 算法
【优化装箱】基于遗传算法求解集装箱船配载优化问题附matlab代码
【优化装箱】基于遗传算法求解集装箱船配载优化问题附matlab代码
|
云安全 运维 监控
网络安全之了解安全托管服务(MSS)
什么是安全托管服务,一般的安全托管服务都覆盖有哪些内容,什么样的企业适合安全托管服务,企业如何通过安全托管服务来构建自身的安全体系,带着这些问题我们一起来了解安全托管服务(MSS)
821 2