2022MathorCup高校数学建模挑战赛B题思路无人仓的搬运机器人调度问题

#2022 年第十二届 MathorCup 高校数学建模挑战赛题目
###思路交流&＃xff1a;点击链接加入群聊【22年mathorcup数模交流】&＃xff1a;https://jq.qq.com/?_wv&＃61;1027&k&＃61;wbVQSibD

B 题 无人仓的搬运机器人调度问题

本题考虑在无人仓内的仓库管理问题之一&＃xff0c;搬运机器人 AGV 的调度问题。更多的背景介绍请参看附件-背景介绍。对于无人仓来说&＃xff0c;仓库的地图 模型可以简化为图的数据结构。

*仓库地图&＃xff1a;*

无人仓内的设施&＃xff0c;可以细分为 AGV 能行驶的道路节点&＃xff0c;和别的功能节点&＃xff08;如工位&＃xff0c;储位等&＃xff09;。这样&＃xff0c;仓库地图模型可以抽象为这些节点构成的图&＃xff0c; 再按 AGV 能到达的节点来添加图的边。简单来说&＃xff0c;附件仓库地图数据

&＃xff08;map.csv&＃xff09;通过描述节点类型&＃xff0c;以及节点之间的关系&＃xff08;边)&＃xff0c;可以构建如下图 1 所示的仓库地图。

图 1&＃xff1a;仓库地图

仓库地图数据&＃xff08;map.csv&＃xff09;是按 csv 格式存储&＃xff0c;其节点类型有如下几类&＃xff0c; 在上图中用不同颜色标注。

1) *路径节点*&＃xff08;灰色&＃xff09;&＃xff1a;AGV 可以自由通行。

**
**

2) *储位节点*&＃xff08;绿色&＃xff09;&＃xff1a;放置托盘或者普通货架&＃xff0c;AGV 可以到达。一般只有一个位置可以进出&＃xff0c;即靠近道路的位置。

3) *保留节点*&＃xff08;黄色&＃xff09;&＃xff1a;保留位置。

4) *柱子节点*&＃xff08;黑色&＃xff09;&＃xff1a;障碍物&＃xff0c;AGV 不能到达。

5) *拣选工位节点*&＃xff08;蓝色&＃xff09;&＃xff1a;拣选机器人在这里把商品打包后从传送带出库&＃xff0c;一般有多个托盘停靠位。

6) *补货位节点*&＃xff08;粉色&＃xff09;&＃xff1a;从高密度区补货的商品放置点&＃xff0c;一般通过传送带输送。

7) *空托盘回收节点*&＃xff08;红色&＃xff09;&＃xff1a;空托盘回收处&＃xff0c;图中只有两处。

*无人仓任务场景&＃xff1a;*

假设仓库地图按上述方式抽象成图&＃xff0c;搬运机器人 AGV—次只搬运一个托盘&＃xff08;带有多种商品&＃xff09;&＃xff0c;能执行从一个地图节点&＃xfffd;!移动到&＃xfffd;"的路径指令&＃xff0c;其中每一步只能移动到有边相连的地图节点&＃xff0c;不能斜着移动。附件中机器人 数据&＃xff08;agv.csv&＃xff09;里&＃xff0c;给出了 20 个搬运机器人 AGV 在仓库地图上的初始位置坐标。

假设仓库内商品都是中大件商品&＃xff0c;每个在储位的托盘上叠放着多种商 品&＃xff0c;附件中的库存数据&＃xff08;pallets.csv&＃xff09;给岀了全部托盘的位置以及托盘上放的商品信息。对于中件仓来说&＃xff0c;即使用户订单包含了多个商品&＃xff0c;实际发货 还是一个商品一个包裹。这样&＃xff0c;AGV 执行任务只需要尽快满足商品数目的要求&＃xff0c;不需要等待同一订单中的全部商品到齐后才能出库。所以附件订单 数据&＃xff08;orders.csv&＃xff09;里&＃xff0c;每个订单只有同一件商品以及对应的数量。

无人仓流程是根据给定的一段时间内订单数据流&＃xff0c;结合当前库存情况&＃xff0c;

统筹安排搬运机器人从储位搬运有需求商品的托盘到附近的拣选工位&＃xff08;即 出库任务&＃xff09;,拣选完成后需安排搬运工位处的非空托盘到空储位&＃xff08;即回库任务&＃xff09;&＃xff0c;或者安排搬运工位处的空托盘到托盘回收处&＃xff08;即回收任务&＃xff09;等。本题只考虑这三种主要任务场景&＃xff0c;即出库、回库、回收任务。

首先&＃xff0c;对于出库任务&＃xff0c;搬运机器人 AGV 把一个托盘搬运到拣选工位。但是对于同一个工位来说&＃xff0c;同时能容纳放置的托盘数目是有限的。假设每 个拣选工位有 b 个停靠位&＃xff0c;也就是能同时最多分派 b 个出库任务到同一个拣选工位&＃xff0c;直到执行回库或者回收任务&＃xff0c;有空停靠位后才能容纳新的出库 托盘。

其次&＃xff0c;出库任务完成后&＃xff0c;搬运机器人处于空闲状态&＃xff0c;可以被安排执行 下一个任务&＃xff0c;而不需要在停靠位等候着。不妨假设出库托盘在拣选工位需 要停留一段时间后&＃xff0c;等拣选机器人打包发货后才能进行后续的回库或者回 收任务。这里假设停留时间固定为&＃xfffd;#,也就是说&＃xff0c;无论需要拣选多少商品&＃xff0c; 都简化为停留时间&＃xfffd;#后&＃xff0c;该托盘可以被执行后续的回库和回收任务。

*无人仓总结&＃xff1a;*

无人仓的主要运行场景就是安排搬运机器人 AGV 执行如下各种任

务。

• *出库*&＃xff1a;AGV 搬运载有商品的托盘到空闲拣选工位

• *回库*&＃xff1a;AGV 搬运拣选完成的托盘从工位回到仓库内空储位

• *回收*&＃xff1a;AGV 搬运拣选完成的空托盘从工位到托盘回收处

无人仓的核心是统筹优化上述任务的执行来最大化出库效率&＃xff0c;安排

AGV 任务和路线需满足全局最优&＃xff0c;达到实时响应&＃xff0c;并避免拥堵/死锁等情况

发生。也需要均衡拣选工位之间的工作量。

*问题* *1*&＃xff1a;AGV 统筹调度的最佳策略

假设先不考虑搬运机器人在执行任务时可能的碰撞问题&＃xff0c;请在无人仓模型下设计调度算法&＃xff0c;根据附件中订单数据&＃xff08;orders.csv&＃xff09;&＃xff0c;和仓库内的库存数据&＃xff08;pallets.csv&＃xff09;&＃xff0c;对于给定的 20 个搬运机器人&＃xff08;agv.csv&＃xff09;&＃xff0c;统筹调度和安排 AGV 任务&＃xff0c;直到满足所有的订单需求&＃xff0c;即全部拣选工位都空闲为止。这里&＃xff0c;目标函数为在每个搬运机器人尽可能忙的同时&＃xff0c;最小化全部搬运机器 人的行走总路径。

下面左图中&＃xff0c;用红色圆圈表示 AGV,用绿色方块表示货架或者托盘&＃xff0c;用蓝色 X 表示拣选工位。右图中匹配了最近的 AGV、托盘和工位&＃xff0c;使得指定AGV 去取托盘后再送到工位拣选。

图 2&＃xff1a;AGV 匹配调度示例图

注意&＃xff0c;现实场景中的目标其实是全局优化出库效率&＃xff0c;节省人力&＃xff0c;避免 高峰期出现"爆仓”现象。所以更合适的衡量指标是时间上的&＃xff0c;要求在最短 的时间内满足订单需求。在某种程度上&＃xff0c;目标可以转化为使得每个拣选工 位尽可能忙&＃xff0c;即最小化最忙拣选工位的工作时长。另一方面&＃xff0c;仓库内搬运 机器人 AGV 的合理投放数量一般是拣选工位的常数倍&＃xff0c;因为投放太多的话出库效率不但不会改善&＃xff0c;反而增加 AGV 拥堵的可能性。进一步考虑到每个工位可以增加停靠位&＃xff0c;而且搬运机器人除了出库任务&＃xff0c;还有回库和回收等

任务。所以使得每个 AGV 尽可能忙&＃xff0c;然后最小化全部 AGV 行走总路径&＃xff0c;

也是合理的模型目标简化。

*问题* *2*&＃xff1a;任务均衡区域划分

为了更好地平衡拣选工位的负载&＃xff0c;同时预防搬运机器人的局部拥堵&＃xff0c; 根据拣选工位和库存商品数量对仓库地图进行动态分区。也就是对仓库内 储位上的每个托盘&＃xff0c;都指定一个默认拣选工位。

请建立优化模型&＃xff0c;使得每个拣选工位对应托盘的商品总量尽可能地平 均&＃xff0c;同时要求最小化全部托盘到其默认拣选工位距离总和。类似下图 3 所示的区域划分。

进一步&＃xff0c;根据某段时间内所需出库商品的库存分布&＃xff0c;再结合问题一的

AGV 调度算法&＃xff0c;更合理地均衡每个拣选工位在某段时间内的工作量。

图 3&＃xff1a;拣选工位划分

*问题* *3*&＃xff1a;避免碰撞和拥堵

在问题一和问题二的基础上&＃xff0c;进一步考虑搬运机器人的碰撞和拥堵问 题。当仓库内同时有多个 AGV 在执行任务时&＃xff0c;不可避免有些 AGV 在某个路径节点上相遇。特别地&＃xff0c;如果两个 AGV 在一条货架窄巷道上相遇&＃xff0c;那么

需要其中一个 AGV 避让。

在合理的假设下&＃xff0c;请设计算法和防碰撞策略&＃xff0c;使得搬运机器人能智能地避免碰撞。特别是在一些特殊节点处&＃xff08;如托盘回收处&＃xff09;&＃xff0c;避免出现多个 AGV 的拥堵&＃xff0c;和可能的死锁场景。

下图是一个死锁场景示例&＃xff0c;一个 AGV 去拣选工位取空托盘&＃xff0c;另一台AGV 去相邻停靠位放置托盘,他们占据了各自的前进路径节点后都不退让&＃xff0c; 造成了死锁。

图 4&＃xff1a;死锁场景示例

**
**

****附件一&＃xff1a;****无人仓的背景介绍

仓库管理(也叫仓储管理)是对仓库内货物的接收、存储、发货等一系列活动进行有效的控制管理&＃xff0c;维护仓库货物并确保日常经营活动正常进行。传统的仓库管理模式大多是人工管理模式&＃xff0c;而这种管理方式有着不少问题&＃xff0c; 特别是因为人力效率低下的因素导致的“爆仓”现象。

随着电商的兴起&＃xff0c;无人仓逐渐作为自动化仓储物流系统的发展方向和 目标。最早的包括 Amazon 的 Kiva 机器人&＃xff0c;以及后来 AGV 搬运机器人、SHUTTLE 货架穿梭车、DELTA 分拣机器人等各式各样的、高度自动化的机器人都是为仓库的无人化量身定制的。而无人仓内搬运机器人的调度问 题是其中的核心问题。

下面是无人仓模型涉及到的设施和因素&＃xff0c;主要包括了搬运机器人&＃xff0c;托 盘&＃xff0c;储位&＃xff0c;拣选工位&＃xff0c;托盘回收处等。

*搬运机器人*

搬运机器人&＃xff0c;即 Automated Guided Vehicle (AGV)&＃xff0c;通过特殊地标导航自动将物品运输至指定地点。它是执行仓库内任务的主要单元&＃xff0c;可以通过 指令指派一个AGV 去取一个货架到仓库内指定地点&＃xff0c;比如拣选工位&＃xff0c;储位&＃xff0c; 回收处等。

**
**

*托盘和储位*

仓库内绝大部分区域都是放置托盘的储位&＃xff0c;而托盘上摆放着待出库商 品。有的仓库里托盘用多层的货架代替&＃xff0c;无论货架还是托盘都可以被 AGV 搬运。

*拣选工位*

由分拣机器人拣选商品&＃xff0c;完成打包后通过传送带输送出库&＃xff0c;包括了多 个放置托盘的停靠位&＃xff0c;分拣机器人以及商品出库的传送带。

*托盘回收处*

仓库内用来回收空托盘的固定区域&＃xff0c;一般仓库内会指定 2-4 个固定位置为托盘回收处。

**
**

*仓库地图*

从上述几个设施&＃xff0c;连同AGV 行驶道路&＃xff0c;把仓库内区域细分为道路节点&＃xff0c; 和有限制的节点&＃xff08;如工位&＃xff0c;储位等&＃xff09;。从而仓库模型可以抽象为节点和边的 图。简单来说&＃xff0c;附件仓库地图数据&＃xff08;map.csv&＃xff09;通过描述节点类型&＃xff0c;以及节点之间的关系&＃xff08;边&＃xff09;&＃xff0c;可以构建如下图所示的仓库地图。

*地图说明*

附件中仓库地图数据&＃xff08;map.csv&＃xff09;是按 csv 格式存储&＃xff0c;节点类型有如下几类&＃xff0c;分别用不同颜色标注&＃xff08;参看上图&＃xff09;。

1) *路径节点*&＃xff08;灰色&＃xff09;&＃xff1a;AGV 可以自由通行。

2) *储位节点*&＃xff08;绿色&＃xff09;&＃xff1a;放置托盘或者普通货架&＃xff0c;AGV 可以到达。一般只有一个位置可以进出&＃xff0c;即靠近道路的位置。

3) *保留节点*&＃xff08;黄色&＃xff09;&＃xff1a;保留位置。

4) *柱子节点*&＃xff08;黑色&＃xff09;&＃xff1a;障碍物&＃xff0c;AGV 不能到达。

5) *拣选工位节点*&＃xff08;蓝色&＃xff09;&＃xff1a;拣选机器人在这里把商品打包后从传送带出库&＃xff0c;一般有多个托盘停靠位。

**
**

6) *补货位节点*&＃xff08;粉色&＃xff09;&＃xff1a;从高密度区补货的商品放置点&＃xff0c;一般通过传送带输送。

7) *空托盘回收节点*&＃xff08;红色&＃xff09;&＃xff1a;空托盘回收处&＃xff0c;图中只有两处。

*附件二* 无人仓数据文件

本题提供了无人仓模型相关的 4 个数据文件&＃xff0c;其数据格式解释如下。数据文件下载地址&＃xff1a;https://www.coap.online/competitions/2

*仓库地图数据*(map.csv)

此文件存放是地图信息&＃xff0c;内容包括仓库内各类节点的具体分布情况&＃xff0c; 以及节点之间的连通性。给定的地图是32 × 22的一块矩形区域。数据字段的含义如下&＃xff1a;

l *TYPE*: 节点类型。

1&＃xff1a;路径节点&＃xff0c;AGV 可以通行。

2&＃xff1a;储位节点&＃xff0c;放置托盘或者普通货架&＃xff0c;AGV 可以到达。一般只有一个位置可以进出。

3&＃xff1a;保留节点&＃xff0c;保留位置&＃xff0c;暂不处理。

4&＃xff1a;柱子节点&＃xff0c;障碍物&＃xff0c;AGV 不能到达。

5&＃xff1a;拣选工位节点&＃xff0c;拣选机器人在这里把商品打包后从传送带出库&＃xff0c; 一般有多个托盘停靠位。

6&＃xff1a;补货位节点&＃xff0c;从高密度区补货的商品放置点&＃xff0c;一般通过传送带输 送。

7&＃xff1a;空托集放工位节点&＃xff0c;空托盘回收处。

l *X*: 节点所在位置的 X 轴坐标。

l *Y*: 节点所在位置的 Y 轴坐标。

l *NEIGHBORS*****&＃xff1a;****AGV 可到达的节点&＃xff0c;格式为&＃xfffd;1: &＃xfffd;1&＃xff1b; … &＃xff1b;&＃xfffd;4: &＃xfffd;4&＃xff0c;表示可以从当前节点能到达的邻近节点的坐标集合。这里最多是 4 个邻近节点。

*搬运机器人数据*(agv.csv)

此文件存放的是搬运机器人的初始信息,内容包括每个 AGV 位置信息。数据字段含意如下:

· *AGV_ID*: 搬运机器人 AGV 的唯一 ID

· *X*: AGV 所在位置的 X 轴坐标

· *Y*: AGV 所在位置的 Y 轴坐标

**
**

*订单数据*(orders.csv)

此文件存放是订单信息&＃xff0c;为一段时间内累计的订单。这里订单已经根 据商品号 SKU 拆分。需要分派 AGV 根据订单上的商品号 SKU 去寻找对应的托盘&＃xff0c;并将托盘搬运到拣选工位上出库。数据字段含意如下&＃xff1a;

· *ORDER_ID*: 订单的唯一 ID

· *SKU*: SKU 的唯一 ID

· *AMOUNT*: 所需该 SKU 的数量

*库存数据*(pallets.csv)

此文件存放的是仓库内托盘上商品信息&＃xff0c;包括每个托盘的位置以及存 放的各个商品 SKU 和数量。数据字段含义如下&＃xff1a;

· *SKU_QUANTITY_LIST*: 该托盘上存放的各个SKU 的ID 和数量&＃xff0c; 格式为“&＃xfffd;&＃xfffd;&＃xfffd;$:\&＃xfffd;$,• • •, &＃xfffd;&＃xfffd;&＃xfffd;% : &＃xfffd;%”&＃xff0c;表示存放了&＃xfffd;$个\&＃xfffd;\&＃xfffd;\&＃xfffd;$, • • •&＃xff0c;和&＃xfffd;%个&＃xfffd;&＃xfffd;&＃xfffd;%

· *X*: 该托盘所在位置的 X 轴坐标

· *Y*: 该托盘所在位置的 Y 轴坐标

· *PALLET_ID*: 托盘的唯一 ID