项目背景

考虑京东、亚马逊等大型B2C电商的订单分拣系统。其典型场景和特点是:

  • 订单大量的、完全电子化的、自动的进入到仓库中待分拣。
  • 每份订单中往往包含多种货物;这些货物在同一个仓库中(订单可能包含不同品类不在同一仓库的货物,但相近品类在同一仓库的货物可能也有多种,可以仅考虑这些在同一仓库的子订单,不影响“一个订单有同一仓库的多个货物”的基本假设)。
  • 货物在仓库中的货架上存放。货架会有多个。
  • 因此每个订单需要从不同货架上取货并放置一起打包。

这些订单可以用完全人工的方式分拣,即,工作人员每次处理一个订单,依照订单上的货物顺序依次到各自货架上取货。也可以有一定的自动化,常见方式可能有如下两种(是否还有其他方式?需要再做调研):

  • 整体分拣,人工方式的初步自动化:工作人员仍然每次处理一个订单,但货架做小,并由底层的移动机器人驱动,可自动运动到工作人员面前,由工作人员从货架上取下需要的货物,然后按照订单打包。
  • 非整体分拣,取货过程的快速自动化:在这种方式下,订单中的多种货物完全分开独立处理。使用流水线或轨道式移动机器人可将货物快速移动出来并自动化的打包、贴标签、装车。

上述第二种方式可以完全没有人参与,自动化程度更高一些,但主要问题是订单中的多种货物被分开分拣,大大增加了打包和后续运输的成本。第一种方式则仍然需要人工参与,自动化程度较低。

因此,需要一种可以整体分拣的、完全自动化的分拣方式。这是本项目研究的初衷。

注意,分拣的场景不限于京东、亚马逊等B2C电商,只要具有整体分拣需求的大量订单情况,都是适用的。另外两种可能情形:(更多可能场景需进一步调研)

  • 大型医院的药方分拣:药方可以完全电子化,药房也可完全自动化。每个药方的多种药物可以从药房中自动化的分拣出来并打包。
  • 英国Argos零售店的订单分拣。Argos具有一种独特的销售模式:它的零售店分为客户选购区和仓库两部分。在选购区中没有实际货物,只有货物目录(纸质的或者iPad上),客户查看货物信息并下单,然后工作人员就根据订单信息从仓库中拿货。它的零售店的主要人工都在订单分拣上。设想一种智能化的仓库,客户订单可以自动进入仓库并从中自动完成分拣,可以节省大量人力成本。

可能的模型架构

针对上述需求,提出一种可能的模型架构。

所需硬件设施和硬件改造如下:

  • 所有货架改造为智能货架,具有如下能力:
    • 货架一侧陈列货物,可接收需要货物的信息,并将该货物取下放置到其下方的无人车上(实现方式可为推取式或机械手等)。
    • 货架另一侧可接收订单信息,并在本订单的所有货物到齐后打包送出。
  • 若干无人车,具有如下能力:
    • 可自动装卸并运送货物
  • 中央处理机构,具有如下能力:
    • 获知所有无人车的运行状态,包括
      • 当前的运动学信息,包括位置、速度、加速度等。
      • 如果工作中,则所运输货物的订单信息。
    • 规划每辆车运行方式的能力
    • 对订单进行分配的能力

依托如上设施,分拣系统架构如下:

  • 所有货架连续的排成封闭的圆形、方形或其他形状,要求货物侧朝向封闭区域内侧,并且任意两个货架之间在封闭区域内侧直线可达。
  • 若干无人车在货架封闭区域内部承担运输任务。

一个特定订单的分拣流程工作如下:

pseudo code 订单到达分拣系统 中央处理机构分配订单到某一货架处理(需考虑订单中所含货物在哪个货架较多,和当前货架是否空闲等) 在订单所在货架上的货物直接取下 在其他货架上的货物则交给无人车运输到订单所在货架 待所有货物到齐,打包并送出

研究内容和方法

本项目研究的创新点是一种新的面向订单自动整体分拣的系统架构,核心是给出无人车在封闭区域满足订单货物运送需求的高效算法,主要的研究方式可能是基于计算机仿真和实验的,并辅之以简单情况下的一些理论分析。

  • 做先期项目合理性和可行性的调研。
  • 设计一套完善的、可扩展的仿真系统。
  • 设计并进行相关实验。
  • 先利用已有算法做适配到本项目问题中来,进而改进算法。
  • 要与现有的方式做大量对比。

关键科学问题

仅列举几个,会有其他问题在进行过程中出现。

  • 无人车的运行规划算法。在无人车要发生碰撞的时候,需要给出相应的通行策略。在简单的假设下,所有无人车只走直线,因此需要告知其减速度。但决定是哪一辆车来避让,需要至少考虑两方面问题:一是后续的路径,即当前的决定应该尽量减少后续会发生碰撞的可能性;二是订单的优先级,可能需要将运送即将完成订单的货物的无人车的通行优先级提高。整个问题大约属于随机规划的范畴。因为要考虑每辆车的优先级和后续的可能路径,可行空间非常大,规划会有难度。
  • 决定让行的无人车的让行方式?在何处开始减速,减速的加速度如何?
  • 订单的发放策略:是否是将订单发送到含订单中货物最多的货架就是最优的,还是有可能有别的更好方式?
  • 无人车的最优数量。在其他参数确定情况下,用多少辆无人车综合效率最好?
  • 货物摆放策略:订单中货物如果符合某种已知的统计分布,如何设计货物在货架上的摆放以提高整体效率?
  • 中央处理机构到无人车的通信如果有延时或者丢失呢?
  • 无人车是否一定需要紧急避障的功能?

研究成果

Journal Articles

  1. 大批量订单整体分拣问题建模及其分布式并行方法 赵云波, 李天舒, and 汪钰皓 高技术通讯 2020 [Abs] [PDF]

Theses

  1. 大批量订单分布式并行整体分拣系统设计 李天舒 浙江工业大学, 杭州 2019 [Abs] [PDF]
  2. 基于多移动机器人的订单分拣系统设计 章鑫 2019 [Abs] [PDF]
  3. 面向订单分拣的多移动机器人调度算法研究 汪钰皓 2018 [Abs] [PDF]
  4. 小车的搬运系统优化控制研究 禤青君 2017 [Abs] [PDF]

项目人员

赵云波 李天舒