Research on the Task Scheduling of “Goods to Picker”Order Picking System Based on Logistics AGV

doi:10.12005/orms.2018.0241

Abstract

Abstract: Becouse of its high efficiency and flexibility, the “goods to picker” order picking mode based on logistics AGV has gradually become the developing trend of e-commerce logistics distribution center. Through the analysis of logistics AGV based order picking process in E-commerce logistics distribution center, two kinds of picking modes, synchronous picking and asynchronous picking, are put forward. Then the logistics AGV task scheduling problem is described. Taking the shortest time to complete all tasks as the planning objective, we establish task scheduling models under the two picking modes respectively. In view of the characteristics of AGV based task scheduling problem, coevolutionary genetic algorithm based on coarse-grained model is improved to solve the models. Finally, the effectiveness of the improved coevolutionary genetic algorithm is verified by the comparison with original coevolutionary genetic algorithm. The solving speed and the optimization result under the two picking modes are also compared and results show that simultaneous picking performs better than asynchronous picking.

Key words: “goods to picker” order picking mode, task scheduling, logistics AGV, improved coevolutionary genetic algorithm

摘要： 基于物流AGV的“货到人”订单拣选模式由于其高效率和灵活性,逐渐成为电商物流配送中心订单拣选系统发展趋势。本文通过对基于物流AGV的电商物流配送中心订单拣选作业流程分析,提出多拣选台同步拣选和多拣选台异步拣选两种作业模式。然后对基于物流AGV的订单拣选任务调度问题进行描述,以物流AGV完成所有任务的时间最短为目标,分别建立同步和异步两种拣选模式下物流AGV任务调度模型;针对物流AGV任务调度问题特性,对共同进化遗传算法粗粒度模型进行改进用于模型求解。最后,通过改进前后算法的对比,验证了改进共同进化遗传算法在求解物流AGV任务调度问题中的有效性;通过在求解速度和优化结果上对多拣选台同步拣选和异步拣选两种作业模式进行比较,得出同步拣选优于异步拣选的结果。

关键词: “货到人”拣选模式, 任务调度, 物流AGV, 改进共同进化遗传算法

CLC Number:

C931

YUAN Rui-ping , WANG Hui-ling, SUN Li-rui, LI Jun-tao. Research on the Task Scheduling of “Goods to Picker”Order Picking System Based on Logistics AGV[J]. Operations Research and Management Science, 2018, 27(10): 133-138.

袁瑞萍, 王慧玲, 孙利瑞, 李俊韬. 基于物流AGV的“货到人”订单拣选系统任务调度研究[J]. 运筹与管理, 2018, 27(10): 133-138.

References

[1]Argos. Argos Fast Track. https://www.argos.co.uk/help/ delivery-and-collection, 2015.
[2]Boysen N, Briskorn D, Emde S. Parts-to-picker based order processing in a rack-moving mobile robots environment[J]. European Journal of Operational Research, 2017, 262(2): 550-562.
[3]Zhou L, Shi Y, Wang J, et al. A balanced heuristic mechanism for multirobot task allocation of intelligent warehouses[J]. Mathematical Problems in Engineering, 2014(1): 1-10.
[4]Ma H, Koenig S, Ayanian N, et al. Overview: generalizations of multi-agent path finding to real-world scenarios[C]. IJCAI-16 Workshop on Multi-Agent Path Finding. 2017. 1-5.
[5]Yu J. Intractability of optimal multirobot path planning on planar graphs[J]. Robotics & Automation Letters IEEE, 2015, 1(1): 33-40.
[6]Khamis A, Hussein A, Elmogy A. Multi-robot task allocation: a review of the state-of-the-art[J]. Cooperative Robots and Sensor Networks, 2015: 31-51.
[7]Tovey C, Lagoudakis M G, Jain S, et al. The generation of bidding rules for auction-based robot coordination[J]. Multi-Robot Systems, 2005,3: 3-14.
[8]Bukchin Y, Khmelnitsky E, Yakuel P. Optimizing a dynamic order-picking process[J]. European Journal of Operational Research, 2012, 219(2): 335-346.
[9]丁滢颍,何衍,蒋静坪.基于蚁群算法的多机器人协作策略[J].机器人,2003,25(5):414-418.
[10]Nagarajan T, Thondiyath A. Heuristic based task allocation algorithm for multiple robots using agents[J]. Procedia Engineering, 2013, 64: 844-853.
[11]Elango M, Nachiappan S, Tiwari M K. Balancing task allocation in multi-robot systems using means clustering and auction based mechanisms[J]. Expert Systems with Applications, 2011, 38(6): 6486-6491.
[12]Singh R, Task scheduling in parallel systems using genetic algorithm[J]. International Journal of Computer Applications, 2014, 108(16): 34-40.
[13]Yuan W D, Tang D B, Wang L, et al. Research of the dynamic task allocation based on genetic algorithm[J]. Manufacture Information Engineering of China, 2010, 39(3): 57-64.
[14]Rashid M A, Khatib F, Hoque M T, et al. An enhanced genetic algorithm for ab initio protein structure prediction[J]. IEEE Transactions on Evolutionary Computation, 2016, 20(4): 627-644.
[15]Zhong Qiuxi, Xie Tao, Chen Huowang. Task matching and scheduling by using genetic algorithms[J]. Journal of Computer Research & Development, 2017, 37(10): 1197-1203.