A Two-Objective ILP Model of OP-MATSP for the Multi-Robot Task Assignment in an Intelligent Warehouse
Source abstract
Abstract
Multi-robot task assignment is one of the main processes in an intelligent warehouse. This paper models multi-robot task assignment in an intelligent warehouse as an open-path multi-depot asymmetric traveling salesman problem (OP-MATSP). A two-objective integer linear programming (ILP) model for solving OP-MDTSP is proposed. The theoretical bound on the computational time complexity of this model is O(n!). We can solve the small multi-robot task assignment problem by solving the two-objective ILP model using the Gurobi solver. The multi-chromosome coding-based genetic algorithm has a smaller search space, so we use it to solve large-scale problems. The experiment results reveal that the two-objective ILP model is very good at solving small-scale problems. For large-scale problems, both EGA and NSGA3 genetic algorithms can efficiently obtain suboptimal solutions. It demonstrates that this paper’s multi-robot work assignment methods are helpful in an intelligent warehouse.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Advanced Manufacturing and Logistics Optimization · Robotic Path Planning Algorithms · Scheduling and Optimization Algorithms
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
School of Mechanical Engineering and Automation, Harbin Institute of Technology (Shenzhen), Shenzhen 518071, China
Funding
Shenzhen Basic Research Program · National Natural Science Foundation
References (33)
Show source-provided references
1. Automated and Robotic Warehouses: Developments and Research Opportunities10.26411/83-1734-2015-2-38-4-18 ↗
2. Advanced approaches for multi-robot coordination in logistic scenarios10.1016/j.robot.2016.08.010 ↗
3. Coordinating hundreds of cooperative, autonomous vehicles in warehouses
4. Effective task scheduling and dynamic resource optimization based on heuristic algorithms in cloud computing environment
5. Erdmann, M., and Lozano-Perez, T. (1986, January 7–10). On multiple moving objects. Proceedings of the 1986 IEEE International Conference on Robotics and Automation, San Francisco, CA, USA.10.1109/ROBOT.1986.1087401 ↗
6. Wagner, G., Choset, H., and Ayanian, N. (2012). Subdimensional Expansion and Optimal Task Reassignment. SOCS, Proceedings of the 5th Annual Symposium on Combinatorial, Niagara Falls, ON, Canada, 19–21 July 2012, Association for the Advancement of Artificial Intelligence.
7. Multi-robot task allocation: A review of the state-of-the-art
8. Liu, Y., Ji, S., Su, Z., and Guo, D. (2019). Multi-objective AGV scheduling in an automatic sorting system of an unmanned (intelligent) warehouse by using two adaptive genetic algorithms and a multi-adaptive genetic algorithm. PLoS ONE, 14.10.1371/journal.pone.0226161 ↗
9. A case study of AGV scheduling for production material handling10.4028/www.scientific.net/AMM.411-414.2351 ↗
10. A tabu search algorithm for simultaneous machine/AGV scheduling problem10.1080/00207543.2014.910628 ↗
11. Mousavi, M., Yap, H.J., Musa, S.N., Tahriri, F., and Md Dawal, S.Z. (2017). Multi-objective AGV scheduling in an FMS using a hybrid of genetic algorithm and particle swarm optimization. PLoS ONE, 12.10.1371/journal.pone.0169817 ↗
12. Survey of task allocation in multi Agent systems
13. On the first come–first served rule in multi-echelon inventory control10.1002/nav.20225 ↗
14. Shi, J., Bao, Y., Leng, F., and Yu, G. (2009, January 12–14). Priority-Based Balance Scheduling in Real-Time Data Warehouse. Proceedings of the 2009 Ninth International Conference on Hybrid Intelligent Systems, Shenyang, China.10.1109/HIS.2009.275 ↗
15. Adaptive task planning for multi-robot smart warehouse10.1109/ACCESS.2021.3058190 ↗
16. A building-block-based genetic algorithm for solving the robots allocation problem in a robotic mobile fulfilment system10.1155/2019/6153848 ↗
17. Integrated tasks assignment and routing for the estimation of the optimal number of AGVS10.1007/s00170-015-7343-4 ↗
18. Some simple applications of the travelling salesman problem10.1057/jors.1975.151 ↗
19. Design and control of warehouse order picking: A literature review10.1016/j.ejor.2006.07.009 ↗
20. Using a TSP heuristic for routing order pickers in warehouses10.1016/j.ejor.2009.01.036 ↗
21. Order batching in warehouses by minimizing total tardiness: A hybrid approach of weighted association rule mining and genetic algorithms10.1155/2013/246578 ↗
22. Tsiropoulou, E.E., Paruchuri, S.T., and Baras, J.S. (2017, January 22–24). Interest, energy and physical-aware coalition formation and resource allocation in smart IoT applications. Proceedings of the 2017 51st Annual Conference on Information Sciences and Systems (CISS), Baltimore, MD, USA.10.1109/CISS.2017.7926111 ↗
23. Multi-depot multiple TSP: A polyhedral study and computational results10.1007/s10479-011-1024-y ↗
24. Solution of a large-scale traveling-salesman problem
25. A Comparative Performance Analysis of Computational Intelligence Techniques to Solve the Asymmetric Travelling Salesman Problem10.1155/2021/6625438 ↗
26. The gurobi optimizer
27. Liu, Z., Liu, G., Wang, H., and He, F. (2011, January 26–28). The linear weighting method for solving a class of non-differentiable multiobjective programming problem. Proceedings of the 2011 International Conference on Multimedia Technology, Hangzhou, China.
28. Ronald, S., Kirkby, S., and Eklund, P. (1997, January 13–16). Multi-chromosome mixed encodings for heterogeneous problems. Proceedings of the 1997 IEEE International Conference on Evolutionary Computation (ICEC’97), Indianapolis, IN, USA.
29. Ciesielski, V., and Scerri, P. (1998, January 4–9). Compound optimisation. Solving transport and routing problems with a multi-chromosome genetic algorithm. Proceedings of the 1998 IEEE International Conference on Evolutionary Computation Proceedings. IEEE World Congress on Computational Intelligence (Cat. No. 98TH8360), Anchorage, AK, USA.
30. Multi-chromosome Genetic Algorithm for Multiple Traveling Salesman Problem
31. Khatib, W., and Fleming, P.J. (1998, January 27–30). The stud GA: A mini revolution?. Proceedings of the International Conference on Parallel Problem Solving from Nature, Amsterdam, The Netherlands.10.1007/BFb0056910 ↗
32. A fast and elitist multiobjective genetic algorithm: NSGA-II10.1109/4235.996017 ↗
33. An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point-Based Nondominated Sorting Approach, Part I: Solving Problems with Box Constraints10.1109/TEVC.2013.2281535 ↗