夜光精讲 Opentcs 三大算法（十）任务分配算法

夜光序言：

 

青年眼眸微闭，双手放于脑后，自言自语道：

享受悠闲生活当然比享受奢侈生活便宜得多。要享受悠闲的生活只要一种艺术家的性情，在一种全然悠闲的情绪中，去消遣一个闲暇无事的下午。

 

 

 

 

正文：

 

２．同一个货架被多个分拣台请求，请求多面的物品

 

此时出库任务的第⑤段子任务取消回退，等到ＡＧＶ运载小车依次至多个操作台完成所有请求后，再将货架送回至存货区的货位点。

---

３．异常情况

出现异常情况时，需要重新分配资源，进行任务的再次分配。可做如下处理：

（１）增添子任务段：货物所在货架被小车搬运中（被占用），直接把任务分配给此车。
（２）变更路径：已经分配任务的车辆，还未搬运货架，但电量过低，要移除该任务，并重新分配该任务给其他车辆。
（３）删除路径：回收刪除任务。

 

---

 

夜光：任务约束规则

１．任务发布的数据信息封装，通过ＸＭＬ报文信息传输，同时可更新数据库的数据字段。
２．毎辆车只知道自己的任务信息，任务信息不共享，可根据任务执行情况修改重写数据库。
３．任务开始时，改写货架信息，货架被车Ａ占用，任务结束后解除ＡＧＶ与货架之间的绑定。
４．新的订单录入后，可以暂时不执行，也可以立即执行。
 

---

５．允许ＡＧＶ和任务的异构性。
６．原始任务生成时，成员变量有些采用默认值，待后续完善填充，需耍补充的成员变量有：

（１）行驶路径：包括路径上经过的点和总耗费值。
（２）为行驶路径上的每个点增加当前站点允许和需要进行的操作、行驶速度等。
（３）在经过的点上附加下一个时刻的行进方向等附加信息，指导小车进行转向决策。
（４）为特殊点进行标识警告；进行路径跟踪，判断下一个点是否将要进入Ｂｕｎｄｌｅ区。
 

---

任务分配代价估计和算法实现

解决任务分配问题的核心在于构建最合适的评估函数，每个子任务最多只能被一辆小车竞争获得，从而确保不会存在任意两个ＡＧＶ的目标点相同，避免货架拾取冲突。

主要指标如下：

（１）期望时间代价Ｅｘｐｅｃｔ：预计小车多久之后可以开始执行此任务，针对一个小车可以同时有多个任务的情况，因此任务下达后可能并不能立即执行该任务。

因此控制中心为每辆小车维护一个订单池，此元素存储小车被分配但尚未被执行的子任务段的序列；

（２）路径算法评估函数指标的注入。
我们设计一种基于效用的评佑函数来改进传统的拍卖机制算法，通过评估任务的代价（路径最优时的代价值）及期望时间代价指标，以期达到任务均衡分配，提高任务分配的综合性能，更适合动态未知多异构任务系统。

 

其算法流程：