没有合适的资源?快使用搜索试试~ 我知道了~
首页《2017阿里技术年度精选》下册:算法与科技创新的结晶
《2017阿里技术年度精选》下册:算法与科技创新的结晶
需积分: 10 2 下载量 139 浏览量
更新于2024-07-19
收藏 16.27MB PDF 举报
"2017阿里技术年度精选(下)" 《2017阿里技术年度精选(下)》是阿里巴巴技术团队从众多技术文章中精心筛选出的精华集,旨在展示阿里在2017年的重要技术成果和深度洞察。这本书的下册汇聚了65篇精选文章,共计678页,涵盖了广泛的IT技术领域,如算法、机器学习、大数据、数据库、中间件、运维、安全以及移动开发等。 文章内容不仅限于技术细节,还包含了技术实践、解决方案以及对技术趋势的洞察。这些文章由阿里集团内超过25000名工程师贡献,他们包括新入职的技术新人、资深工程师以及技术管理者。他们将自己的工作经验、技术洞见和人生感悟以最朴实无华的方式分享出来,期望能帮助读者避免常见的技术陷阱,提升工作效率。 书中还特别收录了对十多位阿里技术领军人物的深度访谈,如从工程师成长为企业合伙人的多隆,通过6年时间影响数亿用户的靖世,以及入选MIT2017年度TR35的王刚和吴翰清,还有免试晋升为研究员的钱磊等。这些访谈揭示了他们的技术生涯,展示了技术人才如何在阿里实现个人价值并推动技术创新。 《2017阿里技术年度精选》并非针对某一特定技术领域的深入教材,而更像是一个技术散文集,主题多样,读者无论是在校学生、科研机构的研究人员还是IT从业者,都能从中找到启发和学习的价值。每篇文章都凝聚了背后团队数月甚至数年的探索与努力,是他们实践、失败、再实践的结晶,旨在激发读者的思考,促进技术的传承与进步。
资源详情
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/10164974/bg10.jpg)
8 > 2017 阿里技术年度精选(下)
论文地址:https://arxiv.org/abs/1708.05930
1. 引言
装箱问题是一类非常经典且重要的优化问题,常被应用于物流系统和生产系统
中。装箱问题有很多变型问题,其中最重要且最难求解的是三维装箱问题,在此问题
中, 需要将若干个不同大小的长方体物品放入箱子中,物品之间不能重叠且不能倾斜,
箱子的尺寸和成本已知,优化目标为最小化箱子的使用数量,即最小化总成本。装箱
问题一直是学术界非常流行的研究方向之一。除此之外,装箱问题在实际中也有很多
应用。有效的装箱算法往往意味着计算时间、装箱成本的大量节省和资源使用效率的
大幅提升。
在某些实际业务场景中,我们发现装箱时并不是使用固定尺寸的箱子(例如在跨
境电商业务中,大部分是使用柔性的塑料材料,而不是箱子来包装货物),而且由于装
箱的成本大部分都由装箱材料成本构成,而装箱材料成本又主要取决于材料的表面积。
所以在本研究中,我们提出了一类新型的装箱问题。与传统三维装箱问题不同的是,本
问题的优化目标为确定一个能够容纳所有物品的箱子,并最小化此箱子的表面积。
由于寻找装箱问题的最优解非常难,所以相关研究者们提出了不同的近似算法和
启发式算法来求解此类问题。但是启发式算法往往有着较强的问题依赖性,一类启发
式算法可能只适用于求解某种或某些业务场景中的装箱问题。近些年来,人工智能技
术,尤其是深度强化学习 (Deep reinforcement learning, DRL) 技术有着非常快速
的发展,并且在某些问题上取得了令人瞩目的成果。而且深度强化学习技术已经被发
现在求解组合优化问题方面具有较大的潜力,所以本研究使用了一种基于深度强化学
习的方法来求解新型三维装箱问题。本文基于大量实际业务数据训练了深度强化学习
模型,并验证了模型的效果。
2. 相关研究介绍
2.1 三维装箱问题相关研究
装箱问题是一类非常经典和流行的优化问题。自从其在 20 世纪 70 年代被提出
![](https://csdnimg.cn/release/download_crawler_static/10164974/bg11.jpg)
AI/ 算法 < 9
以来,大量研究者对此类问题进行了研究并获得了许多有价值的成果。[Coffman
et
al
., 1980] 证明了二维装箱问题是 NP-hard 问题,所以作为二维装箱问题的一般化
问题,三维装箱问题也是 NP-hard 问题。由于此原因,很多之前的研究都集中于近
似算法和启发式算法。[Scheithauer, 1991] 首先提出了针对三维装箱问题的近似算
法并分析了其近似比。
此外,研究者们还提出了很多不同类型的启发式算法,例如禁忌搜索 ([Lodi
et
al
.,2002], [Crainic
et al
., 2009]), 引导式局部搜索 ([Faroe
et al
., 2003]), 基于极点
的启发式算法 ([Crainic
et al
., 2008]),混合遗传算法 ([Kang
et al
.,2012]) 等。在精
确解算法方面,[Chen
et al
., 1995] 考虑了一种有多种尺寸箱子的三维装箱问题,并
建立一个混合整数规划模型来求解最优解。[Martello
et al
.,2000] 提出了一种分支定
界算法来求解三维装箱问题,并通过数值实验表明 90 个物品以内的问题都可以在合
理的时间内获得最优解。
另外,还有一些从实际业务中提出的装箱问题的变型问题,例如 [Kang and
Park, 2003] 提 出 了 一 种 可 变 尺 寸 的 装 箱 问 题,[Khanafer
et al
.,2010], [Gen-
dreau
et al
., 2004] 研究了一种考虑物品冲突的装箱问题,[Clautiaux
et al
.,2014]
对一种考虑易碎物品的装箱问题进行了研究。
另一类装箱问题—条带装箱问题 (Strippacking problem) 与本文提出的新问题
![](https://csdnimg.cn/release/download_crawler_static/10164974/bg12.jpg)
10 > 2017 阿里技术年度精选(下)
比较接近。在一般的条带装箱问题中,若干个长方体物品需要被逐个放入一个给定的
条带中,条带的长度和宽度是已知且固定的,长度为无穷大(在二维条带装箱问题中,
条带的宽度固定,但是长度为无穷大),优化目标为最小化使用的条带的高度。此类
问题在钢铁工业和纺织工业中有很多应用,研究者们也提出了不同类型的求解算法,
例如精确解算法 ([Martello
et al
., 2003],[Kenmochi
et al
., 2009]),近似解算法
([Steinberg, 1997]),启发式算法 ([Bortfeldt and Mack, 2007], [Bortfeldt, 2006],
[Hopper andTurton, 2001]) 等。
2.2 DRL 方法在组合优化问题中的应用研究
虽然机器学习和组合优化问题已经分别被研究了数十年,但是关于机器学习方法
在求解组合优化问题方面的研究却比较少。其中的一个研究方向是使用强化学习的思
想来设计超启发式算法。[Burke
et al
., 2013] 在一篇关于超启发式算法的综述论文中
对于一些基于学习机制的超启发式算法进行了讨论。[Nareyek, 2003] 使用了一种基
于非平稳强化学习的方法来更新启发式算法被选择的概率。除此之外,强化学习思想
在超启发式算法中的应用研究还包括二元指数补偿 ([Remde
et al
.,2009])、禁忌搜
索 ([Burke
et al
.,2003]) 和选择函数等 ([Cowling
et al
., 2000])。
近些 年来,序 列到序 列模型 (sequence-to-sequence) 的 一系 列 研究 突 破
激发 了 研究者 们 对于 神经组 合 优化 (neural combinatorial optimization) 方 向的
兴趣。其中注意机制 (attention mechanism) 对于加强神经网络模型在机器翻译
([Bahdanau
et al
.,2014]) 和算法学 习 ([Graves
et al
.,2014]) 方面的效 果 中 扮演
了重要决策。 [Vinyals
et al
., 2015] 提出了一种带有特殊注意机制的网络模型—
Pointer Net,并使用有监督学习的方法来通过此模型求解旅行商问题 (Travelling
Salesman Problem)。[Bello
et al
., 2016] 提出了一种基于强化学习思想的神经组
合优化 (neural combinatorial optimization) 框架,并使用此种框架求解了旅行商问
题和背包问题 (Knapsack Problem)。因为此种框架的有效性和普适性,本研究在求
解新型装箱问题中主要使用了此种框架和方法。
![](https://csdnimg.cn/release/download_crawler_static/10164974/bg13.jpg)
AI/ 算法 < 11
3. 针对三维装箱问题的 DRL 方法
3.1 问题定义
在经典的三维装箱问题中,需要将若干个物品放入固定尺寸的箱子中,并最小
化箱子的使用数量。与经典问题不同的是,本文提出的新型装箱问题的目标在于设计
能够容纳一个订单中所有物品的箱子,并使箱子的表面积最小。在一些实际业务场景
中,例如跨境电商中,包装物品时使用的是柔性的塑料材料,而且由于包装材料的成
本与其表面积直接正相关,所以最小化箱子的表面积即意味着最小化包装成本。
本文提出的新型装箱问题的数学表达形式如下所示。给定一系列物品的集合,每
个物品
i
都有各自的长 (
l
i
)、宽 (
w
i
)和高(
h
i
)。优化目标为寻找一个表面积最小且能够
容纳所有物品的箱子。我们规定 (
x
i
, y
i
, z
i
) 表示每一个物品的左下后 (left-bottom-
back) 角的坐标,而且 (0, 0, 0) 表示箱子的左下后角的坐标。决策变量的符号及其含
义如表 1 所示。基于以上问题描述和符号定义,新问题的数学表达形式为:
其中,
1
ij
s =
表示第 i 个物品在第 j 个物品的左边,
1
ij
u =
表示第 i 个物品在第 j 个
物品的下边,
1
ij
b =
表示第 i 个物品在第 j 个物品的后边。
1
1
i
δ
=
表示物品 i 的摆放朝向
为正面朝上,
2
1
i
δ
=
表示物品 i 正面朝下,
3
1
i
δ
=
表示物品 i 侧面朝上,
4
1
i
δ
=
表示物
![](https://csdnimg.cn/release/download_crawler_static/10164974/bg14.jpg)
12 > 2017 阿里技术年度精选(下)
品 i 侧面朝下,
5
1
i
δ
=
表示物品底面朝上,
6
1
i
δ
=
表示物品底面朝下。
约束条件中的 (9), (10), (11) 表示物品在不同的朝向情况下占用的空间的长宽
高;约束条件 (1), (3), (4), (5) 表示物品之间没有重叠,约束条件 (6), (7), (8) 保证了
箱子容纳了所有物品。
基于以上的数学模型,我们使用了优化引擎,例如 IBM Cplex 等来直接求解此
问题。但是对于一般规模的问题(例如物品数量大于等于 6),很难在合理的时间内获
得最优解。而且我们还证明了此类问题是 NP-hard 问题。证明过程请见附录。
表1 决策变量符号及含义
变量名 类型 含义
L
连续型变量 箱子的长度
W
连续型变量 箱子的宽度
H
连续型变量 箱子的高度
i
x
连续型变量 物品的左下后角的
x
坐标
i
y
连续型变量 物品的左下后角的
y
坐标
i
z
连续型变量 物品的左下后角的
z
坐标
ij
s
0-1 二元变量 第
i
个物品是否在第
j
个物品的左边
ij
u
0-1 二元变量 第
i
个物品是否在第
j
个物品的下边
ij
b
0-1 二元变量 第
i
个物品是否在第
j
个物品的后边
1i
δ
0-1 二元变量 第
i
个物品是否是正面朝上
2i
δ
0-1 二元变量 第
i
个物品是否是正面朝下
3i
δ
0-1 二元变量 第
i
个物品是否是侧面朝上
4i
δ
0-1 二元变量 第
i
个物品是否是侧面朝下
5i
δ
0-1 二元变量 第
i
个物品是否是底面朝上
6i
δ
0-1 二元变量 第
i
个物品是否是底面朝下
3.2 DRL 方法
在本部分中,我们将介绍用于求解新型三维装箱问题的 DRL 方法。在求解三维
装箱问题时,决策变量主要分为三类:
(1)物品放入箱子的顺序;
(2)物品在箱子中的摆放位置;
剩余309页未读,继续阅读
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/7dca377612164f3db548d4251d58e54e_chen888999.jpg!1)
自在小丁
- 粉丝: 8
- 资源: 12
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
最新资源
- 多模态联合稀疏表示在视频目标跟踪中的应用
- Kubernetes资源管控与Gardener开源软件实践解析
- MPI集群监控与负载平衡策略
- 自动化PHP安全漏洞检测:静态代码分析与数据流方法
- 青苔数据CEO程永:技术生态与阿里云开放创新
- 制造业转型: HyperX引领企业上云策略
- 赵维五分享:航空工业电子采购上云实战与运维策略
- 单片机控制的LED点阵显示屏设计及其实现
- 驻云科技李俊涛:AI驱动的云上服务新趋势与挑战
- 6LoWPAN物联网边界路由器:设计与实现
- 猩便利工程师仲小玉:Terraform云资源管理最佳实践与团队协作
- 类差分度改进的互信息特征选择提升文本分类性能
- VERITAS与阿里云合作的混合云转型与数据保护方案
- 云制造中的生产线仿真模型设计与虚拟化研究
- 汪洋在PostgresChina2018分享:高可用 PostgreSQL 工具与架构设计
- 2018 PostgresChina大会:阿里云时空引擎Ganos在PostgreSQL中的创新应用与多模型存储
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)